第二章线性规划的对偶理论ppt课件

1、第二章第二章 线性规划的对偶理论线性规划的对偶理论北京物资学院北京物资学院 李珍萍李珍萍20132013年年3 3月月北京物资学院运筹学教学课件本章主要内容本章主要内容第一节、原问题与对偶问题第一节、原问题与对偶问题第二节、对偶问题的基本性质第二节、对偶问题的基本性质第三节、影子价格第三节、影子价格第四节、对偶单纯形方法第四节、对偶单纯形方法第五节、灵敏度分析第五节、灵敏度分析第六节、线性规划的求解软件第六节、线性规划的求解软件第一节、原问题和对偶问题第一节、原问题和对偶问题一、引例一、引例二、对称形式的对偶规划二、对称形式的对偶规划三、非对称形式的对偶规划三、非对称形式的对偶规划四、一般形式

2、的对偶规划四、一般形式的对偶规划一、引例一、引例ABCD原料拥有量原料拥有量（单位）（单位）含量（单位含量（单位/公斤）公斤）糖糖524260蛋白质蛋白质321440脂肪脂肪312535单价单价（元（元/公斤）公斤）157912建立其数学模型。建立其数学模型。例例1 1 甲食品厂用糖、蛋白质和脂肪三种原料生产四种复甲食品厂用糖、蛋白质和脂肪三种原料生产四种复合食品合食品A A、B B、C C、D D，复合食品中含有各种原料的数量、，复合食品中含有各种原料的数量、复合食品的单价、三种原料的拥有量分别如下表所示，复合食品的单价、三种原料的拥有量分别如下表所示，问甲厂如何安排生产才能使总产值达到最大

3、？问甲厂如何安排生产才能使总产值达到最大？x1x2x3x4解：设甲厂安排解：设甲厂安排A、B、C、D的产量分别为的产量分别为x1、 x2、x3、 x4 公斤，总产值为公斤，总产值为z 元。于是，例元。于是，例1的数学模的数学模型为：型为：12341234123412341234max15791252426032440. .32535,0zxxxxxxxxxxxxs txxxxxxxx 例例2. 2. 假设乙食品厂欲将甲厂的原料收买过来，问乙厂至少假设乙食品厂欲将甲厂的原料收买过来，问乙厂至少应付出多少代价，才能使甲厂放弃生产活动，出让原料？应付出多少代价，才能使甲厂放弃生产活动，出让原料？建立

4、该问题的数学模型。建立该问题的数学模型。ABCD原料拥有量原料拥有量（单位）（单位）含量（单位含量（单位/公斤）公斤）糖糖524260蛋白质蛋白质321440脂肪脂肪312535单价单价（元（元/公斤）公斤）157912y1y2y3解：设解：设y1,y2y1,y2和和y3y3元元/ /单位分别代表乙厂收购糖、单位分别代表乙厂收购糖、蛋白质和脂肪的单价，乙厂收购原料付出的总费用为蛋白质和脂肪的单价，乙厂收购原料付出的总费用为w w元，于是例元，于是例2 2的数学模型为：的数学模型为：123123123123123123min60403553315227. . 42924512,0wyyyyyyy

5、yys tyyyyyyyyy 例例1 1和例和例2 2的数学模型比较的数学模型比较12341234123412341234max15791252426032440. .32535,0zxxxxxxxxxxxxs txxxxxxxx 123123123123123123min60403553315227. .42924512,0wyyyyyyyyys tyyyyyyyyy 令1234xxXxx (15,7,9,12)C 524232143125A 123(,)Yyyy 604035b 123412341234max1579125242603214403125350000 xxzxxxxxxxxx

6、x 123123123min604035533152217412924512000ywyyyyyyyy 以上两个线性规划分别称为线性规划的原问题和对偶问题。以上两个线性规划分别称为线性规划的原问题和对偶问题。若两个线性规划分别是若两个线性规划分别是和和则称它们是一对对称形式的对偶规划。则称它们是一对对称形式的对偶规划。二、对称形式的对偶规划二、对称形式的对偶规划112211112211211222221122. . .01,2,.nnnnnnmmmnnmjMax zc xc xc xa xa xa xba xa xaxbs taxaxaxbxjn min0wYbYACY max0zCXAXbX

7、 112211121211121222221122. . .01,2,.mmmmmmnnmnmniMinwb yb yb ya ya yayca ya yaycs ta yayaycyim 对称形式的对偶规划还可以写成表格形式，称为对偶表对称形式的对偶规划还可以写成表格形式，称为对偶表Max zMin w原问题（求极大）原问题（求极大）c1 x1c2x2 cnxn右端右端项项对对偶偶问问题题求极小求极小b1 y1a11a12a1n b1 b2 y2a21a22a2n b2bm ymam1am2amn bm右端项右端项 c1 c2 cn对偶规划中的两个问题分别称为原问题和对偶问题对偶规划中的两个

