线性规划问题的对偶问题.ppt

《线性规划问题的对偶问题.ppt》由会员分享，可在线阅读，更多相关《线性规划问题的对偶问题.ppt（59页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、2、线性规划问题的对偶问题例例2 21 1 胜利家具厂生产桌子和椅子两种家具。胜利家具厂生产桌子和椅子两种家具。桌子售价桌子售价5050元元/个，椅子销售价格个，椅子销售价格3030元元/个，生产桌子和椅子要求需要木工和油个，生产桌子和椅子要求需要木工和油漆工两种工种。生产一个桌子需要木工漆工两种工种。生产一个桌子需要木工4 4小时，油漆工小时，油漆工2 2小时。生产一个椅子需要小时。生产一个椅子需要木工木工3 3小时，油漆工小时，油漆工1 1小时。该厂每个月小时。该厂每个月可用木工工时为可用木工工时为120120小时，油漆工工时为小时，油漆工工时为5050小时。问该厂如何组织生产才能使每小时

2、。问该厂如何组织生产才能使每月的销售收入最大？月的销售收入最大？2.1 对偶问题数学模型数学模型 max g=50 xmax g=50 x1 1+30 x+30 x2 2 s.t.4x s.t.4x1 1+3x+3x2 2 120 (2.1)120 (2.1)2x 2x1 1+x+x2 2 50 50 x x1 1,x,x2 2 0 0 假如有一个企业家有一批等待加假如有一个企业家有一批等待加工的订单，有意利用该家具厂的木工工的订单，有意利用该家具厂的木工和油漆工资源来加工他的产品。因此，和油漆工资源来加工他的产品。因此，他要同家具厂谈判付给该厂每个工时他要同家具厂谈判付给该厂每个工时的价格。

3、可以构造一个数学模型来研的价格。可以构造一个数学模型来研究如何既使家具厂觉得有利可图肯把究如何既使家具厂觉得有利可图肯把资源出租给他，又使自己付的租金最资源出租给他，又使自己付的租金最少？少？假设假设 y y1 1,y,y2 2 分别表示每个木工分别表示每个木工和油漆工工时的租金，则所付租金和油漆工工时的租金，则所付租金最小的目标函数可表示为：最小的目标函数可表示为：min s=120 y min s=120 y1 1+50 y+50 y2 2目标函数中的系数目标函数中的系数 120 120，50 50 分别表分别表示可供出租的木工和油漆工工时数。示可供出租的木工和油漆工工时数。该企业家所付的

4、租金不能太低，该企业家所付的租金不能太低，否则家具厂的管理者觉得无利可图否则家具厂的管理者觉得无利可图而不肯出租给他。因此他付的租金而不肯出租给他。因此他付的租金应不低于家具厂利用这些资源所能应不低于家具厂利用这些资源所能得到的利益：得到的利益：4 y 4 y1 1+2y+2y2 2 50 50 3 y 3 y1 1+y+y2 2 30 30 y y1 1,y,y2 2 0 0 得到另外一个数学模型：得到另外一个数学模型：min s=120 y min s=120 y1 1+50 y+50 y2 2 s.t.4 y s.t.4 y1 1+2y+2y2 2 50 (2.2)50 (2.2)3 y

5、 3 y1 1+y+y2 2 30 30 y y1 1,y,y2 2 0 0模型(2.1)和模型(2.2)既有区别又有联系。联系在于它们都是关于家具厂的模型并且使用相同的数据，区别在于模型反映的实质内容是不同的。模型(2.1)是站在家具厂经营者立场追求销售收入最大，模型(2.2)是则站在家具厂对手的立场追求所付的租金最少。如果模型如果模型(2.1)(2.1)称为原问题，称为原问题，则模型则模型(2.2)(2.2)称为对偶问题。称为对偶问题。任何线性规划问题都有对偶问题，任何线性规划问题都有对偶问题，而且都有相应的意义。而且都有相应的意义。例例例例2.2 2.2：常山机器厂生产：常山机器厂生产：

