单纯形法的灵敏度分析与对偶对偶问题.ppt
140页
分别用大M法和两阶段法求解下列 线形规划问题,并指出解的类型• minZ=2x1+3x2+x3 • x1+4x2+2x3≥8 • S.t. 3x1+2x2 ≥6 • x1,x2,x3 ≥0• 时间:1:40—2:10Cj CBXBb检验数jx1x2x3x4x5x6x7-2 -3 -1 0 0 -M-M8142-10 1 0x6x7-M-M初 始 单 纯 形 表 格4M-2 6M -3 2M-1-M-M 0063200-1 0 1Cj CBXBb检验数jx1x2x3x4x5x6x7-2 -3 -1 0 0 -M-M9/5013/5-3/101/10 3/10 -1/10 X2x1-3-2最 终 单 纯 形 表 格4M-2 6M -3 2M-1-M-M 004/510-2/5 1/5-2/5 -1/5 2/5第六章 单纯形法的灵敏度分析 与对偶DUAL窗含西岭千秋雪，门泊东吴万里船对偶是一种普遍现象• §1 单纯形表的灵敏度分析(重点.难点.掌握)• §2 线性规划的对偶问题 (重点.理解.掌握)• §3 对偶规划的基本性质(重点.应用)• §4 对偶单纯形法(难点.掌握---前面已讲)学习重点重点与难点难点§1 单纯形表的灵敏度分析(重点.难点.掌握)§2 线性规划的对偶问题一、对偶问题实例 例1 某工厂生产甲、乙两种产品，要消耗A、B和C三种资源， 已知每件产品对这三种资源的消耗、这三种资源的现有数量和每 件产品可获得的利润如表所示.问：如何安排生产计划，使得既能 充分利用现有资源又使总利润最大？产品 资源甲乙资源 限制A3265B2140C0375单件利 润15002500 该问题的数学模型为：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甲乙资源 限制A3265y1B2140y2C0375y3单件 利润15002500≥1500 ≥2500≥0 原问题：max Z=1500x1+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 ≥ 032 21 0 3A=65 40 75b=1500 2500c=32 0 2 1 3A=1500 2500 b= 65 40 75c=maxmin对偶问题 Min W=bTY s.t. ATY≥CTY ≥0≥maxbACCTATbT≤minmnmn二、对偶问题的形式1、对称型对偶问题原问题 Max Z=cX s.t. AX≤bX ≥0• 对偶关系表 x1x2…xm…xnc1c2…cm…cnmaxZ minWY1A11a12…a1m…a1n≤ b1Y2a21a22…a2m…a2n≤ b2Ymam1am2…amm…amn≤ bm• 由表可以看出：• 从行看是原问题（Ⅰ），从列看是对偶问题（Ⅱ），两个问题的变量系数矩阵互为转置矩阵。
• 原问题（Ⅰ）的常数项是对偶问题（Ⅱ）的目标系数，反之， 原问题（Ⅰ）的目标系数是对偶问题（Ⅱ）的常数项• 原问题（Ⅰ）有n个决策变量，对偶问题（Ⅱ）有n个约束方程 ；原问题有m个约束方程，对偶问题就有m个决策变量• 原问题的约束是“≤”型，对偶问题的约束是“≥”型• 原问题的目标函数是求极大，对偶问题的目标是求极小 max Z＝5x1 +4x2 例2 请给出下列线性规划问题的对偶问题：对称型线性规划问题怎么样 简单吧2、非对称型对偶问题表 对偶变换的规则• 约束条件的类型(规范与否)与非负条件相互对应 • 非标准的约束条件类型对应非正常的非负条件 • 对偶变换是一一对应的好难记呀！例3：Min z= 5x1+ 25x2 7x1+ 75x2 ≤98 s.t. 5x1 + 6x2 = 7824x1+ 12x2≥54x1≥0 、x2 ≤ 0Max w= 98y1+ 78y2 + 54y3 7y1+ 5y2 + 24y3 ≤ 5 s.t. 75y1+ 6y2 + 12y3 ≥25y1 ≤ 0 、y2无限制、 y3≥0怎么样，没问题吧！对称形式线形规划问题为:Max Z=cX s.t. AX≤bX ≥0加上松弛变量化为标准形后为:Max Z=cX +0Xs s.t. AX+IXs=bX ≥0,Xs ≥0§3 对偶规划的基本性质一、单纯形法计算的矩阵描述:检验数j当迭代若干步，基变量为X B时，新的单纯形表:bXS0CjX B XN XSB N ICB CN 0CB CN 0检验数jB-1bXBCBCjX B XN XSI B-1N B-1 0 CN- CB B-1N - CB B-1CB CN 0初始单纯形表为:maxZ=3x1 +5 x2 +0x3 +0x4+0x5 =0x1 + x3 =82x2 + x4 =123x1 +4 x2 + x5=36 Cj比 值CBXBb检验数jx1x2x3x4x53500081010012020103634001x3 x4 x50 0 035000举例• 最优基 Cj35000比 值CBXBbx1x2x3x4x50x340012/3-1/3 5x260101/20 3x14100-2/31/3 检验数j000-1/2-1x3x2x1• 最优基的逆 • 最优基和最优基的逆maxZ=2x1+x25x2≤15 s.t. 6x1+2x2 ≤24x1+x2 ≤5x1,x2 ≥0maxZ=2x1+x2+0x3 +0x4 +0x5 5x2+x3 =15s.t. 6x1+2x2 +x4 =24x1+x2 +x5 = 5x1,x2 ,x3 ,x4,x5 ≥0例4：对称形线性规划问题：标准型： j x3x1x20210 0 0 -1/4 -1/2x1 x2 x3 x4 x5CB XB bCB j 2 1 0 0 0x3x4x500015 0 5 1 0 024 6 2 0 1 05 1 1 0 0 12 1 0 0 0初始单纯形表最终单纯形表B=(P3,P1,P2)15/2 0 0 1 5/4 -15/27/2 1 0 0 1/4 -1/23/2 0 1 0 -1/4 3/2B-1= (P'3,P'4,P'5)初表 中终 表 中• minZ=2x1+3x2+x3 • x1+4x2+2x3≥8 • S.t. 3x1+2x2 ≥6 • x1,x2,x3 ≥0Cj CBXBb检验数jx1x2x3x4x5x6x7-2 -3 -1 0 0 -M-M8142-10 1 0x6x7-M-M初 始 单 纯 形 表 格4M-2 6M -3 2M-1-M-M 0063200-1 0 1Cj CBXBb检验数jx1x2x3x4x5x6x7-2 -3 -1 0 0 -M-M9/5013/5-3/101/10 3/10 -1/10 X2x1-3-2最 终 单 纯 形 表 格0 0 0-1/2-1/2 ½-M½-M4/510-2/5 1/5-2/5 -1/5 2/5maxZ=50x1+100x2x1 +x2 ≤300 s.t. 2x1+x2 ≤400x2 ≤250x1,x2 ≥0maxZ=50x1+100x2+0x3 +0x4 +0x5 x1 +x2 +x3 =300 s.t. 2x1+x2 +x4 =400x2 +x5=250x1,x2 , x3 ,x4,x5 ≥0例5：对称形线性规划问题：x1 x2 x3 x4 x5CB XB bCB j x3x4x5000300 1 1 1 0 0400 2 1 0 1 0250 0 1 0 0 150 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=1 0 - 1 -2 1 10 0 11 0 1 2 1 10 0 11 0 - 1 -2 1 10 0 13004002505050250=σj= Cj-CBB-1 P j x1 x2 x3 x4 x5CB XB bCB j x1x4x250010050 1 0 1 0 -150 0 0 -2 1 1250 0 1 0 0 10 0 -50 0 -50原问题最终单纯形表50 100 0 0 0原问题初始单纯形表x1 x2 x3 x4 x5CB XB bCB j x3x4x5000400 2 1 0 1 0250 0 1 0 0 150 100 0 0 050 100 0 0 0300 1 1 1 0 0检验数j当迭代若干步，基变量为X B时，新的单纯形表:bXS0CjX B XN XSB N ICB CN 0CB CN 0检验数jB-1bXBCBCjX B XN XSI B-1N B-1 0 CN- CB B-1N - CB B-1CB CN 0初始单纯形表为:• 对应初始单纯表中的单位矩阵I，迭代后的 单纯形表中为B-1 • 初始单纯表中的基变量Xs=b，迭代后的单 纯形。