8、问题分别称为原问题和对偶问题互为对偶）。互为对偶）。 一对对称形式的对偶规划之间具有下面的对应关系。 (1)若一个模型为目标求“极大”，约束为“小于等于型不等式，则它的对偶模型为目标求“极小”，约束是“大于等于型不等式。即“max，”和“min，”相对应。 (2) 一个模型是m个约束，n个变量，则它的对偶模型为n个约束，m个变量。从约束系数矩阵看：一个模型中为，则另一个模型中为AT。 (3)原问题目标函数系数是对偶问题的约束条件右端项；原问题的约束条件右端项是对偶问题的目标函数系数。 (4)两个规划模型中的变量皆非负。例例3 3：写出下列线性规划的对偶规划：写出下列线性规划的对偶规划解：原规划

9、的对偶规划为解：原规划的对偶规划为12max2wyyy1y2. .s t 2515y 126224yy 125yy12,0yy 12323123123min1524562. .521,0zxxxxxs txxxxxx 不等式约束对应非负变量不等式约束对应非负变量三、非对称形式的对偶规划三、非对称形式的对偶规划max0zCXAXbX min wYbYAC 叫做非对称形式的对偶规划。非对称形式的对偶规划叫做非对称形式的对偶规划。非对称形式的对偶规划可以由对称形式的对偶规划推出。可以由对称形式的对偶规划推出。例例4 4：写出下列线性规划问题的对偶规划。：写出下列线性规划问题的对偶规划。1234123

10、41234max53345810243280 (1,2,3,4)jzxxxxxxxxxxxxxj 解：将上述线性规划化成对称对偶规划的形式解：将上述线性规划化成对称对偶规划的形式12341234123412341234max533458105810. .24328243280 (1,2,3,4)jzxxxxxxxxxxxxs txxxxxxxxxj 写出它的对偶规划写出它的对偶规划111222121212121212,min10852543. .33824,yyyyyywyyyyyys tyyyyyy 令令得得无无符符号号限限制制y1y1y2y2112211221122112211221122

11、min10108855225443. .33388224,0wyyyyyyyyyyyys tyyyyyyyyyyyy 等式约束对应自由变量等式约束对应自由变量111max(1,2,., )(1,.,)0(1,2,., )(1,., )njjjnijjijnijjijjjzc xa xbipa xbipmxjqxjqn 无无符符号号限限制制111min1,2,. )01,.)(1,2,., )(1,., )miiiiimijijimijijiwb yyipyipma ycjqa ycjqn 无无符符号号限限制制（(D)四、一般形式的对偶规划四、一般形式的对偶规划(P)一般形式的对偶规划的特点一般

12、形式的对偶规划的特点（1 1原问题是原问题是“max“max，=,” =,” 形式，对偶问题是形式，对偶问题是“min“min，=,”=,”形式形式 （2 2原问题的每个等式约束，对应对偶问题一个自由变量，原问题的每个等式约束，对应对偶问题一个自由变量，原问题的每个不等式约束，对应对偶问题的一个非负变量；原问题的每个不等式约束，对应对偶问题的一个非负变量；反之亦然，即原问题中的每个非负变量对应的是对偶问题反之亦然，即原问题中的每个非负变量对应的是对偶问题中的一个不等式约束，而原始问题中的每个自由变量对应中的一个不等式约束，而原始问题中的每个自由变量对应对偶问题中的一个等式约束。对偶问题中的一个

13、等式约束。（3 3原问题目标函数中的系数原问题目标函数中的系数c c就是对偶问题约束条件的就是对偶问题约束条件的右端常数项，而原问题约束的右端常数项就是对偶问题目右端常数项，而原问题约束的右端常数项就是对偶问题目标函数中的系数。标函数中的系数。（4 4如果用矩阵和向量形式写出问题如果用矩阵和向量形式写出问题(P)(P)和和(D)(D)的约束，可的约束，可以看出这两个问题的约束系数矩阵互为转置。以看出这两个问题的约束系数矩阵互为转置。例例5. 5. 写出下面线性规划的对偶规划写出下面线性规划的对偶规划12341234134123412max5732252726022430. .510,0zxxx

14、xxxxxxxxxxxs txxx 解解 先将约束条件变形为先将约束条件变形为“”“”形式形式y1y2y3y4y5123412341341234412max5732252726022430. .105,0zxxxxxxxxxxxxxxs txxxx 再根据非对称形式的对应关系，直接写出对偶规划再根据非对称形式的对应关系，直接写出对偶规划1234512313123124512345min256030105221321274527,0wyyyyyyyyyyyyyyyyyyyyyy 无无符符号号限限制制例写出下列线性规划问题的对偶规划例写出下列线性规划问题的对偶规划1231231232313min7

15、434262436415. .53300,0zxxxxxxxxxs txxxx 1112323232313min7434262436415. .53300,0zxxxxxxxxxs txxxx 解：令解：令 x1= x1 ，将约束化成相对规范形式，将约束化成相对规范形式y1y2y31111123223232max2415304372654. .64330,0wyyyyyyyys tyyyyy 直接写出对偶规划直接写出对偶规划1231212312312max2415304372654. .64330,0wyyyyyyyys tyyyyy 1231231232313min7434262436415

