人工变量法和两阶段法课件.ppt

1、人工变量法和两阶段法人工变量法和两阶段法 对于一般的线性规划问题，在用单纯形法求解对于一般的线性规划问题，在用单纯形法求解之前，总是先化为标准型。如果在系数矩阵中有一之前，总是先化为标准型。如果在系数矩阵中有一个单位阵，则可以作为初始可行基。个单位阵，则可以作为初始可行基。如果约束条件的系数矩阵中不存在单位矩阵，如果约束条件的系数矩阵中不存在单位矩阵，则可以通过添加人工变量的方法，在标准型的约束则可以通过添加人工变量的方法，在标准型的约束方程的系数矩阵中人为地构造一个单位阵，从而获方程的系数矩阵中人为地构造一个单位阵，从而获得初始可行基，再作进一步迭代。得初始可行基，再作进一步迭代。上周内容回

2、顾上周内容回顾 在单纯形迭代过程中，要求人工变量逐步从基在单纯形迭代过程中，要求人工变量逐步从基变量被替换出，变为非基变量，最后，基变量中不变量被替换出，变为非基变量，最后，基变量中不含有人工变量。含有人工变量。为使人工变量被替换出成为非基变量，有为使人工变量被替换出成为非基变量，有1.1.大大M法法2.2.两阶段法两阶段法1.大大M法：在目标函数求最大值的线性规划问题中，法：在目标函数求最大值的线性规划问题中，设人工变量在目标函数中的系数为设人工变量在目标函数中的系数为-M，M为任意大为任意大的正数。只要人工变量不为零，目标函数最大值就的正数。只要人工变量不为零，目标函数最大值就是一个任意小

3、的数。是一个任意小的数。两阶段法两阶段法 第一阶段：希望人工变量等于第一阶段：希望人工变量等于0，为此，构造只，为此，构造只含人工变量的目标函数，并要求实现最小化。含人工变量的目标函数，并要求实现最小化。用单纯形法求解上述模型，若得到用单纯形法求解上述模型，若得到W=0,则必有则必有x6=x7=0。说明原问题存在基可行解，可以进行第二。说明原问题存在基可行解，可以进行第二阶段计算，否则原问题无可行解，应停止计算。阶段计算，否则原问题无可行解，应停止计算。第二阶段：将第一阶段计算得到的最终表，去掉第二阶段：将第一阶段计算得到的最终表，去掉人工变量，将目标函数换为原问题的目标函数，作为人工变量，将

4、目标函数换为原问题的目标函数，作为第二阶段计算的初始表，继续单纯形法第二阶段计算的初始表，继续单纯形法，直至求得，直至求得最优解。最优解。无无可行解在大可行解在大M法中判断法中判断:检验数全部小于等于零且检验数全部小于等于零且有人工变量为基变量，则此线性规划模型无可行解。有人工变量为基变量，则此线性规划模型无可行解。无无可行解在两阶段法中判断可行解在两阶段法中判断:如果第一阶段求解结果如果第一阶段求解结果最优解的目标函数值不为最优解的目标函数值不为0，也即最优解的基变量中，也即最优解的基变量中含有非零的人工变量，表明原含有非零的人工变量，表明原LP问题无可行解。问题无可行解。4.1 对偶模型的

5、提出对偶模型的提出4.2 原模型与对偶模型的线性规划模型之原模型与对偶模型的线性规划模型之 间的关系间的关系4.3 对偶模型的基本性质对偶模型的基本性质4.4 对偶模型的经济意义对偶模型的经济意义影子价格影子价格4.5 对偶模型最优解和影子价格对偶模型最优解和影子价格4.6 对偶单纯形法对偶单纯形法第第4 4章章 对偶模型对偶模型4.2 4.2 原模型与对偶模型的线性规划模型原模型与对偶模型的线性规划模型之间的关系之间的关系定义定义1 具有下列特点的线性规划模型称为对称形式的具有下列特点的线性规划模型称为对称形式的线性规划模型，线性规划模型，4.2.1 对称形式线性规划模型的对偶模型对称形式线

