线性规划对偶理论与灵敏分析运筹学.pptx

《线性规划对偶理论与灵敏分析运筹学.pptx》由会员分享，可在线阅读，更多相关《线性规划对偶理论与灵敏分析运筹学.pptx（83页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、2023/3/17第 1页例例2.12.1常山机械厂生产常山机械厂生产和和两种产品。生产中需使用两种产品。生产中需使用A A、B B、C C三种设备进行加三种设备进行加工，加工每件工，加工每件产品或产品或产品所需的设备机时数、利润值及每种设备可利用机产品所需的设备机时数、利润值及每种设备可利用机时数列于下表，请问：充分利用设备机台时，工厂应生产时数列于下表，请问：充分利用设备机台时，工厂应生产和和产品各多少件产品各多少件才能获得最大利润？试列出相应的线性规划数学模型。才能获得最大利润？试列出相应的线性规划数学模型。A AB BC C产品利润产品利润（元件）（元件）2 24 40 02 22 2

2、0 05 53 3设备可用机时设备可用机时数（工时）数（工时）1212161615151 1 对偶问题的提出对偶问题的提出第2页/共83页第1页/共83页2023/3/17第 2页解：设解：设、产品的生产数量分别为产品的生产数量分别为x1和和x2，建立问题数学模型如下：，建立问题数学模型如下：max z=2x1+3x2 2x1+2x212 4x1 16 5x2 15 xj0，j=1，2现假设有另一家四海机器厂，为了扩大生产想租借常山机器厂拥有的设备资源，问常山现假设有另一家四海机器厂，为了扩大生产想租借常山机器厂拥有的设备资源，问常山厂分别以每小时什么样的价格才愿意出租自己的设备呢？厂分别以每

3、小时什么样的价格才愿意出租自己的设备呢？第3页/共83页第2页/共83页2023/3/17第 3页设设A、B、C设备的机时单价分别为设备的机时单价分别为y1、y2、y3，新的线性规划数学模型为，新的线性规划数学模型为min w=12y1+16y2+15y32y1+4y2 22y1 +5y33yj0，j=1，2，3A（y1）B（y2）C（y3）产品利润产品利润（元件）（元件）（x1）2402（x2）2053设备可用机时设备可用机时数（工时）数（工时）121615第4页/共83页第3页/共83页2023/3/17第 4页23x1 x2 原问题原问题12y1 221216y2 401615y3051

4、5对偶问题对偶问题23第5页/共83页第4页/共83页2023/3/17第 5页X1 ,X2,Xnxjyi原关系原关系对偶关系对偶关系 Min wMax ZMax Z=Min w原问题与对偶问题的形式关系原问题与对偶问题的形式关系第6页/共83页第5页/共83页2023/3/17第 6页原始问题max z=CXs.t.AXbX 0对偶问题对偶问题min w=bTYs.t.ATYCT Y 0maxbACCTATbTminmnmn第7页/共83页第6页/共83页2023/3/17第 7页2 2 原问题与对偶问题原问题与对偶问题 max z=c1x1+c2x2+cnxns.t.a11x1+a12x2

5、+a1nxn b1 a21x1+a22x2+a2nxn b2 (1)am1x1+am2x2+amnxn bm xj 0（j=1,2,n）min w=b1 y1+b2 y2+bm yms.t.a11y1+a21 y2+am1ym c1 a12y1+a22y2 +am2 ym c2 (2)a1ny1+a2ny2+amnym cn yi 0（i=1,2,m）设原设原 LP LP 问题为问题为则称下列则称下列 LP LP 问题问题为其对偶问题，其中为其对偶问题，其中 yi 0（i=1,2,m）称为对偶变量，）称为对偶变量，并称（并称（1）、（）、（2）为一对对称型对偶问题）为一对对称型对偶问题第8页/

6、共83页第7页/共83页2023/3/17第 8页例例2.2写出下列线性规划问题的对偶问题写出下列线性规划问题的对偶问题min w=12x1+8x2+16x3+12x4 s.t.2x1+x2+4x3 2 2x1+2x2 +4x4 3 x1，x2，x3，x4 0min w=12x1+8x2+16x3+12x4 s.t.2x1+x2+4x3 2 y1 2x1+2x2 +4x4 3 y2 x1，x2，x3，x4 0解：该问题的对偶问题：解：该问题的对偶问题：max z=2y1+3y2 s.t.2y1+2y2 12 y1+2y2 8 4 y1 16 4y2 12 y1，y2 0第9页/共83页第8页/

