运筹学2对偶问题-课件.ppt

1、Chapter 2 对偶问题对偶问题Dual Problem1.线性规划的对偶模型线性规划的对偶模型 Dual Model of LP2.对偶性质对偶性质 Dual property 3.对偶单纯形法对偶单纯形法 Dual Simplex Method4.灵敏度分析灵敏度分析 Sensitivity Analysis运筹学运筹学Operations Research2.1线性规划的对偶模型线性规划的对偶模型 Dual model of LPCh2 Dual Problem Page 2 of 192023-1-24 在线性规划问题中，存在一个有趣的问题，即每一个线性规划问题都伴随有另一个线性规

2、划问题，称它为对偶线性规划问题。【例例2.1】某企业用四种资源生产三种产品，工艺系数、资源限量及价值系数如下表：产品资源A B C 资源限量9 8 6 5005 4 7 4508 3 2 3007 6 4 550每件产品利润100 80 70 建立总收益最大的数学模型。2.1线性规划的对偶模型线性规划的对偶模型 Dual model of LPCh2 Dual Problem Page 3 of 192023-1-24【解解】设x1，x2，x3分别为产品A，B，C的产量，则线性规划数学模型为：0,5504673002384507455006897080100max3,2132132132132

3、1321xxxxxxxxxxxxxxxxxxZ现在从另一个角度来考虑企业的决策问题。假如企业自己不生产产品，而将现有的资源转让或出租给其它企业，那么资源的转让价格是多少才合理？价格太高对方不愿意接受，价格太低本单位收益又太少。合理的价格应是对方用最少的资金购买本企业的全部资源，而本企业所获得的利润不应低于自己用于生产时所获得的利润。这一决策问题可用下列线性规划数学模型来表示。2.1线性规划的对偶模型线性规划的对偶模型 Dual model of LPCh2 Dual Problem Page 4 of 192023-1-24设y1，y2，y3及y4分别表示四种资源的单位增殖价格（售价成本增殖）

4、，总增殖最低可用min w=500y1+450y2+300y3+550y4 表示。企业生产一件产品A用了四种资源的数量分别是9，5，8和7个单位，利润是100,企业出售这些数量的资源所得的利润不能少于100，即10078594321yyyy同理，对产品B和C有70427680634843214321yyyyyyyy价格不可能小于零，即有yi0,i=1,4.从而企业的资源价格模型为2.1线性规划的对偶模型线性规划的对偶模型 Dual model of LPCh2 Dual Problem Page 5 of 192023-1-244,1,07042768063481007859550300450

5、500min4321432143214321iyyyyyyyyyyyyyyyyywi这是一个线性规划数学模型，称这一线性规划问题是前面生产计划问题的对偶线性规划问题或对偶问题。生产计划的线性规划问题称为原始线性规划问题或原问题。2.1线性规划的对偶模型线性规划的对偶模型 Dual model of LPCh2 Dual Problem Page 6 of 192023-1-24【例例2.2】某人根据医嘱，每天需补充A、B、C三种营养，A不少于80单位，B不少于150 单位，C不少于180单位。此人准备每天从六种食物中摄取这三种营养成分。已知六种食物每百克的营养成分含量及食物价格如下表，试建立此

6、人在满足健康需要的基础上花费最少的数学模型。营养成分 一 二 三 四 五 六需要量A1325144081180B24930251215150C1872134100180食物单价（元/100g）0.50.40.80.90.30.2 含量 食物2.1线性规划的对偶模型线性规划的对偶模型 Dual model of LPCh2 Dual Problem Page 7 of 192023-1-24【解解】设xj为每天第j种食物的用量，数学模型为01801034217181501512253092480118401425132.03.09.08.04.05.0min6543215432165432165

7、4321654321xxxxxxxxxxxxxxxxxxxxxxxxxxxxxZ、现有一制药厂要生产一种包含A、B、C三种营养成分的合成药，如何制定价格，使得此药既要畅销又要产值最大。设yi（i=1，2，3）为第i种营养成分的单价，则 2.1线性规划的对偶模型线性规划的对偶模型 Dual model of LPCh2 Dual Problem Page 8 of 192023-1-2402.015113.0101289.03425408.02130144.079255.018241318015080max32121321321321321321321yyyyyyyyyyyyyyyyyyyyyy