16、. .53300,0zxxxxxxxxxs txxxx 比较原规划和对偶规划比较原规划和对偶规划1111123223232max2415304372654. .64330,0wyyyyyyyys tyyyyy 令令y1=y1,并把第并把第一个约束两端乘以一个约束两端乘以-1得得不符合要求的约束对应非正变量不符合要求的约束对应非正变量线性规划原问题与对偶问题的对应关系线性规划原问题与对偶问题的对应关系原问题（对偶问题）原问题（对偶问题）对偶问题（原问题）对偶问题（原问题）目标函数目标函数 max目标函数目标函数 min n个个 变量变量 0 0 无限制无限制 n个个 约束条件约束条件 =目标函数

17、中变量的系数目标函数中变量的系数约束条件右端常数约束条件右端常数 m个个约束条件约束条件 = m个个 0 变量变量 0 无限制无限制约束条件右端常数约束条件右端常数目标函数中变量的系数目标函数中变量的系数作业：作业： P881 、 (1) (2)(3)第二节、对偶问题的基本性质对偶定理）第二节、对偶问题的基本性质对偶定理）max( ). .0zCXPAXbs tX 原问题与对偶问题的解之间的关系原问题与对偶问题的解之间的关系定理定理 1( 1(对称性对称性) ) 对偶问题的对偶是原问题。对偶问题的对偶是原问题。定理定理3 3 （强对偶定理若原问题有最优解，则其对（强对偶定理若原问题有最优解，则

18、其对偶问题也一定有最优解，并且此时目标函数的最优偶问题也一定有最优解，并且此时目标函数的最优值相等。值相等。min(). .0wYbDYACs tY 定理定理 2( 2(弱对偶定理弱对偶定理) ) 设设X0X0和和Y0Y0分别是原问题和对偶问分别是原问题和对偶问题的可行解，则题的可行解，则CX0CX0Y0bY0b；特别当；特别当CX0=Y0b CX0=Y0b 时，时， X0 X0和和Y0 Y0 分别是原问题和对偶问题的最优解。分别是原问题和对偶问题的最优解。证明：将原问题加上松弛变量化成标准形式：证明：将原问题加上松弛变量化成标准形式：( ,0)( ,). .0XMax zCSXA EbSs

19、tXS 0. .0,0Max zCXSAXESbs tXS 用单纯形方法求解得最优解用单纯形方法求解得最优解X X，设其最优基为，设其最优基为B B，则，则XB=B-1b,XB=B-1b,检验数为检验数为1( ,0)( ,)0BCC BA E 10BCC B A 100BC B 令令1BYC B 则则Y是对偶问题的可行解是对偶问题的可行解又因为又因为1BCXC B bYb 由定理由定理2知知Y是对偶问题的最优解。是对偶问题的最优解。即即即即max( ). .0zCXPAXbs tX min(). .0wYbDYACs tY 原问题和对偶问题的解的情况如下原问题和对偶问题的解的情况如下 对偶对偶

20、原始原始有最优解有最优解问题无界问题无界无可行解无可行解有最优解有最优解 问题无界问题无界 无可行解无可行解 定理定理4 4 给定一个线性规划的原问题和它的对偶问题，给定一个线性规划的原问题和它的对偶问题，则上表中的三种情况恰有一种出现。则上表中的三种情况恰有一种出现。证明：由定理证明：由定理2 2容易证明，如果原问题或它的对偶中有一个容易证明，如果原问题或它的对偶中有一个是无界的，那么另一个不可能有可行解。（用反正法）是无界的，那么另一个不可能有可行解。（用反正法）下面举例说明剩下的情况下面举例说明剩下的情况2 2和和3 3是可能出现的。是可能出现的。考虑下列对偶规划考虑下列对偶规划1211

21、212121212maxmin11( )()010,0wyyzxyyxxPDyyxxyy 显然两个问题均无可行解，情况显然两个问题均无可行解，情况2 2呈现。呈现。112121212121212minmax11( )()100,00,0zxwyyxxyyPDxxyyxxyy原问题无可行解，对偶问题无界，情况原问题无可行解，对偶问题无界，情况3 3呈现。呈现。考虑下列对偶规划：考虑下列对偶规划：例例6 6 试用对偶理论证明下列线性规划问题无界试用对偶理论证明下列线性规划问题无界12123123123max2. .21,0zxxxxxs txxxxxx 11max(1,2,.,)0(1,2,.,

22、)njjjnijjijjzc xa xbimxjn (P)11min(1,2,., )0(1,2,.,)miiimijijiiwb ya ycjnyim (D)定理定理5 （互补松弛定理设（互补松弛定理设X和和Y分别是原问题和对偶问题分别是原问题和对偶问题的可行解，则它们分别是原问题和对偶问题的最优解的充的可行解，则它们分别是原问题和对偶问题的最优解的充要条件是对一切的要条件是对一切的 i=1,2,m，和一切，和一切 j=1,2,n 有有11()0()0niiijjijmjjijijiuya xbvca y x 证明：由对偶的定义知证明：由对偶的定义知11()01,2,.()01,2,.nii

23、ijjijmjjijijiuya xbimvca y xjn 证明：由对偶的定义知证明：由对偶的定义知111111()0()0mmniiijjiiijnnmjjijijjjiuuya xbvvca y x因而因而00,1,2,. ;00,1,2,. .ijuuimvvjn当当且且仅仅当当 当当且且仅仅当当 11()01,2,.()01,2,.niiijjijmjjijijiuya xbimvca y xjn 定义定义111111111111()()mnnmiijjijijijijjimnmnnmijjiiijjijjiijijjinmjjiijiuvya xbca y xa x yy bc x