7、共83页2023/3/17第 9页例例2.3 写出下列线性规划问题的对偶问题写出下列线性规划问题的对偶问题max z=10 x1+x2 +2x3s.t.X1+x2+2x3 10 y1 4x1+2x2 -x3 20 y2 x1，x2，x3 0解：该问题的对偶问题：解：该问题的对偶问题：min w=10 y1+20 y2 s.t.y1+4y2 10 y1+2y2 1 2 y1-y2 2 y1，y2 0第10页/共83页第9页/共83页2023/3/17第 10页例例2.4 写出下列线性规划问题的对偶问题写出下列线性规划问题的对偶问题 min w=x1+2x2+3x3s.t.2x1+3x2+5x3

8、2 3x1+x2+7x3 3 x1，x2，x3 0解：用（解：用（-1）乘以第二个约束方程两边）乘以第二个约束方程两边 min w=x1+2x2+3x3s.t.2x1+3x2+5x3 2 y1 -3x1-x2-7x3 -3 y2 x1，x2，x3 0该问题的对偶问题：该问题的对偶问题：max z=2 y1-3y2 s.t.2y1-3y2 1 3y1-y2 2 5y1-7y2 3 y1，y2 0第11页/共83页第10页/共83页2023/3/17第 11页例例2.5写出下列线性规划问题的对偶问题写出下列线性规划问题的对偶问题 min z=7x1 4x2 3x3s.t.4x1 2x2 6x3 2

9、4 3x1 6x2 4x3 15 5x1 3x3=30 x10，x2无约束无约束，x3 0解：将原问题的约束方程写成不等式约束形式：解：将原问题的约束方程写成不等式约束形式：min S=2x1+3x2-5x3 x1+x2-x3 5 y1 2x1 +x3 4 y2 -2x1 -x3 -4 y2”x1，x2，x3 0引入变量引入变量 y1,y2，y2”写出对偶问题写出对偶问题 max g=5 y1+4y2-4y2”s.t.y1+2y2-2y2”2 y1 3 -y1+y2-y2”-5 y1，y2，y2”0第12页/共83页第11页/共83页2023/3/17第 12页 原问题与对偶问题的关系原问题原

10、问题目标函数目标函数 max目标函数目标函数 minm个个=n个个=n个个00无符号限制无符号限制m个个00无符号限制无符号限制目标函数的系数目标函数的系数约束条件右端常数约束条件右端常数系数矩阵系数矩阵 A约束条件右端常数约束条件右端常数目标函数的系数目标函数的系数系数矩阵系数矩阵 AT约约束束条条件件约约束束条条件件变变 量量变变 量量对偶问题对偶问题第13页/共83页第12页/共83页2023/3/17第 13页例例2.6 2.6 写出写出(P)(P)问题的问题的(D)(D)问题问题min z=7x1+4x2-3x3 -4x1+2x2-6x324 -3x1-6x2-4x3 15 5x2+

11、3x3=30 x1 0 x2无符号限制无符号限制 x3 0 max w=24y1+15y2+30y3 y1 0 y20 y3无符号限制无符号限制 -4y1-3y2 72 2y1-6y2+5y3 =4 -6y1 -4y2+3y3 -3 第14页/共83页第13页/共83页2023/3/17第 14页练习练习2.1:2.1:写出写出(P)(P)问题的问题的(D)(D)问题问题max z=2x1+3x2-5x3+x4 s.t.4x1+x2-3x3+2x4 5 3x1-2x2 +7x4 4 -2x1+3x2+4x3+x4=6 x1 0,x2,x3 0,x4 无符号限制无符号限制min w=5y1+4y

12、2+6y3 s.t.4y1+3y2-2y3 2 y1-2y2+3y3 3 -3y1 +4y3 -5 2y1+7y2+y3=1 y1 0,y20,y3无符号限制无符号限制第15页/共83页第14页/共83页min Z=-CXs.t.-AX-bX 01、对称性定理：对偶问题的对偶是原问题。、对称性定理：对偶问题的对偶是原问题。min W=Y bs.t.YA C Y 0max Z=C Xs.t.AXb X 0对偶的定义对偶的定义对偶的定义对偶的定义max W=-Ybs.t.YA C Y 0对偶问题的基本性质第16页/共83页第15页/共83页2023/3/17第 16页2、弱对偶原理（弱对偶性）：设

