Cho bài toán gốc và bài toán đối ngẫu ở dạng tổng quát sau:
( P ) max ∑ j = 1 n c j x j s.t. ∑ j = 1 n a i j x j ≤ b i , i ∈ I , ∑ j = 1 n a i j x j = b i , i ∈ E , x j ≥ 0 , j ∈ R . \begin{aligned}
(\mathcal{P}) \quad
\max \quad & \sum_{j=1}^{n} c_j x_j \\
\text{s.t.} \quad
& \sum_{j=1}^{n} a_{ij} x_j \le b_i, \quad i \in I, \\
& \sum_{j=1}^{n} a_{ij} x_j = b_i, \quad i \in E, \\
& x_j \ge 0, \quad j \in R.
\end{aligned} ( P ) max s.t. j = 1 ∑ n c j x j j = 1 ∑ n a ij x j ≤ b i , i ∈ I , j = 1 ∑ n a ij x j = b i , i ∈ E , x j ≥ 0 , j ∈ R . ( D ) min ∑ i = 1 m b i y i s.t. ∑ i = 1 m a i j y i ≥ c j , j ∈ R , ∑ i = 1 m a i j y i = c j , j ∈ F , y i ≥ 0 , i ∈ I . \begin{aligned}
(\mathcal{D}) \quad
\min \quad & \sum_{i=1}^{m} b_i y_i \\
\text{s.t.} \quad
& \sum_{i=1}^{m} a_{ij} y_i \ge c_j, \quad j \in R, \\
& \sum_{i=1}^{m} a_{ij} y_i = c_j, \quad j \in F, \\
& y_i \ge 0, \quad i \in I.
\end{aligned} ( D ) min s.t. i = 1 ∑ m b i y i i = 1 ∑ m a ij y i ≥ c j , j ∈ R , i = 1 ∑ m a ij y i = c j , j ∈ F , y i ≥ 0 , i ∈ I . ▸ ĐỊNH LÝ ĐỘ LỆCH BÙ
Giả sử x ∈ R n x \in \mathbb{R}^n x ∈ R n ( P ) (\mathcal{P}) ( P ) y ∈ R m y \in \mathbb{R}^m y ∈ R m ( D ) (\mathcal{D}) ( D )
Khi đó x x x y y y ( P ) (\mathcal{P}) ( P ) ( D ) (\mathcal{D}) ( D )
Với mọi j ∈ R j \in R j ∈ R x j = 0 x_j = 0 x j = 0 ∑ i = 1 m a i j y i = c j \sum_{i=1}^{m} a_{ij} y_i = c_j ∑ i = 1 m a ij y i = c j
Với mọi i ∈ I i \in I i ∈ I y i = 0 y_i = 0 y i = 0 ∑ j = 1 n a i j x j = b i \sum_{j=1}^{n} a_{ij} x_j = b_i ∑ j = 1 n a ij x j = b i
▸ HỆ QUẢ
x x x ( P ) (\mathcal{P}) ( P )
x x x ( P ) (\mathcal{P}) ( P ) Tồn tại y y y ( D ) (\mathcal{D}) ( D )
{ ∑ j = 1 n a i j x j < b i ⇒ y i = 0 , ∀ i ∈ I , x j > 0 ⇒ ∑ i = 1 m a i j y i = c j , ∀ j ∈ R . \begin{cases}
\sum_{j=1}^{n} a_{ij} x_j < b_i \; & \Rightarrow\; y_i = 0, & \forall i \in I, \\
x_j > 0 \; & \Rightarrow\; \sum_{i=1}^{m} a_{ij} y_i = c_j, & \forall j \in R.
\end{cases} { ∑ j = 1 n a ij x j < b i x j > 0 ⇒ y i = 0 , ⇒ ∑ i = 1 m a ij y i = c j , ∀ i ∈ I , ∀ j ∈ R . ▸ VÍ DỤ
Kiểm tra xem x = ( x 1 , x 2 , x 3 , x 4 , x 5 ) ⊤ = ( 0 , 4 3 , 2 3 , 5 3 , 0 ) ⊤ x = (x_1, x_2, x_3, x_4, x_5)^\top = (0, \frac{4}{3}, \frac{2}{3}, \frac{5}{3}, 0)^\top x = ( x 1 , x 2 , x 3 , x 4 , x 5 ) ⊤ = ( 0 , 3 4 , 3 2 , 3 5 , 0 ) ⊤
max 7 x 1 + 6 x 2 + 5 x 3 − 2 x 4 + 3 x 5 s.t. x 1 + 3 x 2 + 5 x 3 − 2 x 4 + 2 x 5 ≤ − 4 4 x 1 + 2 x 2 − 2 x 3 + x 4 + x 5 ≤ − 3 2 x 1 + 4 x 2 + 4 x 3 − 2 x 4 + 5 x 5 ≤ − 5 3 x 1 + x 2 + 2 x 3 − x 4 − 2 x 5 ≤ − 1 \begin{align*}
\max \quad
& 7x_1 & +\; & 6x_2 & +\; & 5x_3 & -\; & 2x_4 & +\; & 3x_5 & & \\
\text{s.t.} \quad
& \ \ x_1 & +\; & 3x_2 & +\; & 5x_3 & -\; & 2x_4 & +\; & 2x_5 & \le & \ \phantom{-}4 \\
& 4x_1 & +\; & 2x_2 & -\; & 2x_3 & +\; & \ \ x_4 & +\; & \ \ x_5 & \le & \ \phantom{-}3 \\
& 2x_1 & +\; & 4x_2 & +\; & 4x_3 & -\; & 2x_4 & +\; & 5x_5 & \le & \ \phantom{-}5 \\
& 3x_1 & +\; & \ \ x_2 & +\; & 2x_3 & -\; & \ \ x_4 & -\; & 2x_5 & \le & \ \phantom{-}1
\end{align*} max s.t. 7 x 1 x 1 4 x 1 2 x 1 3 x 1 + + + + + 6 x 2 3 x 2 2 x 2 4 x 2 x 2 + + − + + 5 x 3 5 x 3 2 x 3 4 x 3 2 x 3 − − + − − 2 x 4 2 x 4 x 4 2 x 4 x 4 + + + + − 3 x 5 2 x 5 x 5 5 x 5 2 x 5 ≤ ≤ ≤ ≤ − 4 − 3 − 5 − 1 x 1 , x 2 , x 3 , x 4 , x 5 ≥ 0 x_1, x_2, x_3, x_4, x_5 \ge 0 x 1 , x 2 , x 3 , x 4 , x 5 ≥ 0 Viết bài toán đối ngẫu của bài toán gốc như sau:
min − 4 y 1 + 3 y 2 + 5 y 3 + y 4 s.t. − y 1 + 4 y 2 + 2 y 3 + 3 y 4 ≥ − 7 − 3 y 1 + 2 y 2 + 4 y 3 + y 4 ≥ − 6 − 5 y 1 − 2 y 2 + 4 y 3 + 2 y 4 ≥ − 5 − 2 y 1 + y 2 − 2 y 3 − y 4 ≥ − 2 − 2 y 1 + y 2 + 5 y 3 − 2 y 4 ≥ − 3 \begin{align*}
\min \quad
& \phantom{-}4y_1 & +\; & 3y_2 & +\; & 5y_3 & +\; & \ \ y_4 & & \\
\text{s.t.} \quad
& \phantom{-}\ \ y_1 & +\; & 4y_2 & +\; & 2y_3 & +\; & 3y_4 & & \ge & \ \phantom{-}7 \\
& \phantom{-}3y_1 & +\; & 2y_2 & +\; & 4y_3 & +\; & \ \ y_4 & & \ge & \ \phantom{-}6 \\
& \phantom{-}5y_1 & -\; & 2y_2 & +\; & 4y_3 & +\; & 2y_4 & & \ge & \ \phantom{-}5 \\
& -2y_1 & +\; & \ \ y_2 & -\; & 2y_3 & -\; & \ \ y_4 & & \ge & -2 \\
& \phantom{-}2y_1 & +\; & \ \ y_2 & +\; & 5y_3 & -\; & 2y_4 & & \ge & \ \phantom{-}3
\end{align*} min s.t. − 4 y 1 − y 1 − 3 y 1 − 5 y 1 − 2 y 1 − 2 y 1 + + + − + + 3 y 2 4 y 2 2 y 2 2 y 2 y 2 y 2 + + + + − + 5 y 3 2 y 3 4 y 3 4 y 3 2 y 3 5 y 3 + + + + − − y 4 3 y 4 y 4 2 y 4 y 4 2 y 4 ≥ ≥ ≥ ≥ ≥ − 7 − 6 − 5 − 2 − 3 y 1 , y 2 , y 3 , y 4 ≥ 0 y_1, y_2, y_3, y_4 \ge 0 y 1 , y 2 , y 3 , y 4 ≥ 0 Trước hết, ta thế x = ( 0 , 4 3 , 2 3 , 5 3 , 0 ) ⊤ x = \left(0,\frac{4}{3},\frac{2}{3},\frac{5}{3},0\right)^\top x = ( 0 , 3 4 , 3 2 , 3 5 , 0 ) ⊤
0 + 3 ⋅ 4 3 + 5 ⋅ 2 3 − 2 ⋅ 5 3 + 0 = − 4 ( = b 1 ) 0 + 2 ⋅ 4 3 − 2 ⋅ 2 3 + 5 3 + 0 = − 3 ( = b 2 ) 0 + 4 ⋅ 4 3 + 4 ⋅ 2 3 − 2 ⋅ 5 3 + 0 = 14 3 < 5 ( = b 3 ) 0 + 4 3 + 2 ⋅ 2 3 − 5 3 − 0 = − 1 ( = b 4 ) \begin{align*}
& 0 & +\; & 3\cdot \frac{4}{3} & +\; & 5\cdot \frac{2}{3} & -\; & 2\cdot \frac{5}{3} & +\; & 0 & = & \ \phantom{-}4 \;\; (= b_1) \\
& 0 & +\; & 2\cdot \frac{4}{3} & -\; & 2\cdot \frac{2}{3} & +\; & \ \frac{5}{3} & +\; & 0 & = & \ \phantom{-}3 \;\; (= b_2) \\
& 0 & +\; & 4\cdot \frac{4}{3} & +\; & 4\cdot \frac{2}{3} & -\; & 2\cdot \frac{5}{3} & +\; & 0 & = & \ \frac{14}{3} \;<\; 5 \;\; (= b_3) \\
& 0 & +\; & \ \frac{4}{3} & +\; & 2\cdot \frac{2}{3} & -\; & \ \frac{5}{3} & -\; & 0 & = & \ \phantom{-}1 \;\; (= b_4)
\end{align*} 0 0 0 0 + + + + 3 ⋅ 3 4 2 ⋅ 3 4 4 ⋅ 3 4 3 4 + − + + 5 ⋅ 3 2 2 ⋅ 3 2 4 ⋅ 3 2 2 ⋅ 3 2 − + − − 2 ⋅ 3 5 3 5 2 ⋅ 3 5 3 5 + + + − 0 0 0 0 = = = = − 4 ( = b 1 ) − 3 ( = b 2 ) 3 14 < 5 ( = b 3 ) − 1 ( = b 4 ) Từ đó suy ra:
Các ràng buộc (1), (2), (4) là chặt .
Ràng buộc (3) là không chặt vì 14 3 < 5 \frac{14}{3} < 5 3 14 < 5
Theo hệ quả của định lý độ lệch bù, nghiệm tối ưu y y y y 3 = 0 y_3 = 0 y 3 = 0
Cũng theo hệ quả của định lý độ lệch bù, do x 2 , x 3 , x 4 > 0 x_2, x_3, x_4 > 0 x 2 , x 3 , x 4 > 0 y y y
{ 3 y 1 + 2 y 2 + 4 y 3 + y 4 = 6 5 y 1 − 2 y 2 + 4 y 3 + 2 y 4 = 5 − 2 y 1 + y 2 − 2 y 3 − y 4 = − 2 \begin{cases}
3y_1 + 2y_2 + 4y_3 + y_4 = 6 \\
5y_1 - 2y_2 + 4y_3 + 2y_4 = 5 \\
-2y_1 + y_2 - 2y_3 - y_4 = -2
\end{cases} ⎩ ⎨ ⎧ 3 y 1 + 2 y 2 + 4 y 3 + y 4 = 6 5 y 1 − 2 y 2 + 4 y 3 + 2 y 4 = 5 − 2 y 1 + y 2 − 2 y 3 − y 4 = − 2 Do x 1 , x 5 = 0 x_1, x_5 = 0 x 1 , x 5 = 0
Mặt khác, do y 3 = 0 y_3 = 0 y 3 = 0
{ 3 y 1 + 2 y 2 + y 4 = 6 5 y 1 − 2 y 2 + 2 y 4 = 5 − 2 y 1 + y 2 − y 4 = − 2 \begin{cases}
3y_1 + 2y_2 + y_4 = 6 \\
5y_1 - 2y_2 + 2y_4 = 5 \\
-2y_1 + y_2 - y_4 = -2
\end{cases} ⎩ ⎨ ⎧ 3 y 1 + 2 y 2 + y 4 = 6 5 y 1 − 2 y 2 + 2 y 4 = 5 − 2 y 1 + y 2 − y 4 = − 2 Giải hệ trên, ta thu được nghiệm:
y = ( y 1 , y 2 , y 3 , y 4 ) ⊤ = ( 1 , 1 , 0 , 1 ) ⊤ y = (y_1, y_2, y_3, y_4)^\top = (1, 1, 0, 1)^\top y = ( y 1 , y 2 , y 3 , y 4 ) ⊤ = ( 1 , 1 , 0 , 1 ) ⊤ Ta thế nghiệm y = ( 1 , 1 , 0 , 1 ) ⊤ y = (1, 1, 0, 1)^\top y = ( 1 , 1 , 0 , 1 ) ⊤
1 + 4 ⋅ 1 + 2 ⋅ 0 + 3 ⋅ 1 = − 8 > 7 2 ⋅ 1 + 1 + 5 ⋅ 0 − 2 ⋅ 1 = − 1 ≱ 3 \begin{align*}
& \ \ 1 & +\; & 4\cdot 1 & +\; & 2\cdot 0 & +\; & 3\cdot 1 & = & \ \phantom{-}8 \;\; > \;\; 7 \\
& 2\cdot 1 & +\; & \ \ 1 & +\; & 5\cdot 0 & -\; & 2\cdot 1 & = & \ \phantom{-}1 \;\; \ngeq \;\; 3
\end{align*} 1 2 ⋅ 1 + + 4 ⋅ 1 1 + + 2 ⋅ 0 5 ⋅ 0 + − 3 ⋅ 1 2 ⋅ 1 = = − 8 > 7 − 1 ≱ 3 Do y y y
⇒ y = ( 1 , 1 , 0 , 1 ) ⊤ y = (1, 1, 0, 1)^\top y = ( 1 , 1 , 0 , 1 ) ⊤ không phải nghiệm chấp nhận được của bài toán đối ngẫu.
⇒ Kết luận: x = ( 0 , 4 3 , 2 3 , 5 3 , 0 ) ⊤ x = \left(0,\frac{4}{3},\frac{2}{3},\frac{5}{3},0\right)^\top x = ( 0 , 3 4 , 3 2 , 3 5 , 0 ) ⊤ không phải nghiệm tối ưu của bài toán gốc.