24、a x yc xy bCXYb111111111111()()mnnmiijjijijijijjimnmnnmijjiiijjijjiijijjinmjjiijiuvya xbca y xa x yy bc xa x yc xy bCXYb由定理由定理1 1知，知， X X 和和Y Y分别是原问题和对偶问题最优解的充要分别是原问题和对偶问题最优解的充要条件是条件是0uv CXYb 即即也即也即11()0()0niiijjijmjjijijiuya xbvca y x 2122112141622515max213. .02,zxxs txxxxxx 1222311313min121615242.

25、 . 253,0yyywsyyyytyyy 原问题的最优解为原问题的最优解为 x1=3, x2=3.对偶问题的最优解为：对偶问题的最优解为：y1=1, y2=0, y3=1/5.例如：考虑下面的一对对偶规划例如：考虑下面的一对对偶规划原问题的第一个约束对应对偶变量原问题的第一个约束对应对偶变量 y1。12122122323120,10 xxy 原问题的第二个约束对应对偶变量原问题的第二个约束对应对偶变量 y2。124164 31640,0 xy 原问题的第三个约束对应对偶变量原问题的第三个约束对应对偶变量y3。2315155 3150,5xy 123451234512345min2030502

26、0302340. . 23300,1,2,.5jwxxxxxxxxxxs txxxxxxj 例例7 已知线性规划问题已知线性规划问题 其对偶问题的最优解是其对偶问题的最优解是*128,6,500yyz试用对偶理论找出原问题的最优解试用对偶理论找出原问题的最优解12121212121212max4030220(1)30(2)2350(3)20(4)330(5),0zyyyyyyyyyyyyyy 12121212121212max4030220(1)30(2)2350(3)20(4)330(5),0zyyyyyyyyyyyyyy 将y1*=8,y2*=6 代入对偶问题的约束条件，由互补松弛条件得*

27、2340 xxx又因为y1*0,y2*0, 由互补松弛条件得原问题的约束应为等式，因而*15*15340230 xxxx*1510,10 xx解得*(10,0,0,0,10)TX原问题的最优解为定理定理6：线性规划原问题及其对偶之间存在一对互补的：线性规划原问题及其对偶之间存在一对互补的基解，并且原问题单纯形表的检验数行对应对偶问题的基解，并且原问题单纯形表的检验数行对应对偶问题的基解，其中原问题的变量的检验数相反数等于对偶问题基解，其中原问题的变量的检验数相反数等于对偶问题的剩余变量取值，原问题的松弛变量检验数的相反数等的剩余变量取值，原问题的松弛变量检验数的相反数等于对应对偶问题的变量取值

28、。将这对互补的基解分别代于对应对偶问题的变量取值。将这对互补的基解分别代入原问题和对偶问题的目标函数有入原问题和对偶问题的目标函数有z=w。例例8. 8. 考虑如下一对对偶规划考虑如下一对对偶规划12121212max232212416. .515,0zxxxxxs txxx 1231213123min121615242. . 253,0wyyyyys tyyyyy 将其分别化为标准形式：将其分别化为标准形式：412121253max232212416. .5150,1,2,.5jzxxxxxxs txxxxj 123432115min121615242. . 2530,1,2,.5jywyy

29、yys tyyyjyy 原问题的最优单纯形表为原问题的最优单纯形表为原问题变量原问题变量原问题松弛变量原问题松弛变量基基bx1x2x3x4x5x13101/20-1/5x4400-214/5x2301001/5 j00-10-1/5y4y5y1y2y3对偶问题剩对偶问题剩余变量余变量对偶问题变量对偶问题变量原问题的最优解为原问题的最优解为 x1=3, x2=3.对偶问题的最优解为：对偶问题的最优解为：y1=1, y2=0, y3=1/5.对偶问题的最优单纯形表为对偶问题的最优单纯形表为对偶问题变量对偶问题变量对偶问题剩余对偶问题剩余变量变量基基by1y2y3y4y5y11120-1/20y31

30、/50-4/511/5-1/5 j0-40-3-3x3x4x5x1x2原问题松弛变量原问题松弛变量原问题变量原问题变量对偶问题的最优解为：对偶问题的最优解为：y1=1, y2=0, y3=1/5.原问题的最优解为原问题的最优解为 x1=3, x2=3.第三节、对偶问题的经济解释第三节、对偶问题的经济解释影子价格：影子价格：例例9 91 1）：第一工厂生产）：第一工厂生产A A，B B，C C三种产品，每种产品三种产品，每种产品都同时需要甲、乙两种原料，数据见表，问应该如何都同时需要甲、乙两种原料，数据见表，问应该如何安排生产，使获得的利润最大？安排生产，使获得的利润最大？ 消耗消耗 产品产品原