13、、弱对偶原理（弱对偶性）：设 和和 分别是问题（分别是问题（P）和（）和（D）的可行解，则必有）的可行解，则必有 推论一：推论一：若若 和和 分别是问题（分别是问题（P）和（）和（D）的可行解，则）的可行解，则 是（是（D）的目标函数最）的目标函数最小值的一个下界；小值的一个下界；是（是（P）的目标函数最大值的一个上界。）的目标函数最大值的一个上界。第17页/共83页第16页/共83页2023/3/17第 17页Z ZY YX X在在在在Y=0Y=0的平面上鞍点是的平面上鞍点是的平面上鞍点是的平面上鞍点是z=f(0,y)z=f(0,y)的极大值点的极大值点的极大值点的极大值点第18页/共83页

14、第17页/共83页2023/3/17第 18页X XY YZ Z在在在在X=0X=0的平面上鞍点是的平面上鞍点是的平面上鞍点是的平面上鞍点是z=f(0,y)z=f(0,y)的极小值点的极小值点的极小值点的极小值点第19页/共83页第18页/共83页2023/3/17第 19页(弱对偶定理)proof:因为因为 x0 是是(P)问题的可行解问题的可行解,故必有故必有Ax0 b,x0 0 (1)又又y0是问题是问题(D)的可行解的可行解,于是有于是有y0A c,y0 0 (2)用用y0 左乘不等式左乘不等式(1)两边两边,得得y0Ax0 y0b 用用x0 左乘不等式左乘不等式(2)两边两边,得得y

15、0Ax0 cx0 从而有从而有 cx0 y0b 第20页/共83页第19页/共83页2023/3/17第 20页3 3、最优性若原问题的某个可行解X0的目标函数值与对偶问题某个可行解Y0的目标函数值相等，则X0,Y0分别是相应问题的最优解证：由弱对偶定理推论1，结论是显然的。即CX0=Y0b CX,Y0b=CX0 Yb。证毕。第21页/共83页第20页/共83页2023/3/17第 21页4 无界性：无界性：.在一对对偶问题（在一对对偶问题（P）和）和（D）中，若其中一个问题可行但目标函）中，若其中一个问题可行但目标函数无界，则另一个问题不可行；反之不数无界，则另一个问题不可行；反之不成立。这

16、也是对偶问题的无界性。成立。这也是对偶问题的无界性。关于无界性有如下结论：关于无界性有如下结论：问题无界问题无界无可无可行解行解无可无可行解行解问题无界问题无界对偶问题对偶问题原问题原问题无界无界如：如：（原）（原）无可无可行解行解（对）（对）第22页/共83页第21页/共83页2023/3/17第 22页 5、对偶定理（强对偶性）：、对偶定理（强对偶性）：若一对对偶问题若一对对偶问题 P 和和 D 都有可行解，则它们都有最优解，且目标函数的最优值必相都有可行解，则它们都有最优解，且目标函数的最优值必相等。等。推论：若推论：若 P 和和 D 的任意一个有最优解，则另一个也有最优解，且目标函数的

17、最优值的任意一个有最优解，则另一个也有最优解，且目标函数的最优值相等。相等。综上所述，一对对偶问题的关系，只能有下面三种情况之一出现：综上所述，一对对偶问题的关系，只能有下面三种情况之一出现：.都有最优解，分别设为都有最优解，分别设为X*和和 Y*，则必有，则必有CX*=Y*b；.一个问题无界，则另一个问题无可行解；一个问题无界，则另一个问题无可行解；.两个都无可行解。两个都无可行解。第23页/共83页第22页/共83页2023/3/17第 23页在线性规划问题的最优解中，如果对应某一约束条件的对偶变量值为非零，则在线性规划问题的最优解中，如果对应某一约束条件的对偶变量值为非零，则该约束条件取

18、严格等式；反之如果约束条件取严格不等式，则其对应的对偶变该约束条件取严格等式；反之如果约束条件取严格不等式，则其对应的对偶变量一定为零。量一定为零。6、互补松弛性即即第24页/共83页第23页/共83页2023/3/17第 24页证：由定理所设，可知有 A X0+U0=b X0,U0 0 (1)Y0 A V0 =C Y0,V0 0 (2)分别以Y0左乘(1)式，以X0右乘(2)式后，两式相减，得 Y0 U0+V0 X0=Y0 b C X0若 Y0 U0+V0 X0=0，根据最优解判别定理，X0,Y0分别是原问题和对偶问题最优解。反之亦然。证毕。第25页/共83页第24页/共83页2023/3/