6、性规划模型的对偶模型原问题中各系数矩阵为原问题中各系数矩阵为它的对偶问题是：它的对偶问题是：123,Yyyy 这这里里123123123min904902405262680,1,2,3iWyyyyyyyyyyi min90490240115268260TWYYY 1212121212max68905249026240,0Zxxxxxxxxxx 1190524906826240AbC例如：(P)2x 2 206038045060212112121 xxyxyxxxxz,max 0 342 24 121683213121321 y,y,yyyyy.t.syyymin 0 124 16 4 82 3

7、221322112121 x,xyxyxyxxxxzmax05024603608021212121 yyyyyytsyy,.min 2 4.2.2 一般形式的线性规划模型与对偶模型之间的关系一般形式的线性规划模型与对偶模型之间的关系 对于非对称形式的线性规划模型如何写出其对对于非对称形式的线性规划模型如何写出其对偶模型？偶模型？其思路是首先将非对称形式转换为对称形式，然其思路是首先将非对称形式转换为对称形式，然后再按照对应关系写出其对偶模型。后再按照对应关系写出其对偶模型。原问题求极小原问题求极小-minmaxZZ 原问题约束方程有原问题约束方程有“”-两边同乘（两边同乘（-1），），“”原问

8、题约束方程有原问题约束方程有“=”-对偶问题？对偶问题？112233111122133121122223323113223333123max.490,0,Zc xc xc xa xa xa xba xa xa xbsta xa xa xbxxx （）无无约约束束【例【例4-3】写出下列线性回归模型的对偶模型】写出下列线性回归模型的对偶模型原问题约束方程有原问题约束方程有“=”，如何转化？，如何转化？21122223322112222332211222233221122223322112222332a xa xa xba xa xa xba xa xa xba xa xa xba xa xa x

9、b （1 1）将将约约束束条条件件2 2的的等等式式约约束束转转化化为为两两个个不不等等式式约约束束311322333331132233332a xa xa xba xa xa xb （）将将约约束束条条件件3 3两两端端同同乘乘-1-1，得得223332333xxxxxxxx （）非非负负变变量量约约束束变变换换为为；，其其中中0 0，0 0，0 0。1122333311112213313312112222332332211222233233231132233333331233max.0,Zc xc xc xc xa xa xa xa xba xa xa xa xbsta xa xa xa

10、xba xa xa xa xbxxxx 原原数数学学模模型型转转换换为为对对称称形形式式的的数数学学模模型型：0 0，0 0，0 0 原问题：原问题：max0ZCXAXbX 对偶问题：对偶问题：min0WYbYACY 对称对称形式形式线性线性规划规划模型模型的对的对偶模偶模型型122311222233111212212313112122222232321312322323333131232232333312:min0,yyyyWb yb yb yb ya ya ya ya yca ya ya ya yca ya ya ya yca xa ya ya ycyyy 令令各各约约束束对对应应的的对对

11、偶偶变变量量分分别别为为，则则对对偶偶模模型型为为0 0，23,0y 0 0222331122331112123131121222323213123233331312323333123,min0,0yyyyyWb yb yb ya ya ya yca ya ya yca ya ya yca ya ya ycyyy 令令，则则得得到到：无无约约束束,112233111212313112122232321312323333123min0,0Wb yb yb ya ya ya yca ya ya yca ya ya ycyyy 无无约约束束,将条件将条件2两端同乘两端同乘-1，并将条件并将条件3、4

12、合并为合并为等式，得等式，得原问题原问题目标函数目标函数约束条件右端项约束条件右端项目标函数中变量的系数目标函数中变量的系数约束矩阵约束矩阵A对偶问题对偶问题目标函数目标函数目标函数中变量的系数目标函数中变量的系数约束条件右端项约束条件右端项A的转置为约束矩阵的转置为约束矩阵1maxnjjjZc x 1minmiiiWb y 112233111122133121122223323113223333123max.0,0,Zc xc xc xa xa xa xba xa xa xbsta xa xa xbxxx 无无约约束束1122331112123131121222323213123233331

13、23min.0,0Wb yb yb ya ya ya yca ya ya ycsta ya ya ycyyy 无无约约束束,原问题原问题(或对偶问题或对偶问题)对偶问题对偶问题(或原问题或原问题)目标函数目标函数maxZn个个变量变量变量变量0变量变量0变量无限制变量无限制目标函数目标函数minWn个个约束约束约束约束约束约束约束约束=约束约束m个个约束约束约束约束约束约束=约束右端项约束右端项目标函数系数目标函数系数m个个变量变量变量变量0变量变量 0变量无限制变量无限制目标函数系数目标函数系数约束右端项约束右端项原模型与对偶模型之间的关系原模型与对偶模型之间的关系Max w=5y1+4y2

