第2章线性规划的对偶理论

1、第第1页页5-4 单纯形法计算的向量矩阵描述单纯形法计算的向量矩阵描述CXz max0. .XbAXts初始解初始解非基变量非基变量基变量基变量bBAIcj-zj N0,0基可行解基可行解基变量基变量非基变量非基变量B-1bIB-1AB-1cj-zj0,0-y1,-ymN 1110),( BCBCyyYBBmAYCABCCBN1CBC0CBC0CYACAYY 0CB0. .XbXAXtsa第第2页页2132maxxxz 122221 xx1641 x1552 x0,21 xxs.t. 5432100032maxxxxxxz )5 , 1(01551641222.5241321jxxxxxxxx

2、tsj第第3页页cj 23000CB基基bx1x2x3x4x50 x312221000 x416400100 x51505001cj -zj23000cj 23000CB基基bx1x2x3x4x5cj -zjx3x4x2003301001/5164001062010-2/52000-3/5BNx1 x2 x3 x4 x2 x3 x4 x5 0 x3 62010010- 2/50 x4 16400100103x230100100 1/52000000- 3/5x1 x2 x3 x4 x2 x3 x4 x5 0 x3 12221021000 x4 16400100100 x5 1505005001

3、23003000B-1B-1NB-1bNY1 + BY2 + Y3 = bB-1NY1 + Y2 + B-1Y3 = B-1b-CBB-1第第4页页cj 23000CB基基bx1x2x3x4x50 x312221000 x416400100 x51505001cj -zj230000 x40100cj 23000CB基基bx1x2x3x4x52x13101/20-1/50 x4400-214/53x2301001/5cj -zj00-10-1/50 x40100),(),(543241PPPIPPPB 5/1005/4125/102/11B 3431516125/1005/4125/102/1

4、1bB 5/1005/4125/102/13021BCB 5/101 b ),(1myy 第第5页页cj 23000CB基基bx1x2x3x4x50 x312221000 x416400100 x51505001cj -zj23000cj 23000CB基基bx1x2x3x4x5cj -zjx3x4x2003301001/5164001062010-2/52000-3/5cj 23000CB基基bx1x2x3x4x5cj -zjx1x4x2203301001/5400-214/53101/20-1/500-10-1/5第第6页页5-4 单纯形法计算的向量矩阵描述单纯形法计算的向量矩阵描述CXz

5、 max0. .XbAXts初始解初始解非基变量非基变量基变量基变量bBAIcj-zj N0,0基可行解基可行解基变量基变量非基变量非基变量B-1bIB-1AB-1cj-zj0,0-y1,-ymN 1110),( BCBCyyYBBmAYCABCCBN1CBC0CBC0CYACAYY 0CB0. .XbXAXtsa第第7页页cj 23000CB基基bx1x2x3x4x50 x312221000 x416400100 x51505001cj -zj230000 x40100cj 23000CB基基bx1x2x3x4x52x13101/20-1/50 x4400-214/53x2301001/5c

6、j -zj00-10-1/50 x40100),(),(543241PPPIPPPB 5/1005/4125/102/11B 3431516125/1005/4125/102/11bB 5/1005/4125/102/13021BCB 5/101 b ),(1myy 第第8页页线性规划问题具有对偶性线性规划问题具有对偶性, ,即任何一个线性规划问即任何一个线性规划问题题, ,都存在另一个线性规划问题与之对应都存在另一个线性规划问题与之对应. .如果把其如果把其中一个问题叫做原问题中一个问题叫做原问题, ,则另外一个就叫做它的对则另外一个就叫做它的对偶问题偶问题. .并称这两个相互联系的问题为一

7、对对偶问并称这两个相互联系的问题为一对对偶问题题. .研究对偶问题之间的关系及其性质研究对偶问题之间的关系及其性质, ,就是线性规就是线性规划的对偶理论划的对偶理论(Duality(DualityTheory).Theory).第第2章章 线性规划的对偶理论线性规划的对偶理论第第9页页|1 对偶问题的提出对偶问题的提出|2 原问题与对偶问题原问题与对偶问题|3 对偶问题的基本性质对偶问题的基本性质|4 影子价格影子价格|5 对偶单纯形法对偶单纯形法|6 灵敏度分析灵敏度分析|7 参数线性规划参数线性规划第第10页页 常山机器厂用常山机器厂用A、B、C三种设备生产三种设备生产I、II两种两种产品

8、。问该企业应如何安排生产使总的利润收入为最大。产品。问该企业应如何安排生产使总的利润收入为最大。占用设备占用设备时间时间(h)III用于生产用于生产的能力的能力设备设备A2212设备设备B4016设备设备C0515利润利润(元元)23例例1 1 生产计划问题生产计划问题2-1 对偶问题的提出对偶问题的提出模模型型2132maxxx 122221 xx1641 x1552 x0,21 xxs.t. 设设备设设备A, B, C每小时的出租价格分每小时的出租价格分别为别为y1, y2,和和y3元元出租条件出租条件: 租金收入租金收入生产的获利。生产的获利。四海机器厂接受条件四海机器厂接受条件: 租金

9、要低租金要低 0,352242151612min3213121321yyyyyyyyyyw第第11页页2132maxxx 122221 xx1641 x1552 x0,21 xxs.t. 0,352242151612min3213121321yyyyyyyyyyw模模型型第第12页页原始问题原始问题Max z=CXs.t.AX bX 0对偶问题对偶问题Min w =bT Ys.t. AT Y CT Y 0maxbACCTATbT maxmnmn 对偶的定义对偶的定义第第13页页 规范对偶问题规范对偶问题min z=CXs.t.AXbX 0max w=bTYs.t. ATYCY0max z=CX

10、s.t. AX bX 0min w=bTYs.t. ATY CTY0第第14页页2-2 原问题与对偶问题原问题与对偶问题minmax第第15页页 ), 1(0), 1(.min11miynjcyatsybwimijijimiii 0.minYCYAtsYbw 0.maxXbAXtsCXz ), 1(0), 1(.max11njxmibxatsxczjnjijijnjjj第第16页页【例例】写出下列线性规划的对偶问题写出下列线性规划的对偶问题 0,15744325min321321321321xxxxxxxxxxxxZ【解解】这是一个规范形式的线性规划，设这是一个规范形式的线性规划，设Y=（y1

11、，y2），），则有则有) 3 , 2, 5()57,4(571114),(414),(max212121212121 yyyyyyyyAYyyyybYw，线性规划的对偶模型线性规划的对偶模型 Dual model of LP第第17页页从而对偶问题为从而对偶问题为 0, 03527544max2121212121yyyyyyyyyyZ对偶变量对偶变量yi也可写成也可写成xi的形式。的形式。) 3 , 2, 5()57,4(571114),(414),(max212121212121 yyyyyyyyAYyyyybYw，线性规划的对偶模型线性规划的对偶模型 Dual model of LP第第1

12、8页页【例例】 写出下列线性规划的对偶问题写出下列线性规划的对偶问题 0, 01038576534max2121212121xxxxxxxxxxZ【解解】这是一个规范形式的线性规划，它的对偶问题求这是一个规范形式的线性规划，它的对偶问题求最小值，有三个变量且非负，有两个最小值，有三个变量且非负，有两个“ ”约束，即约束，即 3 , 2 , 1, 03324751086min321321321iyyyyyyyyyywi线性规划的对偶模型线性规划的对偶模型 Dual model of LP第第19页页若给出的线性规划不是规范形式，可以先化成规范形式再写对偶若给出的线性规划不是规范形式，可以先化成规

13、范形式再写对偶问题。也可直接按表问题。也可直接按表2-2中的对应关系写出非规范形式的对偶问题。中的对应关系写出非规范形式的对偶问题。 将上述原问题与对偶问题的对应关系列于表将上述原问题与对偶问题的对应关系列于表2-2例如，原问题是求最小值，按表例如，原问题是求最小值，按表2-2有下列关系：有下列关系： 1. 第第i个约束是个约束是“ ”约束时，第约束时，第i个对偶变量个对偶变量yj0 2第第i个约束是个约束是“ = ”约束时，第约束时，第i个对偶变量个对偶变量yi无约束；无约束；3当当xj0时，第时，第j个对偶约束为个对偶约束为“ ”约束，当约束，当xj无约束时，第无约束时，第j个对偶约束为个

14、对偶约束为“ = ”约束。约束。线性规划的对偶模型线性规划的对偶模型 Dual model of LP第第20页页原问题（或对偶问题）原问题（或对偶问题）对偶问题（或原问题）对偶问题（或原问题） 目标函数目标函数max目标函数系数目标函数系数约束条件右端项约束条件右端项约束条件系数矩阵约束条件系数矩阵A(AT) 目标函数目标函数min约束条件右端项约束条件右端项目标函数系数目标函数系数约束条件系数矩阵约束条件系数矩阵AT(A)变变量量n个变量个变量第第j个变量个变量0第第j 个变量个变量0第第j个变量无约束个变量无约束约约束束 n个约束个约束第第j个约束为个约束为第第j个约束为个约束为第第j个

15、约束为个约束为=约约束束m个约束个约束第第i个约束个约束第第i个约束个约束第第i个约束为个约束为=变变量量m个变量个变量第第i个变量个变量0第第i个变量个变量0第第i个变量无约束个变量无约束 线性规划的对偶模型线性规划的对偶模型 Dual model of LP第第21页页 ), 1(0), 1(.min11miynjcyatsybwimijijimiii 0.minYCYAtsYbw 0.maxXbAXtsCXz ), 1(0), 1(.max11njxmibxatsxczjnjijijnjjj第第22页页2-2 原问题与对偶问题原问题与对偶问题minmax第第23页页原问题（或对偶问题）原

16、问题（或对偶问题）对偶问题（或原问题）对偶问题（或原问题） 目标函数目标函数max目标函数系数目标函数系数约束条件右端项约束条件右端项约束条件系数矩阵约束条件系数矩阵A(AT) 目标函数目标函数min约束条件右端项约束条件右端项目标函数系数目标函数系数约束条件系数矩阵约束条件系数矩阵AT(A)变变量量n个变量个变量第第j个变量个变量0第第j 个变量个变量0第第j个变量无约束个变量无约束约约束束 n个约束个约束第第j个约束为个约束为第第j个约束为个约束为第第j个约束为个约束为=约约束束m个约束个约束第第i个约束个约束第第i个约束个约束第第i个约束为个约束为=变变量量m个变量个变量第第i个变量个变

17、量0第第i个变量个变量0第第i个变量无约束个变量无约束 线性规划的对偶模型线性规划的对偶模型 Dual model of LP第第24页页 0, 0837435522.)1(365max32321321321321xxxxxxxxxxxtsxxxz321835minyyyw 无无约约束束1y02 y03 y54321 yyy6752321 yyy332321 yyy第第25页页 ), 1(), 1(0), 1(), 1(.)2(max1111111nnjxnnjxmmibxammibxatsxczjjnjijijnjijijnjjj无无约约束束 miiiybw1min), 1(01miyi )

