大学精品课件：15线性规划(《数值计算方法》清华大学出版社).ppt

1、线性规划线性规划线线性性规规划划模模型型.1标准型标准型.2解解的的概概念念和和性性质质.4单单纯纯形形算算法法.5图解法图解法.3线线性性规规划划模模型型一一.生生产产计计划划问问题题例例1利利润润最最大大？生生产产计计划划，才才能能使使所所获获安安排排千千元元。问问：该该厂厂应应如如何何、单单位位产产品品的的利利润润为为、同同，如如下下表表。耗耗费费的的加加工工时时间间各各不不相相产产品品所所需需材材料料的的数数量量和和三三种种产产品品，它它们们的的单单位位、生生产产某某工工厂厂利利用用某某种种原原材材料料754CBACBA产品产品资源资源原材料原材料工时工时ABC资源总量资源总量215.

2、1232100150解：解：确确定定目目标标函函数数.2确确定定决决策策变变量量.1。、的的产产量量分分别别为为、设设321xxxCBA，则则设设总总利利润润为为 S321754xxxS 确确定定约约束束条条件件.310035.12321 xxx3,2,1,015022321 ixxxxi数数学学模模型型.43217x5x4xSmax 3,2,1,01502210035.12.321321ixxxxxxxtsi线线性性规规划划模模型型：一一组组决决策策变变量量；)1(一一个个线线性性目目标标函函数数；)2(一一组组线线性性的的约约束束条条件件。)3(的的一一般般形形式式：线线性性规规划划模模型

3、型)(LP niiixc1(max)min nixbxaxaxabxaxaxabxaxaxatsimnmnmmnnnn,2,1,0),(),(),(),(.22112222212111212111标标准准型型二二.标标准准型型.1niiixc1min nixbxaxaxabxaxaxabxaxaxatsimnmnmmnnnn,2,1,0.22112222212111212111记记为为。则则线线性性规规划划标标准准型型可可记记nmijTnTmTnaAxxxxbbbbcccc )(,),(,),(,),(212121xcTmin 0.xbAxts化化标标准准型型.2目目标标函函数数：)1(:目标

4、函数原问题xcxcTT minmax约约束束条条件件：)2(ininiibxaxaxai 2211)(：原问题条件原问题条件 02211iniinniniixbxxaxaxa称称为为松松弛弛变变量量。inx ininiibxaxaxaii 2211)(：原问题条件原问题条件 02211iniinniniixbxxaxaxa称称为为剩剩余余变变量量。inx。无无非非负负约约束束，则则令令：原原问问题题 0,)(iiiiiivuvuxxiii为为标标准准型型。将将下下述述线线性性规规划划模模型型化化例例14321332minxxxx 无约束无约束243143214214321,0,63472233

5、32.xxxxxxxxxxxxxxxts解解：则则令令,222vux 432213332minxxvux 0,634472223332.22754317432214221543221vuxxxxxxxxvuxxvuxxxxvuxts图解法图解法三三.求求解解线线性性规规划划例例 2 0,5242.34max21212121xxxxxxtsxxz解：解：。画画出出可可行行解解的的范范围围)1(1x2xoABC求求极极值值点点。利利用用等等值值线线平平移移的的方方法法)2(表表示示一一族族等等值值平平行行线线。为为参参数数，则则方方程程以以zxxz 21344221 xx5221 xx。顶点顶点极

6、大值点为极大值点为B。中中的的目目标标函函数数改改为为将将例例例例21223xxz 1x2xoABC4221 xx5221 xx解：解：。分分析析同同例例 2。等值线：等值线：zxx 212任任一一点点。上上的的极极大大值值点点为为线线段段 AB1x2xoABC221 xx221 xx解：解：。分分析析同同例例 2。等值线：等值线：zxx 2134求求解解线线性性规规划划例例 4 0,22.34max21212121xxxxxxtsxxz不不存存在在最最大大值值。结结果果：线性规划问题的解线性规划问题的解 无无最最优优解解有有最最优优解解 有有无无穷穷多多最最优优解解在在顶顶点点取取到到唯唯一

7、一最最优优解解 可可行行域域为为空空集集解解无无界界优解？优解？，是否在顶点中存在最，是否在顶点中存在最对一般的线性规划问题对一般的线性规划问题质质线线性性规规划划解解的的概概念念和和性性四四.线线性性规规划划解解的的概概念念.1)(LPxczT max 0.xbAxts)1()2()3(的的可可行行解解。称称为为）式式的的解解）、（满满足足（可可行行解解：)(),(3221LPxxxxTn。可行域：可行域：0,|xbAxxD定理定理是是凸凸集集。线线性性规规划划问问题题的的可可行行域域 D证明：证明：。任取任取10,21 Dxx2121)1()1(AxAxxxA bbb )1(是凸集。是凸集

8、。即。即所以所以DDxx 21)1(的一个顶点。的一个顶点。为为则称则称，使使。及及，。如果不存在。如果不存在为凸集，为凸集，设设顶点：顶点：SxxxxSxxSxS2121)1(10 x1x2x一一个个基基。问问题题或或的的为为退退化化子子阵阵，则则称称阶阶的的非非中中为为若若。秩秩为为的的系系数数矩矩阵阵为为设设基基)(,:LPABmmABmnmA 非非基基变变量量。的的变变量量称称为为为为基基变变量量，不不是是基基变变量量对对应应的的变变量量为为基基向向量量，称称称称设设基基),1(),1(,),(21mjxPmjPPPPBjijijimii 为为基基变变量量。为为基基，则则取取列列向向量

9、量线线性性无无关关，则则可可的的前前不不妨妨设设，已已知知mmnmxxPPPBmAmAr,),()(121 bAx 因为因为即即bxPxPxPxPnnmmmm 111所以所以nnmmmmxPxPbxPxP 111解得解得令非基变量令非基变量,01 nmxxbBxxTm11),(的的基基本本解解。为为对对应应于于基基称称解解变变量量的的取取值值得得基基，令令非非基基变变量量取取零零，求求取取定定线线性性规规划划问问题题的的基基基基本本解解：BbBbBBT)0,(,11 解解。的的基基本本解解称称为为基基本本可可行行基基本本可可行行解解：满满足足条条件件)3(问问题题给给定定例例)(LP 0,22

10、22842.22max4321432143214321xxxxxxxxxxxxtsxxxxz和一个基本可行解。和一个基本可行解。求此问题的一个基本解求此问题的一个基本解解：解：。系数矩阵系数矩阵 12224121A得得，则则令令非非基基变变量量取取,0222143 xxB 222822121xxxx 3731021xx可可行行解解。是是基基本本解解，但但不不是是基基本本Tx)0,0,37,310(1 得得，则则令令非非基基变变量量取取,0124132 xxB 22844141xxxx 91491641xx是是基基本本可可行行解解。Tx)914,0,0,916(2 可行解可行解基基本本解解基基本

11、本可可行行解解mnC 基本解数量基本解数量定定存存在在最最优优解解？是是否否在在基基本本可可行行解解中中一一线线性性规规划划解解的的性性质质.2的的顶顶点点。可可行行域域是是是是要要条条件件是是基基本本可可行行解解的的充充分分必必的的解解线线性性规规划划问问题题定定理理DxxLP)(基基本本可可行行解解。如如果果有有可可行行解解，则则必必有有线线性性规规划划问问题题定定理理)(LP可可行行解解。最最优优的的基基本本如如果果有有最最优优解解，则则必必有有线线性性规规划划问问题题定定理理)(LP单单纯纯形形算算法法五五.判判断断出出不不存存在在最最优优解解。直直到到找找到到最最优优解解，或或者者基

12、基本本可可行行解解，则则转转换换到到另另一一个个更更好好的的是是则则算算法法结结束束。不不是是，。，判判断断其其是是否否为为最最优优解解从从一一个个基基本本可可行行解解开开始始算算法法思思路路：.1问问题题：行行解解？如如何何得得到到第第一一个个基基本本可可)1(如何判定最优解？)2(解解？变变换换到到另另一一个个基基本本可可行行如如何何从从一一个个基基本本可可行行解解)3()(1LP求求解解线线性性规规划划问问题题例例0,5242.34min432142132121xxxxxxxxxxtsxxZ解解：。系数矩阵系数矩阵 10120121A。和和非非基基变变量量为为和和则则基基变变量量为为令令

13、基基2143,1001xxxxB 2142132524xxxxxx代代入入目目标标函函数数得得21340 xxz单单纯纯形形算算法法分分析析.2 54,04321xxxx则则令令。目目标标函函数数值值。基基本本可可行行解解0)5,4,0,0(11 zxT是是否否为为最最优优解解？利利用用目目标标函函数数分分析析。21340 xxz小。则目标函数值就可以减取值可以增大为正数，的和的系数为负数，因此若和目标函数中非基变量2121xxxx 2142132524xxxxxx是是否否可可以以增增大大？不不变变，考考察察固固定定12xx 1413254xxxx 254001143xxxx251 x变为非基

14、变量。变为非基变量。变为基变量，变为基变量，。即。即时，时，且且4141025xxxx 421423212125212323xxxxxx 2142132524xxxxxx42210 xxz 2325,03142xxxx则则令令。目标函数值。基本可行解10)0,23,0,25(22zxT42210 xxz，则。固定增大的系数为负，考察能否因为422xxx 421423212125212323xxxxxx 212321252323xxxx12 x变变为为非非基基变变量量。变变为为基基变变量量，。即即时时，且且323201xxxx 4314323231231321xxxxxx43353211xxz

15、12,02143xxxx则则令令。目标函数值。基本可行解11)0,0,1,2(33zxT增大，所以最优解为所以目标函数值不能再的系数皆为正数，和其中因为目标函数4343,353211xxxxz。最优的目标函数值为，11*)0,0,1,2(*33zzxxT最最优优解解的的判判定定条条件件)1()(LPniiixcz1min nixbxaxaxabxaxaxabxaxaxatsimnmnmmnnnn,2,1,0.22112222212111212111 nmjjmjmmnmjjjxabxxabx11111设经过迭代后有设经过迭代后有为为非非基基变变量量。为为基基变变量量，则则nmmxxxx,11)

