线性规划对偶理论与方法

《线性规划对偶理论与方法》由会员分享，可在线阅读，更多相关《线性规划对偶理论与方法（46页珍藏版）》请在装配图网上搜索。

1、湖州师范学院商学院 1 2021年 4月 11日 7时 56分 运筹学 （ operations research, OR） 第四讲 线性规划对偶理论与方法 商学院电子商务系 湖州师范学院商学院 2 2021年 4月 11日 7时 56分 第四讲 线性规划对偶理论与方法 一 . 对偶问题的提出 二 . 写对偶问题 三 . 对偶问题的性质 四 . 对偶单纯形法 湖州师范学院商学院 3 2021年 4月 11日 7时 56分 一、对偶问题的提出 第四讲 线性规划对偶理论与方法 什么是对偶？ 对同一事物（或问题），从不同的角度（或立场） 提出相对的两种不同的表述。 有诗为证： 窗含西岭千秋雪，门泊东

2、吴万里船。 有志者，事竟成，破釜沉舟，百二秦关终属楚； 苦心人，天不负，卧薪尝胆，三千越甲可吞吴。 湖州师范学院商学院 4 2021年 4月 11日 7时 56分 第四讲 线性规划对偶理论与方法 一、对偶问题的提出 对例 1从对偶的角度进行表述。 假设该工厂的决策者决定不生产产品甲、乙， 而将其所有资源出租或外售。这时工厂的决策者就 要考虑给每种资源如何定价的问题。设用 y1， y2， y3分别表示出让单位原材料和出租生产设备 A， B生 产 台时的租金的收益。在做决策时，做如下比较： 若生产一件产品甲，可获利 3元，那么生产每件产 品甲的设备台时和原材料出租或出让的所有收入应 不低于生产一件

3、产品甲的利润，这就有 y1+4y23. 湖州师范学院商学院 5 2021年 4月 11日 7时 56分 第四讲 线性规划对偶理论与方法 一、对偶问题的提出 对例 1从对偶的角度进行表述。 同理将生产每件产品乙的设备台时和原材料出 租或出让的所有收入应不低于生产一件产品乙的 利润 ， 这就有： 2y1+4y33 把工厂所有设备台时和资源都出租或出让 ， 其收入为： w = 8y1+16y2+12y3 湖州师范学院商学院 6 2021年 4月 11日 7时 56分 第四讲 线性规划对偶理论与方法 一、对偶问题的提出 例 1的对偶数学模型为： min w=8y1+16y2+12y3 y1+4y2 3

4、 2y1 +4y34 yi0， i=1,2,3 湖州师范学院商学院 7 2021年 4月 11日 7时 56分 第四讲 线性规划对偶理论与方法 一、对偶问题的提出 从数学逻辑上提出对偶问题 由前可知检验数的表达式是： CNCBB-1N与 CBB-1 即：包含所有变量在内的检验数为： CCBB-1A 将 Y= CBB-1两边右乘 b， 得到 : Yb= CBB-1b = z 因 Y的上界为无限大 ， 所以只存在最小值 。 令： Y= CBB-1，称 Y为单纯形乘子，由最优解的判 定条件可得： Y0 即： CCBB-1A=CYA0 YAC 湖州师范学院商学院 8 2021年 4月 11日 7时 5

5、6分 第四讲 线性规划对偶理论与方法 一、对偶问题的提出 从数学逻辑上提出对偶问题 从这里可以得到另一个线性规划问题 : min w=Yb YAC Y0 称为原线性规划问题 max z=CX AXb， X0 的对偶规划问题 。 湖州师范学院商学院 9 2021年 4月 11日 7时 56分 第四讲 线性规划对偶理论与方法 二、写对偶问题 标准型对偶关系 0 21 1 2 1 21 11211 2211 n m n mnmm n nn x,x,x b b x x x aaa aaa xcxcxczm a x 0, , m i n 21 21 21 11211 21 m2211 n n mnmm

6、n m m yyy ccc aaa aaa yyy bybyby 对偶 湖州师范学院商学院 10 2021年 4月 11日 7时 56分 第四讲 线性规划对偶理论与方法 二、写对偶问题 规范形式原问题与对偶问题变换规则 观察分析上述规范形式下线性规划的原问题及其对偶问题 的模型形式，可发现，按如下规则，可从线性规划原问题得到 其对偶问题： （ 3）对偶问题约束为 型，有 ? 行； （ 1）目标函数由 max型变为 min型； , 1, 2 , ,i imy （ 2）对应原问题，每个约束行有一个对偶变量 ; （ 4）原问题的价值系数 C 变换为对偶问题的右端项； （ 5）原问题的右端项 b 变换

