《单纯形法的灵敏度分析与对偶问题(新)》由会员分享，可在线阅读，更多相关《单纯形法的灵敏度分析与对偶问题(新)（168页珍藏版）》请在金锄头文库上搜索。
1、分别用大M法和两阶段法求解下列线形规划问题,并指出解的类型,minZ=2x1+3x2+x3x1+4x2+2x38 S.t. 3x1+2x2 6x1,x2,x3 0时间:1:402:10,初始单纯形表格,最终单纯形表格,第六章 单纯形法的灵敏度分析与对偶,DUAL,窗含西岭千秋雪，门泊东吴万里船对偶是一种普遍现象,1 单纯形表的灵敏度分析(重点.难点.掌握) 2 线性规划的对偶问题 (重点.理解.掌握) 3 对偶规划的基本性质(重点.应用) 4 对偶单纯形法(难点.掌握-前面已讲),学习重点与难点,1 单纯形表的灵敏度分析(重点.难点.掌握),2 线性规划的对偶问题,一、对偶问题实例,例1 某工
2、厂生产甲、乙两种产品，要消耗A、B和C三种资源，已知每件产品对这三种资源的消耗、这三种资源的现有数量和每件产品可获得的利润如表所示.问：如何安排生产计划，使得既能充分利用现有资源又使总利润最大？,该问题的数学模型为：max Z=1500x1+2500x2 s.t. 3x1+2x2 65 A资源2x1+ x2 40 B资源3x2 75 C资源x1,x2 0,考虑： 1、定价不能太高？ 2、定价不能太低？,假设该厂现自己不生产，因而要转让资源A、B和C，请问他们应如何给这三种资源定价？,咋办？,设A、B、C资源的出售价格分别为 y1 、 y2和y3,1500,2500,0,原问题：max Z=15
3、00x1+2500x2 s.t. 3x1+2x2 65 A资源2x1+ x2 40 B资源3x2 75 C资源x1,x2 0,对偶问题：Min W = 65 y1 + 40 y2 + 75 y3 s.t. 3y1 + 2 y2 15002y1 + y2 + 3y3 2500y1, y2 , y3 0,2 1 0 3,A=,65 40 75,b=,1500 2500,c=,2 0 2 1 3,A=,1500 2500,b=,65 40 75,c=,max,min,对偶问题 Min W=bTY s.t. ATYCTY 0,max,b,A,C,CT,AT,bT,min,m,n,m,n,二、对偶问题的
4、形式1、对称型对偶问题,原问题 Max Z=cX s.t. AXbX 0,对偶关系表,由表可以看出：从行看是原问题（），从列看是对偶问题（），两个问题的变量系数矩阵互为转置矩阵。 原问题（）的常数项是对偶问题（）的目标系数，反之，原问题（）的目标系数是对偶问题（）的常数项。 原问题（）有n个决策变量，对偶问题（）有n个约束方程；原问题有m个约束方程，对偶问题就有m个决策变量。 原问题的约束是“”型，对偶问题的约束是“”型。 原问题的目标函数是求极大，对偶问题的目标是求极小。,max Z5x1 +4x2,例2 请给出下列线性规划问题的对偶问题：,对称型线性规划问题,怎么样简单吧,2、非对称型对偶
5、问题表 对偶变换的规则,约束条件的类型(规范与否)与非负条件相互对应 非标准的约束条件类型对应非正常的非负条件 对偶变换是一一对应的,好难记呀！,例3：,Min z= 5x1+ 25x2 7x1+ 75x2 98 s.t. 5x1 + 6x2 = 7824x1+ 12x254x10 、x2 0,Max w= 98y1+ 78y2 + 54y3 7y1+ 5y2 + 24y3 5 s.t. 75y1+ 6y2 + 12y3 25y1 0 、y2无限制、 y30,怎么样，没问题吧！,对称形式线形规划问题为:,Max Z=cX s.t. AXbX 0,加上松弛变量化为标准形后为:,Max Z=cX
6、+0Xs s.t. AX+IXs=bX 0,Xs 0,3 对偶规划的基本性质,一、单纯形法计算的矩阵描述:,检验数j,当迭代若干步，基变量为X B时，新的单纯形表:,b,XS,0,Cj,X B XN XS,B N I,CB CN 0,CB CN 0,检验数j,B-1b,XB,CB,Cj,X B XN XS,I B-1N B-1,0 CN- CB B-1N - CB B-1,CB CN 0,初始单纯形表为:,maxZ=3x1 +5 x2 +0x3 +0x4+0x5 =0x1 + x3 =82x2 + x4 =123x1 +4 x2 + x5=36,举例,最优基,最优基的逆,最优基和最优基的逆,m
7、axZ=2x1+x25x215 s.t. 6x1+2x2 24x1+x2 5x1,x2 0,maxZ=2x1+x2+0x3 +0x4 +0x5 5x2+x3 =15 s.t. 6x1+2x2 +x4 =24x1+x2 +x5 = 5x1,x2 ,x3 ,x4,x5 0,例4：对称形线性规划问题：,标准型：, j ,x3 x1 x2,0 2 1,0 0 0 -1/4 -1/2,x1 x2 x3 x4 x5,CB XB b,CB , j ,2 1 0 0 0,x3 x4 x5,0 0 0,15 0 5 1 0 0,24 6 2 0 1 0,5 1 1 0 0 1,2 1 0 0 0,初始单纯形表,
8、最终单纯形表,B=(P3,P1,P2),15/2 0 0 1 5/4 -15/2,7/2 1 0 0 1/4 -1/2,3/2 0 1 0 -1/4 3/2,B-1= (P3,P4,P5),初表中,终表中,minZ=2x1+3x2+x3x1+4x2+2x38 S.t. 3x1+2x2 6x1,x2,x3 0,初始单纯形表格,最终单纯形表格,maxZ=50x1+100x2x1 +x2 300 s.t. 2x1+x2 400x2 250x1,x2 0,maxZ=50x1+100x2+0x3 +0x4 +0x5 x1 +x2 +x3 =300 s.t. 2x1+x2 +x4 =400x2 +x5=2
9、50x1,x2 , x3 ,x4,x5 0,例5：对称形线性规划问题：,x1 x2 x3 x4 x5,CB XB b,CB , j ,x3 x4 x5,0 0 0,300 1 1 1 0 0,400 2 1 0 1 0,250 0 1 0 0 1,50 100 0 0 0,原问题初始单纯形表,50 100 0 0 0,已知最优基的基变量为x1， x4， x2，请直接写出该线性规划问题的最终单纯形表。并给出其对偶问题的最优解,最优基为 B=（p1， p4， p2）=,B-1=（p3， p4 ， p5 ）=,b= B-1 b=,=,j= Cj-CBB-1 P j,x1 x2 x3 x4 x5,CB XB b,CB , j ,x1 x4 x2,50 0 100,50 1 0 1 0 -1,50 0 0 -2 1 1,250 0 1 0 0 1,0 0 -50 0 -50,原问题最终单纯形表,50 100 0 0 0,原问题初始单纯形表,x1 x2 x3 x4 x5,CB XB b,CB , j ,x3 x4 x5,0 0 0,400 2 1 0 1 0,250 0 1 0 0 1,50 100 0 0 0,50 100 0 0 0,300 1 1 1 0 0,检验数j,当迭代若干步，基变量为X B时，新的单纯形表:,b,XS,0,Cj,X B XN XS,
