二 对偶问题PPT课件

1、.,1,某工厂用三台设备生产两种产品，已知的条件如表所示，试制订总利润最大的生产计划,引例1 生产计划问题,换一角度：将设备卖出，售价定为多少适宜？,原问题,对偶问题,.,2,两个互为对偶规划问题之间的关系（对称形式）,1）目标函数的目标互为相反。(max,min) 2）目标函数的系数是另一个约束条件右端的向量 3）约束系数矩阵是另一个的约束系数矩阵的转置 4）约束方程的个数与另一个的变量的个数相等,.,3,max 限定向量b 价值向量C m个约束，n个变量 约束条件“” 变量“”,原问题,对偶问题,min 价值向量 限定向量 n个约束，m个变量 变量“” 约束条件“”,对称式对偶,.,4,m

2、ax 限定向量b 价值向量C m个约束，n个变量 约束条件“=”,原问题,对偶问题,min 价值向量 限定向量 n个约束，m个变量 变量自由变量,非对称式对偶,.,5,目标函数max,原问题（对偶问题）,对偶问题（原问题）,目标函数min,目标函数中变量的系数,约束条件右端项,约束条件右端项,目标函数中变量的系数,.,6,例2：给出下列线性规划的对偶问题： min Z=2X1+ 8 X2 -4X3 X1+3X2 3X3 =30 -X1 +5X2 + 4X3 =80 st. 4X1+ 2X2 -4X3 =0, X3 无约束 其对偶问题为： MAX w=30 y1 +80 y2 +50y3 y1

3、- y2 +4y3 =2 st. 3 y1 +5y2 +2 y3 =0, y2 无约束，y3 =0,.,7,一、对称性定理 对偶问题的对偶是原问题。,2.3对偶问题基本性质,二、弱对偶定理,原问题,对偶问题,如果 分别是（1）和（2）的可行解，则有 。,三、最优性定理,如果 分别是(1)和(2)的可行解，且有 ，则 分别是(1)和(2)的最优解.,.,8,四、强对偶定理,原问题,对偶问题,五、无界性定理,对于一对对偶问题，其中一个有有限最优解，则另一个也有最优解，且两个目标函数值相等。,对于一对对偶问题，若一个有无界解，则另一个无可行解。,.,9,例 3 已知原问题,其对偶问题为：,试估计它们

4、的目标函数值的界，并验证弱对偶定理的正确性。,.,10,，,且原问题的目标函数值,对偶问题的目标函数值,并且我们知对偶问题的目标函数值,原问题的目标函数值,.,11,六、互补松弛性定理,利用互补松弛定理,在已知一个问题的最优解的情况下,可以不要列单纯形表求出另一个的最优解.,.,12,例4：已知线性规划问题,要求：1）写出对偶问题； 2）已知原问题的最优解为x1= -5, x2=0, x3= -1; 试根据对偶理论直接求出对偶问题最优解。,.,13,解：1）对偶问题,2）由互补松弛定理，因原问题最优解中x1= -50, 必使对偶问题第一个约束条件为等式，于是有，,.,14,例 5:已知下列线性

5、规划问题的对偶问题的最优解为(6/5, 1/5),求该线性规划问题的最优解.,其对偶问题为：,.,15,原问题的松弛变量为: X5 , X6 , 对偶问题的剩余变量为: Y3,Y4, Y5,Y6, 将(6/5,1/5)代入1)和2)知: Y3,Y4, 均不为0,于是由松弛互补定理知: X1, X2 , =0 又由 Y10,Y20和松弛互补定理知: X5 , X6 ,=0 从而,原问题的约束变为: 2X3 + 3X4 =20 3X3 + 2X4 =20 解此方程得: X3 = X4 =4 于是原问题的最优解为:(0,0,4,4),.,16,七、单纯形表的双重含义 例6：用单纯形法，解线性规划，

6、（LP1）maxZ=2X1+ X2 5 X2=0, X2=0 对偶问题为: （LP2） min W=15Y1+24Y2+5Y3 6Y2+Y3=2 ST. 5Y1+2Y2+Y3=1 Y1=0,Y2=0,.,17,检验数全部0,于是得到最优解为,X=(7/2,3/2,15/2,0,0) ,最优值为:Z=17/2, 把松弛变量的检验数的相反数(0,1/4,1/2)带入对偶问题中,看有什么规律?,.,18,1、松弛变量与对偶变量的乘积有什么关系？ 松弛变量与对偶变量的乘积=0 2、对偶问题的最优解与什么对应？ 对偶问题的最优解是原问题松弛变量检验数的相反数. 结论：将原始单纯形表中松弛变量的检验数反号