31、料原料ABC现有原料现有原料（公斤）（公斤）甲甲2127乙乙13211利润（元利润（元/件）件）231（2 2）：假设第二工厂为了扩大生产想购买第一工厂）：假设第二工厂为了扩大生产想购买第一工厂的原料，问第一工厂分别以什么样的价格才愿意出的原料，问第一工厂分别以什么样的价格才愿意出售自己的原料？售自己的原料？（1 1设第一工厂应安排设第一工厂应安排A A，B B，C C的产量分别为的产量分别为x1x1，x2x2，x3x3件，产值是件，产值是z z元，则问题元，则问题1 1的数学模型是的数学模型是（2 2设第一工厂将甲、乙两种原料的单价分别定为设第一工厂将甲、乙两种原料的单价分别定为y1y1，y

32、2y2元元/ /公斤，出售原料可以获得的收益是公斤，出售原料可以获得的收益是w w元，则问题元，则问题2 2的数学模型是的数学模型是123123123123max232273211,0zxxxxxxxxxxxx 1212121212min7112233. .221,0wyyyyyys tyyyy 设设Y*=（y1*，y2*，,ym*)是对偶问题的最优解是对偶问题的最优解,则则称称yi*是原规划的第是原规划的第i个约束对应的影子价格。个约束对应的影子价格。从上例可以看出，从上例可以看出， yi*是对第是对第i 种资源的一种估价，这种资源的一种估价，这个价格不是市场价格，而是针对具体企业在一定时期

33、个价格不是市场价格，而是针对具体企业在一定时期内存在的一种特殊价格，它蕴涵在求最大利润的生产内存在的一种特殊价格，它蕴涵在求最大利润的生产计划中。计划中。在原规划中引进松弛变量，化成标准形式在原规划中引进松弛变量，化成标准形式 max z = 2x1 + 3x2 + x3 max z = 2x1 + 3x2 + x3 s.t. 2x1 + x2 + 2x3 + x4 = 7 s.t. 2x1 + x2 + 2x3 + x4 = 7 x1 + 3x2 + 2x3 + x5 = 11 x1 + 3x2 + 2x3 + x5 = 11 x1 , x2 , x3 , x4, x5 x1 , x2 ,

34、x3 , x4, x5 0 0该问题的最优单纯形表为该问题的最优单纯形表为原问题的解为：原问题的解为：x1 = 2, x2 = 3 。即产品。即产品A生产生产2件，产件，产品品B生产生产3件，产品件，产品C不生产。不生产。对偶问题的解为：对偶问题的解为： y1* = 3/5 , y2* = 4/5 (单位：元单位：元/公公斤斤)。即甲原料的影子价格为。即甲原料的影子价格为 3/5元元/公斤公斤;乙原料的影子乙原料的影子价格为价格为 4/5元元/公斤公斤;（1第第i 种资源的影子价格种资源的影子价格 yi* 是一个边际价格。是一个边际价格。它表示在第它表示在第i 种资源数量种资源数量bi 附近的

35、某个闭区间内，该附近的某个闭区间内，该资源的数量增加一个单位此时其它资源数量不资源的数量增加一个单位此时其它资源数量不变），生产计划的最大利润变），生产计划的最大利润z*将增加将增加 yi*个单位。个单位。 z*=CBB-1b=Y*b 影子价格的经济含义影子价格的经济含义（2影子价格是对现有资源实现最大效益的一种估价。影子价格是对现有资源实现最大效益的一种估价。这种估价不是资源的市场价格，而是根据资源在生产中这种估价不是资源的市场价格，而是根据资源在生产中作出的贡献而作的估价。作出的贡献而作的估价。*iizyb （3 3影子价格是一种机会成本，对市场有调节作用。影子价格是一种机会成本，对市场有

36、调节作用。当某种资源的市场价格低于影子价格时，企业应当买进当某种资源的市场价格低于影子价格时，企业应当买进该种资源用于扩大生产；当某种资源的市场价格高于影该种资源用于扩大生产；当某种资源的市场价格高于影子价格时，企业的决策者应当把已有资源卖掉。随着资子价格时，企业的决策者应当把已有资源卖掉。随着资源的买进卖出，影子价格也将随着变化，直到影子价格源的买进卖出，影子价格也将随着变化，直到影子价格和市场价格保持同等水平时，才处于平衡状态。和市场价格保持同等水平时，才处于平衡状态。（4 4由对偶问题的互补松弛性质可知，当某种资源未被由对偶问题的互补松弛性质可知，当某种资源未被充分利用时，影子价格为充分

37、利用时，影子价格为0 0；当某种资源的影子价格不为；当某种资源的影子价格不为0 0时，说明该资源在生产中已经消耗完毕。时，说明该资源在生产中已经消耗完毕。*1*10;0;nijjiijniijjija xbyya xb 当当时时，当当时时，（5 5） 从影子价格的含义上来考察单纯形法的计算。从影子价格的含义上来考察单纯形法的计算。11mjjBjjijiicC B Pca y 1mjijiicja y 是是第第 种种产产品品的的产产值值，是是生生产产该该产产品品所所消消耗耗的的资资源源的的影影子子价价格格的的总总和和，即即隐隐含含成成本本。当产品的产值大于隐含成本时，表明生产该项产品有利，当产品

