Bài toán Quy Hoạch Tuyến Tính - Dạng chuẩn (standard form)
Nội dung
Mục tiêu
Chúng ta cần chuyển bài toán quy hoạch tuyến tính từ dạng tổng quát (general form) sang dạng chuẩn (standard form). Tức là:
- Tất cả các biến đều không âm.
- Tất cả các ràng buộc là đẳng thức.
- Hàm mục tiêu được biểu diễn theo các biến không âm mới.
- Tất cả hệ số tự do đều không âm.
- Hàm mục tiêu là cực tiểu hóa (Min).
Trong đó, (1),(2) và (3) là các yêu cầu bắt buộc. (4) và (5) không bắt buộc phải đảm bảo trong dạng chuẩn, nhưng đó sẽ là điều kiện bắt buộc khi giải bài toán tối ưu bằng phương pháp đơn hình về sau.
Bài toán quy hoạch tuyến tính P dạng tổng quát (general form)
$$ 2x_1 + 3x_2 - x_3 \rightarrow \max $$$$ \begin{align} 5x_1 + 3x_2 + 2x_3 &\leq 4 \\ -3x_1 - 2x_2 + x_3 &\geq -1 \\ x_1 - x_2 + 4x_3 &= 5 \end{align} $$$$ x_1 \geq 0, \quad x_2 \leq 0, \quad x_3 \text{ tuỳ ý} $$Bước 1: Kiểm tra và chuyển đổi các biến
1.1 Xét các biến:
- $x_1 \geq 0$: Đã thỏa mãn điều kiện không âm.
- $x_2 \leq 0$: Không thoả mãn điều kiện không âm, vậy nền cần chuyển đổi.
- $x_3$ tuỳ ý: Không thảo mãn điều kiện không âm, vậy nên cần chuyển đổi.
1.2 Đổi biến:
- Đặt $x_2 = -x_2’$, với $x_2’ \geq 0$.
- Biểu diễn $x_3 = x_3^+ - x_3^-$, với $x_3^+, x_3^- \geq 0$. Ý tưởng đằng sau của nó chính là: bất kì số thực nào cũng có thể được biểu diễn bởi hiệu của 2 số thực không âm nào đó.
Bước 2: Thay biến mới vào bài toán
2.1 Hàm mục tiêu:
$$ 2x_1 - 3x_2' - x_3^+ + x_3^- \rightarrow \max $$2.2 Các ràng buộc chính:
$$ \begin{align} 5x_1 - 3x_2' + 2x_3^+ - 2x_3^- &\leq 4 \\ -3x_1 + 2x_2' + x_3^+ - x_3^- &\geq -2 \\ x_1 + x_2' + 4x_3^+ - 4x_3^- &= 5 \end{align} $$Bước 3: Chuyển đổi các ràng buộc thành đẳng thức
3.1 Ràng buộc (1):
$$ 5x_1 - 3x_2' + 2x_3^+ - 2x_3^- + s_1 = 4 $$3.2 Ràng buộc (2):
$$ 3x_1 - 2x_2' - x_3^+ + x_3^- \leq 2 $$$$ 3x_1 - 2x_2' - x_3^+ + x_3^- + s_2 = 2 $$3.3 Ràng buộc (3):
$$ x_1 + x_2' + 4x_3^+ - 4x_3^- = 5 $$Bước 4: Chuyển hàm mục tiêu về dạng cực tiểu hóa
$$ -2x_1 + 3x_2' + x_3^+ - x_3^- \rightarrow \min $$Kết quả cuối cùng
$$ -2x_1 + 3x_2' + x_3^+ - x_3^- \rightarrow \min $$$$ \begin{align} 5x_1 - 3x_2' + 2x_3^+ - 2x_3^- + s_1 &= 4 \\ 3x_1 - 2x_2' - x_3^+ + x_3^- + s_2 &= 1 \\ x_1 + x_2' + 4x_3^+ - 4x_3^- &= 5 \end{align} $$$$ x_1, \quad x_2', \quad x_3^+, \quad x_3^-, \quad s_1, \quad s_2 \geq 0 $$Tham khảo:
- Bertsimas, D., & Tsitsiklis, J.N. (1997). Introduction to linear optimization. Athena scientific optimization and computation series.
- Nguyễn Đức Nghĩa. Tối ưu hóa quy họach tuyến tính và rời rạc. NXB Giáo Dục.