7、恰好得对应对偶问题的一个解。,.,19,事实上，我们把原始问题写成,（1）,其对偶问题写成,其中,其中,.,20,所对应的检验数分别为：,令,这时两组检验数分别为：,和,.,21,再根据问题（2），这两组检验数可分别记为,上述对应关系如表,.,22,2.在获得最优解之前， ，及 的各分量中至少有一大于零，即,即 ,重要结论： 1.原始问题的单纯形表中，原始问题的松弛变量的检验数对应于对偶问题的决策变量，而原始问题的决策变量的检验数对应于对偶问题的松弛变量，只是符号相反；,此时对偶问题也同时获得最优解。,和,当原始问题获得最优解时，表明,.,23,2.4 影子价格,一、影子价格的含义 根据资源在

8、生产中作出的贡献而作的估 价。,是对第i 种资源实现最大利润的一种估计， 是对偶问题的最优解。,二、影子价格的特点,1.区别于市场价格，市场价格相对稳定；而影子价格不稳定，依赖于资源的利用。,.,24,2. 影子价格是一种边际价格。,3. 影子价格是一种机会成本。,4. 互补松弛定理指出： 当某种资源未被充分利用，则该种资 源的影子价格为0；而当资源的影子价格不 为0时，表明该种资源已耗尽。,5. 检验数的经济学含义。,第j种产品的 单位产值,是生产该产品所耗用的各种资源的影子价格，即隐含成本。,.,25,对偶问题的经济意义,1.影子价格:b代表资源的拥有量，Y代表在资源最优利用条件下对单位资

9、源的估价，但不是市场价，而是对资源在生产中做出的贡献的估价(即企业的生产效率)，一般称为影子价格。市场价格是已知的，而影子价格则与资源的利用情况有关，利用的高，影子价格就高，反之亦然。 2.影子价格是一种边际价格，或者边际贡献，即每增加一个单位的资源时在最优利用的条件下，目标函数的增量。在最优条件下, Z=Yb,目标函数是资源量的函数,.,26,3.影子价格又是一种机会成本。减少一件产品，可以节省的资源。Z=cx=yb,在Y确定后,当X变化时,b也跟着变化. 4.当市场价大于影子价格，卖出资源；当市场价小于影子价格，买入资源，组织生产； 5.如果Y中有分量=0，(即松弛变量0)则表示对应的资源

10、没有得到充分利用;所有分量都0(即松弛变量=0)表示资源已消耗尽。 6. 利用影子价格可以有效控制和使用资源，例如对紧缺资源的控制(择优分配);作为同类企业经济效益的评估标准;通过帮助企业提高工艺和管理水平,降低资源的耗费来提高资源的影子价格。,.,27,2.5 对偶单纯形法,.,28,小结：在单纯形表格中 1.得到原问题的基本可行解的同时，其检验数的相反数就构成了对偶问题的一个基本解。,2. 原 对 松弛变量 决策变量 决策变量 剩余变量 基变量 非基变量 非基变量 基变量,.,29,是,否,换基,再确定入基变量：,先确定出基变量：bl=minbibi0，则对应 xl出基；,则对应 xk入基

11、。,对偶单纯形法步骤：,.,30,0 0,-15 -24 -5 0 0,基,-15 -24 -5 0 0,0 -5,-6 -2,-1 -1,1 0,0 1,-2 -1,-24 0,-15 0 -1 -4 0,-24 -5,-15/2 0 0 -7/2 -3/2,Min问题,.,31,Max问题,.,32,单纯形法 （1）保持原问题的可行性，即 （2）最优性： 即使对偶问题达到可行； （3）同时得到原问题与对偶问题最优解,对偶单纯形法 （1）保持对偶问题的可行性，即 （2）最优性： 即使原问题达到可行； （3）同时得到原问题与对偶问题最优解,.,33,从以上求解过程可以看到对偶单纯形法有以下优点

12、：,(1) 初始解可以是非可行解，当检验数都为负数时就可以进行基的变换，这时不需要加入人工变量，因此可以简化计算。 (2) 当变量多于约束条件，对这样的线性规划问题用对偶单纯形法计算可以减少计算工作量，因此对变量较少，而约束条件很多的线性规划问题，可先将它变换成对偶问题，然后用对偶单纯形法求解。 (3) 在灵敏度分析及求解整数规划的割平面法中，有时需要用对偶单纯形法，这样可使问题的处理简化。对偶单纯形法的局限性主要是，对大多数线性规划问题，很难找到一个初始可行基，因而这种方法在求解线性规划问题时很少单独应用。,.,34,引例：某厂生产A、B两种产品，其所需劳动力、材料、设备等有关数据见表。要求