18、, 1(1mmiyi 无无约约束束 mijijinjcya11), 1( mijijinnjcya11), 1(第第26页页321365maxxxxz 00332675254.)3(835min32321321321321yyyyyyyyyyytsyyyw03 x35321 xxx无无约约束束1x02 x8374321 xxx522321 xxx无约束无约束1y第第27页页2-3 对偶问题的基本性质对偶问题的基本性质弱对偶性；强对偶性；弱对偶性；强对偶性；最优性最优性; 无界性无界性; 互补松弛性互补松弛性掌握原问题和掌握原问题和其对偶问题解其对偶问题解之间的关系之间的关系第第28页页 0ma

19、xXbAXCXZ对偶问题是（记为对偶问题是（记为DP）：）： 0minYCAYbYw这里这里A是是mn矩阵矩阵, X是是n1列向量，列向量，Y是是m1列向量。假设列向量。假设Xs与与Ys分别是（分别是（LP）与（）与（DP）的松驰变量。）的松驰变量。设原问题是（记为设原问题是（记为LP）：）： 2.3对偶性质对偶性质Dual property ), 1(0), 1(. .max11njxmibxatsxczjnjijijnjjj ), 1(0), 1(.min11miynjcyatsybwimijijimiii第第29页页 【证证】因为因为X0、Y0是可行解，故有是可行解，故有AX0b, X0

20、0及及AY 0C，Y00,将不等式将不等式 AX0b弱对偶性弱对偶性 设设X0、Y0分别为分别为LP(max)与与DP(min)的可行解，的可行解，则则 00YbCX 两边左乘两边左乘Y0，得，得Y0 AX0Y0b再将不等式再将不等式Y0AC两边右乘两边右乘X0，得，得C X0Y0AX0故故 C X0Y0AX0Y0b这一性质说明了两个线性规划互为对偶时，求最大这一性质说明了两个线性规划互为对偶时，求最大值的线性规划的任意目标值都不会大于求最小值的值的线性规划的任意目标值都不会大于求最小值的线性规划的任一目标值，不能理解为原问题的目标线性规划的任一目标值，不能理解为原问题的目标值不超过对偶问题的

21、目标值。值不超过对偶问题的目标值。2.2 对偶性质对偶性质Dual property第第30页页), 1(njxj ), 1(miyi imiijnjjybxc11 jnjjjnjjxcxc11imiiimiiybyb11 ), 1(njxj ), 1(miyi ), 1(njxj ), 1(miyi 第第31页页CXz max0. .XbAXts初始基可行解初始基可行解 X基变量基变量XsbBAIcj-zj N0,0基可行解基可行解基变量基变量X XsB-1bIB-1AB-1cj-zj0,0-y1,-ymN 1110),( BCBCyyYBBmCAYCABCBN 1 CBC0CBC0CB 0

22、.XbXAXtss 0minYCAYbYw 0YCYAYs第第32页页bB-1 BCZbBCbYwB 1wZ （对偶问题）（对偶问题）原问题原问题记记1-1, )b(BX BCYBXCB bY YXCBbY CYACAYY 0第第33页页wzminmax ), 1, 1(0, 0), 1(.max11njmixxmibxxatsxczsijnjisijijnjjj, 0 Y), 1(0miyi 0 YAC ), 1(1njcyanijiij ), 1(0miyi bBCxcBnjjj11 miiiyb1第第34页页互补松弛定理互补松弛定理 设设X0、Y0分别为（分别为（LP）与（）与（DP）的

23、可行解，）的可行解，XS和和YS是它的松弛变量的可行解，则是它的松弛变量的可行解，则X0和和Y0是最优解当且仅当是最优解当且仅当YSX0=0和和Y0XS=0【证证】设设X和和Y是最优解是最优解,由强对偶性得，由强对偶性得，C X0= bY0，由于，由于XS和和YS是松弛变量，则有是松弛变量，则有A X0XSbY0AYS=C将第一式左乘将第一式左乘Y0，第二式右乘，第二式右乘X0得得Y0A X0Y0XSY0bY0A X0YS X0=C X02.3 对偶性质对偶性质Dual property第第35页页显然有显然有 Y0XS=YS X0又因为又因为Y、Xs、Ys、X0，所以有，所以有Y0XS=0和

24、和YS X0=0成立。成立。反之，反之， 当当Y0XS=0和和YS X=0时，有时，有YA XYbYA X=C X显然有显然有Y0b=C X,由最优性知由最优性知Y与与X是（是（LP）与（）与（DP）的）的最优解。证毕。最优解。证毕。2.3对偶性质对偶性质Dual property第第36页页互补松弛关系互补松弛关系max z=CTXs.t. AX+u=b X, u0min w=bTYs.t. ATY-v=C Y, v0max z=CXs.t. AX b X 0min w=bTYs.t. ATy C y0对偶对偶引进松弛变量引进松弛变量引进松弛变量引进松弛变量XTv=0 YTu=0互补松弛关系

25、互补松弛关系X，uY，v第第37页页max z=CXs.t.AX+u=bX, u 0min w=bTys.t. ATY-v=CTY, v 0XTv=0YTu=0mn=YvAT-ICTn=AuIbnmmX第第38页页y1 yi ym vm+1 vm+j vm+n x1 xj xn un+1 un+i un+m 对偶问题的变量对偶问题的变量 对偶问题的松弛变量对偶问题的松弛变量xjvm+j=0yiun+i=0(i=1,2,m; j=1,2,n)在一对变量中，其中一个大于在一对变量中，其中一个大于0，另一个一定等于，另一个一定等于0第第39页页【例例2】 已知线性规划已知线性规划 3 , 2 , 1

26、, 0162210243max321321321jxxxxxxxxxxzj的最优解是的最优解是 求对偶问题的最优解。求对偶问题的最优解。TX)0 , 2 , 6(2.2 对偶性质对偶性质Dual property第第40页页【解解】对偶问题是对偶问题是 0,1422321610min2121212121yyyyyyyyyyw因为因为X10，X20，所以对偶问题的第一、，所以对偶问题的第一、二个约束的松弛变量等于零，即二个约束的松弛变量等于零，即 422322121yyyy解此线性方程组得解此线性方程组得y1=1,y2=1,从而对偶问题的最优解从而对偶问题的最优解为为Y=（1，1），最优值），最

27、优值w=26。2.2 对偶性质对偶性质Dual property第第41页页2-4 已知线性规划问题：已知线性规划问题： )4 , 3 , 2 , 1(0966283.42max321432214214321jxxxxxxxxxxxxtsxxxxzj对偶问题对偶问题 )4 , 3 , 2 , 1(0114322.9668min314343214214321iyyyyyyyyyyyytsyyyywi要求要求: (a)写出其对偶问题；写出其对偶问题； (b)已知原问题最优解为已知原问题最优解为 根据对偶理论根据对偶理论, 直接求出对偶直接求出对偶问题的最优解问题的最优解.)0 , 4 , 2 ,