14、+6y3 y1+2y2 y1 +y3 -3y1+2y2+y3 y1-y2 +y3=y10,y20,y3无约束设对偶变量为设对偶变量为y y1 1,y,y2 2,y,y3 3,对偶对偶问题模型为：问题模型为：【例【例4-4】写出下列线性规划模型的对偶模型】写出下列线性规划模型的对偶模型无约束无约束432143243143214321006 42 2 53 532x;x,x;xxxxxxxxxxxxxxxzmin 23-5105643732532432321321321321321 xxxxxxxxxxxxxxxZ,min05643732532432321321321321321 xxxxxxxx

15、xxxxxxxZ,max321yyy04675343232532321321321321321 yyyyyyyyyyyyyyyW,min321532yyyW max32132yyy 2343321 yyy4675321 yyy0321 yyy,031 yy,02 y4.3 对偶模型的基本性质对偶模型的基本性质对称性对称性弱对偶性弱对偶性最优解性最优解性强对偶性（对偶定理）强对偶性（对偶定理）互补松弛性互补松弛性（1 1）原问题任一可行解的目标函数值是其对偶问题目）原问题任一可行解的目标函数值是其对偶问题目标函数值的下界；反之对偶问题任一可行解的目标函标函数值的下界；反之对偶问题任一可行解的目标

16、函数值是其原问题目标函数值的上界。数值是其原问题目标函数值的上界。（2 2）如原问题有可行解且目标函数值无界（或具有无）如原问题有可行解且目标函数值无界（或具有无界解），则其对偶问题无可行解；反之对偶问题有可界解），则其对偶问题无可行解；反之对偶问题有可行解且目标函数值无界，则其原问题无可行解（注意：行解且目标函数值无界，则其原问题无可行解（注意：本点性质的逆不成立，当对偶问题无可行解时，其原本点性质的逆不成立，当对偶问题无可行解时，其原问题或具有无界解或无可行解，反之亦然）。问题或具有无界解或无可行解，反之亦然）。由弱对偶性可得出以下推论由弱对偶性可得出以下推论：（3 3）若原问题有可行解而