38、的产值大于隐含成本时，表明生产该项产品有利，可在计划中安排生产，否则这些资源生产别的产品更为可在计划中安排生产，否则这些资源生产别的产品更为有利，就不在生产计划中安排。这就是单纯形法中检验有利，就不在生产计划中安排。这就是单纯形法中检验数的经济意义。数的经济意义。作业：作业：第第89页页 3, 4 ,5题题第四节、对偶单纯形法第四节、对偶单纯形法对偶单纯形法的基本思想对偶单纯形法的基本思想对偶单纯形法求解原规划的主要步骤对偶单纯形法求解原规划的主要步骤对偶单纯形法的适用范围对偶单纯形法的适用范围一一. . 对偶单纯形方法的基本思想对偶单纯形方法的基本思想定理定理 ：设：设(P)的任一基解的任一

39、基解X0对应基对应基B，记，记Y0=CBB-1。若。若X0和和Y0分别是原问题分别是原问题(P)和对偶问题和对偶问题(D)的可行解，则的可行解，则X0和和Y0 分分别是别是(P)和和 (D)的最优解。的最优解。证明：因为证明：因为Y0=CBB-1是是(D)的可行解，即的可行解，即 YAC C- CBB-1A0由此说明由此说明X0是是(P)的可行解且检验数非正，故的可行解且检验数非正，故X0是是(P)的最优解。的最优解。又又 0100BBBBBNXY bC B bC XCCCX 故故Y0 是是 (D)的最优解。的最优解。max( ). .0zCXPAXbs tX min(). .0wYbDYAC

40、s tY 对偶单纯形方法：从原规划的一个基解出发，此基解对偶单纯形方法：从原规划的一个基解出发，此基解不一定是原规划的基可行解，但它对应着对偶问题的不一定是原规划的基可行解，但它对应着对偶问题的基可行解检验数非正），逐步调整，使所有变量取基可行解检验数非正），逐步调整，使所有变量取值变成非负，即得到原问题的基可行解。值变成非负，即得到原问题的基可行解。单纯形方法：从原规划的一个基可行解此基解不一单纯形方法：从原规划的一个基可行解此基解不一定对应对偶问题的可行解，即检验数不一定非正动定对应对偶问题的可行解，即检验数不一定非正动身，逐步调整，使检验数变成非正对应对偶问题的身，逐步调整，使检验数变成

41、非正对应对偶问题的可行解）。可行解）。原问题的基可行解原问题的基可行解对偶问题的基可行解对偶问题的基可行解单纯形方法单纯形方法对偶单纯形方法对偶单纯形方法二二. . 对偶单纯形法的求解步骤对偶单纯形法的求解步骤 1.建立初始对偶单纯形表,对应原问题的一个基解,所有检验数均非正,转2； 2.若b0,则得到最优解,停顿;否则,若有bk0,则选k行的基变量为出基变量(若有多个bk0,则选最小的一个所在的行中的基变量出基),转3; 3.若所有akj0( j = 1,2,n )，则原问题无可行解,停顿;否则,若有akj0, 则计算 =minj / akjakj0=r/akr 并选xr为进基变量,转4；

42、4.以akr为主元素,作矩阵行初等变换使其变为1,该列其他元变为0,转2。例例1010：用对偶单纯形法求解线性规划问题：用对偶单纯形法求解线性规划问题：化成标准形化成标准形若用单纯形方法求解，需若用单纯形方法求解，需再引进两个非负的人工变再引进两个非负的人工变量，然后用大量，然后用大M M法或两阶法或两阶段法求解。段法求解。由本例的特点，我们只要由本例的特点，我们只要将等式两端同乘以将等式两端同乘以-1-1，就，就可以得到原问题的一个基可以得到原问题的一个基解不可行和对偶问题解不可行和对偶问题的一个可行解检验数非的一个可行解检验数非正）正）123123123123min23423. .234,

43、0zxxxxxxs txxxxxx 1231234123512345max 23423. .234,0zxxxxxxxs txxxxxxxxx 1231234123512345max 23423. .234,0zxxxxxxxs txxxxxxxxx -2-3-400CBXBbx1x2x3x4x50 x4-3-1-2-1100 x5-4-21-301 j0-2-3-4000 x4-10-5/21/21-1/2-2x121-1/23/20-1/2 j40-4-10-1-3x22/501-1/5-2/51/5-2x111/5107/5-1/5-2/5 j28/500-9/5-8/5-1/5得原问题

44、的最优解得原问题的最优解 X=（11/5，2/5，0，0，0T，最优值是最优值是 -28/5。单纯形法和对偶单纯形法的步骤单纯形法和对偶单纯形法的步骤是是是是是是是是否否否否否否否否 所有所有 所有所有得到得到最优解最优解计算计算计算计算典式对应原规划的基典式对应原规划的基本解是可行的本解是可行的典式对应原规划的基典式对应原规划的基本解的检验数非正本解的检验数非正所有所有所有所有计算计算计算计算以主元素为中心元素进行迭代以主元素为中心元素进行迭代以主元素为中心元素进行迭代以主元素为中心元素进行迭代停停没没有有有有限限最最优优解解没没有有可可行行解解单纯形法单纯形法对偶单纯形法对偶单纯形法0ib

