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

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

2、的对偶规划四、一般形式的对偶规划一、引例一、引例糖糖蛋白质蛋白质脂肪脂肪单价单价（元（元/公斤）公斤）A含量（单位含量（单位/公斤）公斤）53315B2217C4129D24512原料拥有量原料拥有量（单位）（单位）604035建立其数学模型。建立其数学模型。例例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、模型建立该问题的数学模型。糖糖蛋白质蛋白质脂肪脂肪单价单价（元（元/公斤）公斤）A含量（单位含量（单位/公斤）公斤）53315B2217C4129D24512原料拥有量原料拥有量（单位）（单位）604035y1y2y3解：设解：设y y1 1,y,y2 2和和y y3 3（元元/单位）分别代表乙厂收购糖、蛋单位）分别代表乙厂收购糖、蛋白质和脂肪的单价，乙厂收购原料付出的总费用为白质和脂肪的单价，乙厂收购原料付出的总费用为w w元，元，于是例于是例2 2的数学模型为：的数学模型为：123123123123123123min60403553315227.42924512,0wyyyyyyyyys

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

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

7、121222221122.01,2,.mmmmmmnnmnmniMinwb yb yb ya ya yayca ya yaycs ta yayaycyim 对称形式的对偶规划还可以写成表格形式，称为对偶表对称形式的对偶规划还可以写成表格形式，称为对偶表Max zMin w对对偶偶问问题题求极小求极小b1 y1 b2 y2bm ym右端项右端项原问题（求极大）原问题（求极大）c1 x1a11a21am1 c1c2x2a12a22am2 c2 cnxna1na2namn cn右端右端项项 b1 b2 bm对偶规划中的两个问题分别称为原问题和对偶问题对偶规划中的两个问题分别称为原问题和对偶问题（互为

8、对偶）。（互为对偶）。一对对称形式的对偶规划之间具有下面的对应关系。一对对称形式的对偶规划之间具有下面的对应关系。(1)若一个模型为目标求若一个模型为目标求“极大极大”，约束为，约束为“小于等于小于等于”型不等式，则它的对偶模型为目标求型不等式，则它的对偶模型为目标求“极小极小”，约束是，约束是“大于等于大于等于”型不等式。即型不等式。即“max，”和和“min，”相对相对应。应。(2)一个模型是一个模型是m个约束，个约束，n个变量，则它的对偶模型为个变量，则它的对偶模型为n个约束，个约束，m个变量。个变量。从约束系数矩阵看：一个模型中为从约束系数矩阵看：一个模型中为，则另一个模型中为则另一个

9、模型中为AT。(3)原问题目标函数系数是对偶问题的约束条件右端项；原问题目标函数系数是对偶问题的约束条件右端项；原问题的约束条件右端项是对偶问题的目标函数系数。原问题的约束条件右端项是对偶问题的目标函数系数。(4)两个规划模型中的变量皆非负。两个规划模型中的变量皆非负。例例3 3：写出下列线性规划的对偶规划：写出下列线性规划的对偶规划解：原规划的对偶规划为解：原规划的对偶规划为12max2wyyy1y2.s t 2515y 126224yy125yy12,0yy 12323123123min1524562.521,0zxxxxxs txxxxxx 不等式约束对应非负变量不等式约束对应非负变量三

10、、非对称形式的对偶规划三、非对称形式的对偶规划max0zCXAXbX min wYbYAC 叫做非对称形式的对偶规划。非对称形式的对偶规划叫做非对称形式的对偶规划。非对称形式的对偶规划可以由对称形式的对偶规划推出。可以由对称形式的对偶规划推出。例例4 4：写出下列线性规划问题的对偶规划。：写出下列线性规划问题的对偶规划。123412341234max53345810243280(1,2,3,4)jzxxxxxxxxxxxxxj 解：将上述线性规划化成对称对偶规划的形式解：将上述线性规划化成对称对偶规划的形式12341234123412341234max533458105810.24328243

11、280(1,2,3,4)jzxxxxxxxxxxxxs txxxxxxxxxj 写出它的对偶规划写出它的对偶规划111222121212121212,min10852543.33824,yyyyyywyyyyyys tyyyyyy 令令得得无无符符号号限限制制y1y1 y2y2 112211221122112211221122min10108855225443.33388224,0wyyyyyyyyyyyys tyyyyyyyyyyyy 等式约束对应自由变量等式约束对应自由变量111max(1,2,.,)(1,.,)0(1,2,.,)(1,.,)njjjnijjijnijjijjjzc xa