8、yw、影子价格影子价格(Shadow price):上面两个线性规划有着重要的经济含义。原始线性规划问题考虑的是充分利用现有资源，以产品的数量和单位产品的收益来决定企业的总收益，没有考虑到资源的价格，但实际在构成产品的收益中，不同的资源对收益的贡献也不同，它是企业生产过程中一种隐含的潜在价值，经济学中称为影子价格影子价格，即对偶问题中的决策变量yi的值。2.1线性规划的对偶模型线性规划的对偶模型 Dual model of LPCh2 Dual Problem Page 9 of 192023-1-24 由后面的对偶性质可知：原问题和对偶问题的最优值相等，故有miybZybYbbBCXCZii

9、miiiBBB,111即yi是第i种资源的变化率，说明当其它资源供应量bk(ki)不变时，bi增加一个单位时目标值Z增加yi个单位。2.1线性规划的对偶模型线性规划的对偶模型 Dual model of LPCh2 Dual Problem Page 10 of 192023-1-24例如，第一种资源的影子价格为y1=2，第二种资源的影子价格为y2=2，即当第一种资源增加一个单位时，Z增加2个单位，当第二种资源增加一个单位时，Z增加2个单位。企业可利用影子价格调节生产规模。例如，目标函数Z表示利润（或产值），当第i种资源的影子价格大于零（或高于市场价格）时，表示有利可图，企业应购进该资源扩大生

10、产规模，当影子价格等于零（或低于市场价格），企业不能增加收益，这时应将资源卖掉或出让，缩小生产规模。应当注意，是在最优基B不变的条件下有上述经济含义，当某种资源增加或减少后，最优基B可能发生了变化，这时yi的值也随之变化。iibZy2.1线性规划的对偶模型线性规划的对偶模型 Dual model of LPCh2 Dual Problem Page 11 of 192023-1-24在例2.1中，原问题的最优解X（24.24，0，46.96）对偶问题的最优解Y（10.6，0.91，0，0）最优值z=w=5712.12分析分析：1.y1=10.6说明在现有的资源限量的条件下，增加一个单位第一种资

11、源可以给企业带来10.6元的利润；如果要出售该资源，其价格至少在成本价上加10.6元。2.y3=0说明增加第三种资源不会增加利润，因为第三种资源还有 没有用完。问题问题：1.第三、四种资源的售价是多少，是否不值钱？2.如果要增加利润，企业应增加哪几种资源，各增加多少后再进行调整？2.1线性规划的对偶模型线性规划的对偶模型 Dual model of LPCh2 Dual Problem Page 12 of 192023-1-24上面两种形式的线性规划称为对称形式。原问题和对偶问题是互为对偶的两个线性规划问题，已知一个问题就可写出另一个问题。对称形式对称形式的定义是：目标函数求极大值时，所有约

