对偶问题与灵敏度分析PPT演示课件

第二章线性规划的对偶理论及其应用,对偶是一种普遍现象,1,2.1线性规划的对偶理论2.1.1线性规划原问题与对偶问题的表达形式,任何线性规划问题都有其对偶问题对偶问题有其明显的经济含义,假设有商人要向厂方购买资源A和B，问他们谈判原料价格的模型是怎样的？,2,例2.1.1,设A、B资源的出售价格分别为y1和y2显然商人希望总的收购价越小越好工厂希望出售资源后所得不应比生产产品所得少,目标函数ming(y)=25y1+15y2,3,2.1.1线性规划原问题与对偶问题的表达形式,4,2.1.1线性规划原问题与对偶问题的表达形式,5,2.1.2标准(max,)型的对偶变换,目标函数由max型变为min型对应原问题每个约束行有一个对偶变量yi，i=1,2,m对偶问题约束为型，有n行原问题的价值系数C变换为对偶问题的右端项原问题的右端项b变换为对偶问题的价值系数原问题的技术系数矩阵A转置后成为对偶问题的技术系数矩阵原问题与对偶问题互为对偶对偶问题可能比原问题容易求解对偶问题还有很多理论和实际应用的意义,6,2.1.3非标准型的对偶变换,7,表2.1.1对偶变换的规则,约束条件的类型与非负条件对偶非标准的约束条件类型对应非正常的非负条件对偶变换是一一对应的,8,2.2线性规划的对偶定理,2.2.1弱对偶定理定理对偶问题(min)的任何可行解Y0，其目标函数值总是不小于原问题(max)任何可行解X0的目标函数值,为了便于讨论，下面不妨总是假设,9,弱对偶定理推论,max问题的任何可行解目标函数值是其对偶min问题目标函数值的下限；min问题的任何可行解目标函数值是其对偶max问题目标函数值的上限如果原max(min)问题为无界解，则其对偶min(max)问题无可行解如果原max(min)问题有可行解，其对偶min(max)问题无可行解，则原问题为无界解注：有可能存在原问题和对偶问题同时无可行解的情况,10,2.2.2最优解判别定理,定理若原问题的某个可行解X0的目标函数值与对偶问题某个可行解Y0的目标函数值相等，则X0,Y0分别是相应问题的最优解证：由弱对偶定理推论1，结论是显然的。即CX0=Y0bCX,Y0b=CX0Yb。证毕。,2.2.3主对偶定理定理如果原问题和对偶问题都有可行解，则它们都有最优解，且它们的最优解的目标函数值相等。证：由弱对偶定理推论1可知，原问题和对偶问题的目标函数有界，故一定存在最优解。现证明定理的后一句话。,11,主对偶定理的证明,证：现证明定理的后一句话。设X0为原问题的最优解，它所对应的基矩阵是B，X0=B1b，则其检验数满足CCBB1A0令Y0=CBB1，则有Y0AC；而对原问题松弛变量的检验数有0CBB1I0，即Y00。显然Y0为对偶问题的可行解。因此有对偶问题目标函数值，g(Y0)=Y0b=CBB1b而原问题最优解的目标函数值为f(X0)=CX0=CBB1b故由最优解判别定理可知Y0为对偶问题的最优解。证毕。该定理的证明告诉我们一个非常重要的概念：对偶变量的最优解等于原问题松弛变量的机会成本即对偶变量的最优解是原问题资源的影子价格,12,2.2.4互补松弛定理,定理设X0,Y0分别是原问题和对偶问题的可行解，U0为原问题的松弛变量的值、V0为对偶问题剩余变量的值。X0,Y0分别是原问题和对偶问题最优解的充分必要条件是Y0U0+V0X0=0证：由定理所设，可知有AX0+U0=bX0,U00(1)Y0AV0=CY0,V00(2)分别以Y0左乘(1)式，以X0右乘(2)式后，两式相减，得Y0U0+V0X0=Y0bCX0若Y0U0+V0X0=0，根据最优解判别定理，X0,Y0分别是原问题和对偶问题最优解。反之亦然。证毕。,13,2.2.4互补松弛定理,Y0U0+V0X0=0有什么应用若(Y0)i0，则(U0)i=0，意味着原问题第i约束行必须为=约束；对(X0)i0亦如此可用来简化问题的求解线性规划的高级算法：利用互补松弛定理，原问题与对偶问题同时解原问题为基础可行解，对偶问题为非可行解，但满足互补松弛条件；则当对偶问题为可行解时，取得最优解,14,2.2.5原问题检验数与对偶问题的解,在主对偶定理的证明中我们有：对偶(min型)变量的最优解等于原问题松弛变量的机会成本，或者说原问题松弛变量检验数的绝对值容易证明，对偶问题最优解的剩余变量解值等于原问题对应变量的检验数的绝对值由于原问题和对偶问题是相互对偶的，因此对偶问题的检验数与原问题的解也有类似上述关系。更一般地讲，不管原问题是否标准，在最优解的单纯型表中，都有原问题虚变量(松弛或剩余)的机会成本对应其对偶问题实变量(对偶变量)的最优解，原问题实变量(决策变量)的检验数对应其对偶问题虚变量(松弛或剩余变量)的最优解。因此，原问题或对偶问题只需求解其中之一就可以了。,15,例2.2.3原问题检验数与对偶问题的解,16,17,18,线性规划原问题与对偶问题的表达形式,19,对偶单纯形算法,基本思想算法过程算例,返回,20,对偶单纯型算法基本思路：,原单纯型迭代要求每步都是基础可行解达到最优解时，检验数cjzj0(max)或cjzj0(min)但对于(min,)型所加的剩余变量无法构成初始基础可行解，因此通过加人工变量来解决大M法和二阶段法较繁能否从剩余变量构成的初始基础非可行解出发迭代，但保证检验数满足最优条件，cjzj0(max)或cjzj0(min)每步迭代保持检验数满足最优条件，但减少非可行度如何判断达到最优解如何保证初始基础解满足最优条件为什么叫对偶单纯型法,21,基本思想,返回,22,23,24,正则解,对偶可行解,25,正则解的单纯性表,26,规划无可行解,保持正则性,27,入基变量,28,29,算法,返回,初始正则解,检查可行,是停止,得最优解,否,选出基变量,检查是否无可行解,是停止,否,30,选入基变量,计算典式检验数,31,迭代步骤,确定出变量找非可行解中最小者，即minbi|bi0，设第i*行的最负，则i*行称为主行，该行对应的基变量为出变量，xi*确定入变量最小比例原则,设j*列满足(2.3.1)式，j*列称为主列，xj*为入变量以主元ai*j*为中心迭代检查当前基础解是否为可行解若是，则当前解即为最优解否则，返回步骤1,32,例6对偶单纯型解法,解：化原问题为适合对偶解法的标准型,33,表2.3.1对偶单纯型法的单纯型表(min),答：最优解为x1=11/5,x2=5/2,x3=x4=x5=0,OBJ=-28/5,34,作业,返回,首先化为标准形式,35,迭代,36,37,38,39,40,最小比例原则,令V=C-CBB-1A为检验数向量对max问题，V0称为正则，即满足最优判定条件可以证明，V的迭代也满足四角运算法则令xr为出变量，在第i*行；若选非基变量xj*为入变量必须满足什么条件才能保证迭代后的解仍为正则的？,因此只需考虑非基变量xj观察出变量xr对应的检验数变化，因为有ai*r=1，故,由于vj*0，故必有ai*j*0时，显然有,结合上述的几个条件，则得到最大比例原则,若ai*j0时，则要求vj-vj*ai*j/ai*j*0,可解出,注：这里的aij都表示当前单纯性表中的技术系数,42,则对偶问题的最优解为,对偶单纯形法的特点：,（1）初始解可以是非可行解，当检验数都为负数时，就可以进行基的变换，这时不需要加入人工变量，因此可以简化计算；,（2）当变量多于约束条件，用对偶单纯形法可以减少计算量，因此对变量较少，而约束条件很多的线性规划问题，可先将它变成对偶问题，然后用对偶单纯形法求解；,（3）对大多数线性规划问题，很难找到一个初始可行基，因此对偶单纯形法在求解线性规划问题时很少单独使用；,（4）在灵敏度分析中，有时需要用对偶单纯形法，使问题的处理简化。,43,灵敏度分析,概况改变价值向量改变右端向量,返回,44,概况,信息的不确定性信息的变化：价值向量市场变化(cj)右端向量资源变化(bj)系数矩阵技术进步(aij)认知的误差分析方法静态分析-比较静态分析-动态分析,45,改变价值向量,一般改变情况改变非基变量的价值向量改变基变量的价值向量技术系数aij的变化算例,46,一般改变,47,非基变量,48,基变量,49,50,算例,返回,51,52,改变右端向量,基本思想算例,53,基本思想,返回,54,55,算例,返回,56,57,58,改变技术系数,基本思想算例,（1）增加新变量,（2）新约束条件,59,基本思想,返回,再用单纯形法,60,算例,返回,见书上68页例9和例10,61,计算软件,LinDoLinGoScilab,返回,62,LinDo,输入模型求解点击求解按钮即可结果,返回,63,输入模型,!注释内容，可用中文!目标函数：最大-max,最小-min,大小写不分max3x1+5x2+4x3!约束，以subjectto开始subjectto2x1+3x2=15002x2+4x3=8003x1+2x2+5x3),=,=与等同变量非负约束可省略结束时以end标示,返回,65,结果,LPOPTIMUMFOUNDATSTEP3OBJECTIVEFUNCTIONVALUE1)2675.000VARIABLEVALUEREDUCEDCOSTX1375.0000000.000000X2250.0000000.000000X375.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0.0000001.0500003)0.0000000.6250004)0.0000000.300000,返回,66,LinGo,输入模型LinDo模式LinGo模式求解点击求解按钮即可结果,返回,67,LinDo输入模式,model:MAX=3*x1+5*x2+4*x3;2*x1+3*x2=1500;2*x2+4*x3=800;3*x1+2*x2+5*x3=2000;end,68,注意与LinDo的区别,目标函数中加等号变量与系数之间用“*”Model:-end可省略,返回,69,LinGo模式,Model:Sets:!定义集合EndsetsData:！定义数据Enddata调用函数与计算end,返回,70,集合部分,model:！开始sets:！定义集合ve/1.3/:c,x;co/1.3/:b;ma(co,ve):a;endsets！注：集表达式：名称/成员/：属性名称（初始集）：属性,返回,71,定义数据,data:！定义数据c=354;ba=230024325;Enddata！注：数据的大小与集合定义中一致，分量中间用空格或逗号分开，数据结束后用分号；,返回,72,调用函数,max=sum(ve(j):c(j)*x(j);for(co(i):sum(ve(j):a(i,j)*x(j)b=1500,800,2000；-a=2,3,0;0,2,4;3,2,5；-c=-c；-x,lagr,f=linpro(c,a,b)f=-2675.lagr=x=!1.05!375.!.625!250.!.3!75.!,返回,79,命令2,x,lagr,f=linpro(p,C,b,ci,cs,x0)问题形式minp*xs.t.C*x=bcib=1500,800,2000；-a=2,3,0;0,2,4;3,2,5；-ci=zeros(c);-cs=300*ones(c);-x,lagr,f=linpro(c,a,b,ci,cs),81,f=-2600.lagr=x=!1.!300.!0.!300.!0.!50.!1.!1.!0.!,返回,82,命令3,x,lagr,f=linpro(p,C,b,ci,cs,me,x0)问题minp*xs.t.C(j,:)x=b(j),j=1,.,meC(j,:)x=b(j),j=me+1,.,me+mdcib=1500,800,2000；-a=2,3,0;0,2,4;3,2,5；-ci=zeros(c);-cs=;-me=1;-x,lagr,f=linpro(c,a,b,ci,cs,me),返回,84,命令4：,x,lagr,f=linpro(p,C,b,ci,cs,me,x0,imp)问题形式minp*xs.t.C(j,:)x=b(j),j=1,.,meC(j,:)x=b(j),j=me+1,.,me+mdcic=-3,5,4,0,0,0；-b=1500,800,2000；-a=2,3,0,1,0,0;0,2,4,0,1,0;3,2,5,0,0,1；-x0=0,0,0,1500,800,2000;-x1,crit=karmarkar(a,b,c,x0),返回,87,注意事项,命令2和3中x0可省略，但命令4和5中不可省略向量都是列向量，参数的顺序不可换命令3中等式约束必须在前面,返回,88,人力资源分配问题,某个中型百货商场对售货人员（周工资200元）的需求经统计如下表为了保证销售人员充分休息，销售人员每周工作5天，休息2天。问应如何安排销售人员的工作时间，使得所配售货人员的总费用最小？,89,模型假设,每天工作8小时，不考虑夜班的情况；每个人的休息时间为连续的两天时间；每天安排的人员数不得低于需求量，但可以超过需求量,90,问题分析,因素：不可变因素：需求量、休息时间、单位费用；可变因素：安排的人数、每人工作的时间、总费用；方案：确定每天工作的人数，由于连续休息2天，当确定每个人开始休息的时间就等于知道工作的时间，因而确定每天开始休息的人数就知道每天开始工作的人数，从而求出每天工作的人数。变量：每天开始休息的人数约束条件：1.每人休息时间2天，自然满足。,91,3.变量非负约束：,92,目标函数：总费用最小，总费用与使用的总人数成正比。由于每个人必然在且仅在某一天开始休息，所以总人数等于,93,模型,94,计算,model:min=200*x1+200*x2+200*x3+200*x4+200*x5+200*x6+200*x7;x2+x3+x4+x5+x6=12;x3+x4+x5+x6+x7=15;x1+x4+x5+x6+x7=12;x1+x2+x5+x6+x7=14;x1+x2+x3+x6+x7=16;x1+x2+x3+x4+x7=18;x1+x2+x3+x4+x5=19;end,95,Globaloptimalsolutionfoundatiteration:9Objectivevalue:4400.000VariableValueReducedCostX15.0000000.000000X22.0000000.000000X38.0000000.000000X40.0000000.000000X54.0000000.000000X60.00000066.66667X73.0000000.000000,96,注解,该问题本质上是个整数规划问题，放松的线性规划的最优解是个整数解，所以两规划等价。定义整数变量用函数gin(x1)gin(x7);0-1整数变量为bin(x1),返回,97,配料问题,某化工厂要用三中原料混合配置三种不同规格的产品各产品的规格单价如表1，,98,问