Thuật toán đơn hình đối ngẫu là một biến thể của thuật toán đơn hình.
Nó giải bài toán quy hoạch tuyến tính bằng cách duy trì tính chấp nhận được đối ngẫu thay vì
tính chấp nhận được của bài toán gốc.
\\
▸ Ý TƯỞNG CHÍNH
Thuật toán đơn hình:
Thuật toán đơn hình đối ngẫu:
Thuật toán dừng khi cơ sở vừa chấp nhận được vừa chấp nhận được đối ngẫu ⇒ nghiệm tối ưu.
▸ ĐIỀU KIỆN
Một cơ sở B B B
Là chấp nhận được nếu:
A B − 1 b ≥ 0 A_B^{-1} b \ge 0 A B − 1 b ≥ 0 hay dễ thấy ở bài toán dạng chuẩn tắc là hệ số b i ≥ 0 b_i \ge 0 b i ≥ 0
Là chấp nhận được đối ngẫu nếu:
c ⊤ − c B ⊤ A B − 1 A ≤ 0 c^\top - c_B^\top A_B^{-1} A \le 0 c ⊤ − c B ⊤ A B − 1 A ≤ 0 hay dễ thấy ở bài toán dạng chuẩn tắc là hệ số ở hàm mục tiêu ≤ 0 \le 0 ≤ 0
▸ KHI NÀO DÙNG THUẬT TOÁN ĐƠN HÌNH ĐỐI NGẪU
Khi đã có nghiệm tối ưu cũ, nhưng:
thay đổi b b b
hoặc thêm ràng buộc
→ Cơ sở cũ thường vẫn chấp nhận được đối ngẫu nhưng không còn chấp nhận được.
▸ THUẬT TOÁN ĐƠN HÌNH ĐỐI NGẪU
Bước 1: Chọn hàng xoay (pivot row)b i < 0 b_i < 0 b i < 0
Bước 2: Chọn cột xoay (pivot column)a i j < 0 a_{ij} < 0 a ij < 0
min c j − z j a i j \min \frac{c_j - z_j}{a_{ij}} min a ij c j − z j b i ≥ 0 ∀ i b_i \ge 0 \quad \forall i b i ≥ 0 ∀ i → Khi đó nghiệm là tối ưu.
Về cơ bản, các bước của thuật toán đơn hình đối ngẫu tương tự thuật toán đơn hình,
nhưng ta chọn hàng xoay trước rồi mới chọn cột xoay, và tính ratio theo hàng, chứ không tính theo cột.
▸ ⚠️ LƯU Ý
Nếu trong hàng xoay không có phần tử âm không bị chặn vô nghiệm (theo định lý đối ngẫu yếu).
▸ VÍ DỤ
Giải bài toán sau bằng đơn hình đối ngẫu:
max − 4 x 1 − 2 x 2 − x 3 s.t. − x 1 − x 2 − 2 x 3 ≤ − 3 − 4 x 1 − 2 x 2 + x 3 ≤ − 4 − x 1 + x 2 − 4 x 3 ≤ − 2 \begin{align*}
\max \quad
& -4x_1 & -\; & 2x_2 & -\; & \ \ x_3 & & \\
\text{s.t.} \quad
& \ \ -x_1 & -\; & \ \ x_2 & -\; & 2x_3 & \le & -3 \\
& -4x_1 & -\; & 2x_2 & +\; & \ \ x_3 & \le & -4 \\
& \phantom{-}\ \ x_1 & +\; & \ \ x_2 & -\; & 4x_3 & \le & \phantom{-} 2
\end{align*} max s.t. − 4 x 1 − x 1 − 4 x 1 − x 1 − − − + 2 x 2 x 2 2 x 2 x 2 − − + − x 3 2 x 3 x 3 4 x 3 ≤ ≤ ≤ − 3 − 4 − 2 x 1 , x 2 , x 3 ≥ 0 x_1, x_2, x_3 \ge 0 x 1 , x 2 , x 3 ≥ 0 Dễ thấy bài toán không chấp nhận được, nhưng chấp nhận được đối ngẫu (Do các hệ số ở hàm mục tiêu đều âm).
Ta tiến hành kẻ bảng đơn hình:
[ x 1 x 2 x 3 y 1 y 2 y 3 b y 1 − 1 − 1 − 2 1 0 0 − 3 y 2 − 4 − 2 1 0 1 0 − 4 y 3 1 1 − 4 0 0 1 2 − z − 4 − 2 − 1 0 0 0 0 ] \left[
\begin{array}{c|cccccc|c}
& x_1 & x_2 & x_3 & y_1 & y_2 & y_3 & b \\
\hline
y_1 & -1 & -1 & -2 & 1 & 0 & 0 & -3 \\
y_2 & -4 & -2 & 1 & 0 & 1 & 0 & -4 \\
y_3 & 1 & 1 & -4 & 0 & 0 & 1 & 2 \\
\hline
-z & -4 & -2 & -1 & 0 & 0 & 0 & 0
\end{array}
\right] y 1 y 2 y 3 − z x 1 − 1 − 4 1 − 4 x 2 − 1 − 2 1 − 2 x 3 − 2 1 − 4 − 1 y 1 1 0 0 0 y 2 0 1 0 0 y 3 0 0 1 0 b − 3 − 4 2 0 Các bước làm tiếp theo, các ứng viên để chọn làm hàng xoay sẽ là các hàng có b i < 0 b_i < 0 b i < 0 y y y
[ x 1 x 2 x 3 y 1 y 2 y 3 b y 1 − 1 − 1 − 2 1 0 0 − 3 y 2 − 4 − 2 1 0 1 0 − 4 y 3 1 1 − 4 0 0 1 2 − z − 4 − 2 − 1 0 0 0 0 R a t i o 4 2 − − − − − ] \left[
\begin{array}{c|cccccc|c}
& x_1 & x_2 & x_3 & y_1 & y_2 & y_3 & b \\
\hline
y_1 & -1 & \boxed{-1} & -2 & 1 & 0 & 0 & \boxed{-3} \\
y_2 & -4 & -2 & 1 & 0 & 1 & 0 & -4 \\
y_3 & 1 & 1 & -4 & 0 & 0 & 1 & 2 \\
\hline
-z & -4 & -2 & -1 & 0 & 0 & 0 & 0 \\
Ratio & 4 & \boxed{2} & - & - & - & - & -
\end{array}
\right] y 1 y 2 y 3 − z R a t i o x 1 − 1 − 4 1 − 4 4 x 2 − 1 − 2 1 − 2 2 x 3 − 2 1 − 4 − 1 − y 1 1 0 0 0 − y 2 0 1 0 0 − y 3 0 0 1 0 − b − 3 − 4 2 0 − ↓ \downarrow ↓ [ x 1 x 2 x 3 y 1 y 2 y 3 b x 2 1 1 − 2 − 1 0 0 3 y 2 − 2 0 − 3 − 2 1 0 2 y 3 0 0 − 2 1 0 1 − 1 − z − 2 0 − 5 − 2 0 0 6 ] \left[
\begin{array}{c|cccccc|c}
& x_1 & x_2 & x_3 & y_1 & y_2 & y_3 & b \\
\hline
x_2 & 1 & 1 & -2 & -1 & 0 & 0 & 3 \\
y_2 & -2 & 0 & -3 & -2 & 1 & 0 & 2 \\
y_3 & 0 & 0 & -2 & 1 & 0 & 1 & -1 \\
\hline
-z & -2 & 0 & -5 & -2 & 0 & 0 & 6 \\
\end{array}
\right] x 2 y 2 y 3 − z x 1 1 − 2 0 − 2 x 2 1 0 0 0 x 3 − 2 − 3 − 2 − 5 y 1 − 1 − 2 1 − 2 y 2 0 1 0 0 y 3 0 0 1 0 b 3 2 − 1 6 ↓ \downarrow ↓ [ x 1 x 2 x 3 y 1 y 2 y 3 b x 2 1 1 − 2 − 1 0 0 3 y 2 − 2 0 − 3 − 2 1 0 2 y 3 0 0 − 2 1 0 1 − 1 − z − 2 0 − 5 − 2 0 0 6 R a t i o − − 5 / 2 − − − − ] \left[
\begin{array}{c|cccccc|c}
& x_1 & x_2 & x_3 & y_1 & y_2 & y_3 & b \\
\hline
x_2 & 1 & 1 & -2 & -1 & 0 & 0 & 3 \\
y_2 & -2 & 0 & -3 & -2 & 1 & 0 & 2 \\
y_3 & 0 & 0 & \boxed{-2} & 1 & 0 & 1 & \boxed{-1} \\
\hline
-z & -2 & 0 & -5 & -2 & 0 & 0 & 6 \\
Ratio & - & - & \boxed{5/2} & - & - & - & - \\
\end{array}
\right] x 2 y 2 y 3 − z R a t i o x 1 1 − 2 0 − 2 − x 2 1 0 0 0 − x 3 − 2 − 3 − 2 − 5 5/2 y 1 − 1 − 2 1 − 2 − y 2 0 1 0 0 − y 3 0 0 1 0 − b 3 2 − 1 6 − ↓ \downarrow ↓ [ x 1 x 2 x 3 y 1 y 2 y 3 b x 2 1 1 0 − 2 0 − 1 4 y 2 − 2 0 0 − 7 / 2 1 − 3 / 2 7 / 2 x 3 0 0 1 − 1 / 2 0 − 1 / 2 1 / 2 − z − 2 0 0 − 9 / 2 0 − 5 / 2 17 / 2 ] \left[
\begin{array}{c|cccccc|c}
& x_1 & x_2 & x_3 & y_1 & y_2 & y_3 & b \\
\hline
x_2 & 1 & 1 & 0 & -2 & 0 & -1 & 4 \\
y_2 & -2 & 0 & 0 & -7/2 & 1 & -3/2 & 7/2 \\
x_3 & 0 & 0 & 1 & -1/2 & 0 & -1/2 & 1/2 \\
\hline
-z & -2 & 0 & 0 & -9/2 & 0 & -5/2 & 17/2 \\
\end{array}
\right] x 2 y 2 x 3 − z x 1 1 − 2 0 − 2 x 2 1 0 0 0 x 3 0 0 1 0 y 1 − 2 − 7/2 − 1/2 − 9/2 y 2 0 1 0 0 y 3 − 1 − 3/2 − 1/2 − 5/2 b 4 7/2 1/2 17/2 Đến bước này, do b ≥ 0 b \ge 0 b ≥ 0
( x 1 , x 2 , x 3 ) ⊤ = ( 0 , 4 , 1 2 ) ⊤ (x_1, x_2, x_3)^\top = (0, 4, \frac{1}{2})^\top ( x 1 , x 2 , x 3 ) ⊤ = ( 0 , 4 , 2 1 ) ⊤ và của bài toán đối ngẫu là
( y 1 , y 2 , y 3 ) ⊤ = ( 9 2 , 0 , 5 2 ) ⊤ (y_1, y_2, y_3)^\top = (\frac{9}{2}, 0, \frac{5}{2})^\top ( y 1 , y 2 , y 3 ) ⊤ = ( 2 9 , 0 , 2 5 ) ⊤ với giá trị tối ưu là z = − 17 2 z = -\frac{17}{2} z = − 2 17