线性规划单纯形法运筹学学习教案

1、会计学1线性规划线性规划(xin xn u hu)单纯形法运单纯形法运筹学筹学第一页，共53页。3、图解法的基本(jbn)步骤：的图形上做出可行域、在直角坐标系Soxx211（一般(ybn)是一个凸多边形）,2k给定的常数、令目标函数值取一个kxcxcZ2211做等值线,max3由小变大问题，令目标函数值、对k即让等值线向上平移，点边界线上的点均是最优的一条边界重合，此时若与点，则该点就是所求的最优的一个顶点），是最后交于一个点（一般若它与可行域SSS，即得最优解立求解，边界线所代表的方程联、将最优点所在的两条*4X*CXZX值带入目标函数，得最优把最优解注意(zh y)：若是求目标函数的最小

2、值，目标函数直线向下移动第2页/共53页第二页，共53页。4、线性规划(xin xn u hu)解的结论：1、若（LP）问题有可行(kxng)解，则可行(kxng)域是一个凸多边形（或凸多面体）。它可能是有界的；也可能是无界的。2、若（LP）问题有最优解，则最优解可能是唯一的；也可能 是无穷多个(du )。如果是唯一的，这个解一定在该凸多边形的某 个顶点上；如果是无穷多个(du )，则这些最优解一定充满凸多边 形的一条边界（包括此边界的两个顶点）总之，若（LP）问题有最优解，则最优解一定可以在凸多边形的某个顶点达到3、若（LP）问题有可行解，但没有有限最优解，此时凸多边形 是无界的（反之不成立

