运筹学第2章1：线性规划的对偶理论及其应用

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,第二章线性规划的对偶理论及其应用,窗含西岭千秋雪，门泊东吴万里船,对偶是一种普遍现象,2.1 线性规划的对偶理论,2.1.1,线性规划原问题与对偶问题的表达形式,任何线性规划问题都有其对偶问题,对偶问题有其明显的经济含义,假设有商人要向厂方购买资源,A,和,B，,问他们谈判原料,价格的模型是怎样的？,2,例2.1.1,设,A、B,资源的出售价格分别为,y,1,和,y,2,显然商人希望总的收购价越小越好,工厂希望出售资源后所得不应比生产产品所得少,目标函数,min,g,(,y,)=25,y,1,+15,y,2,3,2.1.1 线性规划原问题与对偶问题的表达形式,4,2.1.1 线性规划原问题与对偶问题的表达形式,5,2.1.2,标准,(,max,),型的对偶变换,目标函数由,max,型变为,min,型,对应原问题每个约束行有一个对偶变量,y,i,，,i,=1,2,m,对偶问题约束为 型，有,n,行,原问题的价值系数,C,变换为对偶问题的右端项,原问题的,右端项,b,变换为对偶问题的,价值系数,原问题的技术系数矩阵,A,转置后成为对偶问题的技术系数矩阵,原问题与对偶问题互为对偶,对偶问题可能比原问题容易求解,对偶问题还有很多理论和实际应用的意义,6,2.1.3,非,标准,型的对偶变换,7,表,2.1.1 对偶变换的规则,约束条件的类型与非负条件对偶,非标准的约束条件类型对应非正常的非负条件,对偶变换是一一对应的,8,2.2 线性规划的对偶定理,2.2.1 弱,对偶定理,定理,对偶问题,(,min),的任何可行解,Y,0,，,其目标函数值总是不小于原问题,(,max),任何可行解,X,0,的目标函数值,为了便于讨论，下面不妨总是假设,9,弱,对偶定理推论,max,问题的任何可行解目标函数值是其对偶,min,问题目标函数值的下限；,min,问题的任何可行解目标函数值是其对偶,max,问题目标函数值的上限,如果原,max(min),问题为无界解，则其对偶,min(max),问题无可行解,如果原,max(min),问题有可行解，其对偶,min(max),问题无可行解，则原问题为无界解,注,：存在原问题和对偶问题同时无可行解的情况,10,2.2.2 最优解判别,定理,定理,若原问题的某个可行解,X,0,的目标函数值与对偶问题某个可行解,Y,0,的目标函数值相等，则,X,0,Y,0,分别是相应问题的最优解,证,：由弱对偶定理推论1，结论是显然的。,即,CX,0,=,Y,0,b,CX,Y,0,b,=,CX,0,Yb,。,证毕,。,2.2.3 主对偶,定理,定理,如果原问题和对偶问题都有可行解，则它们都有最优解，且它们的最优解的目标函数值相等。,证,：由弱对偶定理推论1可知，原问题和对偶问题的目标函数有界，故一定存在最优解。,现证明定理的后一句话。,11,主对偶,定理的证明,证,：现证明定理的后一句话。,设,X,0,为原问题的最优解，它所对应的基矩阵是,B,，,X,0,=,B,1,b,，,则其检验数满足,C,C,B,B,1,A,0,令,Y,0,=,C,B,B,1,，,则有,Y,0,A,C,。,显然,Y,0,为,对偶问题的可行解。因此有对偶问题目标函数值，,g,(,Y,0,)=,Y,0,b,=,C,B,B,1,b,而原问题最优解的目标函数值为,f,(,X,0,)=,CX,0,=,C,B,B,1,b,故由最优解判别定理可知,Y,0,为对偶问题的最优解。,证毕,。,该定理的证明告诉我们一个非常重要的概念：,对偶变量的最优解等于原问题松弛变量的机会成本,即对偶变量的最优解是原问题资源的,影子价格,12,2.2.4 互补松弛,定理,定理,设,X,0,Y,0,分别是原问题和对偶问题的可行解，,U,0,为原问题的松弛变量的值、,V,0,为对偶问题剩余变量的值。,X,0,Y,0,分别是原问题和对偶问题最优解的充分必要条件是,Y,0,U,0,+,V,0,X,0,=,0,证,：由定理所设，可知有,A X,0,+U,0,=,b X,0,U,0,0,(1),Y,0,A,V,0,=,C Y,0,V,0,0,(2),分别以,Y,0,左乘(1)式，以,X,0,右乘(2)式后，两式相减，得,Y,0,U,0,+,V,0,X,0,=Y,0,b,C X,0,若,Y,0,U,0,+,V,0,X,0,=,0，,根据,最优解判别定理，,X,0,Y,0,分别是原问题和对偶问题最优解。反之亦然。,证毕,。,13,2.2.5 原问题检验数与对偶问题的解,在主对偶定理的证明中我们有：对偶(,min,型)变量的最优解等于原问题松弛变量的机会成本，或者说原问题松弛变量检验数的绝对值,容易证明，对偶问题最优解的剩余变量解值等于原问题对应变量的检验数的绝对值,由于原问题和对偶问题是相互对偶的，因此对偶问题的检验数与原问题的解也有类似上述关系。,更一般地讲，不管原问题是否标准，在,最优解的单纯型表中，都有原问题,虚变量,(松弛或剩余)的检验数对应其对偶问题,实变量,(对偶变量)的最优解,，,原问题,实变量,(决策变量)的检验数对应其对偶问题,虚变量,(松弛或剩余变量)的最优解。因此，原问题或对偶问题只需求解其中之一就可以了。,14,例2.2.3 原问题检验数与对偶问题的解,15,16,17,2.3 对偶单纯型算法,2.3.1 基本思路,原单纯型迭代要求每步都是基础可行解,达到最优解时，检验数,c,j,z,j,0(max),或,c,j,z,j,0(min),但对于(,min,),型所加的剩余变量无法构成初始基础可行解，因此通过加人工变量来解决,大,M,法和二阶段法较繁,能否从剩余变量构成的初始基础非可行解出发迭代，但保证,检验数满足最优条件，,c,j,z,j,0(max),或,c,j,z,j,0(min),每步迭代保持,检验数满足最优条件，但减少非可行度,如何判断达到最优解,如何保证初始基础解满足最优条件,为什么叫对偶单纯型法,b,=,B,1,b,0,18,2.3.2 迭代步骤,确定出变量,找非可行解中最小者，即,min,b,i,|,b,i,0，,设第,i,*,行的最负，则,i,*,行称为,主行,，该行对应的基变量为,出变量,，,x,i,*,确定入变量,最大比例原则,设,j*,列满足(2.3.1)式，,j*,列称为,主列,，,x,j,*,为,出变量,以主元,a,i,*j*,为中心迭代,检查当前基础解是否为可行解,若是，则当前解即为最优解,否则，返回,步骤 1,19,例2.3.1 对偶单纯型解法,解,：化原问题为适合对偶解法的标准型,20,表2.3.1 对偶单纯型法的单纯型表(,min),答,：最优解为,x,1,=14,x,3,=8,x,2,=,x,4,=0,OBJ,=14,21,习 题 课,学而时习之，不亦乐乎,论语,第 1 题,解,：设车间,1,生产,x,1A,单位,A,、,生产,x,1B,单位,B,；,设车间,2,生产,x,2A,单位,A,、,生产,x,2B,单位,B,；,设车间,3,生产,x,3A,单位,A,、,生产,x,3B,单位,B,；,则有生产安排最优化的模型如下,：,23,第 2 题,解：,设,x,1A,为饮料甲中,A,的总含量(升),设,x,2A,为饮料乙中,A,的总含量(升),设,x,3A,为饮料丙中,A,的总含量(升),设,x,1B,为饮料甲中,B,的总含量(升),设,x,2B,为饮料乙中,B,的总含量(升),设,x,3B,为饮料丙中,B,的总含量(升),设,x,1C,为饮料甲中,C,的总含量(升),设,x,2C,为饮料乙中,C,的总含量(升),设,x,3C,为饮料丙中,C,的总含量(升),则有模型如下：,24,25,第 3、4 题,原问题,：,标准型,：,对偶问题：,26,