19、17第 25页例例2.7 给定线性规划问题给定线性规划问题min z=2x1+3x2+x3 3x1-x2+x3 1 x1+2x2 -3x3 2 x1,x2,x3 0已知对偶问题的最优解为已知对偶问题的最优解为y=（y1,y2）T=（1/7,11/7）试用互补松弛性质求原问题的最优解。试用互补松弛性质求原问题的最优解。第26页/共83页第25页/共83页2023/3/17第 26页解：先写出它的对偶问题解：先写出它的对偶问题max w=y1+2y2 3y1 +y2 2 -y1+2y2 3 y1 -3y2 1 y1,y2 0将最优解将最优解y=y=（y y1 1,y,y2 2）T T=（1/7,1

20、1/71/7,11/7）代入上面的线性规划中，第三个约束条件）代入上面的线性规划中，第三个约束条件严格不等，说明严格不等，说明x x3 3=0,=0,第一、二个约束条件严格取等，说明，第一、二个约束条件严格取等，说明，解出：解出：x x1 1=4/7,x=4/7,x2 2=5/7=5/7第27页/共83页第26页/共83页2023/3/17第 27页例例2.8 已知线性规划问题已知线性规划问题 Min.Z=2x1+3x2+5x3+2x4 +3x5 S.t.x1+x2+2x3+x4+3x5 4 2x1 x2+3x3+x4+x5 3 xi 0(i=1,2,3,4,5)已知对偶问题的最优解为已知对偶

21、问题的最优解为 y1=4/5,y2=3/5,试应用对偶理论解原问题。试应用对偶理论解原问题。第28页/共83页第27页/共83页2023/3/17第 28页221/5 317/557/5 23=3将将y1、y2的值代入，得知的值代入，得知、为严格不等式，于是由互补松弛定理知，为严格不等式，于是由互补松弛定理知，必有必有x2=x3=x4=0；又因；又因y1,y2 0，故原问题的两个约束必为紧约束，于是，故原问题的两个约束必为紧约束，于是有：有：x1+3x5=4 2x1+x5 =3解之，有：解之，有：x1=x5=1。Z(1,0,0,0,1)=5 解解 写出对偶问题为：写出对偶问题为：Max.S=4

22、y1+3y2 S.t.y1+2y2 2 y1 y2 3 2y1+3y2 5 y1+y2 2 3y1+y2 3 y1,y2 0第29页/共83页第28页/共83页2023/3/17第 29页例例2.9试通过求对偶问题的最优解来求解原问题的最优解。试通过求对偶问题的最优解来求解原问题的最优解。解：对偶问题为解：对偶问题为第30页/共83页第29页/共83页2023/3/17第 30页用图解法求出：用图解法求出：Y*=（1.3），），W=11。将将y*1=1，y*2=3 代入对偶约束条件，代入对偶约束条件，（1）（）（2）（）（5）式为紧约束，（）式为紧约束，（3）（）（4）为松约束。）为松约束。令

23、原问题的最优解为令原问题的最优解为X*=（x1.x2.x3.x4.x5），则根据互补松弛条件，必有），则根据互补松弛条件，必有x3=x4=0(1.3)（1）（2）（3）（4）（5）第31页/共83页第30页/共83页2023/3/17第 31页 又由于又由于y*10，y*2 0，原问题的约束必为等式，即，原问题的约束必为等式，即化简为化简为此方程组为无穷多解此方程组为无穷多解令令x5=0,得到得到x1=1，x2=2 即即X*1=（）为原问题的一个最优解，（）为原问题的一个最优解，Z=11。再令再令 x5=2/3，得到，得到x1=5/3，x2=0 即即X*2（）也是原问题的一个最优解，（）也是原