7、为对偶问题的价值系数； （ 6）原问题的系数矩阵 A转置后成为对偶问题的系数矩阵。 根据上述变换规则，可直接写出规范形式下线性规划问题对偶问题。 湖州师范学院商学院 11 2021年 4月 11日 7时 56分 第四讲 线性规划对偶理论与方法 二、写对偶问题 标准型原问题与对偶问题的关系 m i nm a x zm i n m 21 21 2222212 1112111 21 n mmnmmm n n n i j ccc baaay baaay baaay zaxxxx y x 对偶关系 原关系 湖州师范学院商学院 12 2021年 4月 11日 7时 56分 第四讲 线性规划对偶理论与方法

8、二、写对偶问题 标准型原问题与对偶问题的关系 例 2 根据下表写出原问题与对偶问题的表达式 x y x1 x2 b y1 1 2 8 y2 4 0 16 y3 0 4 12 c 3 4 湖州师范学院商学院 13 2021年 4月 11日 7时 56分 第四讲 线性规划对偶理论与方法 二、写对偶问题 标准型原问题与对偶问题的关系 0, 124 164 82 43m a x 21 2 1 21 21 xx x x xx xxz 原问题 （ LP） 对偶问题 (DP) 对偶 0, 342 24 12168m in 321 31 21 321 yyy yy yy yyy 湖州师范学院商学院 14 20

9、21年 4月 11日 7时 56分 第四讲 线性规划对偶理论与方法 二、写对偶问题 练习题 练习 1 、写出下列线性规划问题的对偶问题 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 m a x 3 4 6 4 4 2 3 3 5 3 5 6 4 5 0 z x x x x x x x x x x x x x x x x ， ， ， 湖州师范学院商学院 15 2021年 4月 11日 7时 56分 第四讲 线性规划对偶理论与方法 二、写对偶问题 非标准型对偶关系 原问题的约束条件中含有等式约束条件时，按以下步骤处理： njx mibxa xcz j n j ijij n j j

10、j ,2,1,0 ,2,1, m a x 1 1 设等式约束条件的线性规划问题为： 第一步：先将等式约束条件分解为两个不等式约束条件 n j ijij n j ijij n j jj mibxa mibxa xcz 1 1 1 ,2,1 ,2,1 m a x n j ijij mibxa 1 ,2,1 湖州师范学院商学院 16 2021年 4月 11日 7时 56分 第四讲 线性规划对偶理论与方法 二、写对偶问题 非标准型对偶关系 第二步：按对称形式变换关系可写出它的对偶问题 设 yi ， yi 是对应上式的对偶变量， i=1,2, ， m m,i,y,y n,j,cyaya ybybm i

11、n i i m i j m i iij iij m i m i ii ii 210 21 1 1 1 1 湖州师范学院商学院 17 2021年 4月 11日 7时 56分 第四讲 线性规划对偶理论与方法 二、写对偶问题 非标准型对偶关系 将上述规划问题的各式整理后得到： m i jiiij m i iii njcyya yyb 1 1 ,2,1, m in 0, iiiii yyyyy令 miy njcya yb i m i jiij m i ii ,.2.1 ,2,1, m i n 1 1 ，为无约束 湖州师范学院商学院 18 2021年 4月 11日 7时 56分 第四讲 线性规划对偶理论

12、与方法 二、写对偶问题 线性规划的原问题与对偶问题的关系可表示为： R H S R H S 0 0 0 0 m n 0 0 n m i nzm a x 约束条件的目标函数变量系数 目标函数变量的系数约束条件 量 变 无约束 个个 件 条 束 约 件 条 束 约个 无约束 个 量 变 目标函数目标函数 对偶问题原问题 m 湖州师范学院商学院 19 2021年 4月 11日 7时 56分 第四讲 线性规划对偶理论与方法 二、写对偶问题 例题 写出下列线性规划问题的对偶问题 无符号约束4321 432 431 4321 4321 ,0,0, 43 523 322 523m i n xxxx xxx

13、xxx xxxx xxxx 0,0y 52 132 22 33 453m a x 321 321 321 31 21 321 yy yyy yyy yy yy yyyz ，无约束 湖州师范学院商学院 20 2021年 4月 11日 7时 56分 第四讲 线性规划对偶理论与方法 二、写对偶问题 练习题 1 xxxz 321 34m a x 无约束xxx xxx xxx xxx 321 321 321 321 ,0,0 4 163 2532 湖州师范学院商学院 21 2021年 4月 11日 7时 56分 第四讲 线性规划对偶理论与方法 练习题 2 0,0, 1482 1056 18827 945

