第二节单纯形法单纯形法是求解线性规划的主要算法,1947年由美国斯坦福大学教授丹捷格(G.B.Dantzig)提出。尽管在其后的几十年中,又有一些算法问世,但单纯形法以其简单实用的特色始终保持着绝对的“市场”占有率。单纯形法是一种迭代的算法(设计在单纯形表上实现),它的思想是在可行域的角点(称为基本可行解)中寻优。检验这个角点是否最优否是停止确定一个初始角点•寻找一个更好的角点••1.将模型化为标准型0..XbAXtsCXMaxz标准型的特征:Max型、等式约束、非负约束一、单纯形法的步骤。)(的秩为其中,0,bnmmA非标准形式如何化为标准1)Min型化为Max型CXMinzCXMaxz/加负号因为,求一个函数的极小点,等价于求该函数的负函数的极大点。)(xf)(xf*x注意:Min型化为Max型求解后,最优解不变,但最优值差负号。2)不等式约束化为等式约束分析:以例1.1中煤的约束为例3604921xx之所以“不等”是因为左右两边有一个差额,称为“松弛量”,若在左边加上这个松弛量,则化为等式。而这个松弛量也是变量,记为X3,则有36049321xxxX3称为松弛变量。问题:它的实际意义是什么?——煤资源的“剩余”。练习:请将例1.1的约束化为标准型0,3001032005436049..21212121xxxxxxxxts解:增加松弛变量则约束化为,,,543xxx0,,,,3001032005436049..54321521421321xxxxxxxxxxxxxxts易见,增加的松弛变量的系数恰构成一个单位阵I。2.建立初始单纯形表前提:模型的系数阵A中含I(单位阵)。否则用人工变量法。0..XbAXtsCXMaxzXCAbXC初始单纯形表的结构全体变量名变量的价格系数约束系数阵与A中的I相应的变量(称基变量)名基变量的价格系数BX约束右端项bB例1.5:列出例1.1标准模型的初始单纯形表0,,,,3001032005436049..54321521421321xxxxxxxxxxxxxxts21127xxMaxz54321xxxxxbBXC0001271001030105400149300200360xxx0003.检验该单纯形表是否最优检验数:每个变量的检验数等于该变量的价格系数减去与该变量的系数列之积。BCXCAbXCbB法则:如果全体检验数均非正,则本表为最优,相应的最优解否则转4。;01*bBX例1.6:检验例1.1的初始单纯形表是否最优54321xxxxxbBXC0001271001030105400149300200360xxx0000001277;3490)0(071111pBCcB检验数相应于x1的系数列练习:计算x2的检验数。由于检验数中有正的,故本表不是最优。练习:写出下列线性规划的标准型和初始单纯形表,并检验该表是否最优。0,25..212121xxxxxxts105153212.5xxMaxz将模型化为标准型:解:增加松弛变量,,43xx21xxMaxz5.20,,,10251553..4342132121xxxxxxxxxxts4321xxxx0012.5bBXC10250153101543xx000012.5由于检验数中有正的,故本表不是最优。确定一个初始角点检验这个角点是否最优寻找一个更好的角点否是停止下一步?4.计算下一张单纯形表(1)确定本表的进基、出基变量和主元•选本表正检验数中最大者,其相应的变量xk进基;•计算与xk的系数列之比(记,称检验比),选中最小者相应的变量xl出基(注意:当xk的系数列中有零或负值时,相应不算);•xk列与xl行的交叉元即主元。bB125[]10250153101543xx000012.54321xxxx0012.5bBXC例如(2)基于主元计算下一张单纯形表•用初等行变换方法,先将主元消成1,再用此1将其所在列的其余元消成0,所得结果写在新表上;•转第3步(即检验新表是否最优)。13xx2.500.5-000X)09,0,2,(5z10250153101543xx000012.525[]4321xxxx0012.5bBXC例如510521253-151909例1.7:用单纯形法求解例1.10,3001032005436049..21212121xxxxxxxxts21127xxMaxz将模型化为标准型:解:增加松弛变量,,,543xxx0,,,,3001032005436049..54321521421321xxxxxxxxxxxxxxts21127xxMaxz问题:标准模型的A中是否含I?——松弛变量系数恰好构成I。54321xxxxxbBXC0001271001030105400149300200360xxx000000127[]3040907;3490)0(071111pBCc其中检验数90436054321xxxxxbBXC0001271001030105400149300200360xxx000000127[]3040900.10010.3300.4-0107.82400.5-1002.550243xxx12001.2-0003.41002030.8[]0.2-0.4001201.163.12-100840.160.12-01024213xxx12700.52-1.36-000428.,0,0)(20,24,84,*zX(请解释其实际意义)练习:用单纯形法求解下面的线性规划0,62-2-..212121xxxxxxts212-xxMins将模型化为标准型:解:增加松弛变量,,43xx212xxMaxz0,,,622-..4342132121xxxxxxxxxxts4321xxxx002-1bBXC10210111-6243xx006002-1[]102161130813xx101-04-0X)0,8,0,6(6s总结表的规律:1.表中基变量的系数列有何特征?2.基变量的检验数有何特征?——均为单位向量列;——均为零。213xxx54321xxxxxbBXC1010301540049300200360xxx000000127例1.8:填出表中空白:0.2-0.4011.163.12-100.160.12-0012700.52-1.36-000242084100001问题:如果空白的不是基变量列怎么办呢?3.表上每一列的含义:),,,(),(PBPBbBAbB4.每张表上B-1的位置在哪?——对应于初表中I的位置。事实上,因此,若已知初表和任意表的B-1,则可用矩阵与向量法的乘法计算得到任意表中的空白列。54321xxxxxbBXC1001030105400149300200360xxx000000127[]例1.9:填表:,2420843002003600.160.1200.20.401.163.1211bB解:10010540.160.1200.20.401.163.1211PB0.2-0.4011.163.12-100.160.12-00213xxx12700.52-1.36-000242084100