12、xbipa xbipmxjqxjqn 无无符符号号限限制制111min1,2,.)01,.)(1,2,.,)(1,.,)miiiiimijijimijijiwb yyipyipma ycjqa ycjqn 无无符符号号限限制制（(D)四、一般形式的对偶规划四、一般形式的对偶规划(P)一般形式的对偶规划的特点一般形式的对偶规划的特点（1 1）原问题是）原问题是“maxmax，=,”=,”形式，对偶问题是形式，对偶问题是“minmin，=,”=,”形式形式 （2 2）原问题的每个等式约束，对应对偶问题一个自由变量，）原问题的每个等式约束，对应对偶问题一个自由变量，原问题的每个不等式约束，对应对偶问

13、题的一个非负变量；原问题的每个不等式约束，对应对偶问题的一个非负变量；反之亦然，即原问题中的每个非负变量对应的是对偶问题反之亦然，即原问题中的每个非负变量对应的是对偶问题中的一个不等式约束，而原始问题中的每个自由变量对应中的一个不等式约束，而原始问题中的每个自由变量对应对偶问题中的一个等式约束。对偶问题中的一个等式约束。（3 3）原问题目标函数中的系数）原问题目标函数中的系数c c就是对偶问题约束条件的就是对偶问题约束条件的右端常数项，而原问题约束的右端常数项就是对偶问题目右端常数项，而原问题约束的右端常数项就是对偶问题目标函数中的系数。标函数中的系数。（4 4）如果用矩阵和向量形式写出问题）

14、如果用矩阵和向量形式写出问题(P)(P)和和(D)(D)的约束，可的约束，可以看出这两个问题的约束系数矩阵互为转置。以看出这两个问题的约束系数矩阵互为转置。例例5.5.写出下面线性规划的对偶规划写出下面线性规划的对偶规划12341234134123412max5732252726022430.510,0zxxxxxxxxxxxxxxs txxx 解解 先将约束条件变形为先将约束条件变形为“”形式形式y1y2y3y4y5123412341341234412max5732252726022430.105,0zxxxxxxxxxxxxxxs txxxx 再根据非对称形式的对应关系，直接写出对偶规划再

15、根据非对称形式的对应关系，直接写出对偶规划1234512313123124512345min256030105221321274527,0wyyyyyyyyyyyyyyyyyyyyyy 无无符符号号限限制制例写出下列线性规划问题的对偶规划例写出下列线性规划问题的对偶规划1231231232313min7434262436415.53300,0zxxxxxxxxxs txxxx 1112323232313min7434262436415.53300,0zxxxxxxxxxs txxxx 解：令解：令 x1=x1，将约束化成相对规范形式，将约束化成相对规范形式y1y2y31111123223232

16、max2415304372654.64330,0wyyyyyyyys tyyyyy 直接写出对偶规划直接写出对偶规划1231212312312max2415304372654.64330,0wyyyyyyyys tyyyyy 1231231232313min7434262436415.53300,0zxxxxxxxxxs txxxx 比较原规划和对偶规划比较原规划和对偶规划1111123223232max2415304372654.64330,0wyyyyyyyys tyyyyy 令令y1=y1,并把第一并把第一个约束两端乘以个约束两端乘以-1得得不符合要求的约束对应非正变量不符合要求的约束对

17、应非正变量线性规划原问题与对偶问题的对应关系线性规划原问题与对偶问题的对应关系原问题（对偶问题）原问题（对偶问题）对偶问题（原问题）对偶问题（原问题）目标函数目标函数 max目标函数目标函数 min n个个 变量变量 0 0 无限制无限制 n个个 约束条件约束条件 =目标函数中变量的系数目标函数中变量的系数约束条件右端常数约束条件右端常数 m个个约束条件约束条件 =m个个 0 变量变量 0 无限制无限制约束条件右端常数约束条件右端常数目标函数中变量的系数目标函数中变量的系数作业：作业：P881、(1)(2)(3)第二节、对偶问题的基本性质（对偶定理）第二节、对偶问题的基本性质（对偶定理）max

