第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
③据表2-5得对偶规划 minG= 5W1+(4)W2-W3 W+2H2-W3≥2 W-W,=1 s{W+3W2+W≥1 ,-W=1 W,H≥0,无非负性要求 定理2若X,W分别为互为对偶规划(I)与(Ⅱ)的可行解,则minG≥maxz 证:因为G=bW≥(AX)W=XAW=X(AW)≥XC=(CX)=CX=所以 minG≥maxz。 定理3若X,W分别为互为对偶规划(I)与(Ⅱ)的可行解,并且CX'=bW, 则X与W·分别为(Ⅰ)与(Ⅱ)的最优解。 因为,由定理2知,对(1)与()的任一可行解X,W都有G≥Z(CX≤bW 所以,特别的对可行解X也有bW≥CX成立。 又因为,CX'=bW,故对任何可行解W都有bW≥CX’=bW”从而由极小值 的最优解的定义知,W是(Ⅱ)的最优解。同理可证,X是规划(Ⅰ)的最优解 定理4对偶问题的对偶是问题 证:设原问题是maxf(X)=CX;AX≤b,X≥0根据对偶问题的标准形式可找到它的 对偶问题minG=bW;AW≥C,W≥0对上式的目标函数两边取负号-minG=-bW 又因为-minG=max(-G),所以max(-G)=-bW,给约束条件两边取负号,得 AW≤-C7,W≥0合起来有线性规划 max(-G)=-b'w AW≤-C W≥0 根据标准形式的对偶关系,上式的对偶问题是 min(-C)=-CX;-AX≥-b;X≥0 又因为min(-G')=-maxW 所以,-maxW=-CX;-AX≥-b,X≥0 即maxf(X)=CX;AX≤b,X≥0即是原问题。 定理5设X为线性规划(Lp)的基本最优解,对应基阵为B,并且其检验数全 部非正,则W=CBB-是对偶规划(Dp)的最优解 证明:由线性代数的知识知(LP)对应于X的典型式为 XB=XR-B-NXN =B-b-BNXN f=f-(CBB-N-CN)XN=f-1rN
③据表 2-5 得对偶规划 1 2 3 1 2 3 1 2 1 2 3 1 3 1 3 2 min 5 ( 4) 2 2 1 3 1 1 , 0, G W W W W W W W W s t W W W W W W W W = + − − + − ≥ − = ⋅ + + ≥ − = ≥ 无非负性要求 定理 2 若 X ,W分别为互为对偶规划（Ⅰ）与（Ⅱ）的可行解，则min G ≥ max z 证：因为G 所以， 。 b W AX W X A W X A W X C CX CX z T T T T T T T T T = ≥ ( ) = = ( ) ≥ = ( ) = = min G ≥ max z 定理 3 若 （Ⅰ）与（Ⅱ）的可行解，并且CX ， 则 X ∗ ,W ∗ 分别为互为对偶规划 ∗ ∗ = b W T ∗ ∗ X 与W 分别为（Ⅰ）与（Ⅱ）的最优解。 因为，由定理 2 知，对（Ⅰ）与（Ⅱ）的任一可行解 X ,W 都有 ， 所以，特别的对可行解 G Z(CX b W ) T ≥ ≤ X ∗ 也有bT W ≥ CX ∗ 成立。 又因为， ，故对任何可行解W 从而由极小值 的最优解的定义知，W 是（Ⅱ）的最优解。同理可证， ∗ ∗ CX = b W T ∗ ,都有 ∗ ∗ b W ≥ CX = b W T T ∗ X 是规划（Ⅰ）的最优解。 定理 4 对偶问题的对偶是问题 证：设原问题是max f (X ) = CX; AX ≤ b; X ≥ 0 W; A W ≥ C ,W ≥ 0 T T max( G), max( G) b W, T − 所以 − = − 0 根据对偶问题的标准形式可找到它的 对偶问题 min 对上式的目标函数两边取负号 又因为 给约束条件两边取负号，得 ，W 合起来有线性规划 G = bT − min G = T −C ≥ G b W T − min = − − A W ≤ ≥ − ≤ − ⋅ − = − 0 max( ) W A W C s t G b W T T T 根据标准形式的对偶关系，上式的对偶问题是 min(−C′) = −CX; − AX ≥ −b; X ≥ 0 又因为min( −G ′) = − max W ′ 所以，− maxW′ = −CX; − AX ≥ −b; X ≥ 0 即max f (X ) = CX; AX ≤ b; X ≥ 0即是原问题。 定理 5 设 ∗ X 为线性规划（L,p）的基本最优解，对应基阵为 B，并且其检验数全 部非正，则W ∗ = CB B−1是对偶规划（D,p）的最优解。 证明：由线性代数的知识知（L,P）对应于 ∗ X 的典型式为 B B N N B N X N X = X − B NX = B b − BNX f = f − C B N − CN X = f − λ ∗ −1 −1 0 −1 0 ( )
又因为A=(,A2…,n)=C-CBA 由A≤0知,C-CBA≤0,从而WA≥C 即W是(DP)的可行解。 又因为,Wb=CBb=CBX=CX”由定理3知W是对偶规划的最优解 2.3对偶单纯形法 2.3.1问题引出 例2.4求解线性规划 max f=-x-3 3x1+2x2≥4 +2x2 x1,x,≥0 解:先把问题标准化: f x3=3 x1+2x2-x4 ≥0(j=12,…,5) 若取x3,x4,x3为基变量,所得基本解X°=(0,00-3-4-1)不是可行解,故它不能 作单纯形法的初始解,为了得到初始可行解,按前章办法引入人工变量x6,x1x3然后 采用两阶段或大M法求解,这样一来,增加了变量的数目。 显然麻烦,眼看一个负的单位阵,但不能作基阵使用,实在遗憾。在这种情况下 能否找到比两阶段法更为简便的方法呢? 也许有的同学们会想到先求其对偶问题 min g=3W,+ 4w,+w 2W1+3H,+W3≤-1 s1W+2W,+2W3≤-3 W1,W2,W3≥0 此对偶问题可用单纯性法求解 但是我们还嫌太麻烦,我们还是希望利用原问题进行迭代求解,这当然不是单纯形 迭代而必须是一种新的迭代方法,这就是对偶单纯形法。 2.2.2方法的基本思想 在本例中,X0=(0,00-3-4-1)虽然不是原问题的可行解,但却是基本解,且对
又因为 1 1 2 ( ,,, ) λ λ λ λm B C C B A− = = " − 1 0 , 0 λ C CB B A− 由 ≤ − 知 ≤ ，从而W A∗ ≥ C 。 即W ∗ 是（D,P）的可行解。 又因为，W ∗ b = CB B−1 b = CB X B ∗ = CX ∗ 由定理 3 知W ∗ 是对偶规划的最优解。 2.3 对偶单纯形法 2.3.1 问题引出 例 2.4 求解线性规划 ≥ + ≥ + ≥ + ≥ ⋅ = − − , 0 2 1 3 2 4 2 3 max 3 1 2 1 2 1 2 1 2 1 2 x x x x x x x x s t f x x 解：先把问题标准化： ≥ = + − = + − = + − = ⋅ = − − 0 ( 1,2, ,5) 2 1 3 2 4 2 3 max 3 1 2 5 1 2 4 1 2 3 1 2 xj j " x x x x x x x x x s t f x x 若取 为基变量，所得基本解 不是可行解，故它不能 作单纯形法的初始解，为了得到初始可行解，按前章办法引入人工变量 ,然后 采用两阶段或大 M 法求解，这样一来，增加了变量的数目。 3 4 5 x , x , x T X (0,0,0, 3, 4, 1) 0 = − − − 6 7 8 x , x , x 显然麻烦，眼看一个负的单位阵，但不能作基阵使用，实在遗憾。在这种情况下， 能否找到比两阶段法更为简便的方法呢？ 也许有的同学们会想到先求其对偶问题。 ≥ + + ≤ − + + ≤ − ⋅ = + + , , 0 2 2 3 2 3 1 min 3 4 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.2.2 方法的基本思想 在本例中， X 0 = (0,0,0,−3,−4,−1) T 虽然不是原问题的可行解，但却是基本解，且对
应的检验数(-1,-3,0,0,0)全部非正,容易验证对应的C2B是对偶问题的可行 解(此时称X°具有对偶可行性),一般地,如果X°是(L,p)的基本解且对应检验数全 部非正,则对应的CB-必为对偶问题(D,p)的可行解。如果在迭代过程中,保持基 本解的对偶可行性,而使其对原问题的非可行性逐步消失,一旦基本解达到可行,则此 解必是原问题的最优解。这就是对偶单纯形法的基本思想,为表达方便起见,先引进下 面概念 定义:对于(L,p),其检验数全部非正的基本解称为(L,p)的正则解,对应的基 称为正则基。 从而可知,如果X°既是(L,p)的正则解,又是它的可行解,则X也是(L,p)的 最优解。所谓对偶单纯形法就是以这一事实为依据。即从(L,p)的正则解开始迭代, 在迭代过程中保持正则性,而使其不可行逐步消失,最后达到可行解,从而得到最优解。 2.3.3对偶单纯形方法步骤 第一步:建立线性规划的单纯形表 第二步:判别,若单纯形表中的b≥0(=1,2,…,m),且λ,≤0,则X是最优解。若某 负常数项,对应行中的变量系数无负数,则该规划无最优解,否则进行第三步 第三步:确定出基变量,选常数列中最小负数对应的行中的基变量出基,即 mn(bb<0}=b所对应行的基变量出基。 第四步:确定入基变量Q={1<0.a<0}对应的变量入基 第五步:确定主元,将主元变1,主元所在列上的其他元素变为零。 2.3.4方法应用举例 例2.5利用对偶单纯形法求解线性规划 3x x,+x2= 3x1+2x2≥4 x1,x,,x3≥0 解:求解过程如表2-6所示。 由对偶单纯形表2-6可知 2,0,0.1 ,max2=、3
应的检验数（-1，-3，0，0，0）全部非正，容易验证对应的C 是对偶问题的可行 解（此时称 −1 B B 0 X 具有对偶可行性），一般地，如果 0 X 是（L,p）的基本解且对应检验数全 部非正，则对应的C 必为对偶问题（D,p）的可行解。如果在迭代过程中，保持基 本解的对偶可行性，而使其对原问题的非可行性逐步消失，一旦基本解达到可行，则此 解必是原问题的最优解。这就是对偶单纯形法的基本思想，为表达方便起见，先引进下 面概念。 −1 B B 0 X ,", 0 } l < 0 = b * + 0 4 3 2 x x 3 1 , 0, , 2 2 , 0 定义：对于（L,p），其检验数全部非正的基本解称为（L,p）的正则解，对应的基 称为正则基。 从而可知，如果 既是（L,p）的正则解，又是它的可行解，则 0 X 也是（L,p）的 最优解。所谓对偶单纯形法就是以这一事实为依据。即从（L,p）的正则解开始迭代， 在迭代过程中保持正则性，而使其不可行逐步消失，最后达到可行解，从而得到最优解。 2.3.3 对偶单纯形方法步骤 第一步：建立线性规划的单纯形表 第二步：判别，若单纯形表中的bi ≥ 0(i =1,2 m),且λ j ≤ ，则 X 是最优解。若某 负常数项，对应行中的变量系数无负数，则该规划无最优解，否则进行第三步。 第三步：确定出基变量，选常数列中最小负数对应的行中的基变量出基，即 min{ i i b b 所对应行的基变量出基。 第四步：确定入基变量 0, 0 j s j i j i j a a λ θ λ ∗ = < < 对应的变量入基。 第五步：确定主元，将主元变 1，主元所在列上的其他元素变为零。 2.3.4 方法应用举例 例 2.5 利用对偶单纯形法求解线性规划 ≥ + ≥ + ≥ − − = − ⋅ = − − , , 2 1 3 2 2 3 max 3 1 2 3 1 2 1 2 1 2 1 x x x x x x x x x s t Z x 解：求解过程如表 2-6 所示。 由对偶单纯形表 2-6 可知 ( ) * T x = 1 2 ， 3 max 2 Z = −
表2-6 0 0 000 n231 12203 0000 乙000I0x 0010000 b341 01+0 1-32-343 1-34-3 0 0100 7-3121 000032121-2 313 1 321250 0000 0000100 12321232 0 2.4灵敏度分析 灵敏度分析所研究的问题是,当某一规划的最优解已知的情况下,某数据发生变化 后对最优解产生的影响。原数据发生变化的主要原因可能有原始数据不可靠或准确度不 髙,实际问题的条件模糊不清或被忽略,优解执行一段时间后环境条件发生变化等。例 如,市场条件一变,显然价值系数c,就随之改变,资源限量根据供应和发展也很可能改 变,因此影响b的取值;约束条件系数an也会随生产条件及技术的改进而发生变化。因 此我们有必要研究当某些系数变化,或增减变量及约束条件时,问题的最优解改变多少 或者最优解不改变时,这些数据的允许变化范围又有多大。当然。以上数据条件改变后
表 2-6 cj -1 -3 0 0 0 cB xB x1 x2 x3 x4 x5 bi 0 x3 -2 -1 1 0 0 -3 0 x4 -3 -2 0 1 0 -4 0 x5 -1 -2 0 0 1 -1 zj 0 0 0 0 0 0 cj- zj -1 -3 0 0 0 0 x3 0 1 3 1 2 3 0 1 3 − -1 x1 1 2 3 0 1 3 − 0 4 3 0 x5 0 4 3 − 0 1 3 − 1 1 3 zj -1 2 3 − 0 1 3 0 4 3 − λj= cj- zj 0 7 3 − 0 1 3 − 0 0 x4 0 1 2 − 3 2 − 1 0 1 2 1 x1 1 1 2 1 2 − 0 0 3 2 -1 x2 0 3 2 − 1 2 − 0 1 1 2 zj -1 1 2 − 1 2 0 0 3 2 − λj= cj- zj 0 5 2 − 1 2 − 0 0 ← ↑ ← ↑ 2.4 灵敏度分析 灵敏度分析所研究的问题是，当某一规划的最优解已知的情况下，某数据发生变化 后对最优解产生的影响。原数据发生变化的主要原因可能有原始数据不可靠或准确度不 高，实际问题的条件模糊不清或被忽略，优解执行一段时间后环境条件发生变化等。例 如，市场条件一变，显然价值系数 就随之改变，资源限量根据供应和发展也很可能改 变，因此影响b 的取值；约束条件系数 也会随生产条件及技术的改进而发生变化。因 此我们有必要研究当某些系数变化，或增减变量及约束条件时，问题的最优解改变多少， 或者最优解不改变时，这些数据的允许变化范围又有多大。当然。以上数据条件改变后， j c i aij
也可建立一个新规划,从头求解,但这样做显得太费时,对一些问题也是无必要的。其 次也不利于计算机的使用 24.1目标函数系数的灵敏度分析 设线性规划maxZ=Cx Ax= b x≥0 的最优解表示为 x j=m+1 其中,=c1-=1,-0=∑cb,Z1=ca 由上式显见,当目标系数c,有改变量△c时,对解x无直接影响,但对目标函数z 值及检验数λ,有影响,如果λ变化比较大,将使得原判断优解的结论改变,导致继续 迭代,使优解变动。现在我们仅考虑在最优解不变的情况下,c,允许有最大变化范围。 因为c变到c+△c(=12,…,m,m+1,…,m)时目标函数变为 z+A=∑(c1+△c)b+∑[c1+△c1-∑(c1+AC)yp cb+∑Ac1b+∑[λ,+(△c ) =m+1 与原式比较,Z得到改变量∑△cb;而检验数据得到改变量(△c-∑△can)。 另外可知,c,的改变在最后单纯形表中仅影响检验数行,约束条件系数的各行不受 影响。假若c,改变后,检验数改变,但仍满足最优判别条件,这时仅需对优值进行调解 例2.7某厂生 产甲、乙两种产品,这 表27 两种产品都需要在A、B、 设备ABC利润(元件) C三种不同的设备上加 加工时 工,每种产品在不同设 70 乙 30 备上加工所需要的时 有效工时 540450720
也可建立一个新规划，从头求解，但这样做显得太费时，对一些问题也是无必要的。其 次也不利于计算机的使用。 2.4.1 目标函数系数的灵敏度分析 设线性规划 maxZ = Cx ≥ = ⋅ x 0 Ax b s t 的最优解表示为: = + = − ∑ ∑ = + = + n j m j j n j m ij i ij i z z x x b a x 1 0 1 λ 其中， ij j i m i i j j j i = c − z z =∑c b Z = c a = , , 1 λ 0 由上式显见，当目标系数c j 有改变量∆c j 时，对解 x j 无直接影响，但对目标函数Z 值及检验数λ j 有影响，如果λ j 变化比较大，将使得原判断优解的结论改变，导致继续 迭代，使优解变动。现在我们仅考虑在最优解不变的情况下，c j 允许有最大变化范围。 因为 变到c j c c ( j 1,2, , m, m 1, , n) j + ∆ j = " + " 时目标函数变为： j m i n j m m i ij j j i m i i i i i j n j m m i ij j j i i m i i i i c b c b c c a x z z c c b c c c c a x ∑ ∑ ∑ ∑ ∑ ∑ ∑ = + = = = = = = + = + ∆ + + ∆ − ∆ + ∆ = + ∆ + + ∆ − + ∆ 1 1 1 1 1 1 1 [ ( )] ( ) [ ( ) ] λ 与原式比较，Z0 得到改变量∑= ∆ m i i ci b 1 ；而检验数据得到改变量( ) 1 ∑= ∆ − ∆ m i ij j i c c a 。 另外可知，c 的改变在最后单纯形表中仅影响检验数行，约束条件系数的各行不受 影响。假若 改变后，检验数改变，但仍满足最优判别条件，这时仅需对优值进行调解。 j j c 例 2.7 某厂生 产甲、乙两种产品，这 两种产品都需要在 A、B、 C 三种不同的设备上加 工，每种产品在不同设 备上加工所需要的时 表 2-7 A B C 利润（元/件） 甲 3 5 9 70 乙 9 5 3 30 有效工时 540 450 720 产 品 数 时 工 加 备 设
