第六章 单纯形法的灵敏度分析与对偶对偶问题.ppt

《第六章 单纯形法的灵敏度分析与对偶对偶问题.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、分别用大M法和两阶段法求解下列线形规划问题,并指出解的类型minZ=2x1+3x2+x3x1+4x2+2x3≥8S.t.3x1+2x2≥6x1,x2,x3≥0时间:1:40—2:10CjCBXBb检验数jx1x2x3x4x5x6x7-2-3-100-M-M8142-1010x6x7-M-M初始单纯形表格4M-26M-32M-1-M-M0063200-101CjCBXBb检验数jx1x2x3x4x5x6x7-2-3-100-M-M9/5013/5-3/101/103/10-1/10X2x1-3

2、-2最终单纯形表格4M-26M-32M-1-M-M004/510-2/51/5-2/5-1/52/5第六章单纯形法的灵敏度分析与对偶DUAL窗含西岭千秋雪，门泊东吴万里船对偶是一种普遍现象§1单纯形表的灵敏度分析(重点.难点.掌握)§2线性规划的对偶问题(重点.理解.掌握)§3对偶规划的基本性质(重点.应用)§4对偶单纯形法(难点.掌握---前面已讲)学习重点与难点§1单纯形表的灵敏度分析(重点.难点.掌握)§2线性规划的对偶问题一、对偶问题实例例1某工厂生产甲、乙两种产品，要消耗A、B和C三种

3、资源，已知每件产品对这三种资源的消耗、这三种资源的现有数量和每件产品可获得的利润如表所示.问：如何安排生产计划，使得既能充分利用现有资源又使总利润最大？产品资源甲乙资源限制A3265B2140C0375单件利润15002500该问题的数学模型为：maxZ=1500x1+2500x2s.t.3x1+2x265A资源2x1+x240B资源3x275C资源x1,x20考虑：1、定价不能太高？2、定价不能太低？假设该厂现自己不生产，因而要转让资源A、B和C，请问他们应如何给这三种资源定价？咋办？

4、设A、B、C资源的出售价格分别为y1、y2和y3甲乙资源限制A3265y1B2140y2C0375y3单件利润15002500≥1500≥2500≥0原问题：maxZ=1500x1+2500x2s.t.3x1+2x265A资源2x1+x240B资源3x275C资源x1,x20对偶问题：MinW=65y1+40y2+75y3s.t.3y1+2y2≥15002y1+y2+3y3≥2500y1,y2,y3≥02103A=654075b=15002500c=20213A=15002500b=65

5、4075c=maxmin对偶问题MinW=bTYs.t.ATY≥CTY≥0≥maxbACCTATbT≤minmnmn二、对偶问题的形式1、对称型对偶问题原问题MaxZ=cXs.t.AX≤bX≥0对偶关系表x1x2…xm…xnc1c2…cm…cnmaxZminWY1A11a12…a1m…a1n≤b1Y2a21a22…a2m…a2n≤b2Ymam1am2…amm…amn≤bm由表可以看出：从行看是原问题（Ⅰ），从列看是对偶问题（Ⅱ），两个问题的变量系数矩阵互为转置矩阵。原问题（Ⅰ）的常数项是对偶问题

6、（Ⅱ）的目标系数，反之，原问题（Ⅰ）的目标系数是对偶问题（Ⅱ）的常数项。原问题（Ⅰ）有n个决策变量，对偶问题（Ⅱ）有n个约束方程；原问题有m个约束方程，对偶问题就有m个决策变量。原问题的约束是“≤”型，对偶问题的约束是“≥”型。原问题的目标函数是求极大，对偶问题的目标是求极小。maxZ＝5x1+4x2例2请给出下列线性规划问题的对偶问题：对称型线性规划问题怎么样简单吧2、非对称型对偶问题表对偶变换的规则约束条件的类型(规范与否)与非负条件相互对应非标准的约束条件类型对应非正常的非负条件对偶变换是

7、一一对应的好难记呀！例3：Minz=5x1+25x27x1+75x2≤98s.t.5x1+6x2=7824x1+12x2≥54x1≥0、x2≤0Maxw=98y1+78y2+54y37y1+5y2+24y3≤5s.t.75y1+6y2+12y3≥25y1≤0、y2无限制、y3≥0怎么样，没问题吧！对称形式线形规划问题为:MaxZ=cXs.t.AX≤bX≥0加上松弛变量化为标准形后为:MaxZ=cX+0Xss.t.AX+IXs=bX≥0,Xs≥0§3对偶规划的基本性质一、单纯形法计算的矩阵描述:检

8、验数j当迭代若干步，基变量为XB时，新的单纯形表:bXS0CjXBXNXSBNICBCN0CBCN0检验数jB-1bXBCBCjXBXNXSIB-1NB-10CN-CBB-1N-CBB-1CBCN0初始单纯形表为:maxZ=3x1+5x2+0x3+0x4+0x5=0x1+x3=82x2+x4=123x1+4x2+x5=36Cj比值CBXBb检验数jx1x2x3x4x53500081010012020103634001x3x4x500035000举例最优基Cj35000比值CBXBbx