第三章线性规划的对偶理论PPT讲稿.ppt

《第三章线性规划的对偶理论PPT讲稿.ppt》由会员分享，可在线阅读，更多相关《第三章线性规划的对偶理论PPT讲稿.ppt（117页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第三章线性规划的对偶理论1 1第1页，共117页，编辑于2022年，星期二第一节第一节 对偶规划问题对偶规划问题一、对偶问题的基本概念一、对偶问题的基本概念 1.对偶现象：事物的两面性。对偶现象：事物的两面性。例如：例如：（1）“在周长一定的四边形中，以正方形的在周长一定的四边形中，以正方形的面积最大。面积最大。”（2）“在面积一定的四边形中，以正方形的在面积一定的四边形中，以正方形的周长最小。周长最小。”这是一个现象的两个提法，我们称这两这是一个现象的两个提法，我们称这两种情况互为对偶，其中一个问题为原问题，种情况互为对偶，其中一个问题为原问题，另外一个问题为原问题的对偶问题。另外一个问题为

2、原问题的对偶问题。第2页，共117页，编辑于2022年，星期二例例例例1-1 1-1 1-1 1-1 某制药厂用甲、乙两台机器生产某制药厂用甲、乙两台机器生产某制药厂用甲、乙两台机器生产某制药厂用甲、乙两台机器生产A A A A、B B B B两种药物。每种药物要两种药物。每种药物要两种药物。每种药物要两种药物。每种药物要经过两道工序，在甲机器上搅拌，在乙机器上包装。已知在未来两经过两道工序，在甲机器上搅拌，在乙机器上包装。已知在未来两经过两道工序，在甲机器上搅拌，在乙机器上包装。已知在未来两经过两道工序，在甲机器上搅拌，在乙机器上包装。已知在未来两周内，甲、乙两台机器的使用时间分别不得超过周

3、内，甲、乙两台机器的使用时间分别不得超过周内，甲、乙两台机器的使用时间分别不得超过周内，甲、乙两台机器的使用时间分别不得超过40404040小时和小时和小时和小时和30303030小时，小时，小时，小时，生产每公斤药物生产每公斤药物生产每公斤药物生产每公斤药物A A A A的利润是的利润是的利润是的利润是30303030元，元，元，元，B B B B是是是是25252525元。生产每公斤药物所需的元。生产每公斤药物所需的元。生产每公斤药物所需的元。生产每公斤药物所需的加工时间如表所示：加工时间如表所示：加工时间如表所示：加工时间如表所示：试问，如何安排这两周的生产，能使工厂利润最大？试问，如何

4、安排这两周的生产，能使工厂利润最大？试问，如何安排这两周的生产，能使工厂利润最大？试问，如何安排这两周的生产，能使工厂利润最大？2.对偶问题：对偶问题：Max Max z z=30=30 x x x x1 1+25+25x x x x2 2 s.t.2 s.t.2x x x x1 1+4+4+4+4x x x x2 2 2 2 40 40 3 3x x1 1 1 1+2+2x x2 2 30 30 x x1 1,x x x x2 2 2 2 0 0药物药物（公斤）（公斤）甲加工时间甲加工时间（小时）（小时）乙加工时间乙加工时间（小时）（小时）利润利润（元）（元）A A2 23 33030B B

