《线性规划进一步研究ppt培训课件》由会员分享，可在线阅读，更多相关《线性规划进一步研究ppt培训课件（76页珍藏版）》请在金锄头文库上搜索。
1、第二章 线性规划进一步研究,第一节 对偶问题 (Dual Problem),线性规划早期发展过程中的最为重要的理论成果之一就是线性规划的对偶问题及相关理论的提出。线性规划的对偶理论解释资源的影子价格、线性规划问题的灵敏度分析等的理论基础。,一、对偶问题的提出,例1 （生产计划问题）某企业利用A、B、C三种资源，在计划期内生产甲、乙两种产品，已知生产单位产品资源的消耗、单位产品利润等数据如下表，问如何安排生产计划使企业利润最大？,决策变量：x1、x2分别代表甲、乙两种产品的生产数量。 即有数学模型（问题A）： 问题A max z=50x1+100x2x1 + x23002x1 + x2400x2
2、250x1、x20 称之为上述问题的数学模型。同样是上述问题，提问：企业不安排生产，而转让三种资源，应如何给三种资源定价？,决策变量：y1、y2、y3分别代表A、B、C三种资源的价格（最低转让净收入）。 约束条件1：生产一件产品甲所耗资源数量转让所得净收入不能低于一 件产品甲所获利润，即：1y1+ 2y2 50 约束条件2：生产一件产品乙所耗资源数量转让所得净收入不能低于一 件产品乙所获利润，即：1y1+ 1y2+ 1y3 100 目标函数为：w=300y1 +400y2 +250y3 即有 w=300y1 +400y2 +250y3y1+ 2y2 50y1+ y2+ y3 100y1、y2、
3、y3 0,从数学和经济的角度分析，该问题的目标函数只能极小，即该问题的数 学模型为： 问题B min w=300y1 +400y2 +250y3y1+ 2y2 50y1+ y2+ y3 100y1、y2、y3 0 称问题B为问题A的对偶问题，问题A为原问题。 问题A max z=50x1+100x2x1 + x23002x1 + x2400x2250x1、x20,定义2.1 设有线性规划问题max z=CXAXbX0 其对偶问题定义为min w=YbYACY0 且前者称为原问题，后者称为对偶问题。,二、对偶问题的定义,具体的数量对应关系为,原问题 max z=c1x1+c2x2+cnxn a1
4、1x1+a12x2+a1nxn b1a21x1+a22x2+a2nxn b2 am1x1+am2x2+amnxn bmx1，x2，xn0 对偶问题 min w =b1y1+b2y2+bmyma11y1+a21y2+am1ym c1a12y1+a22y2+am2ym c2 a1ny1+a2ny2+amnym cny1，y2，ym0,根据对偶问题的定义不难推出，对于线性规划问题：min w=Yb；YAC；Y0 其对偶问题为：max z=CX；AXb；X0 即两线性规划问题互为对偶。 事实上，任一线性规划问题都有一个固定的线性规划问题与之对偶，且二者互为对偶关系，线性规划的这种性质称为对称性。 更进
5、一步有，对于线性规划问题：max z=CX；AX = b，X0 其对偶问题为：min w=Yb；YAC，Y无限制,根据以上分析，线性规划原问题与对偶问题的数量关系可用下表描述。,例2.1 写出下列线性规划问题的对偶问题max z=2x1+2x24x3x1 + 3x2 + 3x3 304x1 + 2x2 + 4x380x1、x2，x30,解：其对偶问题为 min w=30y1+ 80y2y1 + 4y2 2 3y1 + 2y2 2 3y1 + 4y2 4y1、y20,例2.2 写出下列线性规划问题的对偶问题min z=2x1+8x24x3x1 + 3x23x3 30x1 + 5x2 + 4x3
6、= 804x1 + 2x24x350x10、x20，x3无限制 解：其对偶问题为,max w=30y1+80 y2+50 y3 y1 y2 + 4 y3 23y1+5y2 + 2y3 83y1 + 4y24y3 =4y10，y2无限制，y30,一、单纯形法的矩阵描述 设有线性规划问题 max z=CX AXb X0 加上松弛变量XS=（xn+1，xn+2，xn+m）T，将其化为标准形式得到 max z=CX+0XS AX+I XS = b X0，XS0 其中 I为mm阶单位阵。,第二节 对偶理论 (Duality Theory),设A中存在一可行基B，相应的变量X分成基变量XB和非基变量XN，
7、价格系数C也相应地分成CB和CN两部分，A阵也分成B、N两部分，即A=（B，N），X=（XB，XN）T，C=（CB，CN） 这样因而有 BXB+NXN + I XS = b 即 XB = B-1bB-1NXNB-1XS 用非基变量XN表示目标函数有= CBXB+CNXN+0XS,将XB = B-1bB-1NXNB-1XS代入得z = CB（B-1bB-1NXNB-1XS）+CNXN+0XS= CBB-1b+（CNCBB-1N）XNCBB-1XS 令 XN=0，XS=0 得到对应于基B的基可行解X=（XB，XX，XS）T=（B-1b，0，0）T 目标值为 z = CBB-1b 相应的非基变量的检
8、验数为N=（CNCBB-1N，CBB-1） 若将基变量一起考虑有=（0，CNCBB-1N，CBB-1）=（CCBB-1A，CBB-1） 此外，从上式中可推出计算某一具体变量xj的检验数计算公式，即j=cjCBB-1pj,由最优性判别定理可知，当=（CCBB-1A，CBB-1）0时， X=（XB，XX，XS）T=（B-1b，0，0）T为线性规划的最优解；若存在j=cjCBB-1pj0，（jJ），有B-1pj0，则线性规划问题有无界解。,上述过程可用如下单纯形表描述。,定理2.1(弱对偶定理) 设X(0)是原问题max z=CX，AXb，X0的可行解Y(0)是其对偶问题min w=Yb，YAC，Y
9、0的可行解 则 CX（0）Y（0）b。 原问题任一可行解对应的目标函数值不大于其对偶问题的任一可行解对应目标函数值?,二、对偶问题基本定理,定理2.2(最优性定理) 设X(0)是原问题max z=CX，AXb，X0的可行解，Y（0）是其对偶问题min w=Yb，YAC，Y0的可行, 若 CX（0）= Y（0）b， 则 X（0）、Y（0）分别是它们的最优解。 定理2.3(对偶定理) 若原问题max z=CX，AXb，X0有最优解， 则其对偶问题min w=Yb，YAC，Y0 一定有最优解， 且二者的目标函数值相等。 定理2.4(互补松弛定理) 原问题max z=CX，AXb，X0及其对偶问题mi
10、n w=Yb，YAC，Y0 的可行解X（0）、Y（0）是最优解的充要条件是Y（0）XS = 0 ； YSX（0）= 0其中，XS、YS分别是原问题松弛变量向量和对偶问题剩余变量向量。,例2.3 已知线性规划问题max z=x1+2x2+3x3+4x4x1 + 2x2 + 2x3 +3x4202x1 + x2 + 3x3 +2x420x1、x2，x3，x40 解：其对偶问题为min w=20y1+ 20y2y1 + 2y2 1 （1）2y1 + y2 2 （2）2y1 +3y2 3 （3）3y1 +2y2 4 （4）y1、y202x3* +3x4* = 203x3* +2x4* = 20 解得x
11、3* = x4* = 4。故原问题的最优解为X*=（0，0，4，4）T,其对偶问题的最优解为y1*=6/5，y2*=1/5。试用互补松弛定理求该线性规划问题的最优解。,将y1*=6/5，y2*=1/5代入上述约束条件，得（1）、（2）为严格不等式；由互补松弛定理可以推得x1*=0，x2*=0。又因y1*0，y2*0，故原问题的两个约束条件应取等式，所以,定理2.5 原问题单纯形表的检验数行对应对偶问题的一个基本解。 该定理的进一步解释有：若原问题最优解存在，则原问题最优单纯形表的检验数行中，松弛变量或剩余变量的检验数对应对偶问题的最优解。 例2.4 （原问题为极大化问题） 对于原问题：max
12、z=50x1+100x2x1 + x23002x1 + x2400x2250x1、x20 其对偶问题为：min w=300y1 +400y2 +250y3y1+2y2 50y1+ y2+ y3 100y1、y2、y3 0,表中x3、x4、x5为松弛变量； 原问题最优解为：X*=（500，250）T， z*=27500 对偶问题的最优解为：Y*=（y1*，y2*，y3*）=（50，0，50）， w*=27500,解 原问题最优单纯形表如表所示，对应的对偶问题最优解列于表中最后一行。,例2.5 （原问题为极小化问题） 对于原问题：min z=2x1+ 3x2 x1 + x2350 x1 125 2
13、x1 +x2600 x1、x20 其对偶问题为： max w=350y1 +125y2 +600y3 y1+ y2 +2y3 2 y1+ y3 3 y1、y20、y3 0,解 用以极小化为标准形式的单纯形法求得原问题最优单纯形表如下表所示，对应的对偶问题最优解列于表中最后一行。,表中x3、x4为剩余变量，x5为松弛变量； 原问题最优解为：X*=（250，100）T， Z*=800 对偶问题的最优解为：Y*=（y1*，y2*，y3*）=（4，0，1），w*=800,从上述两个例子可以总结出：对偶问题的最优解对应原问题最优单纯形表中松弛变量检验数的相反数或剩余变量的检验数。,一、资源的影子价格(S
14、hadow Price)如前所述，若X*为线性规划max z=CX，AXb，X0的最优解，则z*=CX*；若Y*为其对偶问题的最优解，则有w*=Y*b。根据对偶定理有z*=w*即 z*=Y*b因此 即 由此可以看出，对偶问题的最优解实际上是右端常数项的单位变化所引起的目标值的变化；,第三节 对偶问题的经济意义,若原问题描述的是资源有限条件下最优生产决策问题，则其对偶问题的最优解yi*(i=1,，m)表示第i种资源在最优生产决策下的边际值，即若其他条件不变，增加单位第i种资源将会使目标函数值增加yi*。 其经济意义是：yi*描述了第i种资源在具体生产中的一种估价，这种估价不同于该种资源的市场价格
15、，而是该种资源在给定条件某生产的最优生产方案下的一种实际存在而又看不见的真实价值，因此称之为影子价格（shadow price）。,同一种资源在不同的生产条件或不同的范围可能有不同的影子价格； 产品的市场价格变化，资源的影子价格也会发生变化； 资源的数量结构不同，资源的影子价格也不同。,资源的影子价格是针对具体生产或具体企业而言的,与资源的市场价格比较以决定是否安排生产或转让资源或提高产品的价格； 革新可以提高资源的影子价格； 可以指导管理部门对紧缺资源进行“择优分配”； 帮助预测产品的价格。因此，产品的价格应在“成本”和影子价格之间； 影子价格的高低可以作为同类企业经济效益的评估标准之一。,影子价格对于拥有资源的决策者有非常重要的作用,对于目标函数极小化约束条件为大等号的问题min z=CX，AXb，X0，其右端常数项可理解为需要完成的任务。因此，该类线性规划一般为描述完成一定任务使耗费的资源最小的问题。此时，其对偶问题的最优解yi*(i=1,，m)表示第i种任务的边际成本，即单位任务的增加引起的资源耗费的增加量。,