6、常山机器厂生产：常山机器厂生产、两种产品，按工艺两种产品，按工艺两种产品，按工艺两种产品，按工艺资料获得如下资料：资料获得如下资料：资料获得如下资料：资料获得如下资料：设备设备能力能力设备A2h2h12h设备B4h0h16h设备C0h5h15h单位利润（元）23问该企业因安排生产两种产品各多少件，使总的问该企业因安排生产两种产品各多少件，使总的利润收入为最大？利润收入为最大？数学模型数学模型 max Z=2x max Z=2x1 1+3x+3x2 2 s.t.2x s.t.2x1 1+2x+2x2 2 12 12 4x 4x1 1 16 16 5x2 15 x x1 1,x,x2 2 0 0

7、现某机械厂为扩大生产租借常山机器厂拥有的设备资源，问常山厂分别以每小时什么样的价格才愿意出租自己的设备？设常山厂将设备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 I）Max z =C x Max z =C x s.t.Ax s.t.Ax b b （2.32.3）x x 0 0(II)Min w=b y(II)Min w=b y s.t.Ay s.t.Ay C C （2.42

8、.4）y y 0 0（2.3)(2.4)2.3)(2.4)称作互为对偶问题。其中一个称作互为对偶问题。其中一个称为原问题，另一个称为它的对偶问题。称为原问题，另一个称为它的对偶问题。例例2-32-3：写出下列线性规划问题的：写出下列线性规划问题的对偶问题对偶问题min w=12xmin w=12x1 1+8x+8x2 2+16x+16x3 3+12x+12x4 4 s.t.2xs.t.2x1 1+x+x2 2+4x+4x3 3 2 2 2x 2x1 1+2x+2x2 2 +4x+4x4 4 3 3 x x1 1，x x2 2，x x3 3，x x4 4 0 0解：该问题的对偶问题：解：该问题的

9、对偶问题：max z=2y max z=2y1 1+3y+3y2 2 s.t.2y s.t.2y1 1+2y+2y2 2 12 12 y y1 1+2y+2y2 2 8 8 4 y 4 y1 1 16 16 4y 4y2 2 12 12 y y1 1，y y2 2 0 0例例2-42-4：写出下列线性规划问题的：写出下列线性规划问题的对偶问题对偶问题max S=10 xmax S=10 x1 1+x+x2 2 +2x+2x3 3s.t.Xs.t.X1 1+x+x2 2+2x+2x3 3 10 10 y y1 1 4x 4x1 1+2x+2x2 2 -x-x3 3 20 20 y y2 2 x

10、x1 1，x x2 2，x x3 3 0 0解：该问题的对偶问题：解：该问题的对偶问题：min g=10 y min g=10 y1 1+20 y+20 y2 2 s.t.y s.t.y1 1+4y+4y2 2 10 10 y y1 1+2y+2y2 2 1 1 2 y 2 y1 1-y-y2 2 2 2 y y1 1，y y2 2 0 0例例2-52-5：写出下列线性规划问题的：写出下列线性规划问题的对偶问题对偶问题 min S=x min S=x1 1+2x+2x2 2+3x+3x3 3s.t.2xs.t.2x1 1+3x+3x2 2+5x+5x3 3 2 2 3x3x1 1+x+x2 2

11、+7x+7x3 3 3 3 x x1 1，x x2 2，x x3 3 0 0解：用（解：用（-1-1）乘以第二个约束方程）乘以第二个约束方程两边两边 min S=x min S=x1 1+2x+2x2 2+3x+3x3 3s.t.2xs.t.2x1 1+3x+3x2 2+5x+5x3 3 2 2 y y1 1 -3x-3x1 1-x-x2 2-7x-7x3 3 -3 -3 y y2 2 x x1 1，x x2 2，x x3 3 0 0该问题的对偶问题：该问题的对偶问题：max z=2 y max z=2 y1 1-3y-3y2 2 s.t.2y s.t.2y1 1-3y-3y2 2 1 1 3