45、0maxjjk0miniiebbb0ika0ljaekeikikiabaab0minmin0ikejejekaaa 0j三三. . 对偶单纯形法的适用范围对偶单纯形法的适用范围1.1.如下形式的问题如下形式的问题11(1,2,.). .0(1,2,. )njjjnijjijjMinzc xa xbims txjn 2.2.灵敏度分析灵敏度分析作业：作业： 89页页 第第6题题第五节：灵敏度分析第五节：灵敏度分析n灵敏度分析是指对系统或事物因周围条件变化显示出灵敏度分析是指对系统或事物因周围条件变化显示出来的敏感程度的分析。来的敏感程度的分析。n信息的不确定性信息的不确定性n 信息的变化：信息的

46、变化：n 价值向量价值向量市场变化市场变化 （目标函数系数的变化）（目标函数系数的变化）n 右端向量右端向量资源变化资源变化 （b b 的变化）的变化）n 系数矩阵系数矩阵技术进步技术进步 （aij aij 的变化）的变化）n 认知的误差认知的误差n分析方法分析方法n 静态分析静态分析- - 比较静态分析比较静态分析- -动态分析动态分析一、目标函数中系数变化的分析一、目标函数中系数变化的分析二、约束条件右端常数变化的变化二、约束条件右端常数变化的变化三、增加新变量的分析三、增加新变量的分析四、增加一个约束条件的分析四、增加一个约束条件的分析一、目标函数中系数变化的分析一、目标函数中系数变化的

47、分析目标函数中系数目标函数中系数c的变化仅仅影响到检验数的变化仅仅影响到检验数cj-zj 的的变化，所以可以直接在最终的单纯形表中计算变化，所以可以直接在最终的单纯形表中计算例例11:11:试分析下列线性规划问题的目标函数中试分析下列线性规划问题的目标函数中x3x3的系数在的系数在多大范围内变化时最优解保持不变。多大范围内变化时最优解保持不变。 1231234123512345max23423. .234,0zxxxxxxxs txxxxxxxxx -2 -3 -4+c3 0 0 CB xB b x1 x2 x3 x4 x5 -3 x2 2/5 0 1 -1/5 -2/5 1/5 -2 x1

48、11/5 1 0 7/5 -1/5 -2/5 j 28/5 0 0 -9/5+c3 -8/5 -1/5 解：最优单纯形表解：最优单纯形表从表中看到从表中看到3= -9/5+ c33= -9/5+ c3当当-9/5+ c3 0,-9/5+ c3 0,即即c3 9/5 c3 9/5 时，原最优解不变。时，原最优解不变。例例1212：在第一章例：在第一章例1 1的线性规划问题中的线性规划问题中, ,试分析试分析(1)(1)产品甲的单位利润在多大范围内变化时，最优生产方产品甲的单位利润在多大范围内变化时，最优生产方案保持不变？案保持不变？(2)(2)如果产品甲的单位利润由如果产品甲的单位利润由5050

49、元增加到元增加到6060元，最优生产元，最优生产方案如何变化？方案如何变化？121212112max5060248032603450,0zxxxxxxxxx 1212312415max506024803260. .3450,1,2,3,4,5jzxxxxxxxxs txxxj 5060000CBXBbx1x2x3x4x560 x215013/8-1/4050 x11010-1/41/200 x515003/4-3/21 j-140000-10-100最优单纯形表最优单纯形表 j-1400-10 C100-10+1/4 C1-10-1/2 C10解得解得 -20 C1 40 时，原最优解不变。时

50、，原最优解不变。50+ C160000CBXBbx1x2x3x4x560 x215013/8-1/4050 + C1x11010-1/41/200 x515003/4-3/2110060000CBXBbx1x2x3x4x560 x215013/8-1/40100 x11010-1/41/200 x515003/4-3/21 j-1400005/2-35060 x27.50101/2-1/2100 x11510001/30 x320001-24/3 j-1950000-30-10/3最优解变为：最优解变为：X*=(15,7.5,20,0,0)T二、二、 约束条件右端常数变化的分析约束条件右端常数

51、变化的分析b 的变化在实际问题中表明资源的数量发生变化，反的变化在实际问题中表明资源的数量发生变化，反映到最终单纯形表上只引起基变量列数字的变化。映到最终单纯形表上只引起基变量列数字的变化。根据前面的讨论，最优解的基变量根据前面的讨论，最优解的基变量 XB = B-1b=b*，设设b变化为变化为 b+b，那么只要保持那么只要保持 B-1(b+b)0 ，则最优基不变，则最优基不变，所以所以 关键是求出关键是求出B-1。例例13 13 对于线性规划问题对于线性规划问题(1)(1)第二个约束右端常数在什么范围内变化时第二个约束右端常数在什么范围内变化时, ,问题的最问题的最优基保持不变？优基保持不变

52、？(2)(2)若第二个约束右端常数由若第二个约束右端常数由6060先后增加到先后增加到7070和和8080，问题，问题的最优解如何变化？的最优解如何变化？ 1212312415max506024803260. .3450,1,2,3,4,5jzxxxxxxxxs txxxj 5060000CBXBbx1x2x3x4x50 x380241000 x460320100 x54530001 j0506000060 x215013/8-1/4050 x11010-1/41/200 x515003/4-3/21 j-140000-10-100（1先求先求B-113 / 81/ 401/ 41/ 203

