西安建筑科技大学精品课程：《运筹学》电子教案_第二章 对偶线性规划

第2章对偶线性规划 一般来说,对于一个线性规划问题,一定存在与此互为对偶关系的另一个线性规划 问题。 2.1对偶问题的引出及定义 211引例 例21乐山厂计划出产甲、乙两种产品,该厂使用d1、d2和d三种生产因素的 数量限制、每产品所需各种因素及出厂后可获利润如下表2-1所示,求该厂所能得到的 最大利润。 表2-1 因素 d 单位利润 甲 最多可动用生产因素 45 解:设x为甲产品的生产数量,x2为乙产品的生产数量,据已知条件得出线形规划 max Z=5x, +4 x1+3x,≤90 2x1+X,≤80 x1+X,≤45 0 如果我们反面来考虑该问题:最低应付出多少代价,放能使乐山厂放弃生产x1和x2 的活动而出让d1,d2和d生产因素。 分析:要使乐山厂放弃生产C和x2出让d,a2和d生产因素、也就等于说要乐山 厂放弃由生产x1和x2所获得的最大利益,因此,我们最少应付出相等或大于这个最大收 益的数值,才能从乐山厂获得d,d2和d生产因素。 假设生产因素d1,d2和d3的单位机会成本分别为W1,W2和W3。那么,这三种因 素的最低价值应该是minG=90W1+80W2+45W3 并且有:maxZ≤minG 另一方面,生产单位x或x2所需用的生产因素d,d2和d3的机会价格不能低于x1或 x2的单位收益。否则的话,乐山厂宁愿自己生产而不会出让生产因素,因此我们得到反

第 2 章 对偶线性规划 一般来说，对于一个线性规划问题，一定存在与此互为对偶关系的另一个线性规划 问题。 2.1 对偶问题的引出及定义 2.1.1 引例 例 2.1 乐山厂计划出产甲、乙两种产品，该厂使用 d1、d2 和 d3 三种生产因素的 数量限制、每产品所需各种因素及出厂后可获利润如下表 2-1 所示，求该厂所能得到的 最大利润。 表 2-1 d1 d2 d3 单位利润 甲 1 2 1 5 乙 3 1 1 4 最多可动用生产因素 90 80 45 产 因 素 品 解：设x1为甲产品的生产数量，x2为乙产品的生产数量，据已知条件得出线形规划 ma 1 2 x 5 Z = x x + 4 1 2 1 2 1 2 1 2 x 3x 9 2x x 80 s t x x 45 x x 0  + ≤   + ≤ ⋅  + ≤    、 ≥ 0 W （1） 如果我们反面来考虑该问题：最低应付出多少代价，放能使乐山厂放弃生产 和x 的活动而出让 d 1 x 2 1，d2 和 d3 生产因素。 分析：要使乐山厂放弃生产 C 和 出让 d 2 x 1，d2 和 d3 生产因素、也就等于说要乐山 厂放弃由生产 和 所获得的最大利益，因此，我们最少应付出相等或大于这个最大收 益的数值，才能从乐山厂获得 d 1 x 2 x 1，d2 和 d3 生产因素。 假设生产因素 d1，d2 和 d3 的单位机会成本分别为 W1，W2 和 W3。那么，这三种因 素的最低价值应该是minG W = + 90 1 80W 2 + 45 3 并且有：max Z ≤ minG 另一方面，生产单位x 或x 所需用的生产因素 d 1 2 1，d2 和 d3 的机会价格不能低于 或 的单位收益。否则的话，乐山厂宁愿自己生产而不会出让生产因素，因此我们得到反 1 x 2 x

面问题的约束: st13w1+w2+w324 2 归纳起来,得到反面问题的线形规划 minG=90W1+80W2+45W3 w,+2w,+W,≥5 st3w1+w2+W3≥4 我们称规划(2)是规划(1)的对偶规划。 212定义 称线形规划 max Z=CX . AXsb X≥0 与线形规划 ming=bw (DP)。,「Aw≥C 为互为对偶规划 2.2对偶问题的性质 2.2.1对偶关系表 利用以上两规划的形式我们可以得出一个对偶关系表,如表2-2所示。 表22 a W2 amI amm