28、2( X由互补松弛性得由互补松弛性得14322434321421 yyyyyyyyy由目标函数相等得由目标函数相等得1696684321 yyyy第第42页页jjjcz jjjcz 第第43页页CXz max0. .XbAXts初始解初始解非基变量非基变量基变量基变量bBAIcj-zj N0,0基可行解基可行解基变量基变量非基变量非基变量B-1bIB-1AB-1cj-zj0,0-y1,-ym1110),( BCBCyyYBBmCBC0CBC0CB 0.XbXAXtss 0minYCAYbYw 0YCYAYsjjjjczy ,CAYCABCBN 1 N 第第44页页2132maxxx 12222

29、1 xx1641 x1552 x0,21 xxs.t. 0,352242151612min3213121321yyyyyyyyyyw5432100032maxxxxxxz )5 , 1(015516412225241321jxxxxxxxxj ) 5 , 1( 035224200151612max53142154321iyyyyyyyyyyyywi第第45页页cj 23000CB基基bx1x2x3x4x50 x312221000 x416400100 x51505001cj -zj23000cj 23000CB基基bx1x2x3x4x5cj -zjx3x4x2003301001/5164001

30、062010-2/52000-3/5cj 23000CB基基bx1x2x3x4x5cj -zjx1x4x2203301001/5400-214/53101/20-1/500-10-1/5第第46页页cj 23000CB基基bx1x2x3x4x5zj - cj203301001/5400-214/53101/20-1/500101/5x1x4x2cj-12-16-1500CB基基by1y2y3y4y5-12y11120-1/20-15y31/50-4/511/5-1/5zj - cj04033第第47页页目标函数值目标函数值原问题原问题对偶问题对偶问题第第48页页2-4 影子价格影子价格 mii

31、injjjybxcz11ibiy影子影子价格价格说明：说明：iiybz 第第49页页, 0 iy;1 njijijbxa,1 njijijbxa0 iy;11 miiijjjBjjyacPBCc jc miiijya1第第50页页2-5 对偶单纯形法对偶单纯形法单纯形法计算的基本思想：单纯形法计算的基本思想：即即01 bB01 bB01 ABccB对偶单纯形法的基本思想：对偶单纯形法的基本思想：01 ABccB01 bB01 ABccB即即第第51页页cj c1cmcj cnx1xmxjxnCB基基bc1c2cmx1x2xmcj -zj00100001a1ja1na2ja2namjamnmbb

32、b21cj zjcn -zn对偶单纯形法的初始单纯形表：对偶单纯形法的初始单纯形表：cj zj 0 ( j= 1,n ), 1(mibi 第第52页页0|min iiirbbb,0minrsssrjrjjjjazcaazc ), 1(0mibi . 0, 10 rjranjb有有，而而对对所所有有对对rnrnmmrrbxaxax 11,第第53页页 0,52233.18124min3213231321xxxxxxxtsxxxz )5 , 4 , 3 , 2 , 1( 052233.0018124max53243154321ixxxxxxxtsxxxxxwicj-4-12-1800CB基基bx1

33、x2x3x4x50 x4-3-10-3100 x5-50-2-201cj-zj-4-12-18000 x4cj-zj-12x2cj-zj-12x25/20110-1/2-3-10-310-40-60-6-18x311/301-1/303/2-1/3101/3-1/2-200-2-6第第54页页 ), 1(0)0)(, 1(.)0(min11njxbmibxatscxczjnjiijijjnjjj第第55页页|概况概况|改变价值向量改变价值向量|改变右端向量改变右端向量|增加变量增加变量|增加约束条件增加约束条件2-6 灵敏度分析灵敏度分析第第56页页1. 灵敏度分析的含义灵敏度分析的含义|概况

34、概况2. 灵敏度分析研究的问题灵敏度分析研究的问题3. 如何解决如何解决第第57页页灵敏度分析的步骤灵敏度分析的步骤原问题原问题对偶问题对偶问题结论或继续计算的步骤结论或继续计算的步骤可行解可行解可行解可行解仍为最优解仍为最优解可行解可行解非可行解非可行解用单纯形法继续迭代用单纯形法继续迭代非可行解非可行解可行解可行解用对偶单纯形法继续迭代用对偶单纯形法继续迭代非可行解非可行解非可行解非可行解引入人工变量引入人工变量, 编制新的单纯表编制新的单纯表, 重新计算重新计算第第58页页6-1 价值系数价值系数cj发生变化发生变化(仅影响检验数仅影响检验数)单单纯纯形形表表cjc1c2cnCB基基bx

35、1x2xnCBXBB-1bIB-1N j0CN - CBB-1N2132maxxxz 122221 xx1641 x1552 x0,21 xxs.t. cj 23000CB基基bx1x2x3x4x5cj -zjx1x4x22033101/20-1/5301001/5400-214/500-10-1/52211)3()2(maxxxz 21 、21 、第第59页页cjc1c2cnCB基基bx1x2xnCBXBB-1bIB-1N j0CN - CBB-1Ncj 23000CB基基bx1x2x3x4x5cj -zjx1x4x22033101/20-1/5301001/5400-214/500-10-

36、1/5cj 23000CB基基bx1x2x3x4x5cj -zjx1x4x22033101/20-1/5301001/5400-214/500-10-1/53x141001/400 x5500-5/2 5/412x22011/2 -1/40cj -zj 00-1-1/40第第60页页cj 23000CB基基bx1x2x3x4x5cj -zjx1x4x22033101/20-1/5301001/5400-214/500-10-1/52211)3()2(maxxxz 21 、cj 23000CB基基bx1x2x3x4x5cj -zjx1x4x22033101/20-1/5301001/5400-2

37、14/500-101/502 12 12 221 511 , 0221 0511 121 , 01 21 第第61页页cj 23000CB基基bx1x2x3x4x5cj -zjx1x4x22033101/20-1/5301001/5400-214/500-10-1/52211)3()2(maxxxz 21 、cj 23000CB基基bx1x2x3x4x5cj -zjx1x4x22033101/20-1/5301001/5400-214/500-101/512 12 221 5121 , 0221 1,2121 23 23 05121 2 1 第第62页页6-2 分析分析bi的变化范围的变化范围

38、cjc1c2cnCB基基bx1x2xnCBXBB-1bIB-1N j0CN - CBB-1N原问题原问题对偶问题对偶问题结论或继续计结论或继续计算的步骤算的步骤可行解可行解可行解可行解仍为最优解仍为最优解可行解可行解非可行解非可行解用单纯形法继用单纯形法继续迭代续迭代非可行解非可行解可行解可行解用对偶单纯形用对偶单纯形法继续迭代法继续迭代非可行解非可行解非可行解非可行解引入人工变量引入人工变量, 编制新的单纯编制新的单纯表表, 重新计算重新计算bi的变化引起基变量的的变化引起基变量的取值发生变化，有可取值发生变化，有可能发生能发生1、3两种情况两种情况第第63页页2132maxxxz 1222

39、21 xx1641 x1552 x0,21 xxs.t. cj 23000CB基基bx1x2x3x4x5cj -zjx1x4x22033101/20-1/5301001/5400-214/500-10-1/5)15,16,12(321 321 、321 、第第64页页cj 23000CB基基bx1x2x3x4x5cj -zjx1x4x22033101/20-1/5301001/5400-214/500-10-1/5),(241PPPB 422/72012155/1005/4125/102/11bBTb)20,12,15(1 cj 23000CB基基bx1x2x3x4x5cj -zjx1x4x2

40、203101/20-1/501001/500-214/500-10-1/57/2-242x131001/400 x31001-1/2 -2/53x2401001/5cj -zj 000-1/2 -3/5T)0 , 0 , 1 , 4 , 3(第第65页页cj 23000CB基基bx1x2x3x4x5cj -zjx1x4x22033101/20-1/5301001/5400-214/500-10-1/5 311516125/1005/4125/102/1 bB)15,16,12(321 b321 、,021 )15,16,12(3 bT 53,544,53333 0530544053333 ，1

41、553 2314,0 26,0132 第第66页页解：解：cj 23000CB基基bx1x2x3x4x5cj -zjx1x4x22033101/20-1/5301001/5400-214/500-10-1/5 32111516125/1005/4125/102/1 bBT 53,5424,523332131 )15,16,12(321 b321 、05305424, 0523332131 155/44265/2331231 第第67页页6-3 增加新变量增加新变量(增加新产品增加新产品)cjc1c2cnCB基基bx1x2xnCBXBB-1bIB-1N j0CN - CBB-1N分析步骤：分析步

42、骤：jjjBjjYPcPBCc 1 jjPBP1 0 j 0 j j jP 第第68页页2132maxxxz 122221 xx1641 x1552 x0,21 xxs.t. cj 23000CB基基bx1x2x3x4x5cj -zjx1x4x22033101/20-1/5301001/5400-214/500-10-1/5解：解：jjPBP1 1405425/1005/4125/102/11140)3, 0, 2(46 第第69页页cj 23000CB基基bx1x2x3x4x5cj -zjx1x4x22033101/20-1/5301001/5400-214/500-10-1/5构造新表构造

43、新表cj 23000CB基基bx1x2x3x4x5cj -zjx1x4x22033101/20-1/5301001/5400-214/500-10-1/54x60411利用单纯形利用单纯形法继续迭代法继续迭代第第70页页6-4 增加约束条件增加约束条件(增加工序增加工序)分析步骤：分析步骤：2132maxxxz 122221 xx1641 x1552 x0,21 xxs.t. cj 23000CB基基bx1x2x3x4x5cj -zjx1x4x22033101/20-1/5301001/5400-214/500-10-1/5142321 xx第第71页页cj 23000CB基基bx1x2x3x

44、4x5cj -zjx1x4x22033101/20-1/5301001/5400-214/500-10-1/5解：解：142321 xx构造新表构造新表cj 23000CB基基bx1x2x3x4x52x13101/20-1/50 x4400-214/53x2301001/5cj -zj00-10-1/51423621 xxx0 x6000100 x6142x13101/20-1/500 x4400-214/503x2301001/500 x6-100-3/201/51cj -zj00-10-1/5032000第第72页页2x13101/20-1/500 x4400-214/503x230100

45、1/500 x6-100-3/201/51cj -zj00-10-1/50cj 23000CB基基bx1x2x3x4x50 x6对偶单对偶单纯形法纯形法2x18/31000-2/151/30 x416/300018/15-4/33x2301001/500 x32/30010-2/15-2/3cj -zj0000-1/3-2/3最优解最优解最优值最优值第第73页页2132maxxxz 122221 xx1641 x1552 x0,21 xxs.t. cj 23000CB基基bx1x2x3x4x5cj -zjx1x4x22033101/20-1/5301001/5400-214/500-10-1/

46、5162321 xx142321 xx第第74页页2132maxxxz 122221 xx1641 x1552 x0,21 xxs.t. cj 23000CB基基bx1x2x3x4x5cj -zjx1x4x22033101/20-1/5301001/5400-214/500-10-1/5142321 xx解：解：cj 23000CB基基bx1x2x3x4x52x13101/20-1/50 x4400-214/53x2301001/5cj -zj00-10-1/50 x6000100 x6-14-3-20001423621 xxx第第75页页cj 23000CB基基bx1x2x3x4x52x13

47、101/20-1/50 x4400-214/53x2301001/5cj -zj00-10-1/50 x6000100 x6-14-3-20002x13101/20-1/500 x4400-214/503x2301001/500 x61003/20-1/51cj -zj00-10-1/50第第76页页2132maxxxz 122221 xx1641 x1552 x0,21 xxs.t. cj 23000CB基基bx1x2x3x4x5cj -zjx1x4x22033101/20-1/5301001/5400-214/500-10-1/5162321 xx解：解：1623621 xxx构造新表构造

48、新表cj 23000CB基基bx1x2x3x4x52x13101/20-1/50 x4400-214/53x2301001/5cj -zj00-10-1/50 x6000-100 x61632000第第77页页cj 23000CB基基bx1x2x3x4x52x13101/20-1/50 x4400-214/53x2301001/5cj -zj00-10-1/50 x6000-100 x616320002x13101/20-1/500 x4400-214/503x2301001/500 x6-1003/20-1/51cj -zj00-10-1/502x1410-100-10 x400041043

49、x22013/20010 x3500-15/201-5cj -zj00-5/200-1第第78页页2-7 参数线性规划参数线性规划灵敏度分析：灵敏度分析：参数线性规划：参数线性规划：第第79页页21)3()22()(maxxxz 122221 xx1641 x1552 x0,21 xxs.t. 解：解：cj 23000CB基基bx1x2x3x4x5cj -zjx1x4x22033101/20-1/5301001/5400-214/500-10-1/5将参数的变化反映到将参数的变化反映到最终单纯形表中，得最终单纯形表中，得cj 23000CB基基bx1x2x3x4x5cj -zjx1x4x220

50、33101/20-1/5301001/5400-214/500-101/5 22 22 151 3 301 051, 11 第第80页页cj 23000CB基基bx1x2x3x4x5cj -zjx1x4x22033101/20-1/5301001/5400-214/500-101/5 22 22 15/ )1( 3 30 x362010-2/50 x41640010 x2301001/5cj -zj000 22 5/ )3 ( 13 3 0 x312221000 x416400100 x51505001cj -zj000 22 11 3 3第第81页页cj 23000CB基基bx1x2x3x4

51、x5cj -zjx1x5x22033101/20-1/5301001/5400-214/500-101/5 22 22 15/ )1( 3 30 x141001/400 x5500-5/25/41x22011/2-1/40cj -zj0001 11 3 22 41 2)3( 第第82页页2132maxxxz 122221 xx1641 x 1552x0,21 xxs.t. 解：解：cj 23000CB基基bx1x2x3x4x5cj -zjx1x4x22033101/20-1/5301001/5400-214/500-10-1/5将参数的变化反映到最终单纯形表中将参数的变化反映到最终单纯形表中c

52、j 23000CB基基bx1x2x3x4x5cj -zjx1x4x2203101/20-1/501001/500-214/500-101/505/3, 05/44, 05/3 155 53544531516125/1005/4125/102/11 bB5/3 5/3 5/44 第第83页页cj 23000CB基基bx1x2x3x4x5cj -zjx1x4x2203101/20-1/501001/500-214/500-101/5155 5/3 5/3 5/44 迭迭代代利利用用对对偶偶单单纯纯形形法法继继续续时时当当, 0,54 x 2x141001/400 x3 001-1/2-2/53x2

53、201001/5cj -zj000-1/2-3/55/3 5/22 515 时时，本本题题无无可可行行解解当当15 第第84页页cj 23000CB基基bx1x2x3x4x5cj -zjx1x4x2203101/20-1/501001/500-214/500-101/5155 5/3 5/3 5/44 迭迭代代利利用用对对偶偶单单纯纯形形法法继继续续时时当当, 0,151 x 0 x5-50-5/2010 x416 400103x26111/200cj -zj-10-3/20015 15 第第85页页课后习题选讲课后习题选讲2-1 写出下列线性规划问题的对偶问题写出下列线性规划问题的对偶问题

54、), 1;, 1(0), 1(), 1(.min1111njmixnjbxmiaxtsxczijmijijnjiijminjijij), 1(miyai 无无约约束束), 1(njybj 无无约约束束 minjbjjaiiybyaw11maxijbjaicyy 第第86页页2-2 判断下列说法是否正确，为什么？判断下列说法是否正确，为什么？第第87页页2-3 应用对偶理论证明下述线性规划问题为无界解。应用对偶理论证明下述线性规划问题为无界解。 0, 0, 0122.max32132132121xxxxxxxxxtsxxz对偶问题对偶问题原问题原问题 0, 00112.2min2121212121yyyyyyyytsyyw无可行解无可行解因为对偶问题无可行解，所因为对偶问题无可行解，所以原问题无可行解或无界解以原问题无可行解或无界解而而(0,0,0)是原问题的可行解，是原问题的可行解，所以