14、m in 4321 321 42 4321 4321 xxxx xxx xx xxxx xxxxZ 无约束 1 2 3 13 1 2 3 13 12 m a x 18 10 14 72 2 6 8 8 5 w y y y yy y y y yy yy = y10， y20， 1 5 4 9 y3无约束 二、写对偶问题 湖州师范学院商学院 22 2021年 4月 11日 7时 56分 第四讲 线性规划对偶理论与方法 三、对偶问题的性质 线性规划对偶问题的基本性质 下面 介绍 对偶基本性质时，一般假定是如下规范对偶关系。 设原问题是（记为 LP）： 0 m a x X bAX CXZ 对偶问题是

15、（ 记为 DP） ： 0 m in Y CYA Ybw 这里 A是 m n矩阵 X是 n 1列向量 ， Y是 1 m行向量 。 假设 Xs 与 Ys分别是 （ LP） 与 （ DP） 的松驰变量 。 湖州师范学院商学院 23 2021年 4月 11日 7时 56分 第四讲 线性规划对偶理论与方法 三、对偶问题的性质 【性质 1】 对称性 对偶问题的对偶是原问题。 【 证 】 设原问题是 0,m a x XbAXCXZ 0,m in YCYAYbw 它与下列线性规划问题是等价的： 0,)m a x ( YCYAYbw 再写出它的对偶问题： 0,)m i n ( XbAXCXw 它与下列线性规划问

16、题是等价的 0,m a x XbAXCXZ 即是原问题。 可知，它的对偶问题是 湖州师范学院商学院 24 2021年 4月 11日 7时 56分 第四讲 线性规划对偶理论与方法 三、对偶问题的性质 【性质 2】 弱对偶性 设 X、 Y 分别为 LP(max) 与 DP(min)的可行解，则 bYCX 00 【 证 】 因为 X 、 Y 是可行解，故有 AX b, X 0 及 Y A C， Y 0, 将不等式 AX b 两边左乘 Y ，得 Y0AX Y0b 再将不等式 Y A C两边右乘 X ， 得 C X Y AX 故 C X Y AXY b 这一性质说明了两个线性规划互为对偶时 ， 求最大值

17、 的线性规划的任意目标值都不会大于求最小值的线性规划 的任一目标值 ， 不能理解为原问题的目标值不超过对偶 问题的目标值 。 湖州师范学院商学院 25 2021年 4月 11日 7时 56分 第四讲 线性规划对偶理论与方法 三、对偶问题的性质 【性质 3】 无界性 若原问题（对偶问题）有无 界解，则其对偶问题（原问题）无可行解。 证：假定原问题有无界解，对偶问题有可行解 Y ， Y b 。原问题有无界解，即存在 C X ，根据 若对偶性有， Y b C X ，显然矛盾，故命题成 立。 可理解为：在互为对偶的两个问题中 ， 若一个问题可行且具有 无界解 ， 则另一个问题无可行解 。 注意 ： （

18、 1） 这个定理的逆定理不成立，即若一个问题无可行 解，另一问题不一定有无界解，也可能无可行解； （ 2）若原问题可行且另一个问题不可行，则原问题具有无 界解。 湖州师范学院商学院 26 2021年 4月 11日 7时 56分 第四讲 线性规划对偶理论与方法 三、对偶问题的性质 【性质 4】最优性定理 设 X 、 Y 分别是 （ LP） 与 （ DP） 的可行解，则当 C X = Y b 时， X、 Y 是 （ LP） 与 （ DP） 的最优解 。 【 证 】 若 C X0= Y0b ， 由性质 2， 对偶问题的所有可 行解 Y 都存在 Yb CX。 因为 C X0= Y0b ， 所以 Y b

19、 Y0b ， 可见 Y0是使目标函数取值最小的可行解 ， 因而 Y0是最优解 。 同理可证 ， X0是最优解 。 湖州师范学院商学院 27 2021年 4月 11日 7时 56分 第四讲 线性规划对偶理论与方法 三、对偶问题的性质 【性质 5】 弱对偶性 若互为对偶的两个问题其中一个 有最优解，则另一个也有最优解，且最优值相同。 【 证 】 设 （ LP） 有最优解 X0,那么对于最优基 B必有 C-CBB-1A 0 与 CBB-1 0， 即有 Y A C与 Y 0， 这里 Y = CBB-1 ， 从而 Y 是可行解 ， 对目标函数有 bYbBCXCCX BBB 010 由性质 4知 Y 是最

20、优解 。 由性质 5 还可推出 另一结论 ：若 （ LP） 与 （ DP） 都有可行解 ， 则两者都有最优解 ， 若一个问题无最优解 ， 则另一问题也无最 优解 。 湖州师范学院商学院 28 2021年 4月 11日 7时 56分 第四讲 线性规划对偶理论与方法 三、对偶问题的性质 【性质 6】互补松弛定理 设 X0、 Y0分别为 （ LP） 与 （ DP） 的可行解， XS和 YS分别是 （ LP） 与 （ DP） 的松弛变量， 则当且仅当 X0 和 Y0 是最优解 时，有 YSX0=0和 Y0XS=0。 【 证 】 设 X 和 Y 是最优解 ,由性质 4 ， C X0= Y0b， 由于 X

21、S和 YS 是松弛变量 ， 则有 A X0 XS b Y0A YS=C 将第一式左乘 Y0， 第二式右乘 X0得 : Y0A X0 Y0XS Y0b Y0A X0 YS X0=C X0 湖州师范学院商学院 29 2021年 4月 11日 7时 56分 第四讲 线性规划对偶理论与方法 三、对偶问题的性质 【性质 6】互补松弛定理 : YSX0=0和 Y0XS=0 显然有 : Y0XS= YS X0 又因为 Y 、 Xs、 Ys、 X 0， 所以有 : Y XS=0和 YS X =0 反之 ， 当 Y XS=0和 YS X =0时 ， 有 : Y A X Y b Y A X =C X 显然有 Y0

22、b=C X ,由性质 4知 :Y 与 X 是 （ LP） 与 （ DP） 的最优解 。 思考：性质六有何作用？ 湖州师范学院商学院 30 2021年 4月 11日 7时 56分 第四讲 线性规划对偶理论与方法 三、对偶问题的性质 性质 6告诉我们已知一个问题的最优解时求另一个问题的最优解 的方法 ， 即已知 Y*求 X*或已知 X*求 Y*。 Y * XS=0和 YS X * =0 两式称为互补松弛条件 。 将互补松弛条件写成下式 * 1 * 1 0 0 i j m iS i n Sj j yx yx 由于变量都非负 ， 要使求和式等于零 ， 则必定每一分量为零 ， 因而有下列关系： (1)当

23、 yi*0时 ， ,反之当 时 yi*=0； 0iSx 0iSx *( 2 ) 0 0 , 0 0 jjS j j Sy x x y 时 反 之 当 时 湖州师范学院商学院 31 2021年 4月 11日 7时 56分 第四讲 线性规划对偶理论与方法 【 例 】 已知线性规划 3,2,1,0 1622 102 43m a x 321 321 321 jx xxx xxx xxxz j 的最优解是： 求对偶问题的最优解 。 TX )0,2,6( 【 解 】 对偶问题是 0, 1 422 32 1610m i n 21 21 21 21 21 yy yy yy yy yyw 因为 X10， X20

24、， 所以对偶问题的第 一 、 二个约束的松弛变量等于零 ， 即 422 32 21 21 yy yy 解此线性方程组得 y1=1,y2=1,从而对偶问题的最优解为 Y= （ 1， 1） ， 最优值 w=26。 湖州师范学院商学院 32 2021年 4月 11日 7时 56分 第四讲 线性规划对偶理论与方法 三、对偶问题的性质 练习题 1 例： 已知线性规划问题 min w=2x1+3x2+5x3+2x4+3x5 x1+x2+2x3+x4+3x54 2x1-x2+3x3+x4+x53 xj0， j=1， 2， ， 5 已知其对偶问题的最优解为 y1*=4/5， y2*=3/5； z=5。 试用对

25、偶理论找出原问题的最优解 。 湖州师范学院商学院 33 2021年 4月 11日 7时 56分 第四讲 线性规划对偶理论与方法 三、对偶问题的性质 练习题 2 例 : 已知线性规划问题 ( I ) * 1 1 m a x 1 , 2 , , 0 , 1 , 2 , , n jj j n ij j i j j cxz a x b i m x j n 与 ( I I ) * 1 1 m a x 1 , 2 , , 0 , 1 , 2 , , n jj j n ij j i i j j cxz a x b k i m x j n 若 ),( *2*1 yyy m 为线性规划问题 ( I ) 对偶问题

26、的最优解， 在线性规划问题 ( I I ) 中 ik 为某已知常数，求证： * * * 1 m i i i k yzz 湖州师范学院商学院 34 2021年 4月 11日 7时 56分 第四讲 线性规划对偶理论与方法 三、对偶问题的性质 【 性质 7】 互补对偶性 LP(max)的检验数的相反 数对应于 DP(min)的一组基本解 . 其中第 j个决策变量 xj的检验数的相反数对应于 （ DP） 中第 j个松弛变量 的解 ， 第 i个松弛变 量 的检验数的相反数对应于第 i个对偶变量 yi的解 。 反之 ， （ DP） 的检验数 （ 注意：不乘负 号 ） 对应于 （ LP） 的一组基本解 。

27、互补的两个基解所对应的目标值相等 。 jSy iSx 湖州师范学院商学院 35 2021年 4月 11日 7时 56分 第四讲 线性规划对偶理论与方法 三、对偶问题的性质 【 性质 7】 互补对偶性 设原问题是 max z=CX; AX+XS=b; X,XS0 它的对偶问题是 min w=Yb; YA YS=C; Y,YS0 则原问题单纯形表的检验数行对应其对偶问题的一 个基解 ， 其对应关系如表 。 YYY BCNBCC XXX SS BBN SNB 21 110 YS1是对应原问题中基变量 XB 的剩余变量， YS2是对应原问题中非基变量 XN的剩余变量。 湖州师范学院商学院 36 202

28、1年 4月 11日 7时 56分 第四讲 线性规划对偶理论与方法 证 : 设 B是原问题的一个可行基，于是 A=(B,N)；原 问题可改写为： max z=CBXB+CNXN BXB+NXN+XS=b XB， XN， XS0 相应地对偶问题可表示为： min w=Yb YB YS1=CB YN YS2=CN Y， YS1,YS20 这里 YS=(YS1， YS2)。 当求得原问题的一个解： XB=B-1b,其相应的检验数为 CN CBB-1N 与 CBB-1 现分析这些检验数与对偶问题的解之间的关系：令 Y=CBB-1,将 它代入得： YS1=0, YS2=CN CBB-1N。 湖州师范学院商

29、学院 37 2021年 4月 11日 7时 56分 第四讲 线性规划对偶理论与方法 【 练习题 】 线性规划 0, 44 22 26m a x 321 31 321 321 xxx xx xxx xxxz （ 1） 用单纯形法求最优解； （ 2） 写出每步迭代对应对偶问题的基本解； （ 3） 从最优表中写出对偶问题的最优解； 湖州师范学院商学院 38 2021年 4月 11日 7时 56分 第四讲 线性规划对偶理论与方法 对偶问题的经济解释 -影子价格 * * 11 nm j j i i ji c x b ywz * * i i y b z 在原问题中的 ib 是约束条件右端项代表 i 种资源

30、的拥有量。 对偶问题最优解 y i* 的意义代表在资源最优利用条件下，对单 位第 i 种资源的估价。 这种估价不是资源的市场价格而是根据资源在生产中作出的 贡献而作的估价，为了起见，称为影子价格 （ s hadow pri ce ） 。 湖州师范学院商学院 39 2021年 4月 11日 7时 56分 第四讲 线性规划对偶理论与方法 对偶问题的经济解释 -影子价格 （ 1 ) 资源的市场价格是已知数，相对比较稳定，而它的影子 价格则有赖于资源的利用情况，是未知数。由于企业生产任 务、产品结构等情况发生变化，资源的影子价格也随之改变。 （ 2 ) 影子价格是一种边际价格 y b z i i *

