《657-2、线性规划问题的对偶问题.ppt》由会员分享，可在线阅读，更多相关《657-2、线性规划问题的对偶问题.ppt（59页珍藏版）》请在三一文库上搜索。
1、2、线性规划问题的对偶问题,例21 胜利家具厂生产桌子和椅子两种家具。桌子售价50元/个，椅子销售价格30元/个，生产桌子和椅子要求需要木工和油漆工两种工种。生产一个桌子需要木工4小时，油漆工2小时。生产一个椅子需要木工3小时，油漆工1小时。该厂每个月可用木工工时为120小时，油漆工工时为50小时。问该厂如何组织生产才能使每月的销售收入最大？,2.1 对偶问题,数学模型 max g= 50x1 + 30x2 s.t. 4x1 + 3x2 120 (2.1) 2x1 + x2 50 x1,x2 0,假如有一个企业家有一批等待加工的订单，有意利用该家具厂的木工和油漆工资源来加工他的产品。因此，他要
2、同家具厂谈判付给该厂每个工时的价格。可以构造一个数学模型来研究如何既使家具厂觉得有利可图肯把资源出租给他，又使自己付的租金最少？,假设 y1, y2 分别表示每个木工和油漆工工时的租金，则所付租金最小的目标函数可表示为： min s = 120 y1 + 50 y2 目标函数中的系数 120，50 分别表示可供出租的木工和油漆工工时数。,该企业家所付的租金不能太低，否则家具厂的管理者觉得无利可图而不肯出租给他。因此他付的租金应不低于家具厂利用这些资源所能得到的利益： 4 y1 + 2y2 50 3 y1 + y2 30 y1, y2 0,得到另外一个数学模型： min s = 120 y1 +
3、 50 y2 s.t. 4 y1 + 2y2 50 (2.2) 3 y1+ y2 30 y1, y2 0,模型(2.1)和模型(2.2) 既有区别又有联系。联系在于它们都是关于家具厂的模型并且使用相同的数据，区别在于模型反映的实质内容是不同的。模型(2.1)是站在家具厂经营者立场追求销售收入最大，模型(2.2)是则站在家具厂对手的立场追求所付的租金最少。,如果模型(2.1)称为原问题， 则模型(2.2)称为对偶问题。 任何线性规划问题都有对偶问题， 而且都有相应的意义。,例2.2 ：常山机器厂生产、两种产品，按工艺资料获得如下资料：,问该企业因安排生产两种产品各多少件，使总的利润收入为最大？,
4、数学模型 max Z=2x1+3x2 s.t. 2x1+2x2 12 4x1 16 5x2 15 x1,x2 0,现某机械厂为扩大生产租借常山机器厂拥有的设备资源，问常山厂分别以每小时什么样的价格才愿意出租自己的设备？,设常山厂将设备A、B、C每h的出租价格为y1,y2,y3; 它的对偶问题为 min w=12y1+16y2+15y3 2y1+4y2 2 2y1 +5y33 y1,y2,y30,把例2.2用矩阵表示： 对偶问题 原问题: Max z=(2,3),线性规划的对偶关系： （I） Max z = C x s.t. Ax b （2.3） x 0 (II) Min w = b y s.t
5、. Ay C （2.4） y 0 （2.3)(2.4)称作互为对偶问题。其中一个称为原问题，另一个称为它的对偶问题。,例2-3：写出下列线性规划问题的对偶问题 min w=12x1+8x2 +16x3+12x4 s.t. 2x1+ x2 +4x3 2 2x1+2x2 + 4x4 3 x1，x2 ， x3 ， x4 0,解：该问题的对偶问题： max z = 2y1 + 3y2 s.t. 2y1 + 2y2 12 y1 + 2y2 8 4 y1 16 4y2 12 y1，y2 0,例2-4：写出下列线性规划问题的对偶问题 max S = 10x1 + x2 + 2x3 s.t. X1 + x2
6、+ 2x3 10 y1 4x1 +2x2 - x3 20 y2 x1，x2 ， x3 0,解：该问题的对偶问题： min g = 10 y1 + 20 y2 s.t. y1 + 4y2 10 y1 + 2y2 1 2 y1 - y2 2 y1，y2 0,例2-5：写出下列线性规划问题的对偶问题 min S = x1 + 2x2 + 3x3 s.t. 2x1+3x2 + 5x3 2 3x1+ x2 + 7x3 3 x1，x2 ， x3 0,解：用（-1）乘以第二个约束方程两边 min S=x1+2x2 +3x3 s.t. 2x1+3x2 + 5x3 2 y1 -3x1- x2 - 7x3 -3
7、y2 x1，x2 ， x3 0,该问题的对偶问题： max z = 2 y1 - 3y2 s.t. 2y1- 3y2 1 3y1- y2 2 5y1- 7y2 3 y1，y2 0,例2-6：写出下列线性规划问题的对偶问题 min S = 2x1 + 3x2 - 5x3 s.t. x1+ x2 - x3 5 2x1 + x3 = 4 x1，x2 ， x3 0,解：将原问题的约束方程写成不等式约束形式： min S = 2x1 + 3x2 - 5x3 x1+ x2 - x3 5 y1 2x1 + x3 4 y2 -2x1 - x3 -4 y2” x1，x2 ， x3 0,引入变量 y1 , y2，
8、y2” 写出对偶问题 max g = 5 y1+ 4y2- 4y2” s.t. y1 +2y2- 2y2” 2 y1 3 -y1 + y2- y2” -5 y1， y2，y2” 0,令y2 = y2- y2” 得到 max g = 5 y1 + 4y2 s.t. y1 + 2y2 2 y1 3 -y1+ y2 -5 y1 0 ，y2 无非负约束 此类问题称为非对称型对偶问题。 前面的问题称为对称型对偶问题。,综上所述其变换形式如下：,例2-7：写出下列线性规划的对偶问题 min z=7x1+4x2-3x3 s.t. -4x1+2x2-6x324 -3x1-6x2-4x315 5x2+3x3=3
9、0 x10,x2取值无约束,x30,Max w=24y1+15y2+30y3 s.t. -4y1-3y2 7 2y1-6y2+5y3=4 -6y1-4y2+3y3-3 y10,y20,y3无约束,例2-8：写出下列线性规划问题的对偶问题 min w = 3x1 - 2x2 + x3 s.t. x1+2x2 = 1 y1 2x2 - x3 -2 y2 2x1 +x3 3 y3 x1- 2x2 + 3x3 4 y4 x1，x2 0 ， x3 无非负限制,解: 综合运用对偶原则得到 max g = y1-2y2 +3y3 +4y4 s.t. y1+ 2y3 + y4 3 2y1 +2y2 - 2y4
10、 -2 -y2+ y3 +3y4 = 1 y20, y3, y4 0 ，y1 无非负约束,定理2.1:(弱对偶定理) 对于互为对偶问题(I)(II)中的任意的可行解x(0),y(0),都有 c x(0) y(0) b,2.2 对偶问题的基本定理,定理2.2 (最优准则) 若原问题的某一个可行解与对偶问题的某一可行解的目标函数值相等,则它们分别是原问题与对偶问题的最优解.,定理2.3 (对偶定理) 若原问题有最优解,则对偶问题也有最优解,且最优值相等.,性质2.4 如果原问题(对偶问题）具有无界解，则其对偶问题（原问题）无可行解。 但原问题(对偶问题)无可行解时，其对偶问题（原问题）或无可行解或
11、具有无界解。,定理2.5（互补松弛性） 在线性规划问题的最优解中，如果该约束条件取严格等式，则对应某一约束条件的对偶变量值为非零；反之如果约束条件取严格不等式，则其对应的对偶变量一定为零。,max Z=2x1+3x2 s.t. 2x1+2x2 12 4x1 16 5x2 15 x1,x2 0,它的最优解为（3，3） 而对于第二个约束条件，为严格的不等式，所以y2=0,y1,y2,y3,性质2.6 对偶问题的最优解为原问题最优表中,相应的松驰变量检验数的相反数。（线性规划的原问题与对偶问题中，原问题的松弛变量对应对偶问题的变量，对偶问题的剩余变量对于原问题的变量。）,例：max Z=2x1+3x
12、2 s.t. 2x1+2x2 +x3 12 4x1 +x4 16 5x2+x5 15 x1,x2 0,原问题变量,原问题松弛变量,对偶问题变量,对偶问题的剩余变量,Y2,Y5,Y4,Y3,Y4,2.3 影子价格,在线性规划原问题和对偶问题中：,bi代表第i种资源的拥有量，而yi代表对一个单位第i种资源的估价,影子价格不是市场价格，随企业的生产任务和产品结构而发生变化。 影子价格是一种边际价格。 Z= bTy*=b1y1*+b2y2*+bmym* 可知 Z / bi = yi*,2X+2y=12,1,2,3,4,5,6,6,5,4,3,2,1,X=4,X=3,max Z=2x1+3x2 s.t.
13、 2x1+2x2 12 4x1 16 5x2 15 x1,x2 0,点（3，3）是最优解，z*=15 当A的资源变为13小时，z*=16,说明A的边际价格是1，即影子价格是1。,在对偶问题的互补松弛性质中有,表示某种资源bi没有充分利用，该种资源的影子价格为零。,如果,表示该种资源已耗费完毕。,是生产该种产品所消耗的各项资源的影子价格总和，即产品的隐含成本。,从影子价格的含义上再来考察单纯形法的计算：,当检验数大于零，说明生产此种产品有利，可在生产中安排。,2.4 对偶单纯形法,例：求解如下线性规划问题： min w=12y1+16y2+15y3 s.t. 2y1+4y2 2 2y1+ 5y3
14、 3 y1,y2,y3 0 划为标准形： max w=-12y1-16y2-15y3 -2y1-4y2 +y4 =-2 -2y1 -5y3 +y5=-3 yi 0（i=1,5),如何转换? 当bi0时，令min(bi)所对应的行中的Xr为换出基变量。 令,所对应的列变量为换入基变量,Y5为换出基变量,故x3为换入基变量，-5为主元素,Y4为换出基变量,故Y1为换入基变量，-2为主元素,故此问题的最优解为：Y1=1，Y2=0，Y3=1/5，W=15,对偶单纯形法的基本思想 对偶单纯形法的基本思想是：从原规划的一个基解出发，此基解不一定可行，但它对应着一个对偶可行解（检验数非正）；从对偶可行解出发
15、，然后检验原规划的基本解是否可行，即是否有负的分量，如果有小于零的分量，则进行迭代，求另一个基解，此基解对应着另一个对偶可行解（检验数非正）。 如果得到的基解的分量皆非负则该基解为最优解。也就是说，对偶单纯形法在迭代过程中始终保持对偶解的可行性（即检验数非正），使原规划的基解由不可行逐步变为可行,对偶单纯形法在什么情况下使用 ： 应用前提：有一个基，其对应的基满足: 单纯形表的检验数行全部非正（对偶可行）； 变量取值可有负数（非可行解）。 注：通过矩阵行变换运算，使所有相应变量取值均为非负数即得到最优单纯形表。,对偶单纯形法求解线性规划问题过程： 1.建立初始对偶单纯形表,对应一个基本解,所有
16、检验数均非正,转2； 2.若b0,则得到最优解,停止;否则,若有bk0则选k行的基变量为出基变量,转3 3.若所有akj0( j = 1,2,n )，则原问题无可行解,停止;否则,若有akj0 则选 =minj / akjakj0=r/akr那么 xr为进基变量,转4； 4.以akr为转轴元,作矩阵行变换使其变为1,该列其他元变为0,转2。,对偶单纯形法解的讨论 if br0,而arj0,这时原问题解的情况如何？,故不可能存在xj0（j=1,n）的解，故原问题无可形解，这时对偶问题的目标函数值无界。,例题:用对偶单纯形法求解,解:将上述模型转化为,=min(-9/-1,-12/-1,-15/-5)=3,=min(6*5/9,9*5/14,15)=45/14,=min(1/3,5,33)=1/3,所以， X*=（2 . 2 . 2 . 0 . 0 . 0） Z* =72， 原问题 Z* =72 其对偶问题的最优解为： Y*= (1/3 . 3 . 7/3)，W*= 72,