对偶问题(运筹学).ppt

大连海事大学交通运输管理学院2.4.1 对偶问题的提出2.4.2 原问题与对偶问题2.4.3 对偶问题的性质2.4.4 对偶变量的经济含义2.4.5 对偶单纯形法一、对一、对偶问题的提出偶问题的提出 某工厂在计划期内要安排生产、两种产品，已知生产单位产品所需的设备台时及A、B两种原材料的消耗，如表1-1所示。每生产一件产品可获利2元，每生产一件产品可获利3元，问应如何安排计划使该工厂获利最多?设 企业生产甲产品为X1件，乙产品为X2件，则 2.2.2.2.资源最低售价模型资源最低售价模型资源最低售价模型资源最低售价模型(原问题)(对偶问题)设第i种资源价格为yi,(i=1,2,3)则有y1y2y3y4第2章 对偶问题-一般表示式：原问题：max z=c1 X1+c2 X2+cn Xn s.t a11 X1+a12 X2+a1n Xn b1 a21 X1+a22 X2+a2n Xn b2 am1 X1+am2 X2+amn Xn bm xj 0，j=1,2,n 对偶问题：min w=b1 y1+b2 y2+bm ym s.t a11 y1+a21 y2+am1 ym c1 a12 y1+a22 y2+am2 ym c2 a1n y1+a2n y2+amn ym cn yi 0，(i=1,2,m)典式模型对应对偶结构矩阵表示（1）max z=C X s.t AX b X 0min w=Y b s.t YA C Y 0 对偶问题原问题（2）若模型为 max z=C X s.t AX b X 0max z=C X s.t -AX -b X 0变形min w=Y b s.t YA C Y 0 Min w=Y(-b)st.Y(-A)CY 0令 Y=-Y 对偶问题对偶变量Y（3）max z=C X s.t AX b X 0变形设X=-Xmax=-CX st.-AX b X 0min w=Y b s.t YA C Y 0则有min w=Y b s.t -YA-C Y 0用矩阵形式表示：（1）max z=C X min w=Y b s.t AX b s.t YA C X 0 Y 0 （2）max z=C X min w=Y b s.t AX b s.t YA C X 0 Y 0 （3）max z=C X min w=Y b s.t AX b s.t YA C X 0 Y 0 原问题(对偶问题)对偶问题(原问题)目标函数系数 约束右端项 约束右端项 目标函数系数 约束条件系数列向量 A约束条件系数行向量 AT 变量个数约束条件个数max min 变量 x j:约束方程 i:x j 0 x j 无约束 =x j 0 约束方程:变量 y i:y i 0 =y i 无约束 y i 0 例2-10 写出下述线性规划问题的对偶问题。则由表中原问题和对偶问题的对应关系，可以直接写出上述问题的对偶问题练习练习max z=2y1+5y2+1y3 2 2 y1+3 3 y2+1 1y3 3 3 1 1 y1-5 5 y2+1 1y3 2 2 3 y1 +1y3 -1=y1 0,y2 0,y y3 3自由自由自由自由s.t.解解 min=3 3 x1+2 2 x2-1 x3 2 2 x1+1 1 x2+3x3 2 3 3 x1-5 5 x2 5 1 1 x1+1 1 x2+1 x3=1 x10,x3 0 s.t.性质性质1 对称性对称性对称性对称性 规范原始、对偶问题规范原始、对偶问题(P1)与与(D1)互相对偶。即对偶互相对偶。即对偶问题的对偶是原问题。问题的对偶是原问题。性质性质2 弱对偶性弱对偶性弱对偶性弱对偶性 设设X,Y Y分别为分别为(P1)与与(D1)的任意可行解，则的任意可行解，则 CX Y Y b 性质性质3 最优性最优性最优性最优性 设设X X,Y分别为分别为(P1)与与(D1)的任意可行解，则当的任意可行解，则当 CX X =Yb 时，时，X X,Y分别是分别是(P1)与与(D1)的最优解。的最优解。性质性质4无界性无界性无界性无界性 互为对偶的两个线性规划问题，若其中一个问题的互为对偶的两个线性规划问题，若其中一个问题的解无界解无界解无界解无界，则，则另一个问题另一个问题无可行解无可行解无可行解无可行解。性质性质性质性质5 5 对偶定理对偶定理对偶定理对偶定理 互为对偶的两个线性规划问题，若其中一个问题有最优解，则互为对偶的两个线性规划问题，若其中一个问题有最优解，则另一个问题也有最优解，且二者最优值相等。另一个问题也有最优解，且二者最优值相等。注意注意注意注意：无界性无界性之逆命题不成立。之逆命题不成立。因为一个问题因为一个问题无可行解无可行解无可行解无可行解时，时，另一个问题可能另一个问题可能解无界解无界解无界解无界，也可能，也可能无可行解无可行解无可行解无可行解。兼容性兼容性兼容性兼容性 原始问题的原始问题的检验行的相反数检验行的相反数检验行的相反数检验行的相反数给出对偶问题的一个给出对偶问题的一个基本解基本解基本解基本解。X*=(4,6,4,0,0)T,z*=42y1y2y3y4y5Y*=(0,1/2,1,0,0)T,w*=42 3 3 4 4 5 5 1 1 2 2互补基本解互补基本解x3x2x1 x1 x2 x3 x4 x5 3 5 0 0 005 36 0 1 0 1/2 04 0 0 1 1/3 -1/3 4 1 0 0 -2/3 1/342 0 0 0 -1/2 -1cj 比值比值 基基 解解 :max z=3x1+5x2 x1 8 2x2 12 3x1+4x2 36 x1 ，x2 0s.t.(P1):min w=8y1+12y2+36y3 y1 +3y3 3 2y2+4y3 5 y1,y2,y3 0s.t.(D1):max z=3x1+5x2 x1 +x3 =8 2x2 +x4 =12 3x1+4x2 +x5 =36 x1,x2,x3,x4,x5 0s.t.(Ps s):min w=8y1+12y2+36y3 y1 +3y3-y4 =3 2y2+4y3 -y5=5 y1,y2,y3,y4,y5 0s.t.(Ds s)X*=(4,6)TY*=(0,1)TX*=(4,6,4,0,0)T Y*=(0,1/2,1,0,0)T,z*=42=w*(P)的基本解的基本解 与与(D)的基本解的基本解 相互对应相互对应,且二者目标值相等。且二者目标值相等。我们把这样一对基本解我们把这样一对基本解 与与 ，称为，称为(P)与与(D)的的互补基本解互补基本解。(P)目目 标标 值值(D)序序号号 极极点点 基基 本本 解解 k Xk可可 行行 z=w Yk可可 行行 基基 本本 解解 k 1 O(0 ，0 ，8 ，12 ，36)是是 0 否否(0 ，0 ，0 ，-3 ，-5)2 A(8 ，0 ，0 ，12 ，12)是是 24 否否(3 ，0 ，0 ，0 ，-5)3 D(0 ，6 ，8 ，0 ，12)是是 30 否否(0 ，5/2 ，0 ，-3 ，0)4 B(8 ，3 ，0 ，6 ，0)是是 39 否否(-3/4 ，0 ，5/4 ，0 ，0)5 C(4 ，6 ，4 ，0 ，0)是是是是 42 是是是是(0 ，1/2 ，1 ，0 ，0)6 E(12 ，0 ，-4 ，12 ，0)否否否否 36 否否否否(0,0,1,0,-1)7 G(0 ，9 ，8 ，-6 ，0)否否 45 是是(0,0,5/4 ,3/4 ,0)8 F(8 ，6 ，0 ，0,-12)否否 54 是是(3,5/2,0,0,0)7.互补松弛性互补松弛性互补松弛性互补松弛性 设设 =(x x1 1 ,x x2 2 ,x xn n ,x xn n+1 1,x xn n+mm)T =(y y1 1 ,y y2 2 ,y ymm ,y ymm+1 1,y ymm+n n)T是是(P1)(D1)的一对的一对互补基本解互补基本解互补基本解互补基本解，那么，那么 x xj j y ymm+j j =0，j=1,2,n x xn n+i i y yi i =0，i=1,2,mmin=2x1+3x2+5x3+2x4+3x5x1+x2+2x3+x4+3x542x1-x2+3x3+x4+x53 xj0，j=1，2，5已知其对偶问题的最优解为y1*=4/5，y2*=3/5；z=5。试用对偶理论找出原问题的最优解。max z=4y1+3y2y1+2y22 y1-y23 2y1+3y25 y1+y22 3y1+y23 y1，y20得=1/53，=17/55，=7/52 它们为严格不等式；由互补松弛性得 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对偶变量的意义代表对企业资源的估价，与该种资源的市场价格不同，因此我们称之为影子价格影子价格。（1）资源的市场价格是已知数，相对比较稳定，而它的影子价格则有赖于资源的利用情况，是未知数。由于企业生产任务、产品结构等情况发生变化，资源的影子价格也随之改变。（2）影子价格是一种边际价格，在（2-12）式中将Z对 求偏导数得 ，这说明 相当于在给定的生产条件下，每增加一个单位目标函数Z的增量。（3）资源的影子价格实际上又是一种机会成本。在纯市场经济条件下，当第2种资源的市场价格低于1/4时，可以买进这种资源；相反当市场价格高于影子价格时，就会卖出这种资源。随着资源的买进卖出，它的影子价格也将随之发生变化，一直到影子价格与市场价格保持同等水平时，才处于平衡状态。由于单纯表中同时反映原问题与对偶问题的最优解，故可以从求对偶问题最优解角度求解LP模型。例：min z=2x1+3x2 max z=-2x1-3x2+0 x3+0 x4 s.t x1+x23 标准化 s.t x1+x2-x3=3 x1+2x2 4 x1+2x2-x4=4 x10,x20 xj 0,(j=1,2,3,4)max z=-2x1-3x2+0 x3+0 x4 s.t -x1-x2+x3=-3 -x1-2x2+x4=-4 xj 0,(j=1,2,3,4)Cj x1x2x3x4XBbCB-1 -1 1 0 -1 -2 0 1-2 -3 0 0-3-4x3 x400cj-zj-2-300-1/2 0 1 -1/2 1/2 1 0 -1/2x3 x2-1 2cj-zj-1/2 0 0 -3/2 0-31 0 -2 1 0 1 1 -1x1 x221cj-zj 0 0 -1 -1-2-3列单纯表计算：1111把把m阶阶LPLP问题化成问题化成标准形标准形（允许其右端常数为负允许其右端常数为负）,在其系数阵中找出或构造一个在其系数阵中找出或构造一个mm阶排列阵阶排列阵阶排列阵阶排列阵作作初始基初始基初始基初始基,建立初始单纯形表建立初始单纯形表建立初始单纯形表建立初始单纯形表。若所有检验数。若所有检验数 j j00，则转，则转22;2222最优性检验最优性检验最优性检验最优性检验：检查表中检查表中解列解列各数值各数值b bi i；若所有；若所有b bi i0,0,则问题已得最优解，停止计算则问题已得最优解，停止计算;否则转否则转33。3333无可行解判断无可行解判断无可行解判断无可行解判断：只要存在一个：只要存在一个b br r00，它所在行中所有，它所在行中所有 a arj rj00，则原始问题无可行解，对偶问题无下界，停止；，则原始问题无可行解，对偶问题无下界，停止；否则转否则转44。4444确定主元确定主元确定主元确定主元：先先确定确定离基离基变量，按变量，按 min bmin bi ib bi i 0 0 =b bl 确定第确定第 l 行的基变量行的基变量 xB Bl 离基，第离基，第 l 行为主行；行为主行；后后后后确定确定进基进基变量，按变量，按最小最小最小最小比值比值比值比值规则规则规则规则：m in m in j j/a alj ja alj j 0 0 =k k /a alk k 确定进基变量确定进基变量 xk k 及主元及主元 a alk k。5555按主元按主元 a alk k 对当前表格进行一次对当前表格进行一次换基运算换基运算换基运算换基运算，得到一个新单纯形表，返得到一个新单纯形表，返22 。练习练习练习练习min z=3x1+2x2s.t.2x1+3x2 18 x1-x2 2 x1+3x2 10 x1,x2 0解解解解max z=-3x1-2x2s.t.2x1+3x2+x3 =18 x1 -x2 x4 =2 x1+3x2 x5=10 x1,x2,x3,x4,x5 0 x1+x2 +x4 =2x13x2 +x5=10max z=-3x1-2x2 2x1+3x2+x3 =18 -x1 +x2 +x4 =-2 -x1-3x2 +x5 =-10 x1,x2,x3,x4,x5 0 s.t.cj 基基 解解 x1 x2 x3 x4 x5 -3 -2 0 0 0 2 3 1 0 0 x3x4 x5 18-2-10-1 1 0 1 000 0-1 -3 0 0 1 0 -3 -2 0 0 032/3min-3比比 值值 cj 基基 解解 x1 x2 x3 x4 x5 -3 -2 0 0 0 2 3 1 0 0 x3x4x5 18-2-10-1 1 0 1 0000-1 -3 0 0 1 0 -3 -2 0 0 0-3x3x1 x2 0-3-2 4 1 0 0 -3/4 -1/4 4 0 0 1 3/4 5/4 2 0 1 0 1/4 -1/4-16 0 0 0 -7/4 -5/4x3x4x2 0 0 -2 8 1 0 1 0 1 10/3 1/3 1 0 0 -1/3-20/3 -7/3 0 0 0 -2/3-16/3 -4/3 0 0 1 1/3-4/3X*=(4,2)Tz*=16单纯形法的矩阵描述Cj x1x2x3x4XBbCB1 1 1 0 1 2 0 12 3 0 034x3 x400cj-zj 23001/2 0 1 -1/2 1/2 1 0 1/2x3 x212cj-zj 1/2 0 0 -3/2031 0 2 -1 0 1 -1 1x1 x221cj-zj 0 0 -1 -1231.初等行变换 相当于 左乘一个相应的初等阵2.B-1 B=E3.b/=B-1 b4.目标函数AX=b B-1 AX=B-1 b CB B-1 AX=CB B-1 b与 Z=CX相加Z=CB B-1 b+(C-CB B-1 A)X