31、* 这说明 y i* 的值相 当于在资源得到最优利用的生产条件下， ib 每增加一个单位 时目标函数 z 的增量。 （ 3 ) 资源的影子价格实际上又是一种机会成本。市场价格高 于影子价格时，卖出资源，市场价格低于影子价格时就全买 进资源。 湖州师范学院商学院 40 2021年 4月 11日 7时 56分 第四讲 线性规划对偶理论与方法 对偶问题的经济解释 -影子价格 （ 4) 根据互补松 弛 性质，某种资源未充分利用时，该种资源的影子价格为 0 ， 即某种资源的影子价格不为 0 时，该种资源在生产中已耗费完毕。 （ 5) 从影子价格的含义上考察单纯形表的计算 yac j m i ijjj 1

32、 式中， jc 代表第 j 种产品的产值， ya j m i ij 1 是生产该种产品所消耗的各项资 源的影子价格的总和，即产品的隐含成本。 当产品产值大于隐含成本时，生产该项产品有利，可在计划中安排，否则不在 计划中安排，这就是单纯形表中多个检验数的经济意义。 （ 6) 一般来说，线性规划问题求解是确定资源的最优分配方案，而对于对偶问 题的求解是确定对资源的恰当估价，这种估价直接涉及到资源的最有效利用。 湖州师范学院商学院 41 2021年 4月 11日 7时 56分 第四讲 线性规划对偶理论与方法 四、对偶单纯法 对偶单纯形法的计算步骤如下： (1) 检查 b列的数字时，若至少还有一个负分

