最优化方法-线性规划

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

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

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

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

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

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

7、有最最优优解解 有有无无穷穷多多最最优优解解在在顶顶点点取取到到唯唯一一最最优优解解 可可行行域域为为空空集集解解无无界界质质线线性性规规划划解解的的概概念念和和性性四四.线线性性规规划划解解的的概概念念. 1)(LPxczT min 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(, ),(21mkxPmkPPPPBkkkmiiiiii 为为基基变变量量。为为基基，则则取取列列向向量量线线性

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

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

11、可行行解解mnC 基本解数量基本解数量定定存存在在最最优优解解？是是否否在在基基本本可可行行解解中中一一退化退化：是非退化的。是非退化的。非退化的，称非退化的，称的所有基本解都是的所有基本解都是。如果。如果否则称非退化的基本解否则称非退化的基本解解；解；的基本解为退化的基本的基本解为退化的基本称非零分量个数小于称非零分量个数小于)()(LPLPm线线性性规规划划解解的的性性质质. 2的的顶顶点点。可可行行域域是是充充分分必必要要条条件件是是是是基基本本可可行行解解的的的的解解线线性性规规划划问问题题定定理理DxxLP)(4线性无关。线性无关。的列向量的列向量对应的对应的的非零分量的非零分量解的

12、充要条件是解的充要条件是是基本是基本的一个解，则的一个解，则是是设设定理定理rriiiiiiTnpppAxxxxxbAxxxxx,),(1212121 可可行行解解。基基本本如如果果有有可可行行解解，则则必必有有线线性性规规划划问问题题定定理理)(2LP的的基基本本可可行行解解。最最优优如如果果有有最最优优解解，则则必必有有线线性性规规划划问问题题定定理理)(3LP单单纯纯形形算算法法五五.判判断断出出不不存存在在最最优优解解。直直到到找找到到最最优优解解，或或者者基基本本可可行行解解，则则转转换换到到另另一一个个更更好好的的是是则则算算法法结结束束。不不是是，。，判判断断其其是是否否为为最最

13、优优解解从从一一个个基基本本可可行行解解开开始始算算法法思思路路：. 1问问题题：行行解解？如如何何得得到到第第一一个个基基本本可可)1(最最优优解解的的判判定定法法则则？)2(解解？变变换换到到另另一一个个基基本本可可行行如如何何从从一一个个基基本本可可行行解解)3()(1LP求求解解线线性性规规划划问问题题例例 0,5242.34min432142132121xxxxxxxxxxtsxxZ解解：。系数矩阵系数矩阵 10120121A。和和非非基基变变量量为为和和则则基基变变量量为为令令基基2143,1001xxxxB 2142132524xxxxxx代代入入目目标标函函数数得得21340

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

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

16、xxxxxx43353211xxz 12,02143xxxx则则令令。目目标标函函数数值值。基基本本可可行行解解11)0,0,1,2(33 zxT减减小小，所所以以最最优优解解为为所所以以目目标标函函数数值值不不能能再再的的系系数数皆皆为为正正数数，和和其其中中因因为为目目标标函函数数4343,353211xxxxz 。最最优优的的目目标标函函数数值值为为，11*)0,0,1,2(*33 zzxxT最最优优性性条条件件)1()(LPxczT min0,. xbAxtsNBx非非基基变变量量指指标标集集基基变变量量指指标标集集,:,:1bAbxBB . 0: Nx.:1NBNAAA ,NNBxA

17、bx NTNNNTBTBxcxAcbcz min. 0, 0 NBxxs.ts.t. . bcTBNNTBTNxAcc)( ,1AAccBTBTT 定义定义称为基本可行解 的检验数。x是是最最优优解解。，则则数数若若相相应应的的检检验验的的一一个个基基本本可可行行解解对对应应于于基基若若定定理理*0,*xBx 基基变变换换)2(对对应应的的变变量量，即即若若可可选选取取最最小小的的入入基基变变量量：j 为入基变量。为入基变量。对应的对应的也可任选也可任选为入基变量。为入基变量。则选取则选取jjeejjjxx0,0|min 注意到：注意到：0)2(;, 0)1(1 bANeBe eeBBBxpA

18、bAx11 考虑考虑，若若0)(1 eBpAa ，最最优优值值为为能能任任意意增增加加，问问题题无无界界ex exb 否则，否则，)( 0)( :)()(min111eBieBiBpApAbA 0, oxBo将将会会有有达达到到最最小小的的下下标标使使 优优解解。性性规规划划问问题题有有无无穷穷多多最最，则则线线，且且存存在在，有有任任意意的的果果对对的的一一个个基基本本可可行行解解。如如是是对对应应于于基基设设定定理理)(00*NkNjBxkj 。则则原原线线性性规规划划问问题题无无界界，且且，使使得得果果存存在在的的一一个个基基本本可可行行解解。如如是是对对应应于于基基设设定定理理00*1

19、 jBjpANjBx 单单纯纯形形表表和和单单纯纯形形算算法法. 3,11NNBBBxAAbAx NNBTBTNBTBxAAccbAcz)(min11 . 0, 0 NBxxs.ts.t. .可以用如下表格表示：可以用如下表格表示：AAccBTBT1 bAcBT1 BAAB1 bAB1 单单纯纯形形算算法法步步骤骤：建建立立初初始始单单纯纯形形表表。确确定定初初始始基基本本可可行行解解，）（1）。，算算法法结结束束；否否则则转转（基基本本可可行行解解就就是是最最优优解解则则当当前前的的，数数。如如果果检检验验各各非非基基变变量量的的检检验验）（3)(02Njj ）。（界界，算算法法结结束束；否

20、否则则转转则则线线性性规规划划问问题题的的解解无无，的的系系数数列列向向量量使使得得其其对对应应的的变变量量）如如果果存存在在（4003 kkkPx 为为入入基基变变量量。计计算算选选取取设设eejx,)0min()4( oeoieieiabaab 0|min ）。为为出出基基变变量量。转转（选选取取5ex的的列列。其其它它元元素素为为，个个系系数数列列向向量量变变换换为为变变换换将将第第为为主主元元旋旋转转。即即利利用用行行）以以（015 oeoeaea)(2LP求求解解线线性性规规划划问问题题例例 0,82463.2min321321321321xxxxxxxxxtsxxxZ解：解：化化标

21、标准准型型： 0,82463.2max5432153214321321xxxxxxxxxxxxxtsxxxZ初初始始基基本本可可行行解解的的计计算算. 4人工变量法人工变量法)(a)(LP niiixcz1min0. xbAxts规划问题规划问题个人工变量，得新线性个人工变量，得新线性对每个约束条件增加一对每个约束条件增加一) (LPuewT min0,0. uxbuAxts)(AxbeuewTT ：目目标标函函数数是是不不可可行行误误差差 niiixcz1min0. xbAxts)(LP) (LPuewT min0,0. uxbuAxts则则）有最优解（有最优解（若若,) (*uxLP0,)

22、(* wuxLP）充充要要条条件件有有可可行行解解（不含基变量不含基变量0, 0)1(* uw但但有有人人工工变变量量是是基基变变量量,0)2(* w.Bin 即即有有njaaji, 1,0)(, inxi 因因此此也也去去掉掉了了人人工工变变量量个个约约束束冗冗余余，可可去去掉掉，则则第第0)(, jiajb使使得得变变成成出出基基变变量量。而而为为中中心心做做转转轴轴运运算算，从从则则可可以以injixa , 0,312.2min212212121xxxxxxxtsxxZ)(3LP求求解解线线性性规规划划问问题题例例)(. 4两两阶阶段段法法初初始始基基本本可可行行解解的的计计算算法法大大

23、Mb)()(LP niiixcz1min nixbxaxaxabxaxaxabxaxaxatsimnmnmmnnnn,2,1,0.22112222212111212111规划问题规划问题个人工变量，得新线性个人工变量，得新线性对每个约束条件增加一对每个约束条件增加一) (LP nimiiMuMuxcz11min mnixbuxaxaxabuxaxaxabuxaxaxatsimmnmnmmnnnn,2,1,0.2211222222121111212111 niiixcz1min0. xbAxts)(LP) (LPuMexcwTT min0,0. uxbuAxts则则）有最优解（有最优解（若若,)

24、 (*uxLP最优解最优解是是则则最优解最优解是是)(,)()0 ,)(1(*LPxPLx 无可行解无可行解则则最优解且最优解且是是)(, 0)(),)(2(*LPuPLux 则则无有限最优解无有限最优解若若,) (LP无有限最优解无有限最优解则则且且若若)(, 0, 00)1(*LPupkk 无可行解无可行解则则且且若若)(, 0, 00)2(*LPupkk )(4LP求求解解线线性性规规划划问问题题例例 0,24422.232min32132321321xxxxxxxxtsxxxZ改改进进单单纯纯形形算算法法. 5减少算法的计算量减少算法的计算量主要目的主要目的:.,eo进进基基变变量量为为若若选选定定出出基基变变量量为为.)1()1(,的的表表上上进进行行其其计计算算量量是是在在一一个个变变换换为为中中心心做做则则相相当当于于以以 nmJordanGaussaoeAAccBTBT1 bAcBT1 BAAB1 bAB1 回顾有初始基本可行解的单纯形算法回顾有初始基本可行解的单纯形算法, ,对于标准对于标准: :单纯形表为单纯形表为: :N,j , 数数计计算算过过程程需需要要计计算算检检验验 、系数矩阵系数矩阵AAAccBTBT1 bAcBT1 BAAB1 bAB1 、基本解基本解Bx