18、().0zCXPAXbs tX 原问题与对偶问题的解之间的关系原问题与对偶问题的解之间的关系定理定理 1(1(对称性对称性)对偶问题的对偶是原问题对偶问题的对偶是原问题。定理定理3 3 （强对偶定理）（强对偶定理）若原问题有最优解，则其对若原问题有最优解，则其对偶问题也一定有最优解，并且此时目标函数的最优偶问题也一定有最优解，并且此时目标函数的最优值相等。值相等。min().0wYbDYACs tY 定理定理 2(2(弱对偶定理弱对偶定理)设设X0和和Y0分别是原问题和对偶分别是原问题和对偶问题的可行解，则问题的可行解，则CX0 Y0b；特别当；特别当CX0=Y0b 时，时，X0和和Y0 分别

19、是原问题和对偶问题的最优解。分别是原问题和对偶问题的最优解。证明：将原问题加上松弛变量化成标准形式：证明：将原问题加上松弛变量化成标准形式：(,0)(,).0XMax zCSXA EbSs tXS 0.0,0Max zCXSAXESbs tXS 用单纯形方法求解得最优解用单纯形方法求解得最优解X，设其最优基为，设其最优基为B，则，则XB=B-1b,检验数为检验数为1(,0)(,)0BCC BA E 10BCC B A 100BC B 令令1BYC B 则则Y是对偶问题的可行解是对偶问题的可行解又因为又因为1BCXC B bYb 由定理由定理2知知Y是对偶问题的最优解。是对偶问题的最优解。即即即

20、即max().0zCXPAXbs tX min().0wYbDYACs tY 原问题和对偶问题的解的情况如下原问题和对偶问题的解的情况如下 对偶对偶原始原始有最优解有最优解问题无界问题无界无可行解无可行解有最优解有最优解 问题无界问题无界 无可行解无可行解 定理定理4 4 给定一个线性规划的原问题和它的对偶问题，给定一个线性规划的原问题和它的对偶问题，则上表中的三种情况恰有一种出现。则上表中的三种情况恰有一种出现。证明：由证明：由定理定理2容易容易证明，如果原问题或它的对偶中有一个证明，如果原问题或它的对偶中有一个是无界的，那么另一个不可能有可行解。（用反正法）是无界的，那么另一个不可能有可行

21、解。（用反正法）下面举例说明剩下的情况（下面举例说明剩下的情况（2 2）和（）和（3 3）是可能出现的。）是可能出现的。考虑下列对偶规划考虑下列对偶规划1211212121212maxmin11()()010,0wyyzxyyxxPDyyxxyy 显然两个问题均无可行解，情况（显然两个问题均无可行解，情况（2 2）出现。）出现。112121212121212minmax11()()100,00,0zxwyyxxyyPDxxyyxxyy原问题无可行解，对偶问题无界，情况（原问题无可行解，对偶问题无界，情况（3 3）出现。）出现。考虑下列对偶规划：考虑下列对偶规划：例例6 6 试用对偶理论证明下列

22、线性规划问题无界试用对偶理论证明下列线性规划问题无界12123123123max2.21,0zxxxxxs txxxxxx 11max(1,2,.,)0(1,2,.,)njjjnijjijjzc xa xbimxjn (P)11min(1,2,.,)0(1,2,.,)miiimijijiiwb ya ycjnyim (D)定理定理5（互补松弛定理）设（互补松弛定理）设X和和Y分别是原问题和对偶问题分别是原问题和对偶问题的可行解，则它们分别是原问题和对偶问题的最优解的充的可行解，则它们分别是原问题和对偶问题的最优解的充要条件是对一切的要条件是对一切的 i=1,2,m，和一切，和一切 j=1,2,

23、n 有有11()0()0niiijjijmjjijijiuya xbvca y x 证明：由对偶的定义知证明：由对偶的定义知11()01,2,.()01,2,.niiijjijmjjijijiuya 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 定义定义1111111111

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

25、 xbvca y x 2122112141622515max213.02,zxxs txxxxxx 1222311313min121615242.253,0yyywsyyyytyyy 原问题的最优解为原问题的最优解为 x1=3,x2=3.对偶问题的最优解为对偶问题的最优解为：y1=1,y2=0,y3=1/5.例如：考虑下面的一对对偶规划例如：考虑下面的一对对偶规划原问题的第一个约束对应对偶变量原问题的第一个约束对应对偶变量 y1。12122122 32 3120,10 xxy原问题的第二个约束对应对偶变量原问题的第二个约束对应对偶变量 y2。124164 31640,0 xy 原问题的第三个约

26、束对应对偶变量原问题的第三个约束对应对偶变量y3。2315155 3150,5xy123451234512345min20305020302340.23300,1,2,.5jwxxxxxxxxxxs txxxxxxj 例例7 7 已知线性规划问题已知线性规划问题 其对偶问题的最优解是其对偶问题的最优解是*128,6,500yyz 试用对偶理论找出原问题的最优解试用对偶理论找出原问题的最优解12121212121212max4030220(1)30(2)2350(3)20(4)330(5),0zyyyyyyyyyyyyyy 12121212121212max4030220(1)30(2)2350

27、(3)20(4)330(5),0zyyyyyyyyyyyyyy 将y1*=8,y2*=6 代入对偶问题的约束条件，由互补松弛条件得*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,.5jzx

29、xxxxxs txxxxj 123432115min121615242.2530,1,2,.5jywyyyys tyyyjyy 原问题的最优单纯形表为原问题的最优单纯形表为基基x1x4x2 jb343原问题变量原问题变量x11000y4对偶问题剩对偶问题剩余变量余变量x20010y5原问题松弛变量原问题松弛变量x31/2-20-1y1对偶问题变量对偶问题变量x40100y2x5-1/54/51/5-1/5y3原问题的最优解为原问题的最优解为 x1=3,x2=3.对偶问题的最优解为对偶问题的最优解为：y1=1,y2=0,y3=1/5.对偶问题的最优单纯形表为对偶问题的最优单纯形表为基基y1y3

30、jb11/5对偶问题变量对偶问题变量y1100 x3原问题松弛变量原问题松弛变量y22-4/5-4x4y3010 x5对偶问题剩余对偶问题剩余变量变量y4-1/21/5-3x1原问题变量原问题变量y50-1/5-3x2对偶问题的最优解为：对偶问题的最优解为：y1=1,y2=0,y3=1/5.原问题的最优解为原问题的最优解为 x1=3,x2=3.第三节、对偶问题的经济解释第三节、对偶问题的经济解释影子价格：影子价格：例例9 9（1 1）：第一工厂生产）：第一工厂生产A，B，C三三种产品，每种产种产品，每种产品都同时需要甲、乙两种原料，数据见表，问应该如品都同时需要甲、乙两种原料，数据见表，问应该

31、如何安排生产，使获得的利润最大？何安排生产，使获得的利润最大？消耗消耗 产品产品原料原料ABC现有原料现有原料（公斤）（公斤）甲甲2127乙乙13211利润（元利润（元/件）件）231（2 2）：假设第二工厂为了扩大生产想购买第一工厂）：假设第二工厂为了扩大生产想购买第一工厂的原料，问第一工厂分别以什么样的价格才愿意出的原料，问第一工厂分别以什么样的价格才愿意出售自己的原料？售自己的原料？（1 1）设第一工厂应安排）设第一工厂应安排A A，B B，C C的产量分别为的产量分别为x x1 1，x x2 2，x x3 3件，产值是件，产值是z z元，则问题元，则问题1 1的数学模型是的数学模型是（

32、2 2）设第一工厂将甲、乙两种原料的单价分别定为）设第一工厂将甲、乙两种原料的单价分别定为y y1 1，y y2 2元元/公斤，出售原料可以获得的收益是公斤，出售原料可以获得的收益是w w元，则问题元，则问题2 2的数学模型是的数学模型是123123123123max232273211,0zxxxxxxxxxxxx 1212121212min7112233.221,0wyyyyyys tyyyy 设设Y*=（y1*，y2*，,ym*)是对偶问题的最优解是对偶问题的最优解,则称则称yi*是原规划的第是原规划的第i个约束对应的影子价格。个约束对应的影子价格。从上例可以看出，从上例可以看出，yi*是

33、对第是对第i 种资源的一种估价，这种资源的一种估价，这个价格不是市场价格，而是针对具体企业在一定时期个价格不是市场价格，而是针对具体企业在一定时期内存在的一种特殊价格，它蕴涵在求最大利润的生产内存在的一种特殊价格，它蕴涵在求最大利润的生产计划中。计划中。在原规划中引进松弛变量，化成标准形式在原规划中引进松弛变量，化成标准形式 max z=2x1+3x2+x3 s.t.2x1+x2+2x3+x4 =7 x1+3x2+2x3 +x5=11 x1,x2,x3,x4,x5 0该问题的最优单纯形表为该问题的最优单纯形表为原问题的解为：原问题的解为：x1=2,x2=3。即产品。即产品A生产生产2件，产件，

34、产品品B生产生产3件，产品件，产品C不生产。不生产。对偶问题的解为：对偶问题的解为：y1*=3/5,y2*=4/5(单位：元单位：元/公公斤斤)。即甲原料的影子价格为。即甲原料的影子价格为 3/5元元/公斤公斤;乙原料的影子乙原料的影子价格为价格为 4/5元元/公斤公斤;（1）第）第i 种资源的影子价格种资源的影子价格 yi*是一个边际价格。是一个边际价格。它表示在第它表示在第i 种资源数量种资源数量bi 附近的某个闭区间内，该附近的某个闭区间内，该资源的数量增加一个单位（此时其它资源数量不资源的数量增加一个单位（此时其它资源数量不变），生产计划的最大利润变），生产计划的最大利润z*将增加将增

35、加 yi*个单位。个单位。z*=CBB-1b=Y*b 影子价格的经济含义影子价格的经济含义（2）影子价格是对现有资源实现最大效益的一种估价。）影子价格是对现有资源实现最大效益的一种估价。这种估价不是资源的市场价格，而是根据资源在生产中这种估价不是资源的市场价格，而是根据资源在生产中作出的贡献而作的估价。作出的贡献而作的估价。*iizyb （3 3）影子价格是一种机会成本，对市场有调节作用。）影子价格是一种机会成本，对市场有调节作用。当某种资源的市场价格低于影子价格时，企业应当买进当某种资源的市场价格低于影子价格时，企业应当买进该种资源用于扩大生产；当某种资源的市场价格高于影该种资源用于扩大生产

36、；当某种资源的市场价格高于影子价格时，企业的决策者应当把已有资源卖掉。随着资子价格时，企业的决策者应当把已有资源卖掉。随着资源的买进卖出，影子价格也将随着变化，直到影子价格源的买进卖出，影子价格也将随着变化，直到影子价格和市场价格保持同等水平时，才处于平衡状态。和市场价格保持同等水平时，才处于平衡状态。（4 4）由对偶问题的互补松弛性质可知，当某种资源未被）由对偶问题的互补松弛性质可知，当某种资源未被充分利用时，影子价格为充分利用时，影子价格为0 0；当某种资源的影子价格不为；当某种资源的影子价格不为0 0时，说明该资源在生产中已经消耗完毕。时，说明该资源在生产中已经消耗完毕。*1*10;0;

37、nijjiijniijjija xbyya xb 当当时时，当当时时，（5 5）从影子价格的含义上来考察单纯形法的计算。从影子价格的含义上来考察单纯形法的计算。11mjjBjjijiicC B Pca y 1mjijiicja y 是是第第 种种产产品品的的产产值值，是是生生产产该该产产品品所所消消耗耗的的资资源源的的影影子子价价格格的的总总和和，即即隐隐含含成成本本。当产品的产值大于隐含成本时，表明生产该项产品有利，当产品的产值大于隐含成本时，表明生产该项产品有利，可在计划中安排生产，否则这些资源生产别的产品更为可在计划中安排生产，否则这些资源生产别的产品更为有利，就不在生产计划中安排。这就

38、是有利，就不在生产计划中安排。这就是单纯形法中检验单纯形法中检验数的经济意义。数的经济意义。作业：作业：第第89页页 3,4,5题题第四节、对偶单纯形法第四节、对偶单纯形法一一对偶单纯形法的基本思想对偶单纯形法的基本思想二二对偶单纯形法求解原规划的主要步骤对偶单纯形法求解原规划的主要步骤三三对偶单纯形法的适用范围对偶单纯形法的适用范围一一.对偶单纯形方法的基本思想对偶单纯形方法的基本思想定理定理：设：设(P)的任一基解的任一基解X0对应基对应基B，记，记Y0=CBB-1。若。若X0和和Y0分别是原问题分别是原问题(P)和对偶问题和对偶问题(D)的可行解，则的可行解，则X0和和Y0 分别是分别是

39、(P)和和(D)的最优解。的最优解。证明：因为证明：因为Y0=CBB-1是是(D)的可行解，即的可行解，即 YA C C-CBB-1A 0由此说明由此说明X0是是(P)的可行解且检验数非正，故的可行解且检验数非正，故X0是是(P)的最优解。的最优解。又又 0100BBBBBNXY bC B bC XCCCX 故故Y0 是是(D)的最优解。的最优解。max().0zCXPAXbs tX min().0wYbDYACs tY 对偶单纯形方法：对偶单纯形方法：从原规划的一个基解出发，此基解从原规划的一个基解出发，此基解不一定是原规划的基可行解，但它对应着对偶问题的不一定是原规划的基可行解，但它对应着

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

41、法的求解步骤对偶单纯形法的求解步骤 1.1.建立初始对偶单纯形表建立初始对偶单纯形表,对应原问题的一个基解对应原问题的一个基解,所所有检验数均非正有检验数均非正,转转2 2；2.2.若若b0,0,则得到最优解则得到最优解,停止停止;否则否则,若有若有b bk k0,0,则选则选k k行的基变量为出基变量行的基变量为出基变量(若有多个若有多个b bk k0,0,则选最小的一个则选最小的一个所在的行中的基变量出基所在的行中的基变量出基),),转转3;3;3.3.若所有若所有akj0(0(j=1,2,n)，则原问题无可行解，则原问题无可行解,停止停止;否则否则,若有若有akj0,则计算则计算 =mi

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

43、题的一个基解（不可行）和对偶问题解（不可行）和对偶问题的一个可行解（检验数非的一个可行解（检验数非正）正）123123123123min23423.234,0zxxxxxxs txxxxxx 1231234123512345max 23423.234,0zxxxxxxxs txxxxxxxxx 1231234123512345max 23423.234,0zxxxxxxxs txxxxxxxxx CB00XBx4x5b-3-4-2x1-1-2-3x2-21-4x3-1-30 x4100 x501 j0-2-3-4000 x4-10-5/21/21-1/2-2x121-1/23/20-1/2 j

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

45、以主元素为中心元素进行迭代以主元素为中心元素进行迭代停停没没有有有有限限最最优优解解没没有有可可行行解解单纯形法单纯形法对偶单纯形法对偶单纯形法0ib0maxjjk0miniiebbb0ika0ljaekeikikiabaab0minmin0ikejejekaaa 0j三三.对偶单纯形法的适用范围对偶单纯形法的适用范围1.1.如下形式的问题如下形式的问题11(1,2,.).0(1,2,.)njjjnijjijjMinzc xa xbims txjn 2.2.灵敏度分析灵敏度分析作业：作业：89页页 第第6题题第五节：灵敏度分析第五节：灵敏度分析n灵敏度分析是指对系统或事物因周围条件变化显示出灵

46、敏度分析是指对系统或事物因周围条件变化显示出来的敏感程度的分析。来的敏感程度的分析。n信息的不确定性信息的不确定性 信息的变化：信息的变化：价值向量价值向量市场变化市场变化 （目标函数系数的变化）（目标函数系数的变化）右端向量右端向量资源变化资源变化 （b 的变化）的变化）系数矩阵系数矩阵技术进步技术进步 （aij 的变化的变化）认知的误差认知的误差n分析方法分析方法 静态分析静态分析-比较静态分析比较静态分析-动态分析动态分析一、一、目标函数中系数变化的分析目标函数中系数变化的分析二、二、约束条件右端常数变化的变化约束条件右端常数变化的变化三、三、增加新变量的分析增加新变量的分析四、四、增加

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

48、4 x5-3 x2 2/5 0 1-1/5-2/5 1/5-2 x1 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+c3当当-9/5+c3 0,即即c3 9/5 时，原最优解不变。时，原最优解不变。例例1212：在第一章例：在第一章例1 1的线性规划问题中的线性规划问题中,试分析试分析(1)(1)产品甲的单位利润在多大范围内变化时，最优生产方产品甲的单位利润在多大范围内变化时，最优生产方案保持不变？案保持不变？(2)(2)如果产品甲的单位利润由如果产品甲的单位利润由5050元增加到

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

50、不变。CB6050+C10XBx2x1x5b15101550+C1x101060 x21000 x33/8-1/43/40 x4-1/41/2-3/20 x5001CB601000XBx2x1x5b151015100 x101060 x21000 x33/8-1/43/40 x4-1/41/2-3/20 x5001 j-1400005/2-350601000 x2x1x37.515200101000011/20-2-1/21/34/3 j-1950000-30-10/3最优解变为：最优解变为：X*=(15,7.5,20,0,0)T二、二、约束条件右端常数变化的分析约束条件右端常数变化的分析b