24、问题的一个最优解，Z=11。第32页/共83页第31页/共83页2023/3/17第 32页例例2.10max z=2x1+3x2+0 x3+0 x4+0 x5 2x1+2x2+x3 =12 y1 4x1 +x4 =16 y2 5x2+x5=15 y3 xj0min w=-12y1-16y2-15y3+0y4+0y5 -2y1-4y2 +y4 =-2 x1 -2y1 -5y3 +y5=-3 x2 yi 0第33页/共83页第32页/共83页2023/3/17第 33页 基 b原问题变量原问题松弛变量 x1 x2 x3 x4 x5 x1 3 1 0 1/2 0 -1/5 x4 4 0 0 -2

25、1 4/5 x2 3 0 1 0 0 1/5 0 0 1 0 1/5 变量对偶问题的剩余变量对偶问题变量 y4 y5 y1 y2 y3 基 b对偶问题变量对偶问题的剩余变量 y1 y2 y3 y4 y5 y1 1 1 2 0 -1/2 0 y2 1/5 0 -4/5 1 1/5 -1/5 0 4 0 3 3变量原问题松弛变量原问题变量 x3 x4 x5 x1 x2第34页/共83页第33页/共83页2023/3/17第 34页w1 wi wm wm+1 wm+j wn+m x1 xj xn xn+1 xn+i xn+m 对偶问题的变量对偶问题的变量 对偶问题的松弛变量对偶问题的松弛变量 原始问

