下面我们讨论标准形线性规划的对偶问题 设线性规划问题为 min s=cX AX=b (8.3) X≥0 等价于minS=CX AX≥b X≥ st-AX≥-b即stl-A bb (8.4) X≥0 X≥0
下面我们讨论标准形线性规划的对偶问题. 设线性规划问题为 s t s t min s t min − − − − = = = 0 0 0 X b b X A A X A X b A X b S C X X A X b S C X 即 等价于 (8.3) (8.4)
引进向量Y≥0,Y2≌0,则(84)的对偶问题可表为 maxz=(Y,Y2) C S·t H1≥0,Y2≥0 max=(-n,)b ∫G1-Y2)4≤C H1≥0,Y2≥0
− = − − − = 0 0 ( ) ( ) 0 0 1 2 1 2 1 2 1 2 , max , ( ) s t max ( ) 1 , 2 1 2 Y Y Y Y A C z Y Y b Y Y C A A Y Y b b z Y , Y 即 引进向量 Y1≥0, Y2≥0, 则（8.4）的对偶问题可表为
令 Y=Y 25 得线性规划问题(8.3)的对偶问题为 maxz=Y6 YA<C S·t (8.5) Y无非负限制 由于 min s= cX maxz=Y6 AX=b YA<C S·t 与s·t Ⅹ≥0 Y无非负限制
s t s t min max s t max = = = = = − 无非负限制 与 由于 无非负限制 令 Y YA C X A X b S C X z Yb Y YA C z Yb Y Y Y 0 , 1 2 得线性规划问题（8.3）的对偶问题为 (8.5)
在形式上不对称,故称这类对偶问题为非对称型对偶 问题 可以证明:(8.5)的对偶问题就是(8.3)也就是说(83) 与(8.5)互为对偶问题在这类非对称的对偶问题中, 个问题的约束条件为等式,则另一问题对应的决策变量 就无非负限制,反之亦然 综合对称型与非对称型对偶问题可得各类型对 偶问题的形式的对偶规则如下
在形式上不对称, 故称这类对偶问题为非对称型对偶 问题. 可以证明: (8.5)的对偶问题就是(8.3).也就是说(8.3) 与(8.5)互为对偶问题.在这类非对称的对偶问题中,一 个问题的约束条件为等式,则另一问题对应的决策变量 就无非负限制, 反之亦然. 综合对称型与非对称型对偶问题,可得各类型对 偶问题的形式的对偶规则如下: