运筹学04对偶问题和灵敏度分析

复习上次内容：人工变量法,单纯形表的矩阵表达形式,3线性规划的对偶问题的提出,矩阵形式,实际问题提出：某厂生产甲、乙两种产品，产量、利润、设备台时如下模型所示,甲产品：获利2元乙产品：获利3元,从另一个角度讨论这个问题：工厂决定转让设备并出让原材料收取租金，如何确定租价？设y1为出租单位设备台时的租价，y2，y3分别出让单位原材料、的附加额。,为什么目标取最小？租金定的越高就不会有人来租，问题就没有实际意义，工厂和接受者都愿意的条件为上述规划问题的解。其中Y=（y1，y2，y3）,每个线性规划都有另一个线性规划(对偶问题)与它密切相关，对偶理论揭示了原问题与对偶问题的内在联系。,理论上,因为Yb的上界为无限大,所以b只能有最小值。,4线性规划的对偶理论,原问题与对偶问题的数学模型,原问题标准形式：,对偶问题标准形式：,标准对偶问题,标准形式下原问题与对偶问题的对应关系,根据下表写出原问题与对偶问题的表达式,如果原问题约束条件是等式约束,原问题中的价值向量与对偶问题中的资源向量对换（上下对换）原问题:X在C和A的右边;对偶问题:Y在b和A的左边（左右对换）,对偶问题的基本性质和基本定理1.对称性定理：对偶问题的对偶是原问题证明：,2.弱对偶性定理若X（0）和Y（0）分别是原问题和对偶问题的可行解，则有CX（0）Y（0）b,3.若原问题（对偶问题）为无界解，则其对偶问题（原问题）无可行解。(逆命题未必成立)由弱对偶定理可证得,证明:因为X（0）是原问题的可行解，故有AX（0）b。又因为Y(0)是对偶问题的可行解，则有Y（0）AX（0）Y（0）b,及Y（0）AC故CX（0）Y（0）AX（0）Y（0）b亦即CX（0）Y（0）b证毕,4.最优性定理若X（0）和Y（0）分别是原问题和对偶问题的可行解，且有CX（0）=Y（0）b,则X（0）和Y（0）分别是原问题和对偶问题的最优解。,证明：设X是原问题任一可行解，Y（0）是对偶问题的可行解，根据弱对偶性定理，有CXY（0）b因为CX（0）=Y（0）b，故CXCX（0），即X（0）是原问题的最优解。设Y为对偶问题的任一可行解，同理有YbY（0）b即Y（0）是对偶问题的最优解。,5.对偶定理有一对对偶的线性规划问题，若其中有一个有最优解，则另一个也有最优解，且相应的目标函数值相等。,证明：设X（0）是原问题的最优解，对应的基矩阵为B,非基变量的检验数为CN-CBB-1N0全体检验数C-CBB-1A0，即CCBB-1A令Y（0）=CBB-10，则有Y（0）AC即Y（0）是对偶问题的可行解。由于z=CX（0）=CBXB（0）=CBB-1b=Y（0）b（目标值相等）由最优性定理可知Y（0）为对偶问题的最优解。,综上，一对对偶问题的解必然下列情况之一：,1、原问题和对偶问题都有解，且目标函数值相等，原问题的最优解是其对偶问题的最优解。2、一个问题具有无界解，另一个问题无可行解3、一个问题无可行解,另一个问题或具有无界解或无可行解,6.互补松弛定理若X（0）和Y（0）分别是原问题和对偶问题的可行解，则X（0）和Y（0）都是最优解的充要条件是Y（0）Xs=YsX（0）=0。其中Xs=(xs1,xs2,xsm)T，xs1,xs2,xsm是原问题的松弛变量，Ys=(ys1,ys2,ysn)T，ys1,ys2,ysn是对偶问题的剩余变量。如果有某个原始最优解X(0)YsX（0）=0：对某个下标j满足X(0)j0，那么与之对应的对偶约束在最优的情况下为等式，即ysj=0(不需要松弛变量)；Y（0）Xs=0：如果原始约束在最优情况下对某个下标i满足x(0)si0(原问题约束是严格不等式，需要松弛变量才能化为等式)，那么对偶问题最优解中与之对应的y(0)i=0。,证明:原问题对偶问题maxz=CXmin=YbAX+Xs=bYA-Ys=CX,Xs0Y,Ys0z=(YA-Ys)X=YAX-YsX=Y(AX+Xs)=YAX+YXs若Y(0)Xs=0和YsX(0)=0,则Y(0)b=Y(0)AX(0)=CX(0)，根据性质4知:X(0),Y(0)为最优解。反之,X(0),Y(0)为最优解,则根据性质4:CX(0)=Y(0)b。两组最优解分别代入目标函数:CX(0)=Y(0)AX(0)-YsX(0)Y(0)AX(0)Y(0)b=Y(0)AX(0)+Y(0)YsY(0)AX(0)可知必有Y(0)Xs=YsX(0)=0。证毕,7.原问题的检验数对应对偶问题的一个基本解,设B是原问题的一个可行基,有A=(B,N)maxz=CBXB+CNXNmin=YbBXB+NXN+XS=bYB-Ys1=CBXB,XN，Xs0YN-Ys2=CNY,Ys1，Ys20YS=（YS1，YS2）,证明:原问题对偶问题maxz=CXmin=YbAX+Xs=bYA-Ys=CX,Xs0Y,Ys0,Ys1对应原问题当中基变量XB的剩余变量，Ys2对应原问题当中非基变量XN的剩余变量,当原问题有解XB=B-1b，XN=0时,检验数为：CN-CBB-1N，-CBB-1令Y=CBB-1，代入对偶问题的约束条件得：Ys1=0，-Ys2=CN-CBB-1N则（Y，Ys1，Ys2）为对偶问题的基本解证毕,检验数性质：原问题检验数行对应其对偶问题的一个基解,关系如下:,例4已知线性规划问题maxz=x1+x2-x1+x2+x32-2x1+x2-x31x1,x2,x30试用对偶理论证明上述线性规划问题无最优解。,证:首先看到该问题存在可行解，例如X=(0,0,0)而上述问题的对偶问题为min=2y1+y2-y1-2y21y1+y21y1-y20y1,y20由第一约束条件可知对偶问题无可行解，因而无最优解。由此原问题也无最优解。,例5已知线性规划问题min=2x1+3x2+5x3+2x4+3x5x1+x2+2x3+x4+3x542x1-x2+3x3+x4+x53xj0,j=1,2,3,4,5已知其对偶问题的最优解为y1*=4/5,y2*=3/5；z=5。试用对偶理论找出原问题的最优解.,解:先写出它的对偶问题maxz=4y1+3y2y1+2y22y1-y23(2)2y1+3y25(3)y1+y22(4)3y1+y23y1,y20,将y1*,y2*的值代入上述约束条件，得(2),(3),(4)为严格不等式；由互补松弛性得x2*=x3*=x4*=0因y1,y2=0，原问题的两个约束条件应取等式，故有x1*+3x5*=42x1*+x5*=3求解后得x1*=1，x5*=1故原问题的最优解为X*=(1,0,0,0,1)T最优值为*=5,5对偶问题的经济解释（影子价格）,由对偶定理知，当达到最优解时有：z=CX（0）=Y（0）b=y1（0）b1+y2（0）b2+ym（0）bm在最优解处，常数项bi的微小改变对目标函数值的影响（在不改变最优基情况下）有,这说明若原问题的bi增加一个单位，则由此引起的最优目标函数值增加量等于该约束条件对应的对偶变量yi的最优值。因此，最优对偶变量yi的值，就相当于对单位变化的第i种资源在实现最大利润时的一种价格估计，这种估计被称之为影子价格。,原问题：可以理解为资源的合理利用使总利润最大对偶问题：估计资源的价值问题（但并不是第种资源的实际成本，而是根据企业制造产品的收益估计资源的单位价值，既资源在最优产品组合时具有的潜在价值）影子价格：不同于市场价格，是企业内部估计或核算价格,例：某厂生产、种产品要消耗钢、煤、机械加工时间，现有资源数和利润表如下，试制定一个最优生产计划。,解得：,对偶问题:,由互补松弛条件：,解得：,所以：钢增加一吨，收入增加3/4万煤增加一吨，收入增加0机时增加一个，收入增加1/4万,煤本身没有用完，再增加量，收入也不会增加，而另两种资源已经用完，再增加资源才会增加收益。,影子价格在经济管理中的作用:指示企业内部挖潜的方向：yi高,对目标增益贡献大,应重视此资源的组织、采购；(2)指导企业的购销决策：yi*是新增资源的价值，在最优产品不变的情况下，购入资源价格大于yi*时，企业亏损，若企业有市价高于影子价格的资源，应设法将其转让；(3)用影子价格分析工艺改变后对资源节约的收益:(4)指导企业间的分工协作:,企业接受外协加工时，制定收费标准可依据影子价格，以使双方都有利润，可以促进协作；当外协单位支付的报酬不低于影子价格时，企业可以接受，合作可以促进产品更新换代，以发挥各自优势。,例：A、B、C三厂生产车床、刨床，若只生产一种产品，效率表如右图。车、刨床需求比例为1：2，试制定最优分工协作计划，使总的套数最多。,解：A、B、C三厂编号为1，2，3车、刨床的编号为1，2,为第i厂生产第j种产品的时间比例,则：,车床总数：,刨床总数：,展开得：,总套数：,解得：,生产车床：3/45=15/4（台）生产刨床：41+1/42+31=15/2（台）,A厂只生产刨床，B厂3/4生产车床，1/4生产刨床C厂只生产刨床此计划能否执行要看单独生产获利增加情况,A厂单独生产：,解得,A厂生产能力：2/31=2/3台车床1/34=4/3台刨床,B厂单独生产：,B厂生产能力：1/65=5/6台车床5/62=5/3台刨床,解得：,C厂单独生产：,解得：,C厂生产能力：3/72=6/7台车床4/73=12/7台刨床,A、B、C各单独生产共可生