3、）4、若（LP）问题没有可行解，则该问题没有最优解第3页/共53页第三页，共53页。定义1.3 在（LP）问题中，A的任意一个mm阶 的非奇异子方阵(fn zhn)B（即|B|0）称为 （LP）问题的一个基0,0.max)(bXbAXtsCXzLP问题对设r(A)=m0基本(jbn)可行解非退化基本可行解退化基本可行解退化基本可行解：基本可行解中，存在取0值的基变量非退化基本可行解：基本可行解中，基变量的取值均0对应的基称为退化基对应的基称为非退化基，即001bBX01bB线性规划问题非退化的线性规划问题退化的线性规划问题：存在退化基：所有基均非退化mBxxxX21得, bAX 即对01nmN

4、xxX令m第7页/共53页第七页，共53页。0,0.max)(bXbAXtsCXzLP问题对若有可行(kxng)解，则可行(kxng)域是一个凸多边形若（LP）问题有最优解，则最优解一定(ydng)可以在凸多边形的某个顶点达到基本可行解与可行域的顶点(dngdin)的关系?第8页/共53页第八页，共53页。0,2162.7max211212121xxxxxxxtsxxz对线性规划问题例01x2x.6221xx21x121 xx结论(jiln):1.可行(kxng)域为一个凸集2.凸集上有5个顶点(dngdin)7721 xx3.最优解在顶点产生0,2162.7max54321514213212

5、1xxxxxxxxxxxxxtsxxz其标准型为100010101100121A系数矩阵基的个数35C=10基的个数=9基本可行解的个数基本解的个数=基的个数最优解第9页/共53页第九页，共53页。0,2162.7max211212121xxxxxxxtsxxz对线性规划问题例0,2162.7max543215142132121xxxxxxxxxxxxxtsxxz其标准型为100010101100121A系数矩阵5431PPPB 基211PPN 非基5431xxxXB基变量211xxXN非基变量0211xxXN令非基变量216543xxx，得216001X基本解基本可行解01x2x.6221x

6、x21x121 xx.凸多边形的顶点(dngdin)最优解第10页/共53页第十页，共53页。0,2162.7max211212121xxxxxxxtsxxz对线性规划问题例0,2162.7max543215142132121xxxxxxxxxxxxxtsxxz其标准型为100010101100121A系数矩阵3212PPPB 基542PPN 非基3212xxxXB基变量542xxXN非基变量0542xxXN令非基变量212321xxx，得002122X基本解基本可行解01x2x.6221xx21x.121 xx第11页/共53页第十一页，共53页。0,2162.7max211212121xx

7、xxxxxtsxxz对线性规划问题例0,2162.7max543215142132121xxxxxxxxxxxxxtsxxz其标准型为100010101100121A系数矩阵01x2x.6221xx21x.121 xx5413PPPB 基5413xxxXB基变量323PPN非基323xxXN非基变量0323xxXN令非基变量450063X得一基本解该基本(jbn)解不是基本(jbn)可行解不在可行(kxng)域中第12页/共53页第十二页，共53页。4214PPPB 基534PPN 非基4214xxxXB基变量534xxXN非基变量0534xxXN令非基变量122421xxx，得010224X

8、基本解基本可行解0,2162.7max211212121xxxxxxxtsxxz对线性规划问题例0,2162.7max543215142132121xxxxxxxxxxxxxtsxxz其标准型为100010101100121A系数矩阵01x2x.6221xx21x.121 xx.第13页/共53页第十三页，共53页。5425PPPB 基315PPN 非基5425xxxXB基变量315xxXN非基变量0315xxXN令非基变量243542xxx，得240305X基本解基本可行解0,2162.7max211212121xxxxxxxtsxxz对线性规划问题例0,2162.7max543215142

9、132121xxxxxxxxxxxxxtsxxz其标准型为100010101100121A系数矩阵01x2x.6221xx21x.121 xx.第14页/共53页第十四页，共53页。5316PPPB 基426PPN 非基5316xxxXB基变量426xxXN非基变量0426xxXN令非基变量151531xxx，得105016X基本解基本可行解0,2162.7max211212121xxxxxxxtsxxz对线性规划问题例0,2162.7max543215142132121xxxxxxxxxxxxxtsxxz其标准型为100010101100121A系数矩阵01x2x.6221xx21x.121

10、 xx.第15页/共53页第十五页，共53页。0,2162.7max211212121xxxxxxxtsxxz对线性规划问题例0,2162.7max543215142132121xxxxxxxxxxxxxtsxxz其标准型为100010101100121A系数矩阵01x2x.6221xx21x.121 xx. 基 基本解5431PPPB 216001X5413PPPB 450063X4214PPPB 010224X240305X5425PPPB 105016X5316PPPB 3212PPPB 002122X5217PPPB 3 / 2003 / 53 / 87X4318PPPB 014028

11、X208109X5329PPPB 结论(jiln):顶点(dngdin)基本(jbn)可行解第16页/共53页第十六页，共53页。总结(zngji):1.若（LP）问题有可行(kxng)解，则可行(kxng)域是一个凸多边形2.若（LP）问题(wnt)有最优解，则最优解一定可以在凸多边 形的某个顶点达到4.基本可行解的个数是有限的3.顶点与基本可行解是一一对应的若（LP）问题有最优解，则最优解一定可以在某个 基本可行解达到0,0.max)(bXbAXtsCXzLP 问题对找最优解可从一个基本可行解入手，通过某种方法，调整基变量，转到另一个基本可行解，并使目标函数值不断增大，通过有限次的迭代就能

12、找到最优解单纯形法第17页/共53页第十七页，共53页。第18页/共53页第十八页，共53页。0.maxXbAXtsCXz对问题单纯形法的基本思路：1、找出一个可行基，并得到(d do)一个基本可行解2、检验该基本可行解是否(sh fu)是最优解，即目标函数值 是否(sh fu)最大，或看看是否(sh fu)存在目标函数值比它大的 基本可行解3、换一个目标(mbio)函数值比他大的基本可行解4、重复以上步骤，直至找不到更好的基本可行解第19页/共53页第十九页，共53页。0,4252323632.34max21212212121xxxxxxxxxtsxxz求解线性规划问题例0,42520323

13、632.34max65432162152142132121xxxxxxxxxxxxxxxxxxtsxxz其标准型为第20页/共53页第二十页，共53页。100012010020001023000132A第一步：寻找第一个基本(jbn)可行解（初始基本(jbn)可行解）654321PPPPPP4)(,6543ArPPPP线性无关，且显然，65430PPPPB 初始基6543,xxxx基变量21,xx非基变量0,42520323632.34max65432162152142132121xxxxxxxxxxxxxxxxxxtsxxz其标准型为第21页/共53页第二十一页，共53页。得基本解，令021

14、 xx4536000XX0为基本(jbn)可行解对应目标(mbio)函数值00Z是否为最优解二、判断0X就还没取到最优解量系数中有一个只要目标函数的非基变, 0ic作为基变量取由于121, 0 xcc作为入基变量则取为非基变量且入基变量：若00,0|max) 1 (ijjjixxccc三、换基迭代(di di)0,42520323632.34max65432162152142132121xxxxxxxxxxxxxxxxxxtsxxz65430PPPPB初始基6543,xxxx基变量对应的解为基本可行解尽可能的大，同时又使使既能中哪个作为非基变量，原来的基变量问题：16543xxxxx第22页/

15、共53页第二十二页，共53页。仍为非基变量2x0, 3, 023111111xabxa才能使必须由于0, 0, 034121xxa就有只需由于0, 0531xa有由于0, 2, 026414141xabxa才能使必须由于414110|minabaabiii为出基变量取第四个方程的基变量6x0,42520323632.34max65432162152142132121xxxxxxxxxxxxxxxxxxtsxxz, 201x要得到基本可行解，0,261xx时且当取做非基变量(binling)4250336261514131xxxxxxxx解为基本可行解的大，同时又使对应的尽可能变量，既能使中哪个

16、作为非基，原来的基变量问题：16543xxxxx62,xx ，非基变量5431,PPPP得新的可行基在第四个方程02x令第23页/共53页第二十三页，共53页。0,42520323632.34max65432162152142132121xxxxxxxxxxxxxxxxxxtsxxz26,xx非基变量062 xx令1X得基本可行解1543,xxxx基变量1Z目标函数值4100012501002030010236000132221000211501002030010236000132221000211501002092301027021001202212152932722.62152642632

17、xxxxxxxxxxxts0592021X82134xxzZxx2134是否为最优解四、判断1XZ0000348200010z8262Zxx6228xxZ还没取到最优解, 02c作为入基变量取2xZ000034Zxxxxx5432100034第24页/共53页第二十四页，共53页。0,42520323632.34max65432162152142132121xxxxxxxxxxxxxxxxxxtsxxz2212152932722.62152642632xxxxxxxxxxxts6228xxZ26,xx非基变量062 xx令1X得基本可行解1543,xxxx基变量0592021X不是最优解12,

18、 0 Xc 作为入基变量取2x五、循环(xnhun)迭代出基变量(binling)的确定：为入基变量若0jx000000|minjiiijijiabaab出基变量个方程对应的基变量为则第0i1211ab12275. 25 . 392222ab5 . 2253233ab45 . 024244ab作为出基变量取3x5421,xxxx得新的基变量非基变量，即63,xx第25页/共53页第二十五页，共53页。2212152932722.62152642632xxxxxxxxxxxts6228xxZ36,xx非基变量22100021150100209301027021001208200010z22100

19、02115010020930102701210021108200010z23430041013110100211419014700121002110923002100z23434132114194712121.631653643632xxxxxxxxxxxxts6323219xxZ063 xx令非基变量2X得基本可行解92Z目标函数值1.5105.530最优解第26页/共53页第二十六页，共53页。100012010020001023000132A654321PPPPPP0,4252323632.34max21212212121xxxxxxxxxtsxxz求解线性规划问题0,425203236

20、32.34max65432162152142132121xxxxxxxxxxxxxxxxxxtsxxz其标准型为第一步：寻找(xnzho)初始基本可行解65430PPPPB 初始基6543,xxxx基变量21,xx非基变量，得一基本可行解令021 xx4536000X00Z是否为最优解第二步：判断0X不是最优解基变量的系数标准：若目标函数中非, 0ic第三步：换基迭代(di di)确定入基变量：) 1 (作为入基变量则取0ix,0|max0jjiccc若为入基变量取1,x（2）确定(qudng)出基变量：000000|minjiiijijiabaab为入基变量若0jx出基变量个方程对应的基变量

21、为第0i第27页/共53页第二十七页，共53页。确定入基变量：) 1 (作为基变量取1x（2）确定(qudng)出基变量：为入基变量若0jx000000|minjiiijijiabaab求出基变量个方程对应的基变量为第0i三、换基迭代(di di)242426min，由在第4个方程(fngchng)为出基变量6x为非基变量，即62,xx是否为最优解四、判断1X0,42520323632.34max65432162152142132121xxxxxxxxxxxxxxxxxxt sxxz2212152632722.62152642632xxxxxxxxxxxts6228xxZ062 xx令0592

22、021X得基本可行解81Z目标函数值还没取到最优解, 02c作为入基变量取2x五、循环迭代：11211ab75. 22222ab5 . 23233ab44244ab1mini作为出基变量取3x为非基变量，即63xx第28页/共53页第二十八页，共53页。2212152632722.62152642632xxxxxxxxxxxts6228xxZ为非基变量，取63xx234341321154712121.631653643632xxxxxxxxxxxxts6323219xxZ063 xx令非基变量035 . 5015 . 12X得基本可行解92Z目标函数值是否为最优解判断2X, 0, 063cc由

23、于为最优解所以2X9,2Z最优值第29页/共53页第二十九页，共53页。单纯形法的基本(jbn)思想：（1）入基变量(binling)：设ck=maxci | ci 0,取xk为入基变量(binling) 000000|minjiiijijiabaab为入基变量若0jx出基变量个方程对应的基变量为第0i得到(d do)新的非基变量目标函数表示成新非基变量的函数，4、把约束方程化为每个方程只含一个新的基变量令非基变量取零的一新的基本可行解X（2）出基变量：1、找到一个基本可行解X此时的约束方程每个方程只含一个基变量目标函数必须表示成非基变量的函数2、判断X是否为最优解：若目标函数中有非基变量的系

24、数ci0,则X不是最优解。3、换基迭代第30页/共53页第三十页，共53页。0,42520323632.34max65432162152142132121xxxxxxxxxxxxxxxxxxtsxxz对X1X2X3X4X5X6常数(chngsh)项2 3 1 0 0 0 6-3 2 0 1 0 0 30 2 0 0 1 0 52 1 0 0 0 1 46543PPPP6543xxxx基变量(binling)4 3 0 0 0 0 z4536000X初始基本可行解单纯形表326224主元素(yun s)b1543xxxx1 0.5 0 0 0 0.5 20 2 1 0 0 -1 20 3.5 0

25、 1 0 1.5 90 2 0 0 1 0 50 1 0 0 0 -2 z-80592022X得基本可行解12257. 25 . 395 . 22545 . 02检验行第31页/共53页第三十一页，共53页。b1543xxxx1 0.5 0 0 0 0.5 20 2 1 0 0 -1 20 3.5 0 1 0 1.5 90 2 0 0 1 0 50 1 0 0 0 -2 z-812257. 25 . 395 . 22545 . 02b1542xxxx0 1 0.5 0 0 -0.5 10 0 -1.75 1 0 3.25 5.5 0 0 -1 0 1 1 31 0 -0.25 0 0 0.75

26、 1.50 0 -0.5 0 0 -1.5 z-9035 . 5015 . 13X得基本可行解为最优解. 1, 5 . 121xx原问题的最优解为09 Z最优值9z即9Z最优值第32页/共53页第三十二页，共53页。0,82442.4max2121212121xxxxxxxxtsxxz求解线性规划问题例0,82442.4max5432152142132121xxxxxxxxxxxxxxtsxxz其标准型为常数(chngsh)项 4 1 0 0 0 Z -1 1 1 0 0 21 -4 0 1 0 41 -2 0 0 1 8543xxx842001X初始基本可行解48第33页/共53页第三十三页

27、，共53页。513xxx1 -4 0 1 0 4 0 -3 1 1 0 60 2 0 -1 1 4 0 17 0 -4 0 Z-16 1 0 0 -1 2 12 0 0 1 -1/2 3/2 120 1 0 -1/2 1/2 2 0 0 0 9/2 -17/2 Z-48 213xxx无界!常数(chngsh)项 4 1 0 0 0 Z -1 1 1 0 0 21 -4 0 1 0 41 -2 0 0 1 8543xxx48第34页/共53页第三十四页，共53页。1 0 0 -1 2 12 0 0 1 -1/2 3/2 120 1 0 -1/2 1/2 2 0 0 0 9/2 -17/2 Z-4

28、8 213xxx对应(duyng)的线性规划问题无界122321543xxx482172954zxx122541xxx22121542xxx543232112xxx542172948xxz541212xxx54221212xxx0045Mxx，令），（得解0211221212*MMMMXMz2948*其目标函数值无限增大，无限增大上时，当ZM0* X为可行解*X所以(suy)，该线性规划问题无界第35页/共53页第三十五页，共53页。3、将约束方程化为每个方程只含一个(y )基变量 目标函数表示成非基变量的函数 单纯形法步骤：1、化标准型 2、选定一个可行(kxng)基，并得一基本可行(kxn

29、g)解X？5、判断X是否为最优解：若目标函数(hnsh)行中所有检验数ci0, 则X为 最优解。若存在某个cj0,且所有的aij 0,取xk为入基变量 （2）出基变量： kiiikikiabaab000|min出基变量个方程对应的基变量为则第0i7、对单纯形表做初等行变换：把基变量对应的列化为 单位向量，目标函数的基变量系数化为零，得一新的基本可行解X。转第4步第36页/共53页第三十六页，共53页。0,3035202102.22max5432154153152154321xxxxxxxxxxxxxxt sxxxxxz例如：对线性规划问题432PPPB，取基03020100,，得基本X3035

30、202102541531521xxxxxxxxx由5145135123530220210 xxxxxxxxx310051010220011A系数矩阵可行(kxng)0,3035202102.8750max5432154153152151xxxxxxxxxxxxxxt sxxz典则形式(xngsh)第37页/共53页第三十七页，共53页。0,3035202102.22max5432154153152154321xxxxxxxxxxxxxxtsxxxxxz求解线性规划问题例不是(b shi)单纯形表初始(ch sh)单纯形表 1 0 0 2 2 z-10 11 0 0 0 8 z+50 第38页/

31、共53页第三十八页，共53页。0,2421252.24max2121212121xxxxxxxxtsxxz求解线性规划问题例0,2421252.24max5432152142132121xxxxxxxxxxxxxxtsxxz其标准型为典则形式(xngsh)b 4 2 0 0 0 z2 1 0 1 0 42 5 1 0 0 12-1 1 0 0 1 2543xxx 6 2b 0 0 0 -2 0 z-81 0.5 0 0.5 0 20 4 1 -1 0 80 1.5 0 0.5 1 4513xxx408021，最优解X8Z最优值b 0 0 0 -2 0 z-8 1 0 -0.125 0.125

32、0 1 0 1 0.25 0.25 0 2 0 0 -0.375 0.375 0 1 512xxx010212，最优解X8Z最优值第39页/共53页第三十九页，共53页。本题(bnt)说明：1、最优解不唯一，但最优值唯一无穷多个最优解时，问题有，最优解、当问题有两个不同的212XX10121XXX）（取211CXCXXCZ）（*1ZZ）（*Z也是最优解）（即211XXX多个最优解有无穷多，所以有无穷由于3、在实际(shj)应用中，有多种方案可供选择均为最优解时，因为当21XX且，即有, 002121XXbAXbAX*21ZCXCX，且则0XbXXAXA)1 (21第40页/共53页第四十页，共

33、53页。单纯形法的矩阵(j zhn)形式：0.maxXbAXtsCXz对问题nmmPPPPPA121mPPPB21设可行基nmPPN1非基mBxxxX21基变量nmNxxX1非基变量mBcccC21nmNccC1NBA，则NBXXXNBCCC,第41页/共53页第四十一页，共53页。0.maxXbAXtsCXz对问题mPPPB21取基nmPPN1非基mBxxxX21基变量nmNxxX1非基变量bAX 于是bXXNBNBbNXBXNBB 可逆bBNXBXNB11NBNBXXCCZ且NNBBXCXCNNNBXCNXBbBC)(11NBNBXNBCCbBC)(11mBcccC21nmNccC1NBA

34、，则NBXXXNBCCC,第42页/共53页第四十二页，共53页。0.maxXbAXtsCXz对问题mPPPB21取可行基NBNBXNBCCbBCZ)(max11bBNXBXNB110, 0NBXX关于可行(kxng)基B的典则形式对应的基本可行解：对应的目标函数值：0XObBX10bBCZB10第43页/共53页第四十三页，共53页。?1bBCBmmccc121mmB11mb=一个(y )数Z0bBCB10.maxXbAXtsCXz对问题mPPPB21可行基NBNBXNBCCbBCZ)(max110, 0NBXX:1：目标函数常数(chngsh)ObBX10基本可行解：?1NBCCBNbBN

35、XBXNB11第44页/共53页第四十四页，共53页。0.maxXbAXtsCXz对问题mPPPB21可行基NBNBXNBCCbBCZ)(max110, 0NBXX)(121mnnmmNcccCnmmPPPN21)(mnmNBCB1)(1mnQmnmmmmBNBC1)1()(11)(mnBNNBCCnmm21NBNXNBCC)(1nmm21nmmxxx21nnmmmmxxx2211jjBNNBCC)(1行向量ObBX,10基本可行解：的系数非基变量jx检验(jinyn)数bBNXBXNB11第45页/共53页第四十五页，共53页。：约束方程2bBNXBEXNB11,21mENB1nmPPB11

36、nmPBPB111bBNXBEXNB11m21mxxx21nmPBPB111bBxxnm11bBxPBxPBxxxnnmmmm111112211bBNXBXNB11nmmjpBxjj, 2, 1,:1的系数非基变量0.maxXbAXtsCXz对问题mPPPB21可行基NBNBXNBCCbBCZ)(max110, 0NBXXObBX,10基本可行解：bBNXBXNB11的系数：基变量ixmii,2, 1,第46页/共53页第四十六页，共53页。NBNBXNBCCbBCZ)(max110, 0NBXX设B为一个(y )可行基B的典则形式(xngsh)为：bBNXBXNB11bBNXBEXNB11bBCZXNBCCXBNBNB11)(0NBNBXNBCCbBCZ)(11BXENB1bB10NBCCBN1bBCZB1010bBX基本可行解常数项bBNXBXNB11第47页/共53页第四十七页，共53页。BXENB1bB10NBCCBN1bBCZB1常数(chngsh)项0最优值 最优解最优单纯形表0*1bBXbBCZB1*0第48页/共53页第四十八页，共53页。0.maxXbAXtsCXz对问题NBNBXNBCCbBCZ)(max110, 0NBXX设B为一个(y )可行基B