33、量，检验数保 持非正，那么进行以下计算。 (2) 确定换出变量。按 min (B-1b)i (B-1b)i 0 (B-1b)l对应 的基变量 xi为换出变量 (3) 确定换入变量。在单纯形表中检查 xl所在行的各系数 lj(j=1,2, ， n)。若所有 lj0 ，则无可行解，停止 计算。若存 在 lj 0 (j=1,2, ， n), 计算 (4) 以 lk为主元素，按原单纯形法在表中进行迭代运算， 得到新的计算表。 重复步骤 (1) (4)。 lk kklj lj jj j a zca a zc 0m i n 湖州师范学院商学院 42 2021年 4月 11日 7时 56分 第四讲 线性规划

34、对偶理论与方法 四、对偶单纯法 例 用对偶单纯形法求解 min w=2x1+3x2+4x3 x1+2x2+x33 2x1x2+3x34 x1， x2， x30 解：先将此问题化成下列形式，以便得到对偶问题的初始可 行基 ： max z= 2x1 3x2 4x3 x1 2x2 x3+x4 = 3 2x1+x2 3x3 +x5 = 4 xj0， j=1,2,5 湖州师范学院商学院 43 2021年 4月 11日 7时 56分 x 5 x 4 x 3 x 2 x 1 B 1b XB CB 0 0 -4 -3 -2 c j j X4 x5 0 0 -3 -4 -1 -2 -2 1 -1 -3 1 0

