E包H厄 §2对偶理论 本节将深一步讨论线性规划的对偶问题的性质。 性质1（对称性）对偶问题(D)的对偶是原问题 (L) 卫HI2
§2 对偶理论 本节将深一步讨论线性规划的对偶问题的性质。 性质1（对称性）对偶问题（D）的对偶是原问题（L）
EH厄一G 性质2若原问题第个约束为等式，则其对偶问题中 第个变量为自由变量；反之，若原问题的第个变量是自 由变量，则其对偶问题的第个约束为等式。 卫HI2
性质2 若原问题第i个约束为等式，则其对偶问题中 第i个变量为自由变量；反之，若原问题的第j个变量是自 由变量，则其对偶问题的第j个约束为等式
线性规划的原问题与对偶问题的变换规则表： 原问题（或对偶问题） 对偶问题（或原问题） 目标函数maxZ 目标函数minW 价值系数 资源系数 资源系数 价值系数 行约束的个数为m 对偶变量的个数为m 第个行约束取“≤” 第i个变量y:≥0 第个行约束取“=” 第个变量y无限制 原变量的个数为n 行约束的个数为n 第j个变量x≥0 第j个行约束取“≥” 第k个变量x无限制 第k个行约束取“=” H2
线性规划的原问题与对偶问题的变换规则表： 原问题（或对偶问题） 对偶问题（或原问题） 目标函数 maxZ 价值系数 资源系数 目标函数 minW 资源系数 价值系数 行约束的个数为m 第i个行约束取“≤” 第ι个行约束取“＝” 对偶变量的个数为m 第i个变量yi ≥0 第ι个变量yι无限制 原变量的个数为n 第j个变量xj ≥0 第k个变量xk无限制 行约束的个数为n 第j个行约束取“≥” 第k个行约束取“＝
E包GH厄 例1写出下面线性规划的对偶规划 minZ=2x+x2-4X3 原问题即 2X1+3x2+x3 ≥1 minZ=2x+x2-4X3 3x1-x2+x3≤4 2x1+3x2+x3≥1 X1 +x3=3 -3x+X2-X3≥-4 X1,X2≥0 X1 +x33 其对偶为：maxW-y1-4y2+3y3 X1,X2≥0 2y13y2+y3≤2 3y1+y2 ≤1 y1-y2+y3 三-4 y1,y2≥0 HI口
例1 写出下面线性规划的对偶规划 minZ=2x1+ x2 -4x3 2x1+3x2 +x3 ≥1 3x1 - x2 +x3 ≤4 x1 +x3 =3 x1 ,x2≥0 原问题即 minZ=2x1+ x2 -4x3 2x1+3x2 +x3 ≥1 -3x1+ x2 -x3 ≥-4 x1 +x3 =3 x1 ,x 其对偶为：maxW=y1 -4y2+3y3 2≥0 2y1 - 3y2 +y3 ≤2 3y1+ y2 ≤1 y1 - y2 +y3 =-4 y1 ,y2≥0
E包GHDG 线性规划原问题与其对偶问题不仅具有形式上的对 称性，而且它们的解之间也具有紧密的联系。 性质3（弱对偶性）设X,Y分别是原问题(L)和对 偶问题(D)的任一可行解，则CX≤Yb 卫HI
线性规划原问题与其对偶问题不仅具有形式上的对 称性，而且它们的解之间也具有紧密的联系。 性质3（弱对偶性） 设X,Y分别是原问题（L）和对 偶问题（D）的任一可行解，则CX≤Yb
E包GH厄G 性质4设π是原问题的可行解，T是对偶问题的可行解 且C汉=Tb,则，T是各自问题的最优解。 卫HI2
性质4 设 是原问题的可行解， 是对偶问题的可行解， 且 ， 则 ， 是各自问题的最优解。 X CX=Yb X Y Y
EGH厄一 性质5若原问题 maxZ=CX (L) AX≤b LX≥0 有最优解，则其对偶问题也有最优解，且它们的最优值 相等。 证明：设B,X是原问题的最优基及最优解，记Y=CB1 则有C-YA=(CB,CN)-CBBI(B,N)=(O,CN-CBBN) ≤O,即YA≥C;再由AX≤b,可得AX+EX=b, 显然，松弛变量Xs的检验数os=0-CBE<O, 即 Y=CB1≥0，所以，Y是对偶可行解。又 Yb=CBB-b=CX,知Y=CB1是对偶问题的最优解 由证明过程可知：对偶最优解Y实际是原问题松 弛变量检验数的相反数
性质5 若原问题 maxZ= CX （L） AX≤b X≥0 有最优解，则其对偶问题也有最优解，且它们的最优值 相等。 证明：设B，X是原问题的最优基及最优解，记Y=CBB-1 则有 C-YA=（CB,CN）- CBB-1（B,N）=（0, CN-CBB-1N） ≤0，即YA≥C；再由AX≤b,可得AX+EXS=b, 显然，松弛变量XS的检验数σS=0-CBB-1E≤0,即 Y=CBB-1≥0，所以，Y是对偶可行解。又 Yb=CBB-1b=CX,知Y=CBB-1是对偶问题的最优解。 由证明过程可知：对偶最优解Y实际是原问题松 弛变量检验数的相反数
3对偶问题的经济意义 影子价格 在单纯形算法中，设XBb,XO是最优解；最优值 Z*=CB-b,取Y=CB-1=(y1,y2,,ym),则Y是对偶最优 解。 下面我们讨论y:(i=1,2,.,m)的经济含义。 设b:有单位增量△b:=1,其它参数不变，则 Z+△Z=CB-1.(b+(0,.,△b1,.,0)) =Z+y:△b: 即△Zy:△b:=y。所以y表示在原问题已取得最优 解的情沉下，第种资源改变一个单位时总收益的变化值 业以逸y是对第种资源的一种价格估计。这种价格估计 并不是第种资源的实际价值或成本，而是由该企业在制 产品的收觉来估计所用资源的单位价值，称为影子价格。 卫HI
§3 对偶问题的经济意义——影子价格 在单纯形算法中，设XB=B-1b，XN=0是最优解；最优值 Z﹡ =CBB -1b，取Y= CBB -1=（y1,y2,…,ym）,则Y是对偶最优 解。 下面我们讨论yi（i=1,2, …,m）的经济含义。 设bi有单位增量△ bi =1，其它参数不变，则 Z+△Z=CBB -1·(b+(0,…,△bi,…,0)T） =Z+yi△bi 即△Z= yi△bi = yi。所以yi表示在原问题已取得最优 解的情况下，第i种资源改变一个单位时总收益的变化值， 也可以说yi是对第i种资源的一种价格估计。这种价格估计 并不是第i种资源的实际价值或成本，而是由该企业在制 产品的收益来估计所用资源的单位价值，称为影子价格
EGH厄G 由于影子价格是指资源增加时对最优收益的贡献，所 以，也称它为资源的机会成本或边际产出，它表示资 源在最优产品组合时，具有的潜在价值”或“贡 献”。 资源的影子价格是与具体的企业及产品有关的，同 种资源，在不同企业，或生产不同产品时对应的影子 价格并不相同。 从对偶问题引出的实例中，可以看出，影子价格 趣是企业出让资源的最低价格，企业按这种价格出让 资源与用这种资源自己生产所获得的收益是相等的。 卫H
由于影子价格是指资源增加时对最优收益的贡献，所 以，也称它为资源的机会成本或边际产出，它表示资 源在最优产品组合时，具有的“潜在价值”或“贡 献”。 资源的影子价格是与具体的企业及产品有关的，同一 种资源，在不同企业，或生产不同产品时对应的影子 价格并不相同。 从对偶问题引出的实例中，可以看出，影子价格 也是企业出让资源的最低价格，企业按这种价格出让 资源与用这种资源自己生产所获得的收益是相等的
EH厄G 影子价格是经济学中的重要概念，将一个企亚拥 有的资源的影子价格与市场价格比较，可以决定是购 入还是出让该种资源。当某资源的市场价格低于影子 价格时，企业应该买进该资源用于扩大生产；而当市 场价格高于影子价格时，则企业的决策者应该将已有 资源买掉。这样获利会更多。在考虑一个地区或一个 国家某种资源的进出口决策中，资源的影子价格是影 响谈策的一个重要因素。 利用单纯形表求解线性规划，在求得最优解的同 很容易得到问题的各种资源的影子价格。某资源 的影子价格，就是该资源对应的约束条件所加松弛变 量在最优表中的检验数的相反数。 卫H
影子价格是经济学中的重要概念，将一个企业拥 有的资源的影子价格与市场价格比较，可以决定是购 入还是出让该种资源。当某资源的市场价格低于影子 价格时，企业应该买进该资源用于扩大生产；而当市 场价格高于影子价格时，则企业的决策者应该将已有 资源买掉。这样获利会更多。在考虑一个地区或一个 国家某种资源的进出口决策中，资源的影子价格是影 响决策的一个重要因素。 利用单纯形表求解线性规划，在求得最优解的同 时，很容易得到问题的各种资源的影子价格。某资源 的影子价格，就是该资源对应的约束条件所加松弛变 量在最优表中的检验数的相反数