面问题的约束： 1 2 3 1 2 3 1 2 3 w 2w w s t 3w w w 4 w w w 0  + + ≥  ⋅ +  +   、 、 ≥ 5 ≥ W 5 ≥ 归纳起来，得到反面问题的线形规划： minG W = + 90 1 80W 2 + 45 3 1 2 3 1 2 3 1 2 3 w 2w w s t 3w w w 4 w w w 0  + + ≥  ⋅ +  +   、 、 ≥ （2） 我们称规划（2）是规划（1）的对偶规划。 2.1.2 定义 称线形规划 ( ) max Z CX L P AX b s t X 0  =  ⋅  ≤  ⋅    ≥  与线形规划 ( ) T T T min G b W D P A w C s t W 0  =  ⋅   ≥ ⋅    ≥  为互为对偶规划。 2.2 对偶问题的性质 2.2.1 对偶关系表 利用以上两规划的形式我们可以得出一个对偶关系表，如表 2-2 所示。 表 2-2 x1 x2 … xm … xn c1 c2 … cm … cn W1 a11 a12 … a1m … a1n b1 W2 a21 a22 … a2m … a2n b2 ┇ ┇ ┇ ┇ ┇ ┇ ┇ ┇ Wm am1 am2 … amm … amn bm maxZ ∧ ∧ ∧ ∧ ≤ ≤ ≤ minG