53、/ 43 / 21B 使问题的最优基不变的条件是使问题的最优基不变的条件是212211541()10023152bBbbbb 由此推得由此推得22010b 2122211543 / 81/ 40801()1/ 41/ 20601023 / 43 / 21453152bBbbbbb （2若第二个约束右端常数由若第二个约束右端常数由60增加到增加到70，则基解变为，则基解变为最优基保持不变，新的最优解为：最优基保持不变，新的最优解为：X*=(15,12.5,0,0,0)T13 / 81/ 408012.50()1/ 41/ 20701503 / 43 / 2145450Bbb 若第二个约束右端常数

54、增加到若第二个约束右端常数增加到80，则基解变为，则基解变为由于出现负分量，该基解不是可行解，填入最终的由于出现负分量，该基解不是可行解，填入最终的单纯形表，用对偶单纯形法迭代单纯形表，用对偶单纯形法迭代13 / 81/ 408010()1/ 41/ 2080203 / 43 / 214515Bbb 5060000CBXBbx1x2x3x4x560 x210013/8-1/4050 x12010-1/41/200 x5-15003/4-3/21 j-140000-10-1005060000CBXBbx1x2x3x4x560 x212.5011/40-1/650 x11510001/30 x41

55、000-1/21-2/3 j-150000-150-20/3新的最优解为：新的最优解为：X*=(15,12.5,0,10,0)T 增加一个变量相当于增加一种新产品，分析的步骤是首先计算这种新产品对应的检验数，如果检验数小于等于零，则最优解保持不变，如果检验数大于零，说明投产新产品有利，继续按单纯形法迭代可以求出新的最优解。三、三、 增加新变量的分析增加新变量的分析例例14 在第一章例在第一章例1中假设企业考虑投产一种新的产品中假设企业考虑投产一种新的产品丙，丙产品每单位需要在丙，丙产品每单位需要在A,B,C三台设备上的加工时三台设备上的加工时间分别为间分别为2、1、3小时，利润是小时，利润是4

56、0元，试分析企业投元，试分析企业投产丙产品是否有利。产丙产品是否有利。 解：设丙产品的产量为解：设丙产品的产量为x3单位，单位，6213P 1663101842211010423333142PB P 16661240(60,50,0) 0103BcC B P由于检验数为正，说明投产丙产品有利。将以上结果由于检验数为正，说明投产丙产品有利。将以上结果填入原问题的最后一张单纯形表中填入原问题的最后一张单纯形表中 cj506000040CBXBbx1x2x3x4x5x660 x215013/8-1/401/250 x11010-1/41/2000 x515003/4-3/213 j-140000-1

57、0-10010进一步迭代得进一步迭代得cj506000040CBXBbx1x2x3x4x5x660 x212.5011/40-1/6050 x11010-1/41/20040 x65001/4-1/21/31 j-145000-12.4-500故企业应该投产丙产品，新的生产方案是甲、乙、故企业应该投产丙产品，新的生产方案是甲、乙、丙的产量分别为丙的产量分别为10、12.5、5单位，总利润单位，总利润1450元。元。增加一个约束，在实际中相当于增加一道工序，分析增加一个约束，在实际中相当于增加一道工序，分析的方法是先将原来的最优解代入这个新增加的约束中，的方法是先将原来的最优解代入这个新增加的约

58、束中，若满足，则说明新增加的约束未起到限制作用，原最若满足，则说明新增加的约束未起到限制作用，原最优解不变。否则，将新的约束反映到最终的单纯形表优解不变。否则，将新的约束反映到最终的单纯形表中，再进一步分析。中，再进一步分析。 四、增加一个约束条件的分析四、增加一个约束条件的分析 例15 在第一章例1中增加一个约束条件，分析最优解的变化。122460 xx解解 将最优解将最优解x1=10,x2=15 x1=10,x2=15 代入新的约束条件中，约代入新的约束条件中，约束条件不满足。束条件不满足。所以将新的约束条件加上松弛变量后的方程直接反映所以将新的约束条件加上松弛变量后的方程直接反映到最终的

59、单纯形表中得到最终的单纯形表中得cj50600000CBXBbx1x2x3x4x5x660 x215013/8-1/40050 x11010-1/41/2000 x515003/4-3/2100 x660240001 j-140000-10-1000对上表进行行的初等变换得到表cj50600000CBXBbx1x2x3x4x5x660 x215013/8-1/40050 x11010-1/41/2000 x515003/4-3/2100 x6-2000-1001 j-140000-10-1000cj50600000CBXBbx1x2x3x4x5x660 x215/2010-1/403/850

60、x1151001/20-1/40 x50000-3/213/40 x32000100-1 j-1200000-100-10用对偶单纯形法迭代得新的最优解为*1215,7.5,1200 xxz作业：作业： P91 P91 第第8 8题题第六节：线性规划的求解软件第六节：线性规划的求解软件| Lindo| LinGo| WinQSB| MatlabLindon输入模型输入模型n求解求解n 点击求解按钮点击求解按钮 即可即可n结果结果 !注释内容，可用中文注释内容，可用中文!目标函数：最大目标函数：最大-max,最小最小-min,大小写不分大小写不分 max 3 x1+5 x2+4 x3!约束，以约