12、y 3y1 1-y-y2 2 2 2 5y 5y1 1-7y7y2 2 3 3 y y1 1，y y2 2 0 0例例2-62-6：写出下列线性规划问题的：写出下列线性规划问题的对偶问题对偶问题 min S=2x min S=2x1 1+3x+3x2 2-5x-5x3 3s.t.xs.t.x1 1+x+x2 2-x-x3 3 5 5 2x 2x1 1 +x+x3 3 =4 =4 x x1 1，x x2 2，x x3 3 0 0解：将原问题的约束方程写成不等式解：将原问题的约束方程写成不等式约束形式：约束形式：min S=2x min S=2x1 1+3x+3x2 2-5x-5x3 3 x x1

13、 1+x+x2 2-x-x3 3 5 5 y y1 1 2x 2x1 1 +x+x3 3 4 4 y y2 2 -2x-2x1 1 -x-x3 3 -4 -4 y y2 2”x x1 1，x x2 2，x x3 3 0 0引入变量引入变量 y y1 1,y y2 2，y y2 2”写出对偶问写出对偶问题题 max g=5 y max g=5 y1 1+4y+4y2 2-4y-4y2 2”s.t.y s.t.y1 1+2y+2y2 2-2y-2y2 2”2 2 y y1 1 3 3 -y -y1 1+y+y2 2-y-y2 2”-5-5 y y1 1，y y2 2，y y2 2”0 0令令y y

14、2 2=y=y2 2-y-y2 2”得到得到 max g=5 y max g=5 y1 1+4y+4y2 2 s.t.y s.t.y1 1+2y+2y2 2 2 2 y y1 1 3 3 -y -y1 1+y+y2 2 -5-5 y y1 1 0 0，y y2 2 无非负约束无非负约束此类问题称为非对称型对偶问题。此类问题称为非对称型对偶问题。前面的问题称为对称型对偶问题。前面的问题称为对称型对偶问题。综上所述其变换形式如下：综上所述其变换形式如下：原问题（或对偶问题）原问题（或对偶问题）对偶问题（或原问题）对偶问题（或原问题）目标函数目标函数 max目标函数目标函数 min约约束束条条件件m

15、个个m个个变变量量0000=无约束无约束变变量量n个个n个个约约束束条条件件0000无约束无约束=约束条件右端项约束条件右端项目标函数变量的系数目标函数变量的系数目标函数变量的系数目标函数变量的系数约束条件右端项约束条件右端项例2-7：写出下列线性规划的对偶问题 min z=7xmin z=7x1 1+4x+4x2 2-3x-3x3 3s.t.-4xs.t.-4x1 1+2x+2x2 2-6x-6x3 32424 -3x -3x1 1-6x-6x2 2-4x-4x3 31515 5x 5x2 2+3x+3x3 3=30=30 x x1 10,x0,x2 2取值无约束取值无约束,x,x3 300

16、Max w=24y1+15y2+30y3s.t.-4y1-3y2 7 2y1-6y2+5y3=4 -6y1-4y2+3y3-3 y10,y20,y3无约束例例2-82-8：写出下列线性规划问题的对：写出下列线性规划问题的对偶问题偶问题 min w=3x min w=3x1 1-2x-2x2 2+x+x3 3s.t.xs.t.x1 1+2x+2x2 2 =1 =1 y y1 1 2x 2x2 2 -x-x3 3 -2 -2 y y2 2 2x 2x1 1 +x+x3 3 3 3 y y3 3 x x1 1-2x-2x2 2+3x+3x3 3 4 4 y y4 4 x x1 1，x x2 2 0

