运筹学线性规划的对偶问题.ppt

3 线性规划的对偶问题的提出,从另一个角度讨论这个问题：工厂决定转让设备收取租金，如何确定租价？设y1，y2，y3分别为出租单位设备台时的租价和出让单位原材料、的附加额。,为什么目标取最小？租金定的越高就不会有人来租，问题就没有实际意义，工厂和接受者都愿意的条件为上述规划问题的解。其中Y=（y1，y2，y3）,理论上,因为Y的上界为无限大,所以只能有最小值。,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故 C X（0）Y（0）A X（0）Y（0）b亦即 C X（0）Y（0）b 证毕,4.最优性定理若X（0）和Y（0）分别是原问题和对偶问题的可行解，且有 C X（0）=Y（0）b,则X（0）和Y（0）分别是原问题和对偶问题的最优解。,证明：设 X 是原问题任一可行解，Y（0）是对偶问题的可行解，根据弱对偶性定理，有C XY（0）b 因为C X（0）=Y（0）b，故CXC X（0），即X（0）是原问题的最优解。设Y为对偶问题的任一可行解，同理有Yb Y（0）b 即Y（0）是对偶问题的最优解。,5.对偶定理 有一对对偶的线性规划问题，若其中有一个有最优解，则另一个也有最优解，且相应的目标函数值相等。,证明：设X（0）是原问题的最优解，对应的基矩阵为B,非基变量的检验数为CN-CBB-1N0 全体检验数 C-CBB-1A0，即CCBB-1A 令Y（0）=CBB-1，则有Y（0）AC 即Y（0）是对偶问题的可行解。由于z=C X（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=0和Ys X（0）=0。其中Xs=(xs1,xs2,xsm)T，xs1,xs2,xsm 是原问题的松弛变量.Ys=(ys1,ys2,ysn)T，ys1,ys2,ysn是对偶问题的剩余变量。松弛的含义是如果有某个原始最优解X(0)，使得对某个下标j，满足X(0)j0(原问题是松的)，那么与之对应的对偶约束在最优的情况下为等式，即ysj=0(对偶问题是紧的)；如果原始约束在最优情况下对某个下标i满足x(0)si0(原问题是松的)，那么，对偶最优解中与之对应的y(0)i=0(对偶问题是紧的)。,证明:原问题 对偶问题 max z=CX min=Yb AX+Xs=b YA-Ys=C X,Xs 0 Y,Ys0 z=(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)为最优解,则CX(0)=Y(0)AX(0)=Y(0)b 可知必有Y(0)Xs=0和YsX(0)=0。证毕,7.原问题的检验数对应对偶问题的一个基本解,设B是原问题的一个可行基,有A=(B,N)max z=CBXB+CNXN min=YbBXB+NXN+XS=b YB-Ys1=CBXB,XN，Xs0 YN-Ys2=CN Y,Ys1，Ys20 YS=（YS1，YS2）,证明:原问题 对偶问题 max z=CX min=Yb AX+Xs=b YA-Ys=C X,Xs 0 Y,Ys0,当原问题有解XB=B-1b，XN=0时,检验数为：CN-CBB-1N，-CBB-1 令Y=CBB-1，代入对偶问题的约束条件得：Ys1=0，-Ys2=CN-CBB-1N 则（Y，Ys1，Ys2）为对偶问题的基本解 证毕,检验数性质：原问题检验数行对应其对偶问题的一个 基解,关系如下:,例4 已知线性规划问题 max z=x1+x2-x1+x2+x3 2-2x1+x2-x3 1 x1,x2,x30试用对偶理论证明上述线性规划问题无最优解。,证:首先看到该问题存在可行解，例如X=(0,0,0)而上述问题的对偶问题为 min=2y1+y2-y1-2y2 1 y1+y2 1 y1-y2 0 y1,y2 0 由第一约束条件可知对偶问题无可行解，因而无最优解。由此原问题也无最优解。,例5 已知线性规划问题 min=2x1+3x2+5x3+2x4+3x5 x1+x2+2x3+x4+3x5 4 2x1-x2+3x3+x4+x5 3 xj 0,j=1,2,3,4,5 已知其对偶问题的最优解为y1*=4/5,y2*=3/5；z=5。试用对偶理论找出原问题的最优解.,解:先写出它的对偶问题 max z=4y1+3y2 2y1+y2 2 y1-y2 3 2y1+3y2 5 y1+y2 2 3y1+y2 3 y1,y2 0,将y1*,y2*的值代入上述约束条件，得(2),(3),(4)为严格不等式；由互补松弛性得x2*=x3*=x4*=0 因y1,y2 0，原问题的两个约束条件应取等式，故有 x1*+3x5*=4 2x1*+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各单独生产共可生产：5/6+2/3+6/7=33/14 套单独生产比合作少生产：15/4-33/14=39/28套,合作得以进行，应如何分配成品产量，使各厂利益合理？,利用影子价格得：,即：A厂增加一个生产能力多生产5/3套，而合作过程中其投入的生产能力刚好是1，所以分配其成果为5/3套。同理：分配B厂5/6套，分配C厂5/4套。,A、C厂均比独立生产（2/3，6/7套）多B厂与独立生产相同,所以：这样合作各方均可接受,