35、0 1 -2 -3 -4 0 0 B 1b XB CB j x 1 x 2 x 3 x 4 x 5 X4 x1 0 -2 0 -5/2 1/2 1 -1/2 -1 1 -1/2 3/2 0 -1/2 2 -4 -1 0 -1 0 B 1b XB CB j x 1 x 2 x 3 x 4 x 5 X2 x1 -3 -2 1 0 7/5 -1/5 -2/5 11/5 0 1 -1/5 -2/5 1/5 2/5 0 -9/5 -8/5 -1/5 0 第四讲 线性规划对偶理论与方法 例题 湖州师范学院商学院 44 2021年 4月 11日 7时 56分 第四讲 线性规划对偶理论与方法 上表中 ， b列

36、数字全为非负 ， 检验数全为非正 ， 故问题的最 优解为 X*=(11/5， 2/5， 0， 0， 0)T 例题 若对应两个约束条件的对偶变量分别为 y1和 y2， 则对偶问题的 最优解为 Y*=(y1*,y2*)=(8/5,1/5) 湖州师范学院商学院 45 2021年 4月 11日 7时 56分 第四讲 线性规划对偶理论与方法 从以上求解过程可以看到对偶单纯形法有以下优点： (1) 初始解可以是非可行解，当检验数都为负数时就可以进行基的变 换，这时不需要加入人工变量，因此可以简化计算。 (2) 当变量多于约束条件，对这样的线性规划问题用对偶单纯形法计 算可以减少计算工作量，因此对变量较少，

37、而约束条件很多的线性规 划问题，可先将它变换成对偶问题，然后用对偶单纯形法求解。 (3) 在灵敏度分析及求解整数规划的割平面法中，有时需要用对偶单 纯形法，这样可使问题的处理简化。对偶单纯形法的局限性主要是， 对大多数线性规划问题，很难找到一个初始可行基，因而这种方法在 求解线性规划问题时很少单独应用。 湖州师范学院商学院 46 2021年 4月 11日 7时 56分 第四讲 线性规划对偶理论与方法 四、对偶单纯法 练习题 试用对偶单纯形法求解下列线性规划问题： 0, 77 42 m i n)1( 21 21 21 21 xx xx xx xxz 0, 15625 2273 0542 423m i n)2( 4321 4321 4321 4321 4321 xxxx xxxx xxxx xxxx xxxxz