17、0 ，x x3 3 无非负限制无非负限制解解:综合运用对偶原则得到综合运用对偶原则得到 max g =y max g =y1 1-2y-2y2 2+3y+3y3 3+4y+4y4 4 s.t.y s.t.y1 1+2y+2y3 3+y+y4 4 3 3 2y 2y1 1+2y+2y2 2 -2y-2y4 4 -2-2 -y -y2 2+y+y3 3+3y+3y4 4 =1=1 y y2 200,y y3,3,y y4 4 0 0，y y1 1 无非负约束无非负约束定理定理2.1:(2.1:(弱对偶定理弱对偶定理)对于互为对偶问题对于互为对偶问题(I)(II)(I)(II)中中的任意的可行解的任

18、意的可行解x x(0)(0),y,y(0)(0),都有都有 c x c x(0)(0)y y(0)(0)b b2.2 对偶问题的基本定理对偶问题的基本定理定理定理2.2 (2.2 (最优准则最优准则)若原问题的某一个可行解与若原问题的某一个可行解与对偶问题的某一可行解的目标函对偶问题的某一可行解的目标函数值相等数值相等,则它们分别是原问题则它们分别是原问题与对偶问题的最优解与对偶问题的最优解.定理定理2.3 (2.3 (对偶定理对偶定理)若原问题有最优解若原问题有最优解,则对偶则对偶问题也有最优解问题也有最优解,且最优值相等且最优值相等.性质性质2.4 2.4 如果原问题如果原问题(对偶问题）

19、具有无界对偶问题）具有无界解，则其对偶问题（原问题）无可解，则其对偶问题（原问题）无可行解。行解。但原问题但原问题(对偶问题对偶问题)无可行解时，无可行解时，其对偶问题（原问题）或无可行解其对偶问题（原问题）或无可行解或具有无界解。或具有无界解。定理定理2.52.5（互补松弛性）（互补松弛性）在线性规划问题的最优解中，如在线性规划问题的最优解中，如果该约束条件取严格等式，则对应果该约束条件取严格等式，则对应某一约束条件的对偶变量值为非零；某一约束条件的对偶变量值为非零；反之如果约束条件取严格不等式，反之如果约束条件取严格不等式，则其对应的对偶变量一定为零。则其对应的对偶变量一定为零。max Z

20、=2x1+3x2 s.t.2x1+2x2 12 4x1 16 5x2 15 x1,x2 0它的最优解为（3，3）而对于第二个约束条件，为严格的不等式，所以y2=0y1y2y3性质2.6 对偶问题的最优解为原问题最优表对偶问题的最优解为原问题最优表中中,相应的松驰变量检验数的相反数。相应的松驰变量检验数的相反数。（线性规划的原问题与对偶问题中，原问题的松弛变量对应对偶问题的变量，对偶问题的剩余变量对于原问题的变量。）例：max Z=2xmax Z=2x1 1+3x+3x2 2 s.t.2x s.t.2x1 1+2x+2x2 2+x+x3 3 12 12 4x 4x1 1 +x +x4 4 16

21、16 5x 5x2 2+x+x5 5 1515 x x1 1,x,x2 2 0 0CB B 基 b x1 1 x2 2 x3 3 x4 4 x5 5 2 x1 1 3 0 x4 4 4 3 x2 2 3 1 0 0 -1/5 0 0 -2 1 4/5 0 1 0 0 1/5Cj-zj 0 0 -1 0 -1/5原问题变量原问题松弛变量对偶问题变量对偶问题的剩余变量Y2 2Y5 5Y4 4Y3 3Y4 42.3 影子价格在线性规划原问题和对偶问题中：bi代表第i种资源的拥有量，而yi代表对一个单位第i种资源的估价影子价格不是市场价格，随企业的生产任务和产品结构而发生变化。影子价格是一种边际价格。

22、Z=bTy*=b1y1*+b2y2*+bmym*可知 Z/bi=yi*2X+2y=12123456654321X=4X=3max Z=2x1+3x2 s.t.2x1+2x2 12 4x1 16 5x2 15 x1,x2 0点（3，3）是最优解，z*=15当A的资源变为13小时，z*=16,说明A的边际价格是1，即影子价格是1。在对偶问题的互补松弛性质中有表示某种资源bi没有充分利用，该种资源的影子价格为零。如果表示该种资源已耗费完毕。是生产该种产品所消耗的各项资源的影子价格总和，即产品的隐含成本。从影子价格的含义上再来考察单纯形法的计算：当检验数大于零，说明生产此种产品有利，可在生产中安排。2

23、.4 对偶单纯形法例：求解如下线性规划问题：min w=12y1+16y2+15y3 s.t.2y1+4y2 2 2y1+5y3 3 y1,y2,y3 0 划为标准形：max w=-12y1-16y2-15y3 -2y1-4y2 +y4 =-2 -2y1 -5y3 +y5=-3 yi 0（i=1,5)Cj-12 -16 -15 0 0CB 基 bY1 y2 y3 y4 y50 y4 -20 y5 -3-2 -4 0 1 0-2 0 -5 0 1Cj-Zj-12 -16 -15 0 0如何转换?当bi0时，令min(bi)所对应的行中的Xr为换出基变量。令所对应的列变量为换入基变量Y5为换出基变

24、量故x3为换入基变量，-5为主元素Cj-12 -16 -15 0 0CB 基 bY1 y2 y3 y4 y50 y4 -2-15 y3 3/5-2 -4 0 1 02/5 0 1 0 -1/5Cj-Zj-6 -16 0 0 -3Y4为换出基变量故Y1为换入基变量，-2为主元素Cj-12 -16 -15 0 0CB 基 bY1 y2 y3 y4 y5-12 y1 1-15 y3 1/5 1 2 0 -1/2 0 0 -4/5 1 1/5 -1/5Cj-Zj 0 -4 0 -3 -3故此问题的最优解为：Y1=1，Y2=0，Y3=1/5，W=15对偶单纯形法的基本思想 对偶单纯形法的基本思想是：从原

25、规划的一个基解基解出发，此基解不一定可行，但它对应着一个对偶可行解对偶可行解（检验数非正）；从对偶可行解出发，然后检验原规划的基本解是否可行，即是否有负的分量，如果有小于零的分量，则进行迭代，求另一个基解，此基解对应着另一个对偶可行解（检验数非正）。如果得到的基解的分量皆非负则该基解为最优解。也就是说，对偶单纯形法在迭代过程中始终保持对偶解的可行性（即检验数非正），使原规划的基解由不可行逐步变为可行对偶单纯形法在什么情况下使用：应用前提：有一个基，其对应的基满足:单纯形表的检验数行全部非正（对偶可行）；变量取值可有负数（非可行解）。注：通过矩阵行变换运算，使所有相应变量取值均为非负数即得到最优

26、单纯形表。对偶单纯形法求解线性规划问题过程：对偶单纯形法求解线性规划问题过程：1.建立初始对偶单纯形表,对应一个基本解,所有检验数均非正,转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）的解，故原问题无可形解，这时对偶问题的目标函数

27、值无界。例题例题:用对偶单纯形法求解用对偶单纯形法求解解:将上述模型转化为Cj-9 -12 -15 0 0 0CB 基 bX1 x2 x3 x4 x5 x6 0 x4 -10 0 x5 -12 0 x6 -14-2 -2 -1 1 0 0-2 -3 -1 0 1 0-1 -1 -5 0 0 1 Cj-zj-9 -12 -15 0 0 0=min(-9/-1,-12/-1,-15/-5)=3Cj-9 -12 -15 0 0 0CB 基 bX1 x2 x3 x4 x5 x6 0 x4 -36/5 0 x5 -46/5 -15 x3 14/5-9/5 -9/5 0 1 0 -1/5-9/5 -14/

28、5 0 0 1 -1/51/5 1/5 1 0 0 -1/5 Cj-zj-6 -9 0 0 0 -3=min(6*5/9,9*5/14,15)=45/14Cj-9 -12 -15 0 0 0CB 基 bX1 x2 x3 x4 x5 x6 0 x4 -9/7 -12 x2 23/7 -15 x3 15/7-9/14 0 0 1 -9/14 -1/149/14 1 0 0 -5/14 1/141/14 0 1 0 1/14 -3/14 Cj-zj-3/14 0 0 0 -45/14 -33/14=min(1/3,5,33)=1/3Cj-9 -12 -15 0 0 0CB 基 bX1 x2 x3 x4 x5 x6-9 x1 2 -12 x2 2 -15 x3 21 0 0 -14/9 1 1/90 1 0 1 -1 00 0 1 1/9 0 -2/9 Cj-zj0 0 0 -1/3 -3 -7/3 所以，所以，X*=（2.2.2.0.0.0）Z*=72，原问题原问题 Z*=72 其对偶问题的最优解为：其对偶问题的最优解为：Y*=(1/3.3.7/3)，W*=72