对偶问题的基本性质.ppt

3 对偶问题的基本性质,Max z=CXMin w=Y bs t.AX b s t.YA C X 0 Y 0,(1)弱对偶性：若 X0原问题可行解，Y0对偶问题可行解,则 CX0 Y0 b证明 Y0 0，AX0 b，Y0 AX0 Y0 b，而 Y0 A C，CX0 Y0AX0，CX0 Y0 AX0 Y0 b,（2）最优性：,若 X0原问题可行解，Y0对偶问题可行解，且 CX0=Y0 b 则 X0原问题最优解，Y0对偶问题最优解证明：设 X*原问题最优解，Y*对偶问题最优解 则 CX0 CX*Y*b Y0 b 但 CX0=Y0 b，CX0=CX*=Y*b=Y0 b X0原问题最优解，Y0对偶问题最优解证毕。,（3）无界性,若原问题(对偶问题）最优解无界，则对偶问题（原问题）无可行解 证：有性质1，C X0 Y0 b，当 CX0 时，则不可能存在Y0，使得 C X0 Y0 b。注：逆定理不成立，即 如果原问题（对偶问题）无可行解，那么 对偶问题（或原问题）“解无界”不成立。,（4）强对偶性（对偶定理）,若原问题有最优解，则对偶问题一定有最优解，且有 z max=w min证：由=C-CB B-1 A 0 令 CBB-1=Y*，得 Y*A C若-Y*=-CBB-1 0，则 Y*0 因此，Y*是对偶问题的可行解，又 CX*=CB(B-1 b)=CB B-1b=Y*b Y*是对偶问题的最优解。,原问题（或对偶问题）对偶问题（或原问题）,原问题和对偶问题解之间关系：,有最优解,有最优解,无界,无可行解,无可行解,无可行解或无界,例 证明如下LP问题无界,（5）互补松弛性,例：已知如下问题的对偶问题最优解为,求原问题的最优解,解：对偶问题为,（6）原问题的检验数行对应对偶问题的一个基本解,4 对偶问题的经济解释影子价格,“影子价格”的定义“影子价格”，确切的定义是：一个线性规划对偶问题的最优解（简称为“对偶最优解）。在经济上可以解释为约束条件所付出的代价。讨论例1-1的图解法时，给出了一个例子，并用图解法求出了最优解。现给出其对偶问题并对其进行分析。,（3，0）,C=6,（9，0）,（0，9/4）,E（1，2）,C=0,（0，3）,例1-1的对偶规划如下：,它的图解见右图。其中L1和L2分别为两个约束半平面的边界，虚线为目标函数等值线，可行域为图中阴影部分，沿着与箭头（目标函数值递增的方向）相反的方向平移目标函数等值线（注意：对偶规划中 要求对目标函数极小化）得最优点为A,其对应坐标为 y1=5,y2=1,当原问题和对偶问题都取得最优解时，这一对线性规划对应的目标函数值相等，即有 Zmax=CX*=2x*1+3x*2=Wmin=y*b=y*1+3y*2=8 其中X*是原问题的最优解，y*是对偶问题最优解。,即有 X*=(x1,x2)T=(1,2)T，Y*=(y1,y2)=(5,1)若原材料供应量能增加一个单位，即右端常数向量b=(b1,b2)T=(1,3)T中的b2从3个单位增加到4个单位，则目标函数值的变化量为（y*1+4y*2)-(y*1+3y*2)=y*2=1,说明目标函数值增加一个单位，这就是放宽一个约束条件所产生的附加贡献。就是说，影子价格表明了第i种资源单位资源的变化所引起的目标函数最优值的改变。,正确的理解影子价格，对企业做出正确决策很有帮助：,（1）调节生产规模,（2）分析生产要素对产出的贡献,5 对偶单纯形法,例：,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,x1,x2,x3,x4,XB,b,CB,-1-1 1 0-1-2 0 1,-2-3 0 0,-3-4,x3 x4,00,cj-zj,-2,-3,0,0,-1/2 0 1-1/2 1/2 1 0-1/2,x3 x2,-1 2,cj-zj,-1/2 0 0-3/2,0-3,1 0-2 1 0 1 1-1,x1 x2,21,cj-zj,0 0-1-1,-2-3,列单纯表计算：,对偶单纯形法步骤：,1.列初始单纯形表，使得所有检验数j 0；2.出基变量：取min bi0=bl x(l)3.入基变量：min|alk0=xk4.主元素：alk5.迭代：同单纯形法，新单纯表中pk化为单位向量,cj-zj,alj,说明：10 使用对偶单纯形法时，初始表中检验数必须全部为j 0，即使得其对偶问题为可行解，20 为便于说明，这里采取从原问题角度叙述迭代步骤。,