最优化方法-线性规划

线性规划模型.1标准型.2解的概念和性质.4单纯形算法.5图解法.3线性规划模型一.生产计划问题例1利润最大？生产计划，才能使所获安排千元。问：该厂应如何、、单位产品的利润为、、同，如下表。耗费的加工时间各不相产品所需材料的数量和三种产品，它们的单位、、生产某工厂利用某种原材料754CBACBA产品资源原材料工时ABC资源总量215.1232100150解：确定目标函数.2确定决策变量.1。、、的产量分别为、、设321xxxCBA，则设总利润为S321754xxxS确定约束条件.310035.12321xxx3,2,1,015022321ixxxxi数学模型.4321754minxxxS3,2,1,01502210035.12..321321ixxxxxxxtsi线性规划模型：一组决策变量；)1(一个线性目标函数；)2(一组线性的约束条件。)3(的一般形式：线性规划模型)(LPniiixc1(max)minnixbxaxaxabxaxaxabxaxaxatsimnmnmmnnnn,,2,1,0),(),(),(),(..22112222212111212111标准型二.标准型.1niiixc1minnixbxaxaxabxaxaxabxaxaxatsimnmnmmnnnn,,2,1,0..22112222212111212111标准型可记为。则线性规划记nmijTnTmTnaAxxxxbbbbcccc)(,),,,(,0),,,(,),,,(212121xcTmin0..xbAxts化标准型.2目标函数：)1(xcTmax:目标函数原问题xcTmin约束条件：)2(ininiibxaxaxai2211)(：原问题条件02211iniinniniixbxxaxaxa称为松弛变量。inxininiibxaxaxaii2211)(：原问题条件02211iniinniniixbxxaxaxa称为剩余变量。inx。无非负约束，则令：原问题0,)(iiiiiivuvuxxiii为标准型。将下述线性规划模型化例14321332maxxxxx无约束243143214214321,0,,6347223332..xxxxxxxxxxxxxxxts解：则令,222vux432213332minxxvux0,,,,,,634472223332..22754317432214221543221vuxxxxxxxxvuxxvuxxxxvuxts图解法三.求解线性规划例20,5242..34max21212121xxxxxxtsxxz解：。画出可行解的范围)1(1x2xoABC求极值点。利用等值线平移的方法)2(表示一族等值平行线。为参数，则方程以zxxz21344221xx5221xx。顶点极大值点为B。中的目标函数改为将例例21223xxz1x2xoABC4221xx5221xx解：。分析同例2。等值线：zxx212任一点。上的极大值点为线段AB1x2xoABC221xx221xx解：。分析同例2。等值线：zxx2134求解线性规划例40,22..34max21212121xxxxxxtsxxz不存在最大值。原问题无界。结果：线性规划问题的解无最优解有最优解有无穷多最优解在顶点取到唯一最优解可行域为空集解无界质线性规划解的概念和性四.线性规划解的概念.1)(LPxczTmin0..xbAxts)1()2()3(的可行解。称为）式的解）、（满足（可行解：)(),,,(3221LPxxxxTn。可行域：}0,|{xbAxxD定理是凸集。线性规划问题的可行域D证明：。任取10,,21Dxx2121)1())1((AxAxxxAbbb)1(是凸集。。即所以DDxx21)1(的一个顶点。为则称，使。及，。如果不存在为凸集，设顶点：SxxxxSxxSxS2121)1(10x1x2x一个基。问题或的为退化子阵，则称阶的非中为若。秩为的系数矩阵为设基))((,:LPABmmABmnmA非基变量。的变量称为为基变量，不是基变量对应的变量为基向量，称称设基),,1(),,1(,),,,(21mkxPmkPPPPBkkkmiiiiii为基变量。为基，则取列向量线性无关，则可的前不妨设，已知mmnmxxPPPBmAmAr,,),,,()(121bAx因为即bxPxPxPxPnnmmmm111所以nnmmmmxPxPbxPxP111解得令非基变量,01nmxxbBxxTm11),,(的基本解。为对应于基称解变量的取值得基，令非基变量取零，求取定线性规划问题的基基本解：BbBbBBT)0,(,11解。的基本解称为基本可行条件基本可行解：满足非负问题给定例)(LP0,,,2222842..22min4321432143214321xxxxxxxxxxxxtsxxxxz和一个基本可行解。求此问题的一个基本解解：。系数矩阵12224121A得，则令非基变量取,0222143xxB222822121xxxx3731021xx可行解。是基本解，但不是基本Tx)0,0,37,310(1得，则令非基变量取,0124132xxB22844141xxxx91491641xx是基本可行解。Tx)914,0,0,916(2可行解基本解基本可行解mnC基本解数量定存在最优解？是否在基本可行解中一退化：是非退化的。非退化的，称的所有基本解都是。如果否则称非退化的基本解解；的基本解为退化的基本称非零分量个数小于)()(LPLPm线性规划解的性质.2的顶点。可行域是充分必要条件是是基本可行解的的解线性规划问题定理DxxLP)(4线性无关。的列向量对应的的非零分量解的充要条件是是基本的一个解，则是设定理rriiiiiiTnpppAxxxxxbAxxxxx,,,,,,),,,(1212121可行解。基本如果有可行解，则必有线性规划问题定理)(2LP的基本可行解。最优如果有最优解，则必有线性规划问题定理)(3LP单纯形算法五.判断出不存在最优解。直到找到最优解，或者基本可行解，则转换到另一个更好的是则算法结束。不是，。，判断其是否为最优解从一个基本可行解开始算法思路：.1问题：行解？如何得到第一个基本可)1(最优解的判定法则？)2(解？变换到另一个基本可行如何从一个基本可行解)3()(1LP求解线性规划问题例0,,,5242..34min432142132121xxxxxxxxxxtsxxZ解：。系数矩阵10120121A。和非基变量为和则基变量为令基2143,,1001xxxxB2142132524xxxxxx代入目标函数得21340xxz单纯形算法分析.254,04321xxxx则令。目标函数值。基本可行解0)5,4,0,0(11zxT是否为最优解？利用目标函数分析。21340xxz小。则目标函数值就可以减取值可以增大为正数，的和的系数为负数，因此若和目标函数中非基变量2121xxxx2142132524xxxxxx是否可以增大？不变，考察固定12xx1413254xxxx254001143xxxx251x变为非基变量。变为基变量，。即时，且4141025xxxx421423212125212323xxxxxx2142132524xxxxxx42210xxz2325,03142xxxx则令。目标函数值。基本可行解10)0,23,0,25(22zxT42210xxz，则。固定增大的系数为负，考察能否因为422xxx421423212125212323xxxxxx212321252323xxxx12x变为非基变量。变为基变量，。即时，且323201xxxx4314323231231321xxxxxx43353211xxz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,NNBxAbxNTNNNTBTBxcxAcbczmin.0,0NBxxs.t.bcTBNNTBTNxAcc)(,1AAccBTBTT定义称为基本可行解的检验数。x是最优解。，则数若相应的检验的一个基本可行解对应于基若定理*0,*xBx基变换)2(对应的变量，即若可选取最小的入基变量：j为入基变量。对应的也可任选为入基变量。则选取jjeejjjxx0,}0|{min注意到：0)2(;,0)1(1bANeBeeeBBBxpAbAx11考虑，若0)(1eBpAa，最优值为－能任意增加，问题无界exexb否则，)(0)(:)()(min111eBieBiBpApAbA0,oxBo将会有达到最小的下标使优解。性规划问题有无穷多最，则线，且存在，有任意的果对的一个基本可行解。如是对应于基设定理)(00*NkNjBxkj。则原线性规划问题无界，且，使得果存在的一个基本可行解。如是对应于基设定理00*1jBjpANjBx单纯形表和单纯形算法.3,11NNBBBxAAbAxNNBTBTNBTBxAAccbAcz)(min11.0,0NBxxs.t.可以用如下表格表示：AAccBTBT1bAcBT1BAAB1bAB1单纯形算法步骤：建立初始单纯形表。确定初始基本可行解，）（1）。，算法结束；否则转（基本可行解就是最优解则当前的，数。如果检验各非基变量的检验）（3)(02Njj）。（界，算法结束；否则转则线性规划问题的解无，的系数列向量使得其对应的变量）如果存在（4003kkkPx为入基变量。计算选取设eejx,)0min()4(oeoieieiabaab}0|{min）。为出基变量。转（选取5ex的列。其它元素为，个系数列向量变换为变换将第为主元旋转。即利用行）以（015oeoeaea)(2LP求解线性规划问题例0,,82463..2min321321321321xxxxxxxxxtsxxxZ解：化标准型：0,,,,82463..2max5432153214321321xxx