657-2线性规划问题的对偶问题

1、2、线性规划问题的对偶问题 2.1 对偶问题设备能力设备能力设备a2h2h12h设备b4h0h16h设备c0h5h15h单位利润（元）23问该企业因安排生产两种产品各多少件，使总的问该企业因安排生产两种产品各多少件，使总的利润收入为最大？利润收入为最大？ 现某机械厂为扩大生产租借常山机器厂拥有的设备资源，问常山厂分别以每小时什么样的价格才愿意出租自己的设备？ 设常山厂将设备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,

2、3) 21xx0 xx151612xx5004222121321yyy151612min0yyy32yyy502042321321综上所述其变换形式如下：综上所述其变换形式如下：原问题（或对偶问题）原问题（或对偶问题）对偶问题（或原问题）对偶问题（或原问题）目标函数目标函数 max目标函数目标函数 min约约束束条条件件m个个m个个变变量量0000= =无约束无约束变变量量n个个n个个约约束束条条件件0000无约束无约束= =约束条件右端项约束条件右端项目标函数变量的系数目标函数变量的系数 例2-7：写出下列线性规划的对偶问题 min z=7xmin z=7x1 1+4x+4x2 2-3x-3

3、x3 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 300max w=24y1+15y2+30y3s.t. -4y1-3y2 7 2y1-6y2+5y3=4 -6y1-4y2+3y3-3 y10,y20,y3无约束 性质性质2.4 2.4 如果原问题如果原问题( (对偶问题）具有无对偶问题）具有无界解，则其对偶问题（原问题）无界解，则其对偶问题（原问题）无可行解。可行解。 但原问

4、题但原问题( (对偶问题对偶问题) )无可行解时，无可行解时，其对偶问题（原问题）或无可行解其对偶问题（原问题）或无可行解或具有无界解。或具有无界解。 定理定理2.52.5（互补松弛性）（互补松弛性） 在线性规划问题的最优解中，如在线性规划问题的最优解中，如果该约束条件取严格等式，则对应果该约束条件取严格等式，则对应某一约束条件的对偶变量值为非零；某一约束条件的对偶变量值为非零；反之如果约束条件取严格不等式，反之如果约束条件取严格不等式，则其对应的对偶变量一定为零。则其对应的对偶变量一定为零。它的最优解为（3，3）而对于第二个约束条件，为严格的不等式，所以y2=0y1y2y3 性质2.6线性规

5、划的原问题与对偶问题中，原问题的松弛变量对应对偶问题的变量，对偶问题的剩余变量对于原问题的变量。） 例：c 基 b x x x x x 2 x 3 0 x 4 3 x 3 1 0 0 -1/5 0 0 -2 1 4/5 0 1 0 0 1/5原问题变量原问题松弛变量对偶问题变量对偶问题的剩余变量yyyyy2.3 影子价格在线性规划原问题和对偶问题中： m1iiin1jjjybxczbi代表第i种资源的拥有量，而yi代表对一个单位第i种资源的估价 影子价格不是市场价格，随企业的生产任务和产品结构而发生变化。 影子价格是一种边际价格。 z= bty*=b1y1*+b2y2*+bmym* 可知 z

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

7、下线性规划问题： 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为换出基变量。 令0a|azcminrjrjjjj所对应的列变量为换入基变

8、量 y5为换出基变量515,2-12min故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/5 y4为换出基变量416,2-6min故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/5故此问题的最优解为：y1=1，y2=0，y3=1/5，w=15对偶单纯形法的基本思想 对偶单纯形法的基本思想是：从原规划的一个

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

10、优单纯形表。对偶单纯形法求解线性规划问题过程：对偶单纯形法求解线性规划问题过程： 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,这时原问题解的情况如何？ rnrn1m1m, rrbxaxax 故不可能存在xj

11、0（j=1,n）的解，故原问题无可形解，这时对偶问题的目标函数值无界。 )3.2.1(01451232102215129min321321321321jxxxxxxxxxxxxxzj 例题例题: :用对偶单纯形法求解用对偶单纯形法求解解:将上述模型转化为 01451232102215129max61632153214321321xxxxxxxxxxxxxxxxz 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-

12、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/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