二、对称形式的对偶线性规划互为对偶对称形式：. (LP) Max z=cx(DP) Min f= bT ys.t. ATy ≥cTs.t. Ax ≤bx ≥0≥03“Max -- ≤"Min--≥
二、对称形式的对偶线性规划 对称形式： 互为对偶 • (LP) Max z = c x (DP) Min f = b T y s.t. Ax ≤ b s.t. AT y ≥ c T x ≥ 0 y ≥ 0 “Max - ≤ ” “Min- ≥
·一对对称形式的对偶规划之间具有下面的对应关系。(1)若一个模型为目标求“极大”，约束为“小于等于”的不等式，则它的对偶模型为目标求“极小”，约束是“大于等于”的不等式。即“max，<”和“min，”相对应(2)从约束系数矩阵看：一个模型中为A，则另一个模型中为AT。一个模型是m个约束，n个变量，则它的对偶模型为n个约束，m个变量(3)从数据b、c的位置看：在两个规划模型中，b和c的位置对换。(4)两个规划模型中的变量皆非负
• 一对对称形式的对偶规划之间具有下面的对应 关系。 (1)若一个模型为目标求“极大” ，约束为 “小于等于”的不等式，则它的对偶模型为目 标求“极小” ，约束是“大于等于”的不等式。 即“max，≤”和“min，≥”相对应。 (2)从约束系数矩阵看：一个模型中为Ａ， 则另一个模型中为A T。一个模型是m个约束，n 个变量，则它的对偶模型为n个约束，m个变量。 (3)从数据b、c的位置看：在两个规划模型 中，b和c的位置对换。 (4)两个规划模型中的变量皆非负
对于对称形式的对偶规划问题，原问题与对2偶问题之间的关系可由表3-1直观地表示：表3-1原问题与对偶问题的对应关系表横向组合得原问题：原关系Min XIX2 ......XnMax Z= C, X, + C2 X, +.... + C, X.≤biy1a11a12 ..aina 11 X1 + a 12X2 +.... +a 1n x, <b≤b2Y2a 21a 22 .....a 2na 21 Xj +a 22X2 + ..... +a 2n X, ≤b2≤bmYmamlam2......amna m x,+am2x2 +..... +a m x,≤b对偶关系M(X≥0, Y≥0,)>..I.>/X≥0Max ZC1C2.....c.4若写成矩阵形式，可得：纵向组合得对偶问题：原问题：对偶问题：Min =biyi +b2y2 +.... +bmym3Min W=bTYMax Z=CXa 11 yi +a 21 y2 +..... +a m ym ≥ c1AT Y≥CTAX≤ba 12 Y1 + a 22 y2 + .... + a m2 Ym ≥ C2Y≥0tx≥0注意：其中C是行向量，X、Y与b是ainyi+a2ny2+.....+amym≥C列向量，Amn为ai;所构成的矩阵。Y≥0
对于对称形式的对偶规划问题，原问题与对 偶问题之间的关系可由表3-1直观地表示： 表3-1 原问题与对偶问题的对应关系表 x1 x2 . xn 原关系 Min ω y1 a 11 a 12 . a 1n ≤ b1 y2 a 21 a 22 . a 2n ≤ b2 . . . . . . . . . . ym a m1 a m2 . a mn ≤ bm 对偶关系 ≥ ≥ . ≥ (X≥0,Y≥0,) Max Z c1 c2 . cn 横向组合得原问题： Max Z= c1 x1 + c2 x2 +. + cn xn a 11 x1 + a 12x2 +. + a 1n xn≤b1 a 21 x1 + a 22x2 +. + a 2n xn≤b2 . . . . . . . a m1 x1 + a m2x2 + . + a mn xn≤bm X ≥ 0 纵向组合得对偶问题： Min ω= b1y1 +b2y2 + . +bmym a 11 y1 + a 21 y2 +. + a m1 ym ≥ c1 a 12 y1 + a 22 y2 +. + a m2 ym ≥ c2 . . . . . . . . a 1n y1 + a 2n y2 + . + a mn ym ≥ cn Y ≥ 0 若写成矩阵形式，可得： 原问题： 对偶问题： Max Z=CX Min ω=bTY AX ≤b AT Y ≥CT X ≥ 0 Y ≥0 注意：其中C是行向量，X、Y与b是 列向量，Amn为aij所构成的矩阵。 2 3 4 1
[例2]写出下面线性规划的对偶问题原（对偶）问题：对偶（原）问题为：Min Z=2x+5x2MaxW=4y1 +3 y2 +8y3yi <( Xi ≥4Yi +y3 ≤2→XY2 x2 ≥3Y2 +2y3≤5 ←→ X2Y3 <(Xi+2x2 ≥8y1≥0,2≥0, y3≥0X1 , X2 ≥0
[例2]写出下面线性规划的对偶问题 对偶（原）问题为： MaxW=4y1 +3 y2 +8y3 y1 +y3 ≤2 x1 y2 +2y3 ≤ 5 x2 y1≥0,y2≥0,y3≥0 原（对偶）问题： Min Z=2x1+5x2 y1 x1 ≥4 y2 x2 ≥3 y3 x1+2x2 ≥8 x1 , x2 ≥0
三、非对称的对偶线性规划·对于对称形式的线性规划可按上述规则写出其对偶规划，但是经常遇到的是非对称形式的线性规划问题（dualofanonnormalLP），这时可将其转化为等价的、满足对称形式条件的线性规划问题，然后再按照对称形式的原问题与对偶问题的对应关系表，构造其对偶问题·在非对称形式向对称形式转化的过程中，若原问题是隶省标函数极笑、药策条件果等式为“≥”，奇在不等式两端乘以-1，将“≥”化为“≤”；若决策变量x;或y;≤0，则令x'=-x;或yi=-yi，将决策变量化为非负值。对于约束条件是等式的标准型形式的原问题，可由下述方法导出其对偶规划问题
三、非对称的对偶线性规划 • 对于对称形式的线性规划可按上述规则写出其对偶 规划，但是经常遇到的是非对称形式的线性规划问 题（dual of a nonnormal LP），这时可将其转化为 等价的、满足对称形式条件的线性规划问题，然后 再按照对称形式的原问题与对偶问题的对应关系表， 构造其对偶问题。 • 在非对称形式向对称形式转化的过程中，若原问题 是求目标函数极大、约束条件不等式为“≥”，可 在不等式两端乘以-1，将“≥”化为“≤”；若决策 变量xj或yi≤0，则令xj '=- xj或yi '=-yi，将决策变量化 为非负值。对于约束条件是等式的标准型形式的原 问题，可由下述方法导出其对偶规划问题