Bài toán Quy Hoạch Tuyến Tính - Dạng chuẩn (standard form)
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)
Hàm mục tiêu:
$$ 2x_1 + 3x_2 - x_3 \rightarrow \max $$Các ràng buộc chính:
$$ \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} $$Các ràng buộc về dấu:
$$ 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):
Ràng buộc này có dạng bất đẳng thức, vì vậy ta cần thêm biến phụ $s_1 \geq 0$. Vì đây là bất đẳng thức “$\leq$” nên dấu của $s_1$ sẽ là $+$ (Ngược lại, sẽ là $-$).
$$ 5x_1 - 3x_2' + 2x_3^+ - 2x_3^- + s_1 = 4 $$3.2 Ràng buộc (2):
Vì hệ số tự do (-2) là số âm, nên ta sẽ nhân cả hai vế của bất đẳng thức với -1 để đảm bảo hệ số tự do luôn không âm.
$$ 3x_1 - 2x_2' - x_3^+ + x_3^- \leq 2 $$Lúc này, ràng buộc vẫn thuộc dạng bất đẳng thức, do đó, ta thêm biến phụ $s_2 \geq 0$. Một lần nữa, vì bất đẳng thức thuộc loại “$\leq$”, nên dấu của $s_2$ sẽ là $+$.
$$ 3x_1 - 2x_2' - x_3^+ + x_3^- + s_2 = 2 $$3.3 Ràng buộc (3):
Đã là đẳng thức, và hệ số tự do dương, do đó ta giữ nguyên:
$$ 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
Đổi dấu hàm mục tiêu:
$$ -2x_1 + 3x_2' + x_3^+ - x_3^- \rightarrow \min $$Kết quả cuối cùng
Hàm mục tiêu:
$$ -2x_1 + 3x_2' + x_3^+ - x_3^- \rightarrow \min $$Các ràng buộc chính:
$$ \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} $$Các ràng buộc về dấu:
$$ 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.