17、其对偶问题无可行解，）若原问题有可行解而其对偶问题无可行解，则原问题目标函数值无界；反之对偶问题有可则原问题目标函数值无界；反之对偶问题有可行解而其原问题无可行解，则对偶问题的目标行解而其原问题无可行解，则对偶问题的目标函数值无界。函数值无界。),(max3210132232332132121 jxxxxxxxxxZj 试用对偶理论证明上述问题无最优解。试用对偶理论证明上述问题无最优解。例例 已知线性规划问题已知线性规划问题),(max3210132232332132121 jxxxxxxxxxZj对偶问题对偶问题0033321222121212121 yyyyyyyyyyW,minX（0）=

18、（0，0，0）T是是原问题的一个可行解原问题的一个可行解原问题原问题对偶问题不可行对偶问题不可行 若原问题有可行解而其对偶问题无可行解，若原问题有可行解而其对偶问题无可行解，则原问题目标函数值无界。则原问题目标函数值无界。y10，y20，不满足不满足该约束该约束条件条件性质性质3 3 最优性最优性 设设 是原问题的可行解，是原问题的可行解，是对偶问题的可行是对偶问题的可行解，当解，当 时，时，是最优解。是最优解。XYCXYb利用弱对偶定理利用弱对偶定理同理可知同理可知,也是最优解也是最优解.X 对任何可行解，均有对任何可行解，均有 ，故，故 是目是目标函数取值最小的可行解，因而是最优解。标函数

19、取值最小的可行解，因而是最优解。YbCXYbX,YY性质性质4 强对偶性（对偶定理）强对偶性（对偶定理）若原问题有最优解，则对偶问题也有最优解，且若原问题有最优解，则对偶问题也有最优解，且目标函数最优值相等。目标函数最优值相等。X01ABCCB1BYAC,YC B其其中中Y1BWYbC B bX1BZCXC B b1BYbC B bCXY证：设证：设 是原问题的最优解是原问题的最优解，它对应的基矩阵必存，它对应的基矩阵必存 在在 ，即得到，即得到 若这时若这时 是对偶问题的可行解，它使是对偶问题的可行解，它使 因原问题的最优解因原问题的最优解 使目标函数取值使目标函数取值 由此得到由此得到 可

20、见可见 是对偶问题的最优解。是对偶问题的最优解。原问题与对偶问题的解和目标函数值之间的原问题与对偶问题的解和目标函数值之间的关系关系原问题原问题关系关系对偶问题对偶问题目标函数目标函数最优解最优解无界解无界解无可行解无可行解最优解最优解无可行解无可行解无界解无界解Z*=W*性质性质5 互补松弛性互补松弛性 设设X*和和Y*分别原问题和对偶问题的可行解，那么分别原问题和对偶问题的可行解，那么 Y*XS*=0和和 YS*X*=0，当且仅当，当且仅当X*，Y*是最优解。是最优解。AX*bAX*+XS*=bXS*=b-AX*Y*（b-AX*)=0Y*XS*=002121 *),(smssmxxxyyy

21、02211 *smmssxyxyxy充分必要条件充分必要条件Y*（b-AX*)=0 (Y*A-C)X*=002211 *smmssxyxyxy0002211 *smmssxyxyxy00001111 *yxxyss则则若若则则若若对偶变量不为对偶变量不为0，原问题相应，原问题相应约束式是等式约束式是等式原问题约束为原问题约束为不等式，相应不等式，相应对偶变量为对偶变量为0最优解点最优解点 已知线性规划问题已知线性规划问题【例【例4-5】已知线性规划模型已知线性规划模型（1）写出该模型的对偶模型）写出该模型的对偶模型（2）已知原模型的最优解为：）已知原模型的最优解为：X=（2，2，4，0）T根据

22、对偶理论，直接求对偶模型的最优解。根据对偶理论，直接求对偶模型的最优解。123412412123234max243826.960,1,2,3,4jZxxxxxxxxxs txxxxxxxj （1）对偶模型是：）对偶模型是：（2）已知原模型的最优解为：）已知原模型的最优解为：X=（2，2，4，0）T根据对偶理论，直接求对偶模型的最优解。根据对偶理论，直接求对偶模型的最优解。12341231233414min86962234110,1,2,3,4iWyyyyyyyyyyyyyyyi 123412412123234max243826.960,1,2,3,4jZxxxxxxxxxs txxxxxxxj

23、 （2）根据原模型的最优解为）根据原模型的最优解为X=（2，2，4，0）T将其代入原问题的约束条件，得原模型的松弛变量：将其代入原问题的约束条件，得原模型的松弛变量：x5=0，x6=0，x7=1，x8=012451261237234838(1)26(2).9(3)6(4)0,1,2,3,4jxxxxxxxs txxxxxxxxxj 约束条件约束条件(3)为严格不等式，由互补松弛定理知：为严格不等式，由互补松弛定理知：y3*=0由原模型的最优解为由原模型的最优解为X=（2，2，4，0）T，根据互，根据互补松弛定理知：补松弛定理知：y5=0，y6=0，y7=0，12312343432234.10y

24、yyyyyystyyy12341231233414min86962234110,1,2,3,4iWyyyyyyyyyyyyyyyi求解上面的方程组得：求解上面的方程组得：y1*=4/5，y2*=3/5，y3*=0,y4*=1设对偶模型的剩余变量为设对偶模型的剩余变量为y5，y6，y7，y8，当某约束条件的右端常数增加一个单位时（假当某约束条件的右端常数增加一个单位时（假设原问题的最优基不变），原问题的目标函数最优设原问题的最优基不变），原问题的目标函数最优值增加的数量。值增加的数量。目标函数目标函数Z=CBB-1b和检验数和检验数CN-CBB-1N中都有乘子中都有乘子Y=CBB-1,Y的经济意