13、确定获利最大的生产计划？,建立数学模型：设x1, x2为A,B产品的产量，则,1）A,B两种产品利润改变； 2）增加了材料； 3）开发新项目，增加一新产品C; 4）技术革新，改变B产品的工艺； 5）对两种产品增加一道新工序；,是否影响原最优解呢？,如发生变化：,.,35,2.6 灵敏度分析,灵敏度分析：,指对系统或事物因周围条件变化显示出来的敏感程度分析。,所研究的问题：,参数A、b、C一个或几个发生变化，最优解如何？以及在多大范围内变化，最优解不变？,.,36,.,37,1.目标函数系数变为,2.第二个约束条件右端项变为32；,3.增加一个新的变量,4.,5. 增加一个约束条件,作如下灵敏度

14、分析：,.,38,.,39,基,2 1 0 0 0,0 1 0,0 0 1,1 0 0,5/4 1/4 -1/4,-15/2 -1/2 3/2,15/2 7/2 3/2,0 2 1,0 0 0 -1/4 -1/2,最终表,1.5 2,1.5 2,0 0 0 1/8 -9/4,0 1.5 2,0 0 -1/10 0 -3/2,方法：1.将Cj的变化体现在最终表上； 2.用变化后的数据重新计算检验数； 3.若所有检验数0，原最优解不变，否则用单纯形法继续迭代。,.,40,基,2 1 0 0 0,0 1 0,0 0 1,1 0 0,5/4 1/4 -1/4,-15/2 -1/2 3/2,15/2 7

15、/2 3/2,0 2 1,0 0 0 -1/4 -1/2,最终表,35/2 11/2 -1/2,0 2 0,0 -1 0 0 -2,方法：1. 找出原问题的最优基的逆B-1； 2. 求出X/B =B-1b/ ; 3.若X/B 0，原最优基不变，最优解变为X/B ；否则将变化后的X/B反映在最终表的b列，用对偶单纯形法继续迭代。,.,41,基,2 1 0 0 0,0 1 0,0 0 1,1 0 0,5/4 1/4 -1/4,-15/2 -1/2 3/2,15/2 7/2 3/2,0 2 1,0 0 0 -1/4 -1/2,最终表,0 2 3,0 -1/2 0 -1/8 -5/4 0,3,-7 0

16、 2,1,方法：1. 找出原问题的最优基的逆B-1； 2. 求出 ,计算检验数 3.若 ，原最优解不变；否则将用单纯形法继续迭代。,.,42,基,2 1 0 0 0,0 1 0,0 0 1,1 0 0,5/4 1/4 -1/4,-15/2 -1/2 3/2,15/2 7/2 3/2,0 2 1,0 0 0 -1/4 -1/2,最终表,11/2 1/2 1/2,0 2 3,0 0 0 1/2 -5,3,3,1 0 0,9 0 0 -1 -4 24,0 0 -M -4M+1/2 24M-5 0,.,43,基,2 1 0 0 0,0 1 0,0 0 1,1 0 0,5/4 1/4 -1/4,-15/

17、2 -1/2 3/2,15/2 7/2 3/2,0 2 1,0 0 0 -1/4 -1/2,最终表,0 x6 12 3 2 0 0 0,0 x6 0 0 0 1 0,0 0 0 -1/4 -1/2 0,0 x6 -3/2 0 0 0 -1/4 -3/2 1,.,44,灵敏度分析的步骤,1.将参数的改变计算反映到最终单纯形表中； 2.检查原问题是否可行，即bi0; 3.检查对偶问题是否可行，即j0; 4.按表所列决定继续迭代的步骤： 原问题 对偶问题 步骤 可行解 可行解 仍为问题最优解 可行解 非可行解 用单纯形法迭代 非可行解 可行解 用对偶单纯形法迭代 非可行解 非可行解 引入人工变量构造可行基,.,45,1.目标函数系数变为,2.第一个约束条件右端项变为3；,3.增加一个约束条件,.,46,引例：某厂生产A、B、C三种产品，其所需劳动力、材料等有关数据见表。要求： 1）确定获利最大的生产计划；2）产品A的利润在什么范围内变动时，上述最优计划不