12、束条件 为号，变量非负；目标函数求极小值时，所有约束条件为号，变量非负。对称形式的线性规划的对偶问题亦是对称形式。以上是依据经济问题推导出对偶问题，还可以用代数方法推导出对偶问题。2.1线性规划的对偶模型线性规划的对偶模型 Dual model of LPCh2 Dual Problem Page 13 of 192023-1-24【例例2.3】写出下列线性规划的对偶问题0,15744325min321321321321xxxxxxxxxxxxZ【解解】这是一个对称形式的线性规划，设Y=（y1，y2），则有)3,2,5()57,4(571114),(414),(max212121212121y

13、yyyyyyyYAyyyyYbw，2.1线性规划的对偶模型线性规划的对偶模型 Dual model of LPCh2 Dual Problem Page 14 of 192023-1-24从而对偶问题为0,035275434max2121212121yyyyyyyyyyZ对偶变量yi也可写成xi的形式。2.1线性规划的对偶模型线性规划的对偶模型 Dual model of LPCh2 Dual Problem Page 15 of 192023-1-24【例例2.4】写出下列线性规划的对偶问题0,01038576534max2121212121xxxxxxxxxxZ【解解】这是一个对称形式的线

14、性规划，它的对偶问题求最小值，有三个变量且非负，有两个“”约束，即3,2,1,03324751086min321321321iyyyyyyyyyywi2.1线性规划的对偶模型线性规划的对偶模型 Dual model of LPCh2 Dual Problem Page 16 of 192023-1-24若给出的线性规划不是对称形式，可以先化成对称形式再写对偶问题。也可直接按表21中的对应关系写出非对称形式的对偶问题。将上述原问题与对偶问题的对应关系列于表21例如，原问题是求最小值，按表2-1有下列关系：1.第i个约束是“”约束时，第i个对偶变量yj0 2第i个约束是“=”约束时，第i个对偶变量

15、yi无约束；3当xj0时，第j个对偶约束为“”约束，当xj无约束 时，第j个对偶约束为“=”约束。2.1线性规划的对偶模型线性规划的对偶模型 Dual model of LPCh2 Dual Problem Page 17 of 192023-1-24 原问题（或对偶问题）对偶问题（或原问题）目标函数（max）目标函数系数（资源限量）约束条件系数矩阵A（AT）目标函数（min）资源限量（目标函数系数）约束条件系数矩阵ATA）变 量n个变量第j个变量0第j 个变量0第j个变量无约束约 束 n个约束第j个约束为第j 个约束为第j个约束为=约 束m个约束第i个约束第i个约束第i个约束为=变 量m个变

16、量第i个变量0第i个变量0第i个变量无约束 表212.1线性规划的对偶模型线性规划的对偶模型 Dual model of LPCh2 Dual Problem Page 18 of 192023-1-24【例例2.5】写出下列线性规划的对偶问题 0,0,1482105618827945min43213214243214321xxxxxxxxxxxxxxxxxZ无约束【解解】目标函数求最小值，应将表21的右边看作原问题，左边是对偶问题，原问题有3个约束4个变量，则对偶问题有3 个变量4个约束，对照表21的对应关系，对偶问题为：无约束321213132131321,0,09548586212714

17、1018maxyyyyyyyyyyyyyyyw2.1线性规划的对偶模型线性规划的对偶模型 Dual model of LPCh2 Dual Problem Page 19 of 192023-1-24本节以实例引出对偶问题;介绍了如何写对称与非对称问题的对偶问题;1.您应该会写任意线性规划的对偶问题；2.深刻领会影子价格的含义，学会用影子价格作经济活动分析。作业：教材P74 T2.3（1）（2）The End of Section 2.1对偶性质Exit返回首页Ch2 Dual Problem2.2对偶性质对偶性质 Dual Property Page 20 of 232023-1-24设原问

18、题是（记为LP）：0maxXbAXCXZ对偶问题是（记为DP）：0minYCYAYbw这里A是mn矩阵X是n1列向量，Y是1m行向量。假设Xs与Ys分别是（LP）与（DP）的松驰变量。【性质性质1】对称性 对偶问题的对偶是原问题。【证证】设原问题是0,maxXbAXCXZCh2 Dual Problem2.2对偶性质对偶性质 Dual Property Page 21 of 232023-1-240,minYCYAYbw它与下列线性规划问题是等价的：0,)max(YCYAYbw再写出它的对偶问题。0,minXbAXCXw它与下列线性规划问题是等价的0,maxXbAXCXZ即是原问题。由表21知

19、，它的对偶问题是Ch2 Dual Problem2.2对偶性质对偶性质 Dual Property Page 22 of 232023-1-24【性质【性质2】弱对偶性弱对偶性 设设X、Y分别为（分别为（LP）与（）与（DP）的）的可行解，则可行解，则 【证】因为【证】因为X、Y是可行解，故有是可行解，故有AXb,X0及及YAC，Y0,将不等式将不等式 AXb 两边左乘两边左乘YbYCX00得得YAXYb再将不等式再将不等式YAC两边右乘两边右乘X，故故 C XYAXYb这一性质说明了两个线性规划互为对偶时，求最大值的线性这一性质说明了两个线性规划互为对偶时，求最大值的线性规划的任意目标值都不

20、会大于求最小值的线性规划的任一目规划的任意目标值都不会大于求最小值的线性规划的任一目标值，不能理解为原问题的目标值不超过对偶问题的目标值。标值，不能理解为原问题的目标值不超过对偶问题的目标值。得得C XYAXCh2 Dual Problem2.2对偶性质对偶性质 Dual Property Page 23 of 232023-1-24由这个性质可得到下面几个结论：（1）（LP）的任一可行解的目标值是（DP）的最优值下界；（DP）的任一可行解的目标是（LP）的最优值的上界；（2）在互为对偶的两个问题中，若一个问题可行且具有无界解，则另一个问题无可行解；(3）若原问题可行且另一个问题不可行，则原问

21、题具有无界解。注意上述结论（2）及（3）的条件不能少。一个问题有可行解时，另一个问题可能有可行解（此时具有无界解）也可能无可行解。Ch2 Dual Problem2.2对偶性质对偶性质 Dual Property Page 24 of 232023-1-24例如：0,22212min21212121xxxxxxxxz无可行解，而对偶问题0,221122max21212121yyyyyyyyw有可行解，由结论（3）知必有无界解。Ch2 Dual Problem2.2对偶性质对偶性质 Dual Property Page 25 of 232023-1-24【性质【性质3】最优准则定理】最优准则定理

22、 设设X与与Y分别是（分别是（LP）与（）与（DP）的可行解，则当的可行解，则当X、Y是（是（LP）与（）与（DP）的最优解当且仅）的最优解当且仅当当C X=Yb.【证】若【证】若X、Y为最优解，为最优解，B为（为（LP）的最优基，则有）的最优基，则有Y=CBB1，并且，并且bYbBCCXB010当当C X=Yb时，由性质时，由性质1，对任意可行解，对任意可行解 有有YX及bYCXbYXC00即即Yb是（是（DP）中任一可行解的目标值的下界，）中任一可行解的目标值的下界，C X是是（LP）中任一可行解的目标值的上界，从而）中任一可行解的目标值的上界，从而X、Y是最优是最优解。解。Ch2 Dua

23、l Problem2.2对偶性质对偶性质 Dual Property Page 26 of 232023-1-24【性质【性质4】还可推出另一结论：若（还可推出另一结论：若（LP）与（）与（DP）都有可行）都有可行解，则两者都有最优解，若一个问题无最优解，则另一问题解，则两者都有最优解，若一个问题无最优解，则另一问题也无最优解。也无最优解。【证】设（【证】设（LP）有最优解）有最优解X，那么对于最优基，那么对于最优基B必有必有C CBB-1A0与与CBB-10，即有，即有YAC与与Y0，这里这里Y=CBB-1，从而，从而Y是可行解，对目标函数有是可行解，对目标函数有bYbBCXCCXBBB01

24、0由性质由性质3知知Y是最优解。是最优解。由性质由性质 4 还可推出另一结论：若（还可推出另一结论：若（LP）与（）与（DP）都有可行解，）都有可行解，则两者都有最优解，若一个问题无最优解，则另一问题也无则两者都有最优解，若一个问题无最优解，则另一问题也无最优解。最优解。Ch2 Dual Problem2.2对偶性质对偶性质 Dual Property Page 27 of 232023-1-24【性质【性质5】互补松弛定理】互补松弛定理 设设X、Y分别为（分别为（LP）与）与（DP）的可行解，）的可行解，XS和和YS是它的松弛变量的可行解，则是它的松弛变量的可行解，则X和和Y是最优解当且仅当

25、是最优解当且仅当YSX=0和和YXS=0【证】设【证】设X和和Y是最优解，由性质是最优解，由性质3，C X=Yb，由于由于XS和和YS是松弛变量，则有是松弛变量，则有A XXSbYAYS=C将第一式左乘将第一式左乘Y，第二式右乘，第二式右乘X得得YA XYXSYbYA XYS X=C XCh2 Dual Problem2.2对偶性质对偶性质 Dual Property Page 28 of 232023-1-24显然有 YXS=YS X又因为Y、Xs、Ys、X0，所以有YXS=0和YS X=0成立。反之，当YXS=0和YS X=0时，有YA XYbYA X=C X显然有Yb=C X,由性质3知

26、Y与X是（LP）与（DP）的最优解。证毕。Ch2 Dual Problem2.2对偶性质对偶性质 Dual Property Page 29 of 232023-1-24性质5告诉我们已知一个问题的最优解时求另一个问题的最优解的方法，即已知Y求X或已知X求Y。YXS=0和YS X=0两式称为互补松弛条件。将互补松弛条件写成下式001010mjjSmiSixyxyji由于变量都非负，要使求和式等于零，则必定每一分量为零，因而有下列关系：Ch2 Dual Problem2.2对偶性质对偶性质 Dual Property Page 30 of 232023-1-24（1）当yi0时，反之当 时yi=

27、0；0iSx0iSx00,00)2(00jjSjjSyxxy时反之当时注意：对于非对称形式，性质5的结论仍然有效。【例2.6】已知线性规划3,2,1,0162210243max321321321jxxxxxxxxxxzj的最优解是 ，求对偶问题的最优解。TX)0,2,6(Ch2 Dual Problem2.2对偶性质对偶性质 Dual Property Page 31 of 232023-1-243,2,1,0162210243max321321321jxxxxxxxxxxzj的最优解是 ，求对偶问题的最优解。TX)0,2,6(【解解】对偶问题是0,1422321610min212121212

28、1yyyyyyyyyyw因为X10，X20，所以对偶问题的第一、二个约束的松弛变量等于零，即422322121yyyy解此线性方程组得y1=1,y2=1,从而对偶问题的最优解为Y=（1，1），最优值w=26。Ch2 Dual Problem2.2对偶性质对偶性质 Dual Property Page 32 of 232023-1-24【例例2.7】已知线性规划 无约束321321321321,0,06422minxxxxxxxxxxxxz的对偶问题的最优解为Y=（0,-2），求原问题的最优解。【解解】对偶问题是021264max2121212121yyyyyyyyyyw无约束，由y20得 =0

29、，由 得x2=0，原问题的约束条件变为:12Sy2Sx643131xxxx解此方程组得原问题最优解：X=(-5,0,-1)T，minZ=-12。Ch2 Dual Problem2.2对偶性质对偶性质 Dual Property Page 33 of 232023-1-24【例例2.8】证明下列线性规划无最优解：3,2,1,0324min32131321jxxxxxxxxxZj【证证】容易看出X=（4，0，0）是一可行解，故问题可行。对偶问题0,0121134max212122121yyyyyyyyyw将三个约束的两端分别相加得 ，而第二个约束有y21，矛盾，故对偶问题无可行解，212y因而原问

30、题为无界解，即无最优解。Ch2 Dual Problem2.2对偶性质对偶性质 Dual Property Page 34 of 232023-1-24iSx【性质性质6】（LP）的检验数的相反数对应于（DP）的一组基本解.其中第j个决策变量xj的检验数的相反数对应于（DP）中第j个松弛变量 的解，第i个松弛变量 的检验数的相反数对应于第i个对偶变量yi的解。反之，（DP）的检验数（注意：不乘负号）对应于（LP）的一组基本解。证明略。jSyCh2 Dual Problem2.2对偶性质对偶性质 Dual Property Page 35 of 232023-1-24【例例2.9】线性规划0,4

31、42226max32131321321xxxxxxxxxxxz（1）用单纯形法求最优解；（2）写出每步迭代对应对偶问题的基本解；（3）从最优表中写出对偶问题的最优解；（4）用公式Y=CBB-1求对偶问题的最优解。【解解】（1）加入松弛变量x4、x5后，单纯形迭代如表22所示。Ch2 Dual Problem2.2对偶性质对偶性质 Dual Property Page 36 of 232023-1-24表22XBx1x2x3x4x5b(1)x4x52*1-1024100124j6-2100(2)x1x510-1/21/2*131/2-1/20113j01-5-30(3)x1x21001460-1

32、1246j00-11-2-2 Ch2 Dual Problem2.2对偶性质对偶性质 Dual Property Page 37 of 232023-1-24最优解X=（4，6，0），最优值Z=6426=12；（2）设对偶变量为y1、y2,松弛变量为y3、y4、y5,Y=（y1、y2、y3、y4、y5），由性质6得到对偶问题的基本解 （y1、y2、y3、y4、y5）=（4，5，1，2，3），即 表22（1）中=（6，2，1，0，0），则Y（1）=（0，0，-6，2，1）表22（2）中=（0，1，5，3，0），则Y（2）=（3，0，0，1，5）表22（3）中=（0，0，11，2，2），则Y（3）

33、=（2，2，0，0，11）Ch2 Dual Problem2.2对偶性质对偶性质 Dual Property Page 38 of 232023-1-24（1）因为表22（3）为最优解，故 Y（3）=（2，2，0，0，11）为对偶问题最优解；（1）表22（3）中的最优基 B-1 为表22（3）中x4，x 5两列的系数，即0211BCB=（6，2），因而21101B)2,2(2110)2,6(),(121BCyyYBCh2 Dual Problem2.2对偶性质对偶性质 Dual Property Page 39 of 232023-1-24本节您学了六个对偶性质；这些性质是研究原问题与对偶问题

34、解的对应关系；表23也许对您了解这些性质有帮助。表23一个问题max另一个问题min有最优解有最优解性质4无最优解无最优解无最优解性质4无界解（有可行解）无可行解性质2无可行解无界解（有可行解）应用已知最优解通过解方程求最优解性质5已知检验数检验数乘以1求得基本解性质6Ch2 Dual Problem2.2对偶性质对偶性质 Dual Property Page 40 of 232023-1-24试一试：判断下列结论是否正确，如果不正确，应该怎样改正？1任何线性规划都存在一个对应的对偶线性规划.2原问题第i个约束是“”约束，则对偶变量yi0.3互为对偶问题，或者同时都有最优解，或者同时都无最优解

35、.4对偶问题有可行解，则原问题也有可行解.5原问题有多重解，对偶问题也有多重解.6对偶问题有可行解，原问题无可行解，则对偶问题具有无界解.7原问题无最优解，则对偶问题无可行解.8若某种资源影子价格为零，则该资源一定有剩余.9对偶问题不可行，原问题可能无界解.10原问题与对偶问题都可行，则都有最优解.11原问题具有无界解，则对偶问题不可行.12对偶问题具有无界解，则原问题无最优解.13若X*、Y*是原问题与对偶问题的最优解，则X*=Y*.14在资源优化的线性规划问题中，若某一资源有剩余，则该资源影子价格为零.Ch2 Dual Problem2.2对偶性质对偶性质 Dual Property Pa

36、ge 41 of 232023-1-24作业：教材P75 T2.4、2.6、2.5The End of Section 2.2对偶单纯形法Exit2.3 对偶单纯形法对偶单纯形法The Dual Simplex Method Ch2 Dual Problem Page 42 of 92023-1-24设原问题是（记为LP）：0maxXbAXCXZ对偶问题是（记为DP）：0minYCYAYbw 根据对偶性质6，可以构造一个求线性规划的另一种方法，即对偶单纯形法。对偶单纯形法的计算步骤：对偶单纯形法的条件是：初始表中对偶问题可行，即极大化问题时j0，极小化问题时j0。2.3 对偶单纯形法对偶单纯形

37、法The Dual Simplex Method Ch2 Dual Problem Page 43 of 92023-1-24 （1）将线性规划的约束化为等式，求出一组基本解，因为对偶问题可行，即全部检验数j0（max）或j0（min）,当基本解可行时，则达到最优解；若基本解不可行，即有某个基变量的解bi0，则进行换基计算；（2）先确定出基变量。行对应的变量xl出基；lbbbiiii,0|min（3）再选进基变量。求最小比值0|minljljjjkaa（4）求新的基本解，用初等变换将主元素alk化为l,k列其它元素化为零，得到新的基本解，转到第一步重复运算。2.3 对偶单纯形法对偶单纯形法Th

38、e Dual Simplex Method Ch2 Dual Problem Page 44 of 92023-1-24【例例2.10】用对偶单纯形法求解0,43232432min321321321321xxxxxxxxxxxxz【解解】先将约束不等式化为等式，再两边同乘以（1），得到5,2,1,043232432min53214321321jxxxxxxxxxxxxzj用对偶单纯形法，迭代过程如下页或看演示(请启用宏)。2.3 对偶单纯形法对偶单纯形法The Dual Simplex Method Ch2 Dual Problem Page 45 of 92023-1-24表24XBbx1x

39、2x3x4x5x4-3-1-2-110 x5-4-21-301检验数检验数0-2-3-40011.3333x4-10-2.50.51-0.5x121-0.51.50-0.5检验数检验数40-4-10-11.62x20.401-0.2-0.40.2x12.2101.4-0.2-0.4检验数检验数5.600-1.8-1.6-0.2最优解：最优解：x2=0.4 x1=2.2Max z=-5.6比值比值比值比值2.3 对偶单纯形法对偶单纯形法The Dual Simplex Method Ch2 Dual Problem Page 46 of 92023-1-24 应当注意：（1）用对偶单纯形法求解线

40、性规划是一种求解方法，而不是去求对偶问题的最优解；（2）初始表中一定要满足对偶问题可行，也就是说检验数满足最优判别准则；（3）最小比值中 的绝对值是使得比值非负，在极小化问题时j0，分母aij0 这时必须取绝对值。在极大化问题中，j0分母aij0，总满足非负，这时绝对值符号不起作用，可以去掉。如在本例中将目标函数写成ijjaijja这里j0在求k时就可以不带绝对值符号。32134maxxxxz2.3 对偶单纯形法对偶单纯形法The Dual Simplex Method Ch2 Dual Problem Page 47 of 92023-1-24（4）对偶单纯形法与普通单纯形法的换基顺序不一样

41、，普通单纯形法是先确定进基变量后确定出基变量，对偶单纯形法是先确定出基变量后确定进基变量；（5）普通单纯形法的最小比值是其目的是保证下一个原问题的基本解可行，对偶单纯形法的最小比值是 0minikikiiaab其目的是保证下一个对偶问题的基本解可行；0|minljljjjaa（6）对偶单纯形法在确定出基变量时，若不遵循规则，任选一个小于零的bi对应的基变量出基，不影响计算结果，只是迭代次数可能不一样。0|miniilbbb2.3 对偶单纯形法对偶单纯形法The Dual Simplex Method Ch2 Dual Problem Page 48 of 92023-1-24【例【例2.12】

42、用对偶单纯形法求解】用对偶单纯形法求解4,2,1,0222237max42132121jxxxxxxxxxzj求解过程见演示求解过程见演示（链接到（链接到Excel文件，需启用宏）。文件，需启用宏）。2.3 对偶单纯形法对偶单纯形法The Dual Simplex Method Ch2 Dual Problem Page 49 of 92023-1-24例2.12可用性质6 及性质2来说明，表（2）的第2行对应于对偶问题的第2列（相差一个负号），检验数行对应于对偶问题的常数项（相差一个负号），比值 对应于对偶问题的比值 失效也说明 即对偶问题具有无界解，由性质2知原问题无可行解。LjjaLjj

43、ikiaab比值,ikiab2.3 对偶单纯形法对偶单纯形法The Dual Simplex Method Ch2 Dual Problem Page 50 of 92023-1-24本节利用对偶性质6：原问题的检验数与对偶问题的基本解的对应关系，介绍了一种特殊线性规划的求解方法对偶单纯形法。1.对偶单纯形法的应用条件；2.出基与进基的顺序；3.如何求最小比值；4.最优解、无可行解的判断。作业：教材P76 T2.7The End of Section 3灵敏度分析Exit2.4 灵敏度分析灵敏度分析Sensitivity Analysis Ch2 Dual Problem Page 51 of

44、 342023-1-24 线性规划的灵敏度分析也称为敏感性分析，它是研究和分析参数（cj，bi，aij）的波动对最优解的影响程度，主要研究下面两个方面：（1）参数在什么范围内变化时，原最优解或最优基不变；（2）当参数已经变化时，最优解或最优基有何变化。当模型的参数发生变化后，可以不必对线性规划问题重新求解，而用灵敏度分析方法直接在原线性规划取得的最优结果的基础上进行分析或求解，既可减少计算量，又可事先知道参数的变化范围，及时对原决策作出调整和修正。2.4.1价值系数价值系数cj的变化分析的变化分析 为使最优解不变，求cj的变化范围。2.4 灵敏度分析灵敏度分析Sensitivity Analy

45、sis Ch2 Dual Problem Page 52 of 342023-1-24 设线性规划 0maxXbAXCXz其中Amn，线性规划存在最优解，最优基的逆矩阵为),(),(21211miiiimB，检验数为 njPBccjBjj,2,1,1要使最优解不变，即当cj变化为 后，检验数仍然是小于等于零，即jjjccc01iBjjPBCc这时分cj是非基变量和基变量的系数两种情况讨论。2.4 灵敏度分析灵敏度分析Sensitivity Analysis Ch2 Dual Problem Page 53 of 342023-1-24一、cj是非基变量xj的系数0111jjjjBjjBjjjB

46、jjccPBCcPBCccPBCc即cj的增量 不超过cj的检验数的相反数时，最优解不变，否则最优解就要改变。jc所以 jjc2.4 灵敏度分析灵敏度分析Sensitivity Analysis Ch2 Dual Problem Page 54 of 342023-1-24 二、ci是基变量xi的系数因ciCB，所以每个检验数j中含有c i,当c i变化为c i 后j同时变化，这时令ic0),)(0,0,0,0()(2111111ijijmjjjijjBjjBjBjjBBjjBjjacaaacPBCPBCPBCcPBCCcPBCc,0ijjiijaca 时有当。时有当ijjiijaca 00m

47、in0max21ijijjjijijjjaaaa令2.4 灵敏度分析灵敏度分析Sensitivity Analysis Ch2 Dual Problem Page 55 of 342023-1-24要使得所有 ，则有0j21ic的变化区间。就可以求出及下限只要求出ic12【例例2.13】线性规划0,152024023max32132321321321xxxxxxxxxxxxxxZ（1）求最优解；（2）分别求c1,c2,c3的变化范围，使得最优解不变。2.4 灵敏度分析灵敏度分析Sensitivity Analysis Ch2 Dual Problem Page 56 of 342023-1-2

48、4【解解】（1）加入松弛变量x4,x5,x6，用单纯形法求解，最优表如表26所示。表26Cj113000bCBXBx1x2x3x4x5x60 x402011151x111001153x301100115j030012 最优解X=（5，0，15）;最优值Z=50。2.4 灵敏度分析灵敏度分析Sensitivity Analysis Ch2 Dual Problem Page 57 of 342023-1-24（2）x2为非基变量，x 1、x 3为基变量，则322cc2变化范围是：4,431)(2222ccc或对于c1：表26是x 1对应行的系数只有一个负数 ,有两个正数 126a则有及,1125

49、22aa21212min111,13max,max126622552221caaac1的变化范围是：3,030,1121111ccccc或2.4 灵敏度分析灵敏度分析Sensitivity Analysis Ch2 Dual Problem Page 58 of 342023-1-24对于c3：表26中x3对应行则有而，,0,11353632aaa212,13max,max3663221aac3无上界，即有c32，c3的变化范围是。,1133cc或2.4 灵敏度分析灵敏度分析Sensitivity Analysis Ch2 Dual Problem Page 59 of 342023-1-24

50、 对c3的变化范围，也可直接从表26推出，将c3=3写成 分别计算非基变量的检验数并令其小于等于零。333ccc5155332122031123,1,0(1PBCcccPBCcBB02111)3,1,0(1011)3,1,0(3363ccc2.4 灵敏度分析灵敏度分析Sensitivity Analysis Ch2 Dual Problem Page 60 of 342023-1-24得c32，同理，用此方法可求出c2和c1的变化区间。020333cc015，要使 、同时小于等于零，解不等式组262.4.2 资源限量bi变化分析为了使最优基B不变，求bi的变化范围。设br的增量为br，b的增量