16、1(代代入入目目标标函函数数得得nmiiiminmjjijiixcxabcz111)(min nmjjjminmjjijmiiiixcxacbc1111)(nmjjjminmjjijmiiiixcxacbc1111)(minmjjijmiijiixaccbc111)(。则有。则有令令 miijijjmiiiaccbcz110,nmjjjxzz10 为为检检验验数数。称称),1(nmjj )2(是最优解。，则，有且对任意的的一个基本可行解。是对应于基若定理*01)0,0,*,*(*1xnjmBbbxjTm最优解。线性规划问题有无穷多，则，且存在，有如果对任意的的一个基本可行解。是对应于基设定理)

17、0(001)0,0,*,*(*1knjmBbbxkmjTm无界。则原线性规划问题的解，）式中（，且对任意的，如果存在的一个基本可行解。是对应于基设定理01,1)1(0)0,0,*,*(*,1kmikmTmamimnkBbbx基基变变换换)2(对对应应的的变变量量，即即若若可可选选取取最最大大的的入入基基变变量量：j 为入基变量。对应的也可任选为入基变量。则选取jjkkjjjxxx0,0|min）式计算）式计算则由（则由（设入基变量为设入基变量为离基变量：离基变量：1,kx0|min,kllkikiiabaab 为离基变量。为离基变量。选取选取lx单单纯纯形形表表和和单单纯纯形形算算法法.3)(

18、LPnmiiixzz10min nixbxaxaxbxaxaxbxaxaxtsimnmnmmmmnnmmnnmm,2,1,0.11,2211,221111,11形形式式：约约束束条条件件已已改改写写为为如如下下为为基基变变量量，且且其其），不不妨妨设设给给定定线线性性规规划划问问题题（mxxLP,1 011,221,2111,1000100010001zbaabaabaanmmmnmmnmnm 1x2xmx1 mxnxb单单纯纯形形表表：函函数数值值的的相相反反数数。可可行行解解对对应应的的目目标标列列的的元元素素表表示示当当前前基基本本、行行）第第（当当前前基基变变量量的的取取值值；）最最后

19、后一一列列的的元元素素对对应应（数数为为零零；行行，其其中中基基变变量量的的检检验验）最最后后一一行行称称为为检检验验数数（的的变变量量为为基基变变量量；作作为为基基矩矩阵阵，它它所所对对应应）包包含含一一个个单单位位子子矩矩阵阵（单单纯纯形形表表的的结结构构：114321 nm单单纯纯形形算算法法步步骤骤：建建立立初初始始单单纯纯形形表表。确确定定初初始始基基本本可可行行解解，）（1）。否则转（是最优解，算法结束；则当前的基本可行解就，数。如果检验各非基变量的检验）（3),1(02nmjj）。（界，算法结束；否则转则线性规划问题的解无，的系数列向量使得其对应的变量）如果存在（4003kkkP

20、x为入基变量。计算选取设kkjx,)0(min)4(lklikikiabaab 0|min）。为为离离基基变变量量。转转（选选取取5lx的的列列。其其它它元元素素为为，个个系系数数列列向向量量变变换换为为变变换换将将第第为为主主元元旋旋转转。即即利利用用行行）以以（015 lklkaka)(2LP求求解解线线性性规规划划问问题题例例0,82463.2min321321321321xxxxxxxxxtsxxxZ解：解：化化标标准准型型：0,82463.2min5432153214321321xxxxxxxxxxxxxtsxxxZ第第一一次次迭迭代代：000112810124601131初初始始单

21、单纯纯形形表表：1x2x3x4x5xb。基变量基变量54,xx。目目标标函函数数值值基基本本可可行行解解0,)8,6,0,0,0(11 zxT031、不不是是最最优优解解。1x为为入入基基变变量量，则则取取3x。818 为离基变量。为离基变量。取取5x为为主主元元进进行行旋旋转转。以以23a第第二二次次迭迭代代：单单纯纯形形表表：81001281012414110151x2x3x4x5xb。基变量基变量43,xx。目标函数值基本可行解8,)0,14,8,0,0(22zxT02不不是是最最优优解解。2x为为入入基基变变量量，则则取取2x。14114 为离基变量。为离基变量。取取4x为为主主元元进

22、进行行旋旋转转。以以12a第第三三次次迭迭代代：单单纯纯形形表表：22210073632101414110151x2x3x4x5xb。基变量基变量32,xx。目标函数值基本可行解22,)0,0,36,14,0(33zxT。5,1,0ii。函数值为即为最优解。最优目标2233zx初初始始基基本本可可行行解解的的计计算算.4法法大大M)(LPniiixcz1min nixbxaxaxabxaxaxabxaxaxatsimnmnmmnnnn,2,1,0.22112222212111212111规划问题规划问题个人工变量，得新线性个人工变量，得新线性对每个约束条件增加一对每个约束条件增加一)(LPni

23、mnniiMxMxxcz11min mnixbxxaxaxabxxaxaxabxxaxaxatsimmnnmnmmnnnnnn,2,1,0.2211222222121111212111为为充充分分大大的的正正数数。其其中中 M为为初初始始的的基基变变量量。）问问题题中中可可以以取取则则在在（mnnxxLP ,1的的最最优优解解。）问问题题原原（变变量量，则则此此最最优优解解也也是是基基变变量量中中必必不不包包含含人人工工最最优优的的基基本本可可行行解解的的）问问题题存存在在最最优优解解，则则结结论论：如如果果（LPLP)(3LP求求解解线线性性规规划划问问题题例例0,24422.232max3

24、2132321321xxxxxxxxtsxxxZ解：解：0,24422.232min43214323214321xxxxxxxxxxtsMxxxxZ）（LP第第一一次次迭迭代代：初初始始单单纯纯形形表表：1x2x3x4xb。基变量基变量41,xx。目标函数值基本可行解MzxT28,)2,0,0,4(1102322114040221M1x2x3x4xbMMM2804440211404022102不不是是最最优优解解。1x为为入入基基变变量量，则则取取2x。2142,24min 为离基变量。为离基变量。取取4x为为主主元元进进行行旋旋转转。以以22a第第二二次次迭迭代代：1x2x3x4xb6150

25、0214141103212501M。基变量基变量21,xx。目标函数值基本可行解6,)0,0,21,3(22zxT。4,1,0ii。函数值为即为最优解。最优目标622zx灵敏度分析一.产品产品资源资源乙甲千元单位利润ABC资源总量资源总量3634315543045例题例题 设某厂在资源甲乙的限制下，考虑制定能使总设某厂在资源甲乙的限制下，考虑制定能使总利润最大的产品利润最大的产品A,B,C的生产计划，相关数据如下：的生产计划，相关数据如下：解：解：确确定定目目标标函函数数.2确确定定决决策策变变量量.1。、的的产产量量分分别别为为、设设321xxxCBA，则则设设总总利利润润为为 S32143

26、xxxS确确定定约约束束条条件件.345536321xxx3,2,1,030543321ixxxxi数数学学模模型型.43217x5x4xSmax3,2,1,03054345536.321321ixxxxxxxtsi将其化为标准型如下：32143minxxx0,3054345536.5432153214321xxxxxxxxxxxxxts第第一一次次迭迭代代：00041330105434501536初初始始单单纯纯形形表表：1x2x3x4x5xb。基变量基变量54,xx。目标函数值基本可行解0,)30,45,0,0,0(11zxT不不是是最最优优解解。1x为入基变量，则取1x645330,64

27、5min为离基变量。取4x第二次迭代：2452123212152125252156165210010011x2x3x4x5xb。基变量15,xx。目标函数值基本可行解24522152152,),0,0,0,(zxT不是最优解。2x为入基变量，则取3x33,9min为离基变量。取5x第三次迭代：270203110501535152513131311x2x3x4x5xb。基变量13,xx。目标函数值基本可行解27,)0,0,3,0,5(33zxT是最优解。3x原问题的最大利润为原问题的最大利润为27进一步考虑如下问题：进一步考虑如下问题：1.两种资源中哪一种是制约进一步提高利润的因素？两种资源中哪

28、一种是制约进一步提高利润的因素？将最优解代人两个约束，它们都已经是等式。因此都将最优解代人两个约束，它们都已经是等式。因此都是制约利润再提高的因素。是制约利润再提高的因素。2.若在市场上能比正常价高若在市场上能比正常价高0.5千元买到甲乙，为提高净千元买到甲乙，为提高净利润是否买？利润是否买？最后的目标函数为最后的目标函数为 max -2x2-0.2x4-0.6x5资源甲的影子价格为资源甲的影子价格为0.2，资源乙的影子价格为，资源乙的影子价格为0.6.所以，所以，够买甲不合算，购买乙合算。够买甲不合算，购买乙合算。3.B的单位利润要提高多少，才能仍在追求最大利润的前的单位利润要提高多少，才能

29、仍在追求最大利润的前提下安排提下安排B的生产？的生产？假定假定B的单位利润提高的单位利润提高C千元。由前面的单纯形表，千元。由前面的单纯形表，第三次迭代：27020311050153515251313131C1x2x3x4x5xb。基变量13,xx。目标函数值基本可行解27,)0,0,3,0,5(33zxT是最优解。3x若若C2.f=-2 1-1;a=1 3-1;4-2 1;-1 0 0;0-1 0;0 0-1;b=6 8 0 0 0 a=1 3 -1 4 -2 1 -1 0 0 0 -1 0 0 0 -1b=6 8 0 0 0f=2 2 -1x=linprog(f,a,b)Optimization terminated successfully.x=0 13.8879 35.7757 t=f*xt=-8.0000