第二节单纯形法(简化)

1、第二节 单纯形法 单纯形法是求解线性规划的主要算法，1947年由美国斯坦福大学教授丹捷格（G.B.Dantzig）提出。 尽管在其后的几十年中，又有一些算法问世，但单纯形法以其简单实用的特色始终保持着绝对的“市场”占有率。 单纯形法是一种迭代的算法（设计在单纯形表上实现），它的思想是在可行域的角点（称为基本可行解）中寻优。检验这个角点是否最优否是停止停止确定一个初始角点寻找一个更好的角点1.将模型化为标准型 0. .XbAXtsCXMaxz 标准型的特征：Max型、等式约束、非负约束一、单纯形法的步骤一、单纯形法的步骤。）（的秩为其中，0,bnmmAnm非标准形式如何化为标准1) Min型化为

2、Max型 CXMinzCXMaxz/加负号 因为，求一个函数的极小点，等价于求该函数的负函数的极大点。)(xf)(xf*x注意： Min型化为Max型求解后，最优解不变，但最优值差负号。 2) 不等式约束化为等式约束分析：以例1.1中煤的约束为例3604921 xx之所以“不等”是因为左右两边有一个差额，称为“松弛量”，若在左边加上这个松弛量，则化为等式。而这个松弛量也是变量，记为X3 ，则有36049321xxxX3称为松弛变量。问题：它的实际意义是什么？ 煤资源的“剩余”。练习：请将例1.1的约束化为标准型0,3001032005436049.21212121xxxxxxxxts解：增加松

3、弛变量则约束化为,543xxx0,300 10320054360 49.54321521421321xxxxxxxxxxxxxxts易见，增加的松弛变量的系数恰构成一个单位阵I。2.建立初始单纯形表 前提：模型 的系数阵A A中含I I（单位阵）。否则用人工变量法。0.XbAXtsCXMaxz X CAbBXBC初始单纯形表的结构初始单纯形表的结构全体变量名全体变量名变量的价格系数变量的价格系数约束系数阵约束系数阵与与A中的中的I 相应相应的变量（称基的变量（称基变量）名变量）名基变量基变量 的的价格系数价格系数BX约束右端项约束右端项bB例1.5：列出例1.1标准模型的初始单纯形表0,300

4、 10320054360 49.54321521421321xxxxxxxxxxxxxxts21127xxMaxz54321 xxxxxbBBXBC0 0 0 12 71001030105400149300200360543xxx0003. 检验该单纯形表是否最优检验数：每个变量的检验数等于该变量的检验数：每个变量的检验数等于该变量的价格系数减去价格系数减去 与该变量的系数列之积。与该变量的系数列之积。BC X CAbBXBCbB1法则：如果全体检验数均非正，则本表为最优，相应的最优解 否则转4。；01*bBX例1.6：检验例1.1的初始单纯形表是否最优54321 xxxxxbB1BXBC0

5、0 0 12 71001030105400149300200360543xxx000 0 0 0 12 77;3490) 0 (071111pBCcB检验数相应于相应于x1 的系数列的系数列练习：计算x2的检验数。由于检验数中有正的，故本表不是最优。练习：写出下列线性规划的标准型和初始单纯形表，并检验该表是否最优。0,25.2121 21xxxxxxts105153212.5xxMaxz将模型化为标准型：解：增加松弛变量, 43xx21xxMaxz5 .20,102515 53. .4342132121xxxxxxxxxxts 4321xxxx 0 0 1 2.5bB1BXBC10 2 501

6、 5 3101543xx00 0 0 1 2.5由于检验数中有正的，故本表不是最优。确定一个初始角点检验这个角点是否最优寻找一个更好的角点否是停止下一步？4. 计算下一张单纯形表（1 1）确定本表的进基、出基变量和主元）确定本表的进基、出基变量和主元 选本表正检验数中最大者，其相应的变量xk 进基； 计算 与xk 的系数列之比（记 ，称检验比）,选 中最小者相应的变量xl 出基（注意：当xk 的系数列中有零或负值时，相应 不算）； xk 列与xl 行的交叉元即主元。bB125 10 2 501 5 3101543xx00 0 0 1 2.5 4321xxxx 0 0 1 2.5bB1BXBC例

7、如例如（2 2）基于主元计算下一张单纯形表）基于主元计算下一张单纯形表 用初等行变换方法，先将主元消成1，再用此1将其所在列的其余元消成0，所得结果写在新表上； 转第3步（即检验新表是否最优）。13xx2.50 0.5- 0 0 0TX)09,0,2,(5z10 2 501 5 3101543xx00 0 0 1 2.525 4321xxxx 0 0 1 2.5bB1BXBC例如例如51 0 52 1 253- 1 519 0 9例1.7：用单纯形法求解例1.10,3001032005436049.21212121xxxxxxxxts21127xxMaxz将模型化为标准型：解：增加松弛变量,5

8、43xxx 0,3001032005436049.54321521421321xxxxxxxxxxxxxxts 21127xxMaxz问题：标准模型的A中是否含I？松弛变量系数恰好构成I。54321 xxxxxbB1BXBC0 0 0 12 71001030105400149300200360543xxx000 0 0 0 12 7 3040907;3490) 0 (071111pBCcB其中检验数904360354321 xxxxxbB1BXBC0 0 0 12 71001030105400149300200360543xxx000 0 0 0 12 7 3040900.1 0 0 1 0.

9、3 300.4- 0 1 0 7.8 2400.5- 1 0 0 2.5 50243xxx1200 1.2- 0 0 0 3.41002030.8 0.2- 0.4 0 0 1 201.16 3.12- 1 0 0 840.16 0.12- 0 1 0 24213xxx1270 0.52- 1.36- 0 0 0428.,0,0)(20,24,84,*zXT（请解释其实际意义）练习：用单纯形法求解下面的线性规划0,62-2-.2121 21xxxxxxts 212-xxMins将模型化为标准型：解：增加松弛变量, 43xx212xxMaxz0,622 -. .4342132121xxxxxxx

10、xxxts 4321xxxx 0 0 2- 1bB1BXBC10 2 101 1 1- 6243xx006 0 0 2- 1 1 0 2 1 6 1 1 3 0 813xx10 1- 0 4- 0TX)0,8,0,6(6s总结表的规律：总结表的规律：表中基变量的系数列有何特征？1. 基变量的检验数有何特征？均为单位向量列；均为零。213xxx54321 xxxxxbB1BXBC1010301540049300200360543xxx000 0 0 0 12 7例1.8：填出表中空白：0.2- 0.4 0 1 1.16 3.12- 1 0 0.16 0.12- 0 0 1270 0.52- 1.36- 0 0 0242084100001问题：如果空白的不是基变量列怎么办呢？问题：如果空白的不是基变量列怎么办呢？ 3. 表上每一列的含义：),(),(11111n3B3BbBAbB4. 每张表上B-1的位置在哪？对应于初表中I 的位置。事实上，事实上， 因此，若已知初表和任意表的B-1，则可用矩阵与向量法的乘法计算得到任意表中的空白列。54321 xxxxxbB1BXBC1001030105400149300200360543xxx000 0 0 0 12 7