(1)从行看是原问题(Ⅰ),从列看是对偶问题(Ⅱ),两个问题的变量系数矩阵互 为转置矩阵 (2)原问题(Ⅰ)的常数项是对偶问题(Ⅱ)的目标系数,反之,原问题(I) 的目标系数是对偶问题(Ⅲ)的常数项。 (3)原问题(Ⅰ)有n个决策变量,对偶问题(Ⅱ)有n个约束方程:原问题有m 个约束方程,对偶问题就有m个决策变量。 (4)原问题的约束是“≤”型,对偶问题的约束是“≥”型 (5)原问题的目标函数是求极大,对偶问题的目标是求极小 例2.2在例2.1中引出的两规则 maxz=5x,+4x2 minG=901+80n2+453 x1+3x2≤90 212 2x1+x,≤80 s-n{3+n,+v2≥4 x1+x2≤45 ≥0 x1,x2≥0 的对偶关系表如表2-3。 从以上对偶表的关系知,只要我们得到定 表23 义中的原线性规划就可得到对偶规划,这样不 x 要再像例1那样通过分析建模,但对于一个普 5 4^3 ming 通线性规划的对偶规划的寻找方法还需要进 一步探讨。 2.1.2对偶问题的性质 对偶问题的性质比较多,在这里我们仅介 1≤45 绍几个较常用的性质,至于别的性质,请同学参阅其他的有关运筹学的书籍。 定理1如果线性规划(I)中的第k个约束条件是等式,则它的对偶规划(I 中的第k个变量Wk无非负限制(Wk为自由变量)。 反之,若原线性规划(Ⅰ)中的第k个变量无非负性要求,则对偶规划(Ⅱ)中的 第k个约束为等式 证:设线性规划(I)的第k个约束条件为等式,即 maxZ=Cx,+C2x2+.+Cnx a1x1+a12x2+…+a1nx≤b1 a21x1+a2x2+…+a2nxn≤b2 (I) s1{a1x+a42x2+…+mx=b anx1+an2x2+…+amxn≤bn ≥0

(1)从行看是原问题（Ⅰ），从列看是对偶问题（Ⅱ），两个问题的变量系数矩阵互 为转置矩阵。 （2）原问题（Ⅰ）的常数项是对偶问题（Ⅱ）的目标系数，反之，原问题（Ⅰ） 的目标系数是对偶问题（Ⅱ）的常数项。 （3）原问题（Ⅰ）有 n 个决策变量，对偶问题（Ⅱ）有 n 个约束方程：原问题有 m 个约束方程，对偶问题就有 m 个决策变量。 （4）原问题的约束是“≤”型，对偶问题的约束是“≥”型。 （5）原问题的目标函数是求极大，对偶问题的目标是求极小。 例 2.2 在例 2.1 中引出的两规则：        ≥ + ≤ + ≤ + ≤ ⋅ = + , 0 45 2 80 3 90 max 5 4 1 2 1 2 1 2 1 2 1 2 x x x x x x x x s t Z x x      ≥ + + ≥ + + ≥ ⋅ = + + , , 0 3 4 2 5 min 90 80 45 1 2 3 1 2 3 1 2 3 1 2 3 w w w w w w w w w s t G w w w 的对偶关系表如表 2-3。 从以上对偶表的关系知，只要我们得到定 义中的原线性规划就可得到对偶规划，这样不 要再像例 1 那样通过分析建模，但对于一个普 通线性规划的对偶规划的寻找方法还需要进 一步探讨。 2.1.2 对偶问题的性质 对偶问题的性质比较多，在这里我们仅介 绍几个较常用的性质，至于别的性质，请同学参阅其他的有关运筹学的书籍。 表 2-3 x1 x2 5 4 W1 1 3 90 W2 2 1 80 Wm 1 1 45 ≤ ≤ minG maxZ ∧ ∧ ≤ 定理 1 如果线性规划（Ⅰ）中的第 个约束条件是等式，则它的对偶规划（Ⅱ） 中的第 个变量W 无非负限制（W 为自由变量）。 k k k k 反之，若原线性规划（Ⅰ）中的第 个变量无非负性要求，则对偶规划（Ⅱ）中的 第 个约束为等式。 k k 证：设线性规划（Ⅰ）的第k 个约束条件为等式，即 1 1 2 2 11 1 12 2 1 1 21 1 22 2 2 2 1 1 2 2 1 1 2 2 1 2 max , , , 0 n n n n n n k k kn n m m mn n n Z C x C x C x a x a x a x b a x a x a x b s t a x a x a x b a x a x a x b x x x = + + +  + + + ≤  + + + ≤   ⋅ +  + + =   + + + ≤   ≥ " … … ……………………………… … ……………………………… … … k m (Ⅰ)

将aA1x1+a42x2+…+axn=b写为两个等价的不等式 akr, +akx ≥b akx+ak2x2+…+aonx≤b 或 x ≤b x b 代入(Ⅰ)式得出线性规划 x,+c2l a1x1+a12x2+…+a1nxn≤b a21x1+a2x2+…+a2nxn≤b2 akx, +ak2x ≤b (I) +,+a_x.≤b x1, x.≥0 得对偶关系表如表2-4 表2-4 x a12 a a 由对偶关系表得出(Ⅰ)的对偶规划 G=bW+bW2+…+bW-bW” b w w,+a,n wr-akw Wm≥C1 a12W+a22+…+a2Wk Wn≥C2 …+a +aW≥C. W,Wk",…,Wm≥0

将ak1 x1 + ak 2 x2 +"+ akn xn = bk 写为两个等价的不等式：    + + + ≤ + + + ≥ k k kn n k k k kn n k a x a x a x b a x a x a x b " " 1 1 2 2 1 1 2 2 或    − − + − ≤ − + + + ≤ k k kn n k k k kn n k a x a x a x b a x a x a x b " " 1 1 2 2 1 1 2 2 代入（Ⅰ）式得出线性规划 1 1 2 2 11 1 12 2 1 1 21 1 22 2 2 2 1 1 2 2 1 1 2 2 1 1 2 2 1 2 max , , , 0 n n n n n n k k kn n k k k kn n m m mn n n Z C x C x C x a x a x a x b a x a x a x b a x a x a x b s t a x a x a x b a x a x a x b x x x = + + +  + + + ≤  + + + ≤    + + + ≤ ⋅  − − − − ≤ −    + + + ≤   ≥ " … … ……………………………… " " ……………………………… … … k m (Ⅱ) 得对偶关系表如表 2-4 表 2-4 x1 x2 … xm … xn c1 c2 … cm … cn W1 a11 a12 … a1m … a1n b1 W2 a21 a22 … a2m … a2n b2 ┇ ┇ ┇ ┇ ┇ ┇ ┇ ┇ Wk ' ak1 ak2 … akm … akn bk Wk '' -ak1 -ak2 … -akm … -akn -bk ┇ ┇ ┇ ┇ ┇ ┇ ┇ ┇ Wm am1 am2 … amm … amn bm 由对偶关系表得出（Ⅰ）的对偶规划 1 1 2 2 11 1 21 2 1 1 1 1 12 1 22 2 2 2 2 2 1 1 2 2 1 2 min , , , , , , 0 k k k k k k k m m k k k m m k k k m m n n kn k kn mn m k k m G bW b W b W b W b W a W a W a W a W a W C a W a W a W a W a W C s t a W a W a W a W a W C W W W W W n = + + + ′ − ′′+ +  + + + ′ ′ − ′+ + ≥  + + + ′ ′ − ′+ + ≥ ⋅  + + + ′ ′ − ′+ + ≥ ′ ′′ ≥ " " " " " " """""""""""""""""" " " " "       ∧ maxZ minG ∧ ∧ ∧ ≤ ≤ ≤ ≤ ≤

令 (W,WF≥0) 则上式变为 minG=bW+bW2+…+bW+…+bnWn W+a21W2+…+ak1Wk+…+an1Wm≥C1 aM,+a2,W2 W , w s·t W1+a2W2+…+ak W≥C W,W2,…,Wm20,W无非负要求,K∈{12,…m 同样可证定理的反面(情形2)。 有了定义和定理1后,任一个线性规划得对偶规划都可以写出,其写法为: (i)将目标函数转化为求最大 (ⅱ)将约束条件转化为“≤”型或“=”型 (ii)写出对偶关系表 (iⅳv)据对偶表的规定写出对偶规划。 例2.3写出线性规划 max:=2x,+x2+x,+x x3+x4≤5 x2+3x3 3x2+x≥1 x1,x3≥ x2,x无非负性限制 的对偶规划 解:①将规划的“≥”型约束变为“≤”型约束,得到 max==2x1+x2+x3+ x+x2+x3+x4≤5 S x1+3x3-x4 x1,x3≥0,x2,x无非负性限制 ②写出对偶关系表如表2-5 表25 2 2

令 Wk = Wk ′ −Wk ′′ ( ) Wk ′,Wk ′′ ≥ 0 则上式变为 { } 1 1 2 2 11 1 21 2 1 1 1 12 1 22 2 2 2 2 1 1 2 2 1 2 min , , , 0, , 1,2, k k m m k k m m k k m m n n kn k mn m n m k G bW b W b W b W a W a W a W a W C a W a W a W a W C s t a W a W a W a W C W W W W K m = + + + + +  + + + + + ≥  + + + + + ≥   ⋅   + + + + + ≥    ≥ ∈ " " " " " " """""""""""""""""" " " " " 无非负要求 同样可证定理的反面（情形 2）。 有了定义和定理 1 后，任一个线性规划得对偶规划都可以写出，其写法为： （ⅰ）将目标函数转化为求最大 （ⅱ）将约束条件转化为“≤”型或“=”型 （ⅲ）写出对偶关系表 （ⅳ）据对偶表的规定写出对偶规划。 例 2.3 写出线性规划 1 2 3 4 1 2 3 4 1 2 3 1 3 4 1 3 4 2 max 2 5 2 3 4 3 1 , 0, , z x x x x x x x x x x x s t x x x x x x x = + + +  + + + ≤  − + = −  ⋅  − + ≥    ≥ 无非负性限制 的对偶规划 解：①将规划的“≥”型约束变为“≤”型约束，得到 1 234 1 2 3 4 1 2 3 1 3 4 1 3 2 4 max 2 5 2 3 4 3 1 , 0, , z x x x x x x x x x x x s t x x x x x x x = + + +  + + + ≤  − + = −  ⋅ − + − ≤ −   ≥ 无非负性限制 ②写出对偶关系表如表 2-5。 表 2-5 x1 x2 x3 x4 2 1 1 1 W1 1 1 1 1 5 W2 2 -1 3 0 -4 Wm -1 0 3 -1 -1 minG ∧∧ ‖∧ ≤ = ≤ ∧ ‖ maxZ