25、义？的经济意义？设设B是是 的最优解，则该的最优解，则该基所对应最优解的目标函数值基所对应最优解的目标函数值 Z*=CBB-1b=Y*b0X,bAXCXZmax由此由此*YBCb*ZB14.4 对偶模型的经济意义对偶模型的经济意义影子价格影子价格当某个右端常当某个右端常数数bi bi+1时时m*mi*i*mi*m*i*bybybybybbbby,y,y,yb*Y*CX*Z22112121m*mi*i*bybybyby*Z12211*im*mi*i*ybybybyby*Z2211*iyb*Y*iy*Z第第i 种资源的影子种资源的影子价格是第价格是第i个约束条个约束条件的右端常数增加件的右端常数增

26、加一个单位时，目标一个单位时，目标函数增加的数量函数增加的数量 在在【例【例4-14-1】中，当原问题和对偶问题都取得最】中，当原问题和对偶问题都取得最优解时，这一对线性规划对应的目标函数值相等，优解时，这一对线性规划对应的目标函数值相等，即有：即有：其中其中X X*=（7575，1515）T T，是原问题的最优解，是原问题的最优解，y y*=（5 5，0 0，0.50.5）T T是对偶问题最优解。是对偶问题最优解。121236857090490240570ZCXxxWY byyy 若甲原料供应量能增加一个单位，即右端常数向若甲原料供应量能增加一个单位，即右端常数向量量b=(90，490，24

27、0)T中的中的b1从从90个单位增加到个单位增加到91个个单位，则目标函数值的变化量为：单位，则目标函数值的变化量为：1231231(91490240)(90490240)5yyyyyyy 对偶变量对偶变量 的意义的意义代表在资源最优利用条件下代表在资源最优利用条件下对单位第对单位第 种资源的估价，这种估价不是资源的市种资源的估价，这种估价不是资源的市场价格，而是根据资源在生产中作出的贡献而作的场价格，而是根据资源在生产中作出的贡献而作的估价，为区别起见，称为影子价格（估价，为区别起见，称为影子价格（shadow price)shadow price)。*iyi1231231(91490240

28、)(90490240)5yyyyyyy y1*=5描述了在生产最优安排下，原料甲的变动描述了在生产最优安排下，原料甲的变动给总利润带来的影响。给总利润带来的影响。1资源的市场价格是已知数，相对比较稳定，而它资源的市场价格是已知数，相对比较稳定，而它的影子价格则有赖于资源的利用情况，是未知数。的影子价格则有赖于资源的利用情况，是未知数。由于企业生产任务、产品结构等情况发生变化，资由于企业生产任务、产品结构等情况发生变化，资源的影子价格也随之改变。源的影子价格也随之改变。2影子价格是一种边际价格。影子价格是一种边际价格。在式中，在式中，。说明说明 的值相当于在资源得到最优利用的生产的值相当于在资源

29、得到最优利用的生产条件下，条件下，每增加一个单位时目标函数每增加一个单位时目标函数 的增量。的增量。影子价格的经济意义影子价格的经济意义z*iybzi*iyib3资源的影子价格实际上又是一种机会成本资源的影子价格实际上又是一种机会成本.在纯市场经济条件下在纯市场经济条件下,当资源的市场价格低于影当资源的市场价格低于影子价格时，可以买进这种资源用于扩大生产；相反子价格时，可以买进这种资源用于扩大生产；相反当市场价格高于影子价格时，就会卖出这种资源获当市场价格高于影子价格时，就会卖出这种资源获利。随着资源的买进卖出，它的影子价格也将随之利。随着资源的买进卖出，它的影子价格也将随之发生变化，一直到影

30、子价格与市场价格保持同等水发生变化，一直到影子价格与市场价格保持同等水平时，才处于平衡状态，因此影子价格具有市场调平时，才处于平衡状态，因此影子价格具有市场调节的作用。节的作用。4在对偶问题的互补松弛性质中有在对偶问题的互补松弛性质中有 这表明生产过程中如果某种资源这表明生产过程中如果某种资源 未得到未得到充分利用时，该种资源的影子价格为零；又当充分利用时，该种资源的影子价格为零；又当资源的影子价格不为零时，表明该种资源在生资源的影子价格不为零时，表明该种资源在生产中已耗费完毕。产中已耗费完毕。110 y0nijjiijniijjija xby;a xb时时，当当当当时时，ib5从影子价格的含

