北邮最优化课件4单纯形方法

2023/5/3最优化理论最优化理论与算法帅天平北京邮电大学数学系§4，线性规划的单纯形方法2023/5/3最优化理论第三章单纯形方法1，单纯形方法原理2，两阶段法和大Mf法3，退化情形4，修正单纯形方法2023/5/3最优化理论单纯形法的基本思路

是有选择地取（而不是枚举所有的）基本可行解，即是从可行域的一个顶点出发，沿着可行域的边界移到另一个相邻的顶点，要求新顶点的目标函数值不比原目标函数值差，如此迭代，直至找到最优解，或判定问题无界。

初始基本可行解是否最优解或无界解?结束沿边界找新的基本可行解NY单纯形法的基本过程

3.1线性规划-单纯形方法1怎么判断达到最优解?如何给出初始基可行解?迭代如何进行?2023/5/3最优化理论

3.1线性规划-单纯形方法2给定标准形式的LP利用分块矩阵2023/5/3最优化理论3.1线性规划-单纯形方法3于是目标函数于是有

基本可行解x与基B关联;2023/5/3最优化理论3.线性规划-单纯形方法4于是我们有如下定理：2023/5/3最优化理论3.1.线性规划-单纯形方法5由上知,要减少费用,只有当C0时才可能，即2023/5/3最优化理论3.1线性规划-单纯形方法6令y=x+d,>0,我们能降低费用吗？2023/5/3最优化理论3.1线性规划-单纯形方法72023/5/3最优化理论3.1线性规划-单纯形方法82023/5/3最优化理论3.1线性规划-单纯形方法9正确性如何？显然按上述取法，是可以保证y≥0的。y还是基本可行解吗？2023/5/3最优化理论3.1线性规划-单纯形方法102023/5/3最优化理论3.1线性规划-单纯形方法11单纯形法2023/5/3最优化理论3.1线性规划-单纯形方法12Th3.4(单纯形法的收敛性）对于相容的非退化(每个基可行解都是非退的)LP问题，那么经过有限次迭代后，单纯形法或者得到最优的BFS(最优可行基B）或有一个方向d:且最优的费用为-∞.2023/5/3最优化理论3.1线性规划-单纯形方法13例12023/5/3最优化理论3.1线性规划-单纯形方法142023/5/3最优化理论3.1线性规划-单纯形方法15Tc

=(0702-300)2023/5/3最优化理论3.1线性规划-单纯形方法162023/5/3最优化理论3.1线性规划-单纯形方法172023/5/3最优化理论3.1线性规划-单纯形方法182023/5/3最优化理论3.1线性规划-单纯形方法19新的基为B=(A1,A3,A4,A7)2023/5/3最优化理论3.1线性规划-单纯形方法202023/5/3最优化理论3.1线性规划-单纯形方法21新的基为B=(A3,A4,A5,A7)2023/5/3最优化理论

3.1线性规划-单纯形方法22利用分块矩阵表格形式的单纯形方法2023/5/3最优化理论

3.1线性规划-单纯形方法232023/5/3最优化理论3.1线性规划-单纯形方法240

Im

10ff右端2023/5/3最优化理论3.1线性规划-单纯形方法25进基变量离基变量旋转元右端向量返回单纯形表2023/5/3最优化理论例2：求解线性规划问题化成标准化形式

3.1线性规划-单纯形方法26

2023/5/3最优化理论写出单纯形表25/136/20-3-20-2-7201/201-1/27/0.511/2101/218/0.5x271811/21/2x5x6离基，x2进基，x5离基，x1进基，3.1线性规划-单纯形方法272023/5/3最优化理论0-4-2-2-1-860102-1101-11141100得到最优解，最优解为：（x1，x2，x3，x4，x5，x6）=（14,11,0,0,0,0）minz’=-86，maxz=861

3.1线性规划-单纯形方法282023/5/3最优化理论例3：求解线性规划问题3.1线性规划-单纯形方法292023/5/3最优化理论3.1线性规划-单纯形方法302023/5/3最优化理论x3进基，x6离基3.1单纯形方法312023/5/3最优化理论初始单纯型表最优单纯型表2023/5/3最优化理论3.2两阶段法&大M法1单纯形法三要素：初始基本可行解，解的迭代，最优性检验后两个已解决,现考虑如何获得一个初始基可行解.（一）两阶段法设标准LP为2023/5/3最优化理论3.2两阶段法&大M法2若系数矩阵中有一个单位矩阵，则容易得到初始基可行解.所以我们希望幸运的碰到这种矩阵.没有的话，硬性加一个？2023/5/3最优化理论3.2两阶段法&大M法3问题是如何由(3.2.3)的初始可行解获得原来LP的一个初始可行解？为此，考虑如下辅助LP(第一阶段)2023/5/3最优化理论如果原问题有可行解，则辅助问题的最优值为0，反之亦然。就可以得到辅助问题的初始基可行解2．由于，所以以为基变量，,同时所以一定有最小值.3.2两阶段法&大M法4关系?2023/5/3最优化理论3.2两阶段法&大M法5利用单纯形法求得一个最优可行解.这个解将会给我们带来什么？2023/5/3最优化理论3.2两阶段法&大M法6于是我们获得一个初始基可行解,从而可以以此基可行解出发利用单纯形法求出最优解.第一阶段：不考虑原LP问题是否有基可行解，添加人工变量，构造仅含人工变量的目标函数，得辅助规划(3.2.4)单纯型法求解上述模型，若有目标函数=0，说明原问题存在初始基本可行解，转入第二阶段。否则，原问题无可行解，计算停止。

第二阶段：将第一阶段计算得到的最终表，除去人工变量，从该初始基本可行解开始，用单纯形法求原问题的最优解或判定原问题无界。2023/5/3最优化理论3.2两阶段法&大M法7写成标准化形式例1求解2023/5/3最优化理论3.2两阶段法&大M法8第1

阶段首先引入人工变量，构造辅助规划问题如果以为基变量，则可以得到该问题的BFS,其对应的单纯形表为2023/5/3最优化理论3.2两阶段法&大M法9-50-210000000000-1-101-16-101021120-1011RHS-50-2100000208-1-10031-16-101021120-1011gzgz2023/5/3最优化理论3.2两阶段法&大M法10-3/2-7/20-7/207/20-72/34/301/3-1-4/301/31/6-1/61-1/601/601/32/34/301/3-1-1/311/3RHSgz1/400-21/8-21/821/821/863/800000-1-101/401-1/8-1/81/81/83/81/2101/4-3/4-1/43/41/4RHSgz2023/5/3最优化理论1/400-21/8-21/821/821/863/800000-1-101/401-1/8-1/81/81/83/81/2101/4-3/4-1/43/41/4RHSgz第一阶段结束，得到辅助问题的一个最优解同时得到原问题的一个初始基本可行解3.2两阶段法&大M法112023/5/3最优化理论去掉人工变量对应的行、列，得到原问题的初始典式，直接开始第二阶段运算第

2

阶

段1/400-21/8-21/821/821/863/800000-1-101/401-1/8-1/81/81/83/81/2101/4-3/4-1/43/41/4RHSgzRHS0-1/20-11/4-9/431/4

0-1/21-1/41/41/41201/2-3/21/2z原问题的最优解其最优值为2023/5/3最优化理论3.2两阶段法&大M法12例2求解2023/5/3最优化理论3.2两阶段法&大M法13解：引进人工变量进行第一阶段2023/5/3最优化理论3.2两阶段法&大M法14单纯形法求解：2023/5/3最优化理论3.2两阶段法&大M法15011-10104002-300140-11-21000004-600082023/5/3最优化理论3.2两阶段法&大M法160201-20140201-11040402-400832023/5/3最优化理论3.2两阶段法&大M法17010½-½½020000-1-110001-3/2½½020000-2-20822023/5/3最优化理论3.2两阶段法&大M法18第二阶段：

2023/5/3最优化理论3.2两阶段法&大M法19第二阶段初始单纯形表：2023/5/3最优化理论3.2两阶段法&大M法20前面所说的两阶段法分成两步走。能不能把这两步合并？如何合并？（二）大M法设原问题为引入m个人工变量2023/5/3最优化理论3.2两阶段法&大M法21现在关键是如何选取目标函数，因要包含原问题,所以必须包含原目标。联系到两阶段法，我们要强迫人工变量取值为0，于是加上一个惩罚因子，因为是极小化，所以希望这个惩罚因子越大越好！！在目标函数中增加2023/5/3最优化理论3.2两阶段法&大M法22可行吗？直观上，因M为足够大的正数，新问题最优解对应的人工变量取值应满足，（除非原问题不可行）从而新LP问题的最优解对应于原问题的（基本）可行解，容易知道此时两个问题的目标函数值满足2023/5/3最优化理论3.2两阶段法&大M法23因此只需求解辅助问题就可求得原问题的最优解。另一方面，原问题的任意可行解x对应于辅助问题的可行解，也对应新问题的可行解且两个规划目标值相等，故原问题的最优解综合2023/5/3最优化理论3.2两阶段法&大M法24例3求解如下LP解：2023/5/3最优化理论

得到最优解：(25/3，10/3，0，11)T

最优目标值：max=112/33.2两阶段法&大M法252023/5/3最优化理论3.2.3单个人工变量技巧1前述方法引入多个人工变量，能否只引入一个变量而达到目标？考虑LP2023/5/3最优化理论3.2.3单个人工变量技巧22023/5/3最优化理论3.2.3单个人工变量技巧3例子：2023/5/3最优化理论3.2.3单个人工变量技巧4利用表格形式求解一个(3.2.17)的BFS：2023/5/3最优化理论3.2.3单个人工变量技巧5于是得到(3.2.17)的一个BFS，下面再用两阶段(或大M)法求解之.2023/5/3最优化理论3.2.3单个人工变量技巧62023/5/3最优化理论3.2.3单个人工变量技巧7于是得到进行第二阶段时的初始表。由上知道这是最优单纯形表。2023/5/3最优化理论3.3退化情形1单纯形法收敛定理要求BFS非退化，这个限制可以去掉吗？试看下例。例(3.3.1)：用单纯形法求解下面的LP注意到该LP有一个明显的BFS

x=(0，0，1，0，0，0，0)2023/5/3最优化理论3.3退化情形2其单纯形法迭代过程如下：2023/5/3最优化理论3.3退化情形32023/5/3最优化理论3.3退化情形42023/5/3最优化理论3.3退化情形52023/5/3最优化理论3.3退化情形6前例表明算法会无限循环下去，能否找到一种办法避免出现这种情况？(a)摄动法2023/5/3最优化理论3.3退化情形7下面讨论这种办法的可行性。对右端向量b作如下摄动。令于是得（3.3.1）的摄动问题：2023/5/3最优化理论3.3退化情形8下面我们将证明当适当对取值时，LP(3.3.3)非退化，且可以通过求解LP(3.3.3)来确定原LP(3.3.1)的最优解或得出其他结论。2023/5/3最优化理论3.3退化情形9前面分析表明摄动问题当>0充分小时非退化，因此可以避免循环，并且通过求解摄动问题一定能够给出线性规划

(3.3.1)的解答。下一个问题是如何求解摄动问题？此时需要处理两个问题：（1）初始可行解；（2）迭代过程中如何处理b().(a)初始可行解的确定思想：是由原LP(3.3.1)的BFS来找LP(3.3.3)的BFS.2023/5/3最优化理论3.3退化情形10对应的摄动问题约束为幸运的是我们可以通过将变量下标进行适当调整，使得上述情况不出现。改变标号，使得(3.3.8)为如下等价约束:2023/5/3最优化理论3.3退化情形11一般地，若已知LP(3.3.1)的一个BFS，则进行列调换，把基列排在非基列的左边，并相应地改变变量的下标，使其从1开始按递增顺序排列，这样x1,x2,..,xm是基变量，然后再建立摄动问题(3.3.3).这时，若(3.3.1)的现行BFS是2023/5/3最优化理论3.3退化情形12于是可以用单纯形法求解下去。但右端向量含有参数，这对计算有影响吗？实际上我们可以不必让取具体数字。注意到：2023/5/3最优化理论3.3退化情形13概言之，以如下步骤确定离基之变量：(b)

置j=1.(a)令(c)令(d)

置j:=j+1,转(c).2023/5/3最优化理论3.3退化情形14例：用摄动法解例(3.3.1),初始单纯形表如下(0,4)(0,0)2023/5/3最优化理论3.3退化情形152023/5/3最优化理论即在单纯形表中选最左边的正检验数对应的非基变量入基。即在比值达到最小的行中，选最上面的那行所对应的基变量出基。3.3退化情形17解LP问题时常遇到基本可行解退化的情形，但在迭代过程中极少出现循环情形。注意Bland规则(退化问题的处理)：2023/5/3最优化理论该问题的最优解model:[obj]min=-0.75*x4+20*x5-0.5*x6+6*x7;[con1]x1+0.25*x4-8*x5-x6+9*x7=0;[con2]x2+0.5*x4-12*x5-0.5*x6+3*x7=1;[con3]x3+x6=1;end3.3退化情形182023/5/3最优化理论1，修正单纯形方法2，逆的乘积形式3.4修正单纯形方法2023/5/3最优化理论1，修正单纯形方法3.4修正单纯形方法-12023/5/3最优化理论回忆单纯形方法，不妨设初始单纯形表中系数矩阵含有单位阵，即系数矩阵为3.4修正单纯形方法-22023/5/3最优化理论3.4修正单纯形方法-32023/5/3最优化理论这样，有了初始表(即问题的系数矩阵，费用向量和右端向量子集组成)，当前表*和基B，则修正单纯形方法就可进行下去了3.4修正单纯形方法4修正单纯形方法2023/5/3最优化理论4)

把主列置于逆矩阵表的右边，组成下列表3.4修正单纯形方法52023/5/3最优化理论例3.4.1，用修正单纯形法解下列LP3.4修正单纯形方法-62023/5/3最优化理论约束方程的系数矩阵3.4修正单纯形方法-700001005010600132023/5/3最优化理论第1次迭代：3.4修正单纯形方法-80000100501060