線性規劃和對偶問題
任一線性規劃問題都存在另一與之伴隨的線性規劃問題，它們組成一對互為對偶的線性規劃問題，
線性規劃的對偶問題與原問題互為對偶，線性規劃的原問題與對偶問題地位具有對稱關系，
原問題和對偶問題的轉化
例子
原問題：
對偶問題：
轉化方法
1、原問題有幾個約束，對偶問題就有幾個變數
2、原來的約束系數矩陣轉個置就是對偶問題的約束系數矩陣
3、原來的目標函式系數變對偶問題約束常量，原來的約束常量變對偶問題的目標系數
4、左邊求最大，右邊求最小，按照這個模板帶進去就可以了 ——大佬
對偶問題的性質
在這里給出對偶問題的一些基本結論，暫不做證明
弱對偶引理：假設
x
x
x 和
λ
λ
λ 分別是線性規劃的原問題和對偶問題（對稱形式及非對稱形式）的可行解，則
x
T
x
≥
λ
T
b
x^Tx\ge λ^Tb
xTx≥λTb ，即“極大值
≤
\le
≤ 極小值”，
定理1：假設 x 0 x_0 x0? 和 λ 0 λ_0 λ0? 分別是原問題和對偶問題的可行解，如果 c T x 0 ≥ λ 0 T b c^Tx_0\ge λ_0^Tb cTx0?≥λ0T?b，那么 x 0 x_0 x0? 和 λ 0 λ_0 λ0? 分別是各自問題的最優解，
定理2（對偶定理）：如果原問題有最優解，那么其對偶問題也有最優解，并且它們目標函式的最優解相同，
定理3（互補松弛條件）：
x
x
x 和
λ
λ
λ 分別是原問題和對偶問題的可行解，則它們分別是各自問題的最優解的充分必要條件為
1.
(
c
T
?
λ
T
A
)
x
=
0
2.
λ
T
(
A
x
?
b
)
=
0
\begin{aligned} & 1.\ \ \ \ (c^T-λ^TA)x=0 \\ & 2.\ \ \ \ λ^T(A_x-b)=0 \end{aligned}
?1. (cT?λTA)x=02. λT(Ax??b)=0?
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/262989.html
標籤：其他