31、义上考察单纯形表的检验数从影子价格的含义上考察单纯形表的检验数 的经济意义。的经济意义。jc第第j j种产品的产值或者利润种产品的产值或者利润1miijiy a 生产第生产第j j中产品所消耗各项资源的中产品所消耗各项资源的影子价格的总和。（即隐含成本）影子价格的总和。（即隐含成本）可见，产品产值或者利润可见，产品产值或者利润 隐含成本隐含成本 可生产该可生产该产品；否则，不安排生产。产品；否则，不安排生产。检验数的经济意义检验数的经济意义11mjjBjjiijicC B Pcy a 6一般说对线性规划问题的求解是确定资源的最一般说对线性规划问题的求解是确定资源的最优分配方案，而对于对偶问题的

32、求解则是确定对优分配方案，而对于对偶问题的求解则是确定对资源的恰当估价，这种估价直接涉及到资源的最资源的恰当估价，这种估价直接涉及到资源的最有效利用有效利用。原问题的最终单纯形表中松弛变量的检验数对原问题的最终单纯形表中松弛变量的检验数对应对偶问题的最优解。应对偶问题的最优解。如何从单纯形表中找到影子价格？如何从单纯形表中找到影子价格？4.5 对偶模型最优解和影子价格对偶模型最优解和影子价格4.5.1 对偶模型的最优解对偶模型的最优解对偶模型与原模型单纯形表之间的关系对偶模型与原模型单纯形表之间的关系 设设B是原问题的一个基，是原问题的一个基，A=(B,N),原问题可改写为原问题可改写为0SN

33、BSNBNNBBX,X,XbXNXBXXCXCZmax 其相应的对偶问题为其相应的对偶问题为02121SSNSBSY,Y,YCYYNCYYBYbWminmax0ZCXAXbX 对偶问题对偶问题02121SSNSBSY,Y,YCYYNCYYBYbWmin原问题的单纯形表原问题的单纯形表bBCBCNBCCbBBNBIBBBN1111110 XB XN XS 取取YS1为对偶问题的非基变量为对偶问题的非基变量,即有即有YS1=0,故可得故可得对偶问题的一个基解对偶问题的一个基解.Y=CBB-1 YS2=CBB-1N-CN YS1=0与原问题的检验数比较与原问题的检验数比较-原问题的检验数对应对偶问原

34、问题的检验数对应对偶问题的基解题的基解(差一负号差一负号)原原问问题题变量性质变量性质基变量基变量非基变量非基变量XBXNXS检验数检验数0CN-CBB-1N-CBB-1对偶对偶问题问题基解基解-YS1-YS2-Y变量性质变量性质非基变量非基变量基变量基变量 在用单纯形法求解原问题的过程中，每迭代一在用单纯形法求解原问题的过程中，每迭代一次，得到原问题的一个基本可行解，其对应一组检次，得到原问题的一个基本可行解，其对应一组检验数，这组检验数又对应对偶问题的一个解（只是验数，这组检验数又对应对偶问题的一个解（只是符号相反）。符号相反）。用单纯形法进行迭代求解得到最优单纯形表，用单纯形法进行迭代求

35、解得到最优单纯形表，那么对偶问题的最优解就是松弛变量和剩余变量对那么对偶问题的最优解就是松弛变量和剩余变量对应的检验数的相反数。应的检验数的相反数。例如，【例例如，【例4-1】线性规划模型的单纯形解法迭代过程】线性规划模型的单纯形解法迭代过程 原原问问题题 对对偶偶问问题题1212121212max68905249026240,0Zxxxxxxxxxx 123123123min904902405262680,1,2,3iWyyyyyyyyyyi 原模型的最优解：原模型的最优解：x x1 1=75=75，x x2 2=15=15。松弛变量对应的检。松弛变量对应的检验数为（验数为（-5-5，0 0，-0.5-0.5）。由此得对偶模型的最优解）。由此得对偶模型的最优解为：为：y1*=5，y2*=0，y3*=0.5。进一步求解【例进一步求解【例4-1】线性规划模型的对偶模型】线性规划模型的对偶模型原模型的最优解：原模型的最优解：5 5，0 0，0.50.5。对偶模型的最优解为。对偶模型的最优解为剩余变量对应的相反数剩余变量对应的相反数7575，1515。