26、题的变量原始问题的变量 原始问题的松弛变量原始问题的松弛变量 xjwm+j=0 wixn+i=0(i=1,2,m;j=1,2,n)在一对变量中，其中一个大于在一对变量中，其中一个大于0，另，另一个一定等于一个一定等于0第35页/共83页第34页/共83页2023/3/17第 35页 我们前面介绍的一般单纯形法，是从“可行”(右端项非负）开始，逐步地迭代运算，直到得出最优解。而应用对偶规划的性质，可以找到一种求解线性规划的新方法对偶单纯形法。对偶单纯形法则是从“不可行”(右端项含负）开始，在保持最优性之下逐步迭代，直到不可行变为可行，即得到可行最优解为止。当对偶问题的约束条件的数目较原问题为少时

27、，应用对偶单纯形法求解较为方便。对偶单纯形法的基本思想对偶单纯形法的基本思想第36页/共83页第35页/共83页2023/3/17第 36页单纯形法思路单纯形法思路（保持可行性）（保持可行性）对偶单纯形法思路对偶单纯形法思路（保持最优性）（保持最优性）可行可行(右端项非负）右端项非负）非最优（检验数非最优（检验数非负非负）最优（检验数非正）最优（检验数非正）不可行不可行(右端项右端项含负含负）可行可行(右端项非负）右端项非负）非最优（检验数非最优（检验数非负非负）最优（检验数非正）不可行最优（检验数非正）不可行(右端项右端项含负含负）可行可行(右端项非负）右端项非负）最优解（检验数最优解（检验

28、数非正）非正）最优（检验数非正）最优（检验数非正）可行解可行解(右端项右端项非负）非负）第37页/共83页第36页/共83页2023/3/17第 37页原始单纯形法其基本思路：原始单纯形法其基本思路：在换基迭代过程中，始终保持在换基迭代过程中，始终保持基变量值非负，基变量值非负，逐步使逐步使检验数变成非正检验数变成非正，最后求得最优解或判断无最优解。，最后求得最优解或判断无最优解。对偶单纯形法其基本思路：对偶单纯形法其基本思路：在换基迭代过程中，始终保持在换基迭代过程中，始终保持检验数非正检验数非正，逐步使逐步使基变量值变成非负基变量值变成非负，最后求得最优解或判断无最优解。最后求得最优解或判

29、断无最优解。第38页/共83页第37页/共83页2023/3/17第 38页第39页/共83页第38页/共83页2023/3/17第 39页例例2.11 用对偶单纯形法解下列线性规划问题用对偶单纯形法解下列线性规划问题 min w=12y1+16y2+15y3s.t.2y1+4y2 2 2y1 +5y3 3 y1，y2，y3 0解：此题可用人工变量方法求，但也可用对偶单纯形法。解：此题可用人工变量方法求，但也可用对偶单纯形法。max w=-12y1-16y2 15y3s.t.-2y1-4y2 +y4 =-2 -2y1 -5y3 +y5=-3 y1，y2，y3，y4，y5 0第40页/共83页第

30、39页/共83页2023/3/17第 40页列单纯形表列单纯形表Cj12161500CBXBby1y2y3y4y500y4y5-2-3-2-2-400-51001-12-16-15000-15y4y3-23/5-22/5-4001100-1/5-6-1600-3-12-15y1y311/5102-4/501-1/21/50-1/50-40-3-3Y*=(1,0,1/5,0,0)第41页/共83页第40页/共83页2023/3/17第 41页例例2.12 用对偶单纯形法解下列线性规划问题用对偶单纯形法解下列线性规划问题 min S=x1+4x2+3x4s.t.x1+2x2 -x3+x4 3 -2

31、x1-x2+4x3+x4 2 x1，x2，x3，x4 0解：此题可用人工变量方法求，但也可用对偶单纯形法。解：此题可用人工变量方法求，但也可用对偶单纯形法。max S=-x1-4x2-3x4s.t.-x1-2x2 +x3-x4+x5 =-3 2x1+x2 -4x3-x4 +x6=-2 x1，x2，x3，x4，x5，x6 0第42页/共83页第41页/共83页2023/3/17第 42页计算检验数全为非正，称为对偶可行；而常数项全是负数，称为原始不可行。计算检验数全为非正，称为对偶可行；而常数项全是负数，称为原始不可行。常数项是负数且最小，确定出基变量常数项是负数且最小，确定出基变量x5。第43

32、页/共83页第42页/共83页2023/3/17第 43页用出基变量用出基变量x5行的所有负数分别去除对应的检验数，最小值对应的为进基变量行的所有负数分别去除对应的检验数，最小值对应的为进基变量x1，交交叉元素为主元（叉元素为主元（-1）主元运算：第一行乘（主元运算：第一行乘（-1）第44页/共83页第43页/共83页2023/3/17第 44页主元运算：第二行加上第一行（主元运算：第二行加上第一行（-2）计算检验数计算检验数第45页/共83页第44页/共83页2023/3/17第 45页确定出基变量确定出基变量X6确定进基变量确定进基变量X3，主元（主元（-2）第46页/共83页第45页/共

33、83页2023/3/17第 46页主元运算：第二行乘（主元运算：第二行乘（-1/2）主元运算：第一行加第二行主元运算：第一行加第二行第47页/共83页第46页/共83页2023/3/17第 47页计算检验数：全为非正。但此时常数计算检验数：全为非正。但此时常数b已全大于零，最优解已全大于零，最优解=（7，0，4，0）最优值最优值 S =-7 S=7第48页/共83页第47页/共83页2023/3/17第 48页例例2.13 用对偶单纯形法解下列线性规划问题用对偶单纯形法解下列线性规划问题 min S=x1+2x2s.t.-x1+2x2 -x3 1 -x1-2x2 +x3 6 x1，x2，x3

34、0解：将原问题化成解：将原问题化成 max S=-x1-2x2s.t.x1-2x2 +x3+x4 =-1 x1+2x2 -x3 +x5=-6 x1，x2，x3，x4，x5 0第49页/共83页第48页/共83页2023/3/17第 49页常数项最小出基变量常数项最小出基变量X5，按比值无法比较。，按比值无法比较。常数项次小出基变量常数项次小出基变量X4，按比值，按比值X2为进基变量。主元（为进基变量。主元（-2）第50页/共83页第49页/共83页2023/3/17第 50页主元运算：第一行乘（主元运算：第一行乘（-1/2）主元运算：第二行加第一行（主元运算：第二行加第一行（-2）第51页/共

35、83页第50页/共83页2023/3/17第 51页计算检验数：全小于零。但常数项为负数的行元素全大于零，原问题无可行解。计算检验数：全小于零。但常数项为负数的行元素全大于零，原问题无可行解。第52页/共83页第51页/共83页2023/3/17第 52页练习练习2.2 用对偶单纯形法解下列线性规划问题用对偶单纯形法解下列线性规划问题解：先化为标准型解：先化为标准型约束条件两边同乘约束条件两边同乘(-1)第53页/共83页第52页/共83页2023/3/17第 53页列单纯形表列单纯形表Cj1524500CBXBbx1x2x3x4x500 x4x52105-6-2-1-11001-15-24-

36、500-45-240 x2x51/3-1/30-5101/6-2/3-1/6-1/301-150-1-4033/212-24-5x2x31/41/2-5/415/21001-1/41/21/4-3/2-15/200-7/2-3/2X*=(0,1/4,1/2)Y*=(7/2,3/2)第54页/共83页第53页/共83页2023/3/17第 56页对偶单纯形法与原始单纯形法内在的对应关系原始单纯形法原始单纯形法对偶单纯形法对偶单纯形法前提条件前提条件所有所有 bi0所有所有 bi0?最优性检验最优性检验所有所有所有所有换入、出基换入、出基变量的确定变量的确定先确定换入基变量先确定换入基变量后确定换

37、出基变量后确定换出基变量先确定换出基变量先确定换出基变量后确定换入基变量后确定换入基变量原始基本解的进化原始基本解的进化可行可行 最优最优非可行非可行 可行可行(最优最优)对偶单纯形法有以下优点：对偶单纯形法有以下优点：（1）初始解可以是非可行解；）初始解可以是非可行解；（2）当变量多于约束条件，可以减少计算工作量；）当变量多于约束条件，可以减少计算工作量；（3）在灵敏度分析中，有时需要用对偶单纯形法，这样可以）在灵敏度分析中，有时需要用对偶单纯形法，这样可以 使问题的处理简便。使问题的处理简便。第57页/共83页第56页/共83页6 6 灵敏度分析灵敏度分析 灵敏度分析一词的含义是指对系统或

38、事物因周围条件变化显示出来的敏感灵敏度分析一词的含义是指对系统或事物因周围条件变化显示出来的敏感程度的分析。程度的分析。在前面所讲的线性规划问题中，都假定了各系数在前面所讲的线性规划问题中，都假定了各系数c cj j,a aijij,b bi i等始终保持等始终保持不变，是已知常数。而实际当中，这些系数通常是一些估计或预测数字。如果不变，是已知常数。而实际当中，这些系数通常是一些估计或预测数字。如果外界条件发生了变化，这些系数也会发生相应变化，这样以来，就会引出一些外界条件发生了变化，这些系数也会发生相应变化，这样以来，就会引出一些问题：问题：这些系数中，如果有一些发生变化，问题的最优解会发生

39、怎样的变化？这些系数中，如果有一些发生变化，问题的最优解会发生怎样的变化？如果发生变化，又将使用何种简便方法求出新的最优解？如果发生变化，又将使用何种简便方法求出新的最优解？（一）价值系数（一）价值系数c c 发生变化发生变化1.1.非基变量的系数发生变化非基变量的系数发生变化2 2基变量的系数发生变化基变量的系数发生变化3.3.基变量系数和非基变量系数都变化基变量系数和非基变量系数都变化（二）右端项（二）右端项 b b 发生变化发生变化第59页/共83页第58页/共83页2023/3/17第 59页1当当C发生变化时发生变化时不变项：(1)可行域不变。(2)原问题的最优解还是新问题的基本可行

40、解。要修改：(1)目标函数系数行 Cj；(2)检验数行 j；(3)目标函数值；然后根据检验数是否满足j0 的条件，决定是否迭代。若 cj 是非基变量的系数，则只有其对应的j发生改变。若 cj 是基变量的系数，则CB 将发生改变，那么所有的j 发生改变。第60页/共83页第59页/共83页2023/3/17第 60页 max w=2x1+3x2+x3+0 x4+0 x5 1/3 x1+1/3 x2+1/3 x3+x4=1 1/3 x1+4/3 x2+7/3 x3+x5=3 x1,x2,x3,x4,x5 0例例2.14 max w=2x1+3x2+x3 1/3 x1+1/3 x2+1/3 x3 1

41、 1/3 x1+4/3 x2+7/3 x3 3 x1,x2,x3 06-1 价值系数价值系数 c 发生变化发生变化1.非基变量的系数发生变化非基变量的系数发生变化第61页/共83页第60页/共83页2023/3/17第 61页 最优单纯形表 可得到可得到c3 3 时，原最优解不变。时，原最优解不变。当当-3+c3 0最最优解不变优解不变第62页/共83页第61页/共83页2023/3/17第 62页 设设 cs 变化为变化为 cs+cs ，那么，那么 j=cj-cri arij -(cs+cs)asj=j-cs as，is 观察所有非基变量：对于极小化问题，只要对所有非基变量观察所有非基变量：

42、对于极小化问题，只要对所有非基变量 j0，即，即 j cs asj，则最优解不变；否则，将最优单纯形表中的检验数则最优解不变；否则，将最优单纯形表中的检验数 j 用用 j取代，继续取代，继续单纯形法的表格计算。单纯形法的表格计算。Max j/asj asj 0 csMin j/asj asj 0 br Min-bi /air air 0 第69页/共83页第68页/共83页2023/3/17第 69页最优单纯形表如下最优单纯形表如下 例例2.15Max Z=2x1+3x2+0 x3+0 x4+0 x5 x1+2x2+x3 =84x1 +x4 =16 4x2 +x5=12+b3 x1,x2,x3

43、,x4,x5 0 （二）右端项（二）右端项 b 发生变化发生变化第70页/共83页第69页/共83页2023/3/17第 70页第71页/共83页第70页/共83页2023/3/17第 71页若若b 3=-8，则，则 4+（-8）=-4 0，改变了最优性，只要再继续迭代即可。见下表，改变了最优性，只要再继续迭代即可。见下表比如第三个式子中，由比如第三个式子中，由4+b3 0，解得，解得b3-4 时最优性不变时最优性不变 第72页/共83页第71页/共83页2023/3/17第 72页第73页/共83页第72页/共83页2023/3/17第 73页例例2.16 已知线性规划问题及其最优单纯形表已

44、知线性规划问题及其最优单纯形表 Cj114000CBXBbx1x2x3x4x5x6104x1x5x31/3613/3100-1/322/30011/301/3010-2/311/3-Z-170-40-10-2若右端列向量若右端列向量，求新问题的最优解。，求新问题的最优解。第74页/共83页第73页/共83页2023/3/17第 74页解：解：因为因为1小于小于0，因此继续迭代，因此继续迭代Cj114000XBbx1x2x3x4x5x6x1x5x3152100-1/322/30011/301/3010-2/311/3-Z-90-40-10-2j/arj123x6x5x33/27/23/2-3/2

45、3/21/21/23/21/2001-1/21/21/2010100-Z-6-3-30-200 新问题的最优解为新问题的最优解为X*=(0,0,3/2,0,7/2,3/2)Z*=6第75页/共83页第74页/共83页2023/3/17第 75页常山机械厂生产常山机械厂生产和和两种产品。生产中需使用两种产品。生产中需使用A A、B B、C C三种设备进行加工，加三种设备进行加工，加工每件工每件产品或产品或产品所需的设备机时数、利润值及每种设备可利用机时数列产品所需的设备机时数、利润值及每种设备可利用机时数列于下表，请问：充分利用设备机台时，工厂应生产于下表，请问：充分利用设备机台时，工厂应生产和

46、和产品各多少件才能获产品各多少件才能获得最大利润？试列出相应的线性规划数学模型。得最大利润？试列出相应的线性规划数学模型。A AB BC C产品利润产品利润（元件）（元件）2 24 40 02 22 20 05 53 3设备可用机时设备可用机时数（工时）数（工时）1212161615156-3 增加一个变量的分析增加一个变量的分析第76页/共83页第75页/共83页2023/3/17第 76页解：设解：设、产品的生产数量分别为产品的生产数量分别为x1和和x2，建立问题数学模型如下：，建立问题数学模型如下：max z=2x1+3x2 2x1+2x212 4x1 16 5x2 15 xj0，j=1

47、，2第77页/共83页第76页/共83页2023/3/17第 77页若增加一个变量若增加一个变量x x6 6。试分析问题最优解的变化。试分析问题最优解的变化第78页/共83页第77页/共83页2023/3/17第 78页第79页/共83页第78页/共83页2023/3/17第 79页6-4 增加一个约束条件的分增加一个约束条件的分析析解：设解：设、产品的生产数量分别为产品的生产数量分别为x1和和x2，建立问题数学模型如下：，建立问题数学模型如下：max z=2x1+3x2 2x1+2x212 4x1 16 5x2 15 xj0，j=1，2第80页/共83页第79页/共83页2023/3/17第 80页增加一个约束条件增加一个约束条件3x1+2x214因为有因为有33+23=1533+23=151414，所以将约束条件加上松弛变量后的方程，所以将约束条件加上松弛变量后的方程 3x1+2x2+x6=14第81页/共83页第80页/共83页2023/3/17第 81页（1）=（1）（2）=（2）（3）=（3）（4）=（4）-3（1）-2（3）（1）（2）（3）（4）第82页/共83页第81页/共83页2023/3/17第 82页第83页/共83页第82页/共83页2023/3/17第 83页感谢您的观看！第83页/共83页