mpa 定量法第十一，十二章07.ppt
第十一章 单纯形法 (Simplex Method),本章授课内容: 单纯形法的解题思路 单纯形法的计算步骤,1947年夏末, George Dantzig 提出求解线形规划问题的一般方法-单纯形法,单纯形法的基本原理,求解LP问题的单纯形法的基本原理是：从一个初始基本可行解出发，通过对基变量的迭代运算(每次更换一个基变量，即从一个可行极点移动到与之相邻的一个可行极点)，而得到下一个基本可行解，同时使目标函数得到改善；经过有限次的迭代运算，就可得到LP的最优解。,单纯形法的解题思路,找出一个基本可行解,最优吗?,是,停止计算,否,从一个基本可行解转移到另一个基本可行解,并使目标函数值进一步增大,利用图解法中的例， 了解基解在几何中的对应关系,= 10个,X (1) = ( 0,0,4,2,2 ) T ······ O 点，,X (2) = ( 0,4,0,-6,6 ) T ······ H1点，,X (3) = ( 0,1,3,0,3 ) T ······ A 点，,X (4) = ( 0,-2,6,6,0 ) T ······ H2点，,X (5) = ( 4,0,0,6,-2 ) T ······ H3点，,X (6) = (-2,0 ,6,0,4 ) T ······ H4点，,X ( 7) = ( 2,0,2,4,0 ) T ······ D 点，,X (8) = ( 2,2,0,0,2 ) T ······ B 点，,X (9) = ( 3,1,0,3,0 ) T ······ C 点，,X (10) = (6,4,-6,0,0 ) T ······ H5点。,非基列,( P1 P2 ),( P1 P3 ),( P1 P4 ),( P1 P5 ),( P2 P3 ),( P2 P4 ),( P2 P5 ),( P3 P4 ),( P3 P5 ),( P4 P5 ),结论：,上例中，基可行解有： X(1)，X(3)，X(7)，X(8)，X(9) 分别与约束域顶点 O，A，D，B，C 对应。,基解不一定是可行解。,即基可行解与（LP）约束域顶点： 构成了一一对应关系。,二、基本定理,经严格的数学证明，可以得出如下结果： 定理1 线性规划（LP）的基可行解 与其约束域的顶点构成一一对应。 定理2 对于线性规划（LP）问题： 1、若存在一个可行解， 则一定存在基可行解； 2、若最优解存在， 则一定在某个（些）基可行解处达到。,案例1 最优生产计划问题,设某厂生产甲、乙、丙三种产品，要经过三道工序加工，每种产品在各道工序的加工时间，各工序的生产能力和各产品的单位利润如下： 问：应如何安排生产计划，可使总利润为最大？试建立此问题的LP模型。,案例1 分析,设X1,X2,X3分别为产品甲,乙,丙的计划日产量，X0为每天的总利润，则： 目标函数：max X0=3X1+2X2+5X3 约束条件： X1+2X2+ X3430 3X1 +2X3460 X1+4X2 420 X1,X2,X30,用Excel求解案例1的输入格式,案例1的计算机求解,设X1,X2,X3分别为产品甲,乙,丙的计划日产量，X0为每天的总利润，则LP模型为： max X0=3X1+2X2+5X3 X1+2X2+ X3430 3X1 +2X3460 X1+4X2 420 X1,X2,X30 使用 Excel 【工具】“规划求解”，可得最优解为： X1*=0，X2*=100，X3*=230，X0*=1350 此外输出的“运算结果报告”还给出了最优解中松弛变量的值，为：S1=S2=0，S3=20，说明第一、二道工序的能力已用完，第三道工序则每天有20分钟的富裕能力。,作业,P52 : 2.2中的(2) 用单纯形法求解：,第十二章 对偶理论(Duality Theory),授课内容 对偶问题(Dual Problem)的提出 线性规划的对偶关系 线性规划的对偶性质 影子价格(Shadow Price),第一节 对偶问题的提出,对偶问题的概念 从经济意义提出的对偶问题,一、对偶问题的概念,内容一致但从相反角度提出的一对问题称为对偶问题,原问题 (Primal Problem),对偶问题 (Dual Problem),内容一致 角度相反,二、从经济意义提出的对偶问题,例1. 某工厂在计划期内要生产产品I和产品II这两种产品，已知生产单位产品所需的设备台时及A、B、c、D两种设备计划期的有效台时，如下表： 问如何安排生产最有利？,y1 y2 y3 y4,生产产品的数学模型,设产品I和产品II的产量分别为x1和x2件, 利润为Z, 则:,Max Z = 2 x1 + 3 x2 2 x1 + 2 x2 12 x1 + 2 x2 8 4x1 + 0 x2 16 0x1 + 4 x2 12 x1 , x2 0,不生产产品(出租设备)的数学模型,设设备A、B、C、D每小时的租金分别为y1 、 y2、 y3、 y4, 则:,2y1 + y2 + 4y3 + 0 y4 2 2y1 + 2 y2 + 0y3 + 4 y4 3 y1 , y2 , y3 , y4 0,W=12y1 + 8y2 + 16y3 + 12 y4,Min,P:原问题,D:对偶问题,y1 y2 y3 y4,第二节 线性规划的对偶关系,例1 写出下列LP问题的对偶问题:,Min Z = 4 x1 + 6 x2 5 x1 + 7 x2 1 3 x1 + 2 x2 9 x1 , x2 0,解:原LP模型变为: Min Z = 4 x1 + 6 x2 -5 x1 -7 x2 - 1 3 x1 + 2 x2 9 x1 , x2 0,对偶问题为:,y1 y2,Max w = - y1 + 9y2 -5y1 + 3y2 4 -7y1 + 2 y2 6 y1 , y2 , 0,第二节 线性规划的对偶关系,例2 写出下列LP问题的对偶问题:,Max Z = 4 x1 + 6 x2 5 x1 + 7 x2 1 3 x1 + 2 x2 9 x1 0 , x2取值无约束,解:原LP模型变为: Max Z = 4 x1 + 6 x2- 6x2 5 x1 + 7 x2- 7x2 1 3 x1 + 2 x2 - 2x2 9 x1 , x2, x2 0,对偶问题为:,y1 y2,Min w = y1 + 9y2 5y1 + 3y2 4 7y1 + 2 y2 6 -7y1 - 2 y2 -6 y1 , y2 , 0,Min w = y1 + 9y2 5y1 + 3y2 4 7y1 + 2 y2 =6 y1 , y2 , 0,原始问题为典则形式的对偶问题,对比上例中的(P)与(D)的LP模型，可以发现两个LP模型中有如下对偶关系： 1. 一个为最大化问题， 约束，另一个为最小化问题， 约束； 2. (P)的一个约束条件对应(D)的一个变量，(P)的一个变量对应(D)的一个约束条件，反之亦然； 3. (P)的约束条件右端常数是(D)的目标函数系数，(P)的目标函数系数是(D)的约束条件右端常数，反之亦然； 4. (P)与(D)的约束条件系数矩阵是互为转置的。,称以下形式的LP模型为典则形式：,(P)：max X0=c1X1+ c2 X2+cn Xn a11X1+a12X2+a1nXnb1 a21X1+a22X2+a2nXnb2 . am1X1+am2X2+amnXnbm Xj0，j=1,2,n,则定义其对偶问题为：,(D)：min Y0 =b1Y1+ b2Y2+ bmYm a11Y1+a21Y2+am1Ymc1 a12Y1+a22Y2+am2Ymc2 . a1nY1+a2nY2+amnYmcn Yi0，i=1,2,m 上述(D)也是典则形式。,例3. 写出下面LP问题的对偶问题,(P) max X0=5X1+6X2 X1+9X260 Y1 2X1+3X245 Y2 5X1-2X220 Y3 X230 Y4 X1，X20 (D) min Y0=60Y1+45Y2+20Y3+30Y4 Y1+2Y2+5Y3 5 9Y1+3Y2-2Y3+Y46 Yi0，i=1,2,3,4,对偶问题的基本性质,一. 对偶问题的基本定理 若(P)和(D)都有可行解，则(P)和(D)都有最优解，且(P)和(D)最优解的目标函数值相等。 二. 可由(P)的最优解中得到(D)的最优解 在用 Excel 软件求得(P)的最优解的同时，软件输出的“敏感性报告”中的“阴影价格”给出的就是各最优对偶变量的值。 例如求解案例1输出的“敏感性报告”中给出的(D)的最优解为：Y1*=1，Y2*=2，Y3*=0。,二、Excel 的“敏感性报告”,求解典例 1 问题的敏感性报告,为最优单纯形迭代中各决策变量检验数的负值， 其含义是若将该非基变量调入基，则每增加一个单位对目标函数值的影响。 2.“可变单元格”下“允许的增量”和“允许的减量” 给出在不影响当前最优解的条件下(基变量的值不变，但目标函数的值会改变)，各决策变量目标函数系数 cj 单独变化时的可变动范围。 可用以分析市场价格或成本、利润的变化对最优解的影响。,1.“可变单元格”下的“递减成本”,3. “约束”下的“阴影价格”,即各资源的“影子价格”。可获得优化配置资源的有关信息。 4. “约束”下“允许的增量”和“允许的减量” 给出在不影响当前最优基的条件下(最优基变量的组成不变，但值会改变；在此条件下各资源的影子价格不变)，各有限资源数量 bi 单独变化时的可变动范围。它同样提供了优化配置资源的有关信息。 要分析各种参数同时变化，或增加新变量、新约束条件后对最优解的影响，则可改变模型中有关参数后重新求解，这在使用软件求解的情况下是非常方便的。,对偶变量的经济含义影子价格,设(P):： max X0 = CjXj s.t： aijXjbi，bi0，i=1,2,m Xj 0，j=1,2,n 并设Y1*,Y2*,Ym*是(D)的最优解，则 max X0 = minY0 = b1Y1*+b2Y2*+bmYm* 上式说明最优对偶解Yi*是第i种有限资源对目标函数的单位贡献，即该资源的价值。当资源i的市场价格低于Yi*时，就应购入一定数量的资源i；反之就应出售一部分资源i。此外，当(P)最优解中某个松弛变量Si0时，则对应的对偶变量Yi*=0，此时无论资源i的市场价格是多少，企业都不应购入而应售出一部分(此时企业的该资源有富裕)。 因此，称Yi*为第i种资源的影子价格。,案例1最优对偶解的经济含义,由求解案例1时输出的“敏感性报告”中，得到(D)的最优解为：Y1*=1，Y2*=2，Y3*=0。 说明该厂第一、二道工序每分钟所提供的利润分别为1和2，如果增加这两道工序的能力所需增加的费用(包括外发加工)分别不超过每分钟1和2，就可适当增加这两道工序的加工能力。但所能增加的数量则需要通过敏感性分析后决定。第三道工序的影子价格为0，说明该道工序能力有多余(多余20分钟/天，即最优解中松弛变量S3的值，在输出的“运算结果报告”中给出)，企业可考虑承接该工序的对外加工业务(至多20分钟/天)。,敏感性分析简介,1.敏感性分析的意义 线性规划的敏感性分析（Sensitivity Analysis）是分析LP模型的各种参数的变化以及增加新的决策变量、新的
