运筹学教学资料运筹学第1章第34节.ppt
-1-运筹学 第一章第一章 线性规划线性规划1 线性规划问题及其模型线性规划问题及其模型2 线性规划问题几何意义线性规划问题几何意义3 单纯形法单纯形法4 单纯形法计算步骤单纯形法计算步骤5 单纯形法进一步讨论单纯形法进一步讨论6 应用举例应用举例-2-运筹学 本节学习要点：本节学习要点：1、重点掌握单纯形的变换过程及基本思路；、重点掌握单纯形的变换过程及基本思路；2、了解单纯形解的判别。、了解单纯形解的判别。-3-运筹学 先找出一个基可行解，判断其是否为最优解；先找出一个基可行解，判断其是否为最优解；如为否，则转换到相邻的基可行解，并使目标函数值如为否，则转换到相邻的基可行解，并使目标函数值不断增大；不断增大；一直找到最优解为止。一直找到最优解为止。定义：定义：两个基可行解称为两个基可行解称为相邻相邻的，如果它们之间变换且的，如果它们之间变换且仅变换仅变换一个一个基变量。基变量。单纯形法迭代的单纯形法迭代的基本思路基本思路是：是：3 单纯形法单纯形法-4-运筹学 单纯形法是一单纯形法是一种迭代的算法，它种迭代的算法，它的思想是在可行域的思想是在可行域的顶点的顶点基本可基本可行解中寻优。由于行解中寻优。由于顶点是有限个顶点是有限个,因因此，算法经有限步此，算法经有限步可终止。可终止。单纯形法的步骤单纯形法的步骤确定初始基本可行解确定初始基本可行解检验其是否最优？检验其是否最优？寻找更好的基本可行解寻找更好的基本可行解是是否否方法前提：模型化为标准型方法前提：模型化为标准型3 单纯形法单纯形法-5-运筹学 12345max35000zxxxxx0,12241823543215241321xxxxxxxxxxxx3.1 引例：引例：例：例：3 单纯形法单纯形法-6-运筹学 345,x x x为基变量为基变量312415218 324122xxxxxxx120 xx34518412xxx3 05 00 18040 120z 没有安排生产没有安排生产1、2两种产品，资源没有利用，所以利润为零。两种产品，资源没有利用，所以利润为零。即这个基可行解不是极点。即这个基可行解不是极点。分析：如果将非基变量转变成基变量，目标函数就可能增大。分析：如果将非基变量转变成基变量，目标函数就可能增大。如果目标函数中还有正系数的非基变量存在，则说明目标如果目标函数中还有正系数的非基变量存在，则说明目标函数还有增大的可能。函数还有增大的可能。12345max35000zxxxxx0,12241823543215241321xxxxxxxxxxxx3 单纯形法单纯形法-7-运筹学 将正系数最大的那个非基变量换入（即该变量将正系数最大的那个非基变量换入（即该变量0）,以获得该以获得该产品的最大产量和对应的最大利润。产品的最大产量和对应的最大利润。312415218320401220 xxxxxxx120,0 xx2296xx即即x2=6时可以使约束条件不被破坏。而此时时可以使约束条件不被破坏。而此时x5=0，不再适合做基变量，所以将其用不再适合做基变量，所以将其用x2换出，因此得到：换出，因此得到：231412521830402120 xxxxxxx3154125630401602xxxxxxx3 单纯形法单纯形法-8-运筹学 3154125630401602xxxxxxx同理：同理：150,0 xx153302.5zxx342646xxx30z 3 单纯形法单纯形法-9-运筹学 153302.5zxx此时的目标函数为：此时的目标函数为：函数中的函数中的x1，仍然没有利用，其系数仍然为正数，说明目标，仍然没有利用，其系数仍然为正数，说明目标还有增长的余地，该基可行解仍不是最优解，下一步将还有增长的余地，该基可行解仍不是最优解，下一步将x1换换入基变量中。入基变量中。3154125630401602xxxxxxx150,0 xx1124xx即即x1=2时可以使约束条件不被破坏。而此时时可以使约束条件不被破坏。而此时x3=0，不再适合做基变量，所以将其用不再适合做基变量，所以将其用x1换出，因此得到：换出，因此得到：3 单纯形法单纯形法-10-运筹学 1351425360401602xxxxxxx135435251120331120331602xxxxxxxx35361.5zxx350,0 xx142226xxx36z 3 单纯形法单纯形法-11-运筹学 35361.5zxx此时的目标函数为：此时的目标函数为：函数中所有非基变量的系数都是负数，说明如果想要得到利润函数中所有非基变量的系数都是负数，说明如果想要得到利润的增加，就需要对的增加，就需要对“不存在的、没有利用的不存在的、没有利用的”资源付出代价，资源付出代价，这是不现实的，所以求解停止。也就是说，生产这是不现实的，所以求解停止。也就是说，生产x1 2吨，生产吨，生产x2 6吨，可以得到最的利润吨，可以得到最的利润36万元。这个结果与前面万元。这个结果与前面图解法图解法的结的结果相同。果相同。该例子是一个二维的规划问题，但是在加入松弛变量该例子是一个二维的规划问题，但是在加入松弛变量x3 x4 x5之之后就变成了高维的规划问题。这时可以想象，满足所有约束条后就变成了高维的规划问题。这时可以想象，满足所有约束条件的可行域是高维空间的凸多面体，基可行解就是凸多面体上件的可行域是高维空间的凸多面体，基可行解就是凸多面体上的顶点。的顶点。下面将前面所使用的方法进行总结归纳，推导求解一般线性规下面将前面所使用的方法进行总结归纳，推导求解一般线性规划问题的基本方法划问题的基本方法单纯形算法。单纯形算法。3 单纯形法单纯形法-12-运筹学 给定一个初始基可行解给定一个初始基可行解 ,0X对线性规划问题对线性规划问题 ,21mPPPB ;,1nmPPN ,21TmBxxxX TnmNxxX,1 ,21mBcccC 12,NmmnCcccmax.0zCXAXbstX,BNXXX则基可行解可写成则基可行解可写成。NBCCC,对应的对应的 A=(B,N)，3.2 解的判别定理解的判别定理3 单纯形法单纯形法-13-运筹学 max.0zCXAXbstXmax.,0,|0,0NNBBNBNBzC XC XNXB XbstXXBb11BNXBbBNX11()BNBNzC BbCC BN Xmax110,0BNBNXB NXB bXX称为基称为基 所对应的所对应的典式典式。12,mx xx3 单纯形法单纯形法-14-运筹学 01,0.TXB b mmnmmmmnmmnmmbBNB 2112122212121111,N 11()BNBNzC BbCC BN Xmax110,0BNBNXB NXB bXX0z3 单纯形法单纯形法-15-运筹学 01111(1)11122(1)122(1)1121max,0mmnnmmnnmmnnmm mmmnnmmmnzzxxxxxxxxxxxx x xxx线性规划线性规划典式典式(proper form)(proper form)的分量表示：的分量表示：称称 是非基变量是非基变量 的的检验数检验数。nm,1nmxx,1重要！重要！重要！重要！11()BNBNzC BbCC BN Xmax110,0BNBNXB NXB bXX3 单纯形法单纯形法-16-运筹学 1）基可行解）基可行解mjmjjjjcccc2211注：注：给出基给出基 后后,由其典式可得出结论由其典式可得出结论12,mx xx2）其对应目标函数值）其对应目标函数值z0=CBB-1b0112(,0,0)(,0)TTmXB b（针对非基变量）（针对非基变量）3）检验数）检验数nm,1利用这组数来判断利用这组数来判断X0是否是最优解。是否是最优解。11,NNBmnCC B N3 单纯形法单纯形法-17-运筹学 定理定理1 最优解判定准则最优解判定准则,0,1 jnmj 有有如果对一切如果对一切 则则 X 0是线性是线性规划问题的规划问题的最优解最优解。,0,1 jnmj 有有如果对一切如果对一切 则则 X 0是线性规是线性规划问题的划问题的唯一最优解唯一最优解。,0,1 jnmj 有有,0 lm 如果对一切如果对一切 并且存在某个并且存在某个 则线性规划问题有则线性规划问题有无穷多最优解无穷多最优解。,0 km ,0,2,1 kmimi 如果存在一个如果存在一个 并且对一切并且对一切则线性规划问题则线性规划问题无最优解无最优解(也称也称无界解无界解，即最优值为无穷，即最优值为无穷)。设设 X 0 是基可行解，则：是基可行解，则：3 单纯形法单纯形法-18-运筹学 定理定理2 （基可行解改进定理）（基可行解改进定理）证明证明 略。略。设设X0是基可行解，典式如前所示，如果是基可行解，典式如前所示，如果0 km 存在一个存在一个 ；kmmkmkm ,21 中至少有一个正分量；中至少有一个正分量；01CXCX 0 i 所有的所有的 ;则一定存在另一个基可行解则一定存在另一个基可行解X1,使使3 单纯形法单纯形法-19-运筹学 1 线性规划问题及其模型线性规划问题及其模型2 线性规划问题几何意义线性规划问题几何意义3 单纯形法单纯形法4 单纯形法计算步骤单纯形法计算步骤5 单纯形法进一步讨论单纯形法进一步讨论6 应用举例应用举例-20-运筹学 1947年，年，G.B.Dantzig提出求解线性规划的单纯形法。提出求解线性规划的单纯形法。单纯形算法的直接思想：单纯形算法的直接思想：从一个基可行解开始，通过基变换，到另一个基可行解，从一个基可行解开始，通过基变换，到另一个基可行解，逐步达到最优解的过程。基变换是通过迭代法实现的。逐步达到最优解的过程。基变换是通过迭代法实现的。4.1 单纯形算法计算步骤单纯形算法计算步骤-21-运筹学 Step1 求初始基可行解。求初始基可行解。找出一个初始基可行解找出一个初始基可行解X0，写出，写出X0相应的典式相应的典式.3）进行基变换）进行基变换.得到新的基可行解得到新的基可行解 X1及其典式，转及其典式，转step 2.Step2 最优性检验。最优性检验。如果所有非基变量如果所有非基变量 xj 的检验数都不大于的检验数都不大于0，则，则X0是最优解，是最优解，计计 算结束；若存在某个检验数算结束；若存在某个检验数k0，其所有的其所有的ik0，则线，则线性规划问题无最优解，计算结束；否则转至性规划问题无最优解，计算结束；否则转至step 3.Step3 进行基变换。进行基变换。1）确定换入变量）确定换入变量.规则规则,找最大的找最大的其对应的其对应的 xk 就是换入变量就是换入变量.max:0kjjlklikiki0:min2）确定换出变量）确定换出变量.规则规则,计算计算确定确定 xl 是换出变量是换出变量.4.1 单纯形算法计算步骤单纯形算法计算步骤-22-运筹学 找初始基可行解找初始基可行解X0及可行基及可行基B j 0?写出最优解写出最优解与最优值与最优值停停是否有是否有 ik0无界解无界解N确定换出变量确定换出变量x l ,klliikik0min以以 kl为主元作基变换为主元作基变换停停NYY确定换入变量确定换入变量x k k=max j|j 04.1 单纯形算法计算步骤单纯形算法计算步骤-23-运筹学 01111(1)11122(1)122(1)1121max,0mmnnmmnnmmnnmm mmmnnmmmnzzxxxxxxxxxxxx x xxx基变换基变换示示例例11(1)(1)mmm m1,1 1111 1mnnxxx21 1222 0 nnxxx1 1 0 mmmnnmxxx121,0mmnx x xxx01 1max 0nnzzxx 主元主元0011mzz-24-运筹学 0max()0(1,2,)jjj Riijjij RjzzxxxiSxjn如果存在某个如果存在某个 ,使使,并且至少有一个并且至少有一个Rk0k)(0Siiklklikiki0:minSixi:设基设基 （S 为