5、4 42 22525限制时间限制时间40403030A A：x x1 1公斤；公斤；B B：x x2 2公斤。公斤。第3页，共117页，编辑于2022年，星期二 设设设设 y y1 1 ，y y2 2 分别为出租资源设备甲分别为出租资源设备甲分别为出租资源设备甲分别为出租资源设备甲、乙、乙、乙、乙每工时收取的费用。每工时收取的费用。每工时收取的费用。每工时收取的费用。Min w=40Min w=40y y1 1+30+30y y2 2 (租金额最小）租金额最小）s.t.2s.t.2y y1 1+3+3y y2 2 30 30（药物（药物A A的租金不少于药物的租金不少于药物A A的的利润）利润

6、）4 4y y1 1+2+2y y2 2 25 25（药物（药物B B的租金不少于药物的租金不少于药物B B的的利润）利润）y y1 1,y y2 2,0,0若若若若第二章例第二章例第二章例第二章例1 1 1 1中制药厂的中制药厂的中制药厂的中制药厂的设备都用于外协加工，即设备都用于外协加工，即设备都用于外协加工，即设备都用于外协加工，即该厂的决策者不是该厂的决策者不是该厂的决策者不是该厂的决策者不是考虑自己生产甲、乙两种产品，而是将厂里的现有资源用于接受外考虑自己生产甲、乙两种产品，而是将厂里的现有资源用于接受外考虑自己生产甲、乙两种产品，而是将厂里的现有资源用于接受外考虑自己生产甲、乙两种

7、产品，而是将厂里的现有资源用于接受外来加工任务，来加工任务，来加工任务，来加工任务，工厂工厂工厂工厂只收取加工费。只收取加工费。只收取加工费。只收取加工费。试问：设备甲试问：设备甲试问：设备甲试问：设备甲、乙、乙、乙、乙每工时各应如何每工时各应如何每工时各应如何每工时各应如何收费才最有竞争力？收费才最有竞争力？收费才最有竞争力？收费才最有竞争力？下面从另一个角度来讨论这个问题：下面从另一个角度来讨论这个问题：分析问题：分析问题：1.1.每种资源收回的费用不能低于自己生产时的可获利每种资源收回的费用不能低于自己生产时的可获利润；润；2.2.定价又不能太高，要使对方能够接受。定价又不能太高，要使对

8、方能够接受。第4页，共117页，编辑于2022年，星期二 Max Max z z=30=30 x x1 1+25+25x x2 2 s.t.2 s.t.2x x1 1+4+4x x2 2 40 40 3 3x x1 1+2+2x x2 2 30 30 原问题原问题 x x1 1,x x2 2 0 0 Min w=40Min w=40y y1 1+30+30y y2 2 s.t.2 s.t.2y y1 1+3+3y y2 2 3030 4 4y y1 1+2+2y y2 2 2525 对偶问题对偶问题 y y1 1,y y2 2 0 0线性规划的对偶线性规划的对偶每一个线性规划（每一个线性规划（

9、LP ）必然有与之相伴而生的另一个线性规划问题，）必然有与之相伴而生的另一个线性规划问题，其中的一个问题叫其中的一个问题叫“原问题原问题”，记为，记为“L“LP”，另一个称为，另一个称为“对偶问题对偶问题”，记为，记为“DP”。第5页，共117页，编辑于2022年，星期二3.影子价格影子价格 在上例中，对偶问题的最优解为原问题约在上例中，对偶问题的最优解为原问题约束条件的影子价格，解束条件的影子价格，解yi称为第称为第i种资源（设备）种资源（设备）的影子价格。的影子价格。影子价格并非市场上的真实价格，而是企影子价格并非市场上的真实价格，而是企业根据本企业的具体生产过程，为使药物业根据本企业的具

10、体生产过程，为使药物A、B实现最大利润而得到的一种估计价格。为了实现最大利润而得到的一种估计价格。为了与市场价格相区别，我们称它为影子价格。影与市场价格相区别，我们称它为影子价格。影子价格是厂家对所拥有的资源的稀缺程度的一子价格是厂家对所拥有的资源的稀缺程度的一种度量，是相对于具体厂家而言的。种度量，是相对于具体厂家而言的。影子价格提供了一个价格的标准，如果市影子价格提供了一个价格的标准，如果市场上某种资源的价格低于影子价格，那么应当场上某种资源的价格低于影子价格，那么应当购进这种资源，增加生产，提高利润；反之就购进这种资源，增加生产，提高利润；反之就应该售出这种资源，求得更高的利润。应该售出

11、这种资源，求得更高的利润。第6页，共117页，编辑于2022年，星期二 对称形式：互为对偶 (LP)Max z=c x (DP)Min f=bT y s.t.Ax b s.t.AT y cT x 0 y 0 “Max-”“Min-”二、对称形式的对偶线性规划二、对称形式的对偶线性规划第7页，共117页，编辑于2022年，星期二 一对一对对称形式对称形式的对偶规划之间具有下面的对应关系。的对偶规划之间具有下面的对应关系。的对偶规划之间具有下面的对应关系。的对偶规划之间具有下面的对应关系。(1)(1)若若一一个个模模型型为为目目标标求求“极极大大”，约约束束为为“小小于于等等于于”的的不不等等式式

12、，则则它它的的对对偶偶模模型型为为目目标标求求“极极小小”，约约束束是是“大大于于等等于于”的的不不等等式式。即即“max“max，”和和“min“min，”相对应。相对应。相对应。相对应。(2)(2)(2)(2)从从从从约约约约束束束束系系系系数数数数矩矩矩矩阵阵阵阵看看看看：一一一一个个个个模模模模型型型型中中中中为为为为，则则另另一一个个模模型型中中为为A AT T T T。一一一一个个个个模模模模型型型型是是是是m m个个约约束束，n n个个变变量量，则则它它的的对对偶偶模模型为型为n n个约束，个约束，m m m m个变量。个变量。(3)(3)从从数数据据b b b b、C C的的的

13、的位位位位置置置置看看看看：在在在在两两两两个个个个规规规规划划划划模模模模型型型型中中中中，b b和和C C的的的的位置对换。位置对换。位置对换。位置对换。(4)(4)两个规划模型中的变量皆非负。两个规划模型中的变量皆非负。第8页，共117页，编辑于2022年，星期二 11 对偶规划问题对偶规划问题 P.44 任一任一L.P.问题，都有一个与之密切相关的问题，都有一个与之密切相关的L.P.问题，问题，叫对偶问题。叫对偶问题。给定一个给定一个L.P.问题，如何引出其对偶问题？见问题，如何引出其对偶问题？见P.52.表表 31。x1 x2.xn 原关系原关系 Min y1 a 11 a 12.a

14、 1n b b1 1 y2 a 21 a 22.a 2n b b2 2 .ym a m1 a m2.a mn b bm m 对偶关系对偶关系 .(X0,Y0,)(X0,Y0,)Max Z c Max Z c1 c c2 .cn 横向组合得原问题：横向组合得原问题：Max Z=c c1 x1+c c2 x2+.+c cn xn a 11 x1+a 12x2+.+a 1n xnbb1 1 a 21 x1+a 22x2+.+a 2n xnbb2 2 .a m1 x1+a m2x2+.+a mn xnbbm m X 0X 0纵向组合得对偶问题：纵向组合得对偶问题：Min =b1y1+b2y2+.+bm

15、ym a 11 y1+a 21 y2+.+a m1 ym c c1 1 a 12 y1+a 22 y2+.+a m2 ym c c2 2 .a 1n y1+a 2n y2 +.+a mn ym c cn n Y 0 Y 0若写成矩阵形式，可得：若写成矩阵形式，可得：原问题：原问题：对偶问题：对偶问题：Max Z=CX Min =bTY AX b Ab AT T Y Y CCT T X 0 YX 0 Y 00注意：其中注意：其中C C是行向量，是行向量，X X、Y Y与与b b是列是列向量，向量，AmnAmn为为a aijij所构成的矩阵。所构成的矩阵。2341第9页，共117页，编辑于2022

16、年，星期二其矩阵形式为：其矩阵形式为：对偶（原）问题为对偶（原）问题为:以下举例说明对偶问题的作法，见以下举例说明对偶问题的作法，见 P.52 例例 2原（对偶）问题：原（对偶）问题：Min Z=2x1+5x2 y1 x1 4 4 y2 x2 3 3 y3 x x1 1+2x2 8 x1 ,x2 00 x1 x2 1 0 1 0 1 2y y1 1 y y2 2y y3 3 对偶（原）问题为：对偶（原）问题为：MaxW=4y1+3 y2+8y3 y1+y3 2 2 x1y2 +2y3 5 5 x2y y1 10,y0,y2 20,y0,y3 300 25 1 0 0 1 1 2438 x1 x

17、2y y1 1 y y2 2y y3 3 XoYoMax W=(4 ,3 ,8)原（对偶）问题：原（对偶）问题：Min Z=(2,5)第10页，共117页，编辑于2022年，星期二写出下面线性规划的对偶规划写出下面线性规划的对偶规划：1.max z=2xmax z=2x1 1+3x+3x2 2 2x 2x1 1+2x+2x2 21212 x x1 1+2x+2x2 288 s.t.s.t.4x 4x1 1 16 16 4x 4x2 2 12 12 x x1 1,x,x2 200 2.第11页，共117页，编辑于2022年，星期二Min w=12y1+8y2+16y2+12y2s.t.2y1+y

18、2+4y3 22y1+2y2+4y4 3y1,y2,y3,y4 0解：解：2.首先将原式变形首先将原式变形对偶问题：对偶问题：解：解：1.第12页，共117页，编辑于2022年，星期二三、非对称的对偶线性规划三、非对称的对偶线性规划 对于对称形式的线性规划可按上述规则写出其对偶规划，但对于对称形式的线性规划可按上述规则写出其对偶规划，但对于对称形式的线性规划可按上述规则写出其对偶规划，但对于对称形式的线性规划可按上述规则写出其对偶规划，但是经常遇到的是非对称形式的线性规划问题（是经常遇到的是非对称形式的线性规划问题（是经常遇到的是非对称形式的线性规划问题（是经常遇到的是非对称形式的线性规划问题

19、（dual of a nonnormal LP），这时可将其转化为等价的、满足对），这时可将其转化为等价的、满足对称形式条件的线性规划问题，然后再按照对称形式的原称形式条件的线性规划问题，然后再按照对称形式的原问题与对偶问题的对应关系表，构造其对偶问题。问题与对偶问题的对应关系表，构造其对偶问题。在非对称形式向对称形式转化的过程中，在非对称形式向对称形式转化的过程中，在非对称形式向对称形式转化的过程中，在非对称形式向对称形式转化的过程中，若原问题是求目若原问题是求目标函数极大、约束条件不等式为标函数极大、约束条件不等式为“”，可在不等式两，可在不等式两端乘以端乘以-1，将，将“”化为化为“”；

20、若决策变量；若决策变量xj或或或或yiyi0000，则，则令令xj=-xj或或或或y yi i=-yi，将决策变量化为非负值。对于约束，将决策变量化为非负值。对于约束条件是等式的标准型形式的原问题，可由下述方法导条件是等式的标准型形式的原问题，可由下述方法导出其对偶规划问题。出其对偶规划问题。例如：对约束条件是等式的例如：对约束条件是等式的例如：对约束条件是等式的例如：对约束条件是等式的LPLP问题问题问题问题 max z=CX max z=CX s.t.AX=b X0 X0第13页，共117页，编辑于2022年，星期二 s.t.AX=b X0 由于由于 AXb AXb 即即AX=bAX=b

21、AXb-AX-b所以，原问题可化为所以，原问题可化为 max z=CX s.t.AXb -AX-b X0 A b X -A -b 第14页，共117页，编辑于2022年，星期二 设设设设YY：AXbAXb的对偶变量（行向量）的对偶变量（行向量）的对偶变量（行向量）的对偶变量（行向量）Y Y：-AX-b-AX-b的对偶变量（行向量）的对偶变量（行向量）的对偶变量（行向量）的对偶变量（行向量）按对称形式的对偶关系可得出原问题的对偶问题如下：按对称形式的对偶关系可得出原问题的对偶问题如下：按对称形式的对偶关系可得出原问题的对偶问题如下：按对称形式的对偶关系可得出原问题的对偶问题如下：min w =Y

22、b-Yb=min w =Yb-Yb=（Y-YY-Y）b b （Yb=bYb=bTYT）s.t YA-YAC （YA=A YA=ATY YT T）Y0，Y0 令令令令Y=Y-YY=Y-Y，则对偶问题为，则对偶问题为，则对偶问题为，则对偶问题为 min w=Yb min w=Yb s.t YAC s.t YAC Y Y符号不限符号不限符号不限符号不限 结论：原问题中约束条件为等式，对应的对偶变量无结论：原问题中约束条件为等式，对应的对偶变量无非负要求；反过来同样成立。非负要求；反过来同样成立。第15页，共117页，编辑于2022年，星期二 求下列原问题的对偶问题：求下列原问题的对偶问题：求下列原问

23、题的对偶问题：求下列原问题的对偶问题：max z=4x max z=4x1 1 1 1+5x+5x2 2 2 2 s.t.3x s.t.3x1 1+2x+2x2 2 2 220202020 4x 4x 4x 4x1 1-3x-3x2 2 2 21010 x x1 1 1 1+x+x2 2 2 2=5=5=5=5 x x x x1 1 0,x0,x2 2 符号不限符号不限符号不限符号不限 解：解：首先将原问题化成首先将原问题化成首先将原问题化成首先将原问题化成 对称形式，令对称形式，令 x x x x2 2=x=x3 3 3 3-x-x4 4 4 4,x x x x3 3 3 300，x x4

24、400，原问题化为原问题化为 max z=4xmax z=4xmax z=4xmax z=4x1 1+5x+5x3 3-5x-5x4 4 s.t.3x s.t.3x s.t.3x s.t.3x1 1+2x+2x+2x+2x3 3-2x-2x4 4 4 4 2020 -4x -4x -4x -4x1 1+3x+3x3 3 3 3-3x-3x4 4-10101010 x x1 1+x+x3 3xx4 4 5 5 -x -x1 1-x-x-x-x3 3 3 3+x+x+x+x4 4-5 5 5 5 x x x x1 1 1 1，x x3 3，x x4 4 4 4 00 将对称形式线性规划问题化为对偶

25、问题如下将对称形式线性规划问题化为对偶问题如下将对称形式线性规划问题化为对偶问题如下将对称形式线性规划问题化为对偶问题如下第16页，共117页，编辑于2022年，星期二 Min W=20wMin W=20w1-10w-10w2 2+5w+5w3-5w4 s.t.3w s.t.3w1-4w-4w2+w3 3-w4 444 2w 2w1 1+3w+3w2 2+w+w3 3-w4 45 -2w1 1-3w-3w2-w3+w+w4 4-5 w1，w w2，w3 3，w400 -1-1，得，得 2w 2w1+3w2 2+w3-w-w4 5 5 令令y y1 1=w=w1 1，y y2 2=w=w2，y3

26、 3=w=w3 3-w4，得，得 Min W=20y1 1-10y-10y2 2+5y3 s.t.3y s.t.3y1-4y2+y3 4 2y 2y1 1+3y+3y2+y3=5=5 y1 1，y2 20,y0,y3 3符号不限第17页，共117页，编辑于2022年，星期二原规划与对偶规划的线性关系56 56 表表3 33 3原（对偶）规划原（对偶）规划对偶（原）规划对偶（原）规划目标目标max zmax zmin fmin f目标目标约束约束mm个个 =mm个个 0 0 0 0自由自由变量变量变量变量n n个个 0 0 0 0自由自由n n个个 =约束约束限制向量限制向量b b价值向量价值向

27、量C C系数矩阵系数矩阵A A价值向量价值向量C C限制向量限制向量b b系数矩阵系数矩阵A AT T第18页，共117页，编辑于2022年，星期二 对对对对于于于于非非非非对对对对称称称称形形形形式式式式的的的的规规规规划划划划，可可可可以以以以按按按按照照照照下下下下面面面面的的的的对对对对应应应应关关关关系系系系直直直直接接接接给给给给出出出出其其其其对偶规划。对偶规划。对偶规划。对偶规划。（1 1 1 1）对对对对原原原原问问问问题题题题模模模模型型型型为为为为“max“max“max“max，约约约约束束束束条条条条件件件件为为为为”或或或或“min“min“min“min，约约约约

28、束束束束条条条条件件件件为为为为”的的的的形形形形式式式式，对对对对应应应应的的的的对对对对偶偶偶偶规规规规划划划划的的的的变变变变量量量量大大大大于于于于0 0 0 0；反反反反之之之之，若若若若原原原原问问问问题题题题模模模模型型型型为为为为“max“max“max“max，”或或或或“min“min“min“min，”的形式，对应的对偶规划的变量小于的形式，对应的对偶规划的变量小于的形式，对应的对偶规划的变量小于的形式，对应的对偶规划的变量小于0 0 0 0。（2 2 2 2）原原原原问问问问题题题题线线线线性性性性规规规规划划划划的的的的决决决决策策策策变变变变量量量量大大大大于于于于

29、0 0 0 0，则则则则对对对对偶偶偶偶问问问问题题题题的的的的模模模模型型型型为为为为“max“max“max“max，约约约约束束束束条条条条件件件件为为为为”或或或或“min“min“min“min，约约约约束束束束条条条条件件件件为为为为”的的的的形形形形式式式式；若若若若原原原原问问问问题题题题线线线线性性性性规规规规划划划划的的的的决决决决策策策策变变变变量量量量小小小小于于于于0 0 0 0；则则则则对对对对偶偶偶偶问问问问题题题题的的的的模模模模型型型型为为为为“max“max“max“max，”或或或或“min“min“min“min，”的形式。的形式。的形式。的形式。非对称

30、形式非对称形式的对偶规划的对偶规划 （3 3 3 3）若若若若原原原原规规规规划划划划的的的的某某某某个个个个约约约约束束束束条条条条件件件件为为为为等等等等式式式式约约约约束束束束，则则则则在在在在对对对对偶偶偶偶规规规规划划划划中中中中与与与与此约束对应的那个变量取值没有非负限制；此约束对应的那个变量取值没有非负限制；此约束对应的那个变量取值没有非负限制；此约束对应的那个变量取值没有非负限制；（4 4 4 4）若若若若原原原原规规规规划划划划的的的的某某某某个个个个变变变变量量量量的的的的值值值值没没没没有有有有非非非非负负负负限限限限制制制制，则则则则在在在在对对对对偶偶偶偶问问问问题题

31、题题中中中中与与与与此变量对应的那个约束为等式。此变量对应的那个约束为等式。此变量对应的那个约束为等式。此变量对应的那个约束为等式。第19页，共117页，编辑于2022年，星期二 max z=4x max z=4x1 1+5x+5x2 s.t.3x s.t.3x1 1+2x22020 4x1-3x-3x2 21010 x x1+x2 2 =5 x1 1 0,x2 符号不限符号不限 Min W=20yMin W=20y1+10y2+5y+5y3 3 s.t.3y1 1+4y2+y+y3 3 4 2y 2y1 1-3y-3y2 2+y3 3=5 y y1 0 0，y y2 20,y3 3符号不限符

32、号不限符号不限符号不限 Min W=20y Min W=20y1 1-10y2+5y3 3 s.t.3y1-4y2 2+y+y3 4 2y1+3y+3y2 2+y3 3=5 y1，y20,y0,y3 3符号不限符号不限 第20页，共117页，编辑于2022年，星期二 例例 写出下面线性规划的对偶规划模型写出下面线性规划的对偶规划模型解：先将约束条件变形为如下形式解：先将约束条件变形为如下形式第21页，共117页，编辑于2022年，星期二 再根据非对称形式的对应关系，直接写出对偶规划再根据非对称形式的对应关系，直接写出对偶规划max z=xmax z=x1 1 1 1-x-x2 2+5x+5x3

33、 3-7x-7x4 4 4 4 第22页，共117页，编辑于2022年，星期二求下列原问题的对偶问题：求下列原问题的对偶问题：1.max z=2x 1.max z=2x1 1+3x+3x2 2 s.t.2x s.t.2x1 1+x+x2 2=15=15 4x 4x1 1+3x+3x2 22020 x x1 1，x x2 2 0,0,2.max z=3x 2.max z=3x1 1-6x-6x2 2+5x+5x3 3+4x+4x4 4 s.t.x s.t.x1 1+2x+2x2 2-3x-3x3 3-4x-4x4 4=-5=-5 3x 3x1 1-x-x2 2+x+x3 3-7x-7x4 414

34、14 -4x -4x1 1-5x-5x2 2+3x+3x3 3+2x+2x4 43 x x1 1，x x2 2 0,x0,x3 3，x x4 4符号不限符号不限 第23页，共117页，编辑于2022年，星期二解答：1 Min W=15y1+20y2 s.t.2y1+4y2 4 y1+3y2 3 y1符号不限，y2 02 Min W=-5y1+14y2+3y3 s.t.Y1+3y2-4y3 3 2y1-y2-5y3-6 -3y1+y2+3y3 =5 -y1-7y2+2y3=4 y20，y3 0，y1符号不限第24页，共117页，编辑于2022年，星期二练习：练习：第25页，共117页，编辑于20

35、22年，星期二答案：答案：第26页，共117页，编辑于2022年，星期二作业题作业题课后习题二第课后习题二第1题（题（P7980页）。页）。第27页，共117页，编辑于2022年，星期二四、线性规划的矩阵表示第28页，共117页，编辑于2022年，星期二第29页，共117页，编辑于2022年，星期二初始单纯形表 非基变量基变量基XBXNXICIXIbBNICj=cj-ziCB-CIBCN-CIN0最优单纯形表基变量非基变量基XBXNXICBXBB-1 bIB-1NB-1Cj=cj-zi0CN-CB B-1 NCI-CB B-1第30页，共117页，编辑于2022年，星期二CBcj302500b

36、x1x2x3x40 x3241040 200 x432013010Cj302500Z=CBb=025x2013/8-1/415/230 x110-1/41/25Cj00-15/8-35/4Z=337.5XBXj请分别指出，请分别指出，B-1，B-1，CN-CB B-1 N，CI-CB B-1第31页，共117页，编辑于2022年，星期二初始单纯形表初始单纯形表2 2-1-11 10 00 0C CB BX XB Bb bx x1 1x x2 2x x3 3x x4 4x x5 50 0 x x4 46 61 11 11 11 10 00 0 x x5 54 4-1-12 20 00 01 1Z

37、 Z2 2-1-11 10 00 0最终单纯形表最终单纯形表2 2-1-11 10 00 0C CB BX XB Bb bx x1 1x x2 2x x3 3x x4 4x x5 52 2x x1 1（）（）（）（）1 1（）0 0 x x5 5（）（）（）（）1 1（）Z Z（）（）（）（）（）习题：一个极大化（目标函数为习题：一个极大化（目标函数为习题：一个极大化（目标函数为习题：一个极大化（目标函数为max Zmax Z）的线性规划问题，有三个非）的线性规划问题，有三个非）的线性规划问题，有三个非）的线性规划问题，有三个非负变量负变量负变量负变量x x1 1,x,x2 2,x,x3 3，

38、两个，两个，两个，两个“”“”型约束条件，型约束条件，型约束条件，型约束条件，x x4 4,x,x5 5是松弛变量，用单是松弛变量，用单是松弛变量，用单是松弛变量，用单纯形法计算时得到的初始单纯型表及最终单纯型表如下，最优单纯纯形法计算时得到的初始单纯型表及最终单纯型表如下，最优单纯纯形法计算时得到的初始单纯型表及最终单纯型表如下，最优单纯纯形法计算时得到的初始单纯型表及最终单纯型表如下，最优单纯型表中，型表中，型表中，型表中，x x1 1、x x5 5为基变量，请将表中空白处数字填上。为基变量，请将表中空白处数字填上。为基变量，请将表中空白处数字填上。为基变量，请将表中空白处数字填上。1 1

39、0 00 01 11 13 36 610101 11 10 0-3-3-1-1-2-20 0第32页，共117页，编辑于2022年，星期二性质一、对称性定理：对偶问题的对偶是原问题。性质一、对称性定理：对偶问题的对偶是原问题。第二节第二节 对偶问题的性质对偶问题的性质max z=-Cmax z=-CT TX Xs.t.-AXs.t.-AX-b-bX 0X 0min y=-bTWs.t.-ATW-CW 0max y=bTWs.t.ATWCW 0min z=Cmin z=CT TX Xs.t.AXbs.t.AXb X 0 X 0对偶的定义对偶的定义第33页，共117页，编辑于2022年，星期二其他

40、形式问题的对偶其他形式问题的对偶原问题与对偶问题互为对偶，任意一个原问原问题与对偶问题互为对偶，任意一个原问题经过两次对偶形式的转换后，必定等价于题经过两次对偶形式的转换后，必定等价于原问题。原问题。min z=CTXs.t.AXbX 0max y=bTWs.t.ATWC W 0min z=CTXs.t.AX=bX 0max y=bTWs.t.ATWC W：unr第34页，共117页，编辑于2022年，星期二性质二性质二 弱对偶性弱对偶性 若若X为原问题（最大化）为原问题（最大化）的可行解，的可行解，Y为对偶问题（最小化）的可为对偶问题（最小化）的可行解，行解，则则 CXYb。Max Max

41、z z=30=30 x x1 1+25+25x x2 2 CX s.t.2 s.t.2x x1 1+4+4x x2 2 40 40 3 3x x1 1+2+2x x2 2 30 30 原问题原问题 x x1 1,x x2 2 0 0 Min w=40Min w=40y y1 1+30+30y y2 2 Yb s.t.2 s.t.2y y1 1+3+3y y2 2 3030 4 4y y1 1+2+2y y2 2 25 25 对偶问题对偶问题 y y1 1,y y2 2,0 0第35页，共117页，编辑于2022年，星期二z z=30=30 x x1 1+25+25x x2 2 w=40w=40

42、y y1 1+30+30y y2 2(LP)Max z=c x (DP)Min f=y b s.t.Ax b s.t.y A c x 0 y 0 “Max-”“Min-”yAx yb y A x cx 由上面两个不等式由上面两个不等式 yb cx 弱对偶定理说明：如果原问题是最大化问题，则它的任一弱对偶定理说明：如果原问题是最大化问题，则它的任一弱对偶定理说明：如果原问题是最大化问题，则它的任一弱对偶定理说明：如果原问题是最大化问题，则它的任一可行解对应的目标函数值不大与其对偶问题（最小化问题可行解对应的目标函数值不大与其对偶问题（最小化问题可行解对应的目标函数值不大与其对偶问题（最小化问题可

43、行解对应的目标函数值不大与其对偶问题（最小化问题）的可行解对应的目标函数值。）的可行解对应的目标函数值。）的可行解对应的目标函数值。）的可行解对应的目标函数值。第36页，共117页，编辑于2022年，星期二性质三性质三（最优性判定定理最优性判定定理）可行解是最优解时的性）可行解是最优解时的性质质 当当X*是原问题（是原问题（Max）的可行解，）的可行解，Y*是其对偶问题是其对偶问题（Min）的可行解时，若的可行解时，若 CX*=Y*b，则，则 X*与与 Y*是各自问题是各自问题的最优解。的最优解。证明证明：设设X*是原问题的任意一个可行解，由性质是原问题的任意一个可行解，由性质 2即即弱对偶定

44、理可知，弱对偶定理可知，CX*YY*b b，又由又由 CX*=Y*b知知:CX*YY*b=CXb=CX*,就是说就是说,X,X*使目标函数所达到的值比其它任何可行解使目使目标函数所达到的值比其它任何可行解使目标函数所达到的值不会小，所以标函数所达到的值不会小，所以X X*是最优解。是最优解。同理（设同理（设Y*b CX*=Y*b），Y Y*是是其对偶问题的最优其对偶问题的最优解。解。证毕。证毕。第37页，共117页，编辑于2022年，星期二 性质四性质四 （强强对偶定理）若原问题有最优解，则对偶对偶定理）若原问题有最优解，则对偶问题也有最优解，且目标函数最优值相等。问题也有最优解，且目标函数最

45、优值相等。证明证明 设原问题的形式为：设原问题的形式为：Max Z=CX，AX b;X 0 b;X 0，于是，于是AX+XS=b=b，即（，即（A A，I I）=b =b，其中，其中A A为为 m x n m x n 矩阵，矩阵，I I为为 m m 阶单位阶单位矩阵，矩阵，XS为为m 维列向量。维列向量。既知有最优解，必有最优基变量对应的矩阵，记之为既知有最优解，必有最优基变量对应的矩阵，记之为 B B，那么，那么，在最终单纯形表中，检验数所形成的行向量为：在最终单纯形表中，检验数所形成的行向量为：（C-CC-CB BB B-1-1A A，-C-CB BB B-1-1）0 0，于是，于是 C-

46、C C-CB BB B-1-1A0 A0，即，即 C CB BB B-1-1A C A C （YA C）令令 Y Y*=C=CB BB B-1-1，又又-CBB-10，即，即 CBB-1 0，可得，可得 Y*=CBB-1 0，则则 YA C,Y Y*是对偶问题是对偶问题 （Min W=Yb;YA C;Y 0C;Y 0）的可行解，）的可行解，而而 W=Y W=Y*b=C b=CB B B B-1-1b b。因为。因为 B B 是最优是最优基变量对应的矩阵基变量对应的矩阵，所以，所以 Zmax=Zmax=CX=C CB B B B-1-1b=Yb=Y*b b，由性质由性质3 3，定理获证。，定理获

47、证。XXS对偶性质对偶性质对偶性质对偶性质4 4第38页，共117页，编辑于2022年，星期二 性质五性质五 （52页）互补松驰定理页）互补松驰定理 若若X*与与Y*分别为原问题和对偶问题分别为原问题和对偶问题的可行解，那么的可行解，那么Y*XS=0和和 YSX*=0的充分必要条件是的充分必要条件是 X*、Y*为最优为最优解。解。XS与与 YS分别为原问题和对偶问题的松弛变量和剩余变量。分别为原问题和对偶问题的松弛变量和剩余变量。Max Z=CXAX+XS=b b X 0 X 0 Min W=Yb YA-YS=C C Y 0 Y 0证明证明 必要性：设原问题和对偶必要性：设原问题和对偶 问题的

48、标准形式分别为：问题的标准形式分别为：和和 于是于是 C=YA-YS，b=b=AX+XS，所以所以Z Z（X X）=CX=CX=（YA-YS ）X=YAX-X=YAX-YS X X，而而 W W（Y Y）=Y b=Y=Y b=Y（AX+XS）=YAX+Y=YAX+YXS 可见可见,若若 Y*XS=YSX*=0,则则 Z（X*）=Y*AX*=W（Y*）,由性质由性质3知知 X*,Y*为最优解。必要性获证。以下证充分性。为最优解。必要性获证。以下证充分性。若若X*与与Y*分别为原问题和对偶问题的最优解，分别为原问题和对偶问题的最优解，由性质由性质4可知可知 Z（X*）=Y*AX*-YS X*=Y*

49、AX*+Y*XS=W（Y*）。又由于）。又由于X*与与Y*为可行为可行解，存在解，存在X*、Y*、XS，YS 00，则必有则必有YSX*00，Y*XS00，于是于是由上式知由上式知 Y*XS=YSX*=0，充分性获证，充分性获证，完！完！第39页，共117页，编辑于2022年，星期二原始问题和对偶问题最优解之间的互补松弛关系原始问题和对偶问题最优解之间的互补松弛关系min z=CTXs.t.AX-XS=b X,XS0max y=bTWs.t.ATW+WS=C W,WS0min z=CTXs.t.AXb X 0max y=bTWs.t.ATWC W0对偶对偶引进剩余变量引进剩余变量引进松弛变量引

50、进松弛变量XWS=0 WXS=0互补松弛关系互补松弛关系X，XsW，Ws第40页，共117页，编辑于2022年，星期二 设有设有L.P.问题问题 Max Z=x1+2x2+3x3+4x4 x1+x2+2x3+3x4 2020 2 2 x1+x2+3+3 x3+2+2 x420 xj 0,1 j 4 0,1 j 4 已知其对偶问题的最优解为：已知其对偶问题的最优解为：y y1 1*=1.2,y=1.2,y2 2*=0.2,=0.2,相应的目标函数值相应的目标函数值W W*=28,=28,试用对偶理论求原问题的解。试用对偶理论求原问题的解。解：解：其对偶问题为：其对偶问题为：Min W=20 y1