运筹学第二单纯形法

关于运筹学第二单纯形法第一页，共七十三页，2022年，8月28日1一、基础定理定理1若线性规划问题存在最优解，则问题的可行域是凸集。定理2线性规划问题的基本可行解对应线性规划问题可行域（凸集）的顶点。定理3若线性规划问题最优解存在，则最优解一定在可行域顶点处取得。由此可看出，最优解要在基本可行解（可行域顶点）中找。第二页，共七十三页，2022年，8月28日2

若LP问题有最优解的话，定在可行域的某顶点处达到，又，一个顶点对应一个基本可行解，一个自然的想法是：找出所有的基本可行解。因基本可行解的个数有限，通过“枚举法”，从理论上讲总能找出所有的基本可行解。而事实上随着m，n的增大，解的个数迅速增大，致使此路行不通。第三页，共七十三页，2022年，8月28日3换一种思路：若从某一基本可行解（今后称之为初始基本可行解）出发，每次总是寻找比上一个更“好”的基本可行解，逐步改善，直至最优。这需要解决以下三个问题：1.如何找到一个初始的基本可行解。2.如何判别当前的基本可行解是否已达到了最优解。3.若当前解不是最优解，如何去寻找一个改善了的基本可行解。第四页，共七十三页，2022年，8月28日4定义：如何从一个可行基找另一个可行基？称基变换。定义：两个基本可行解称为相邻的，如果它们之间仅变换一个基变量。对应的基称为相邻可行基。例LP问题二、思路解析第五页，共七十三页，2022年，8月28日5当前可行基{}所对应的基本可行解显然不是最优。因为从经济意义上讲，意味着该厂不安排生产，因此没有利润。相应地，将代入目标函数得从数学角度看，若让非基变量取值从零增加，(对应可行域的)第六页，共七十三页，2022年，8月28日6相应的目标函数值Z也将随之减少。因此有可能找到一个新的基本可行解，使其目标函数值有所改善。即进行基变换，换一个与它相邻的基。再注意到前的系数－2比

前的系数－1小，即每增加一个单位对Z的贡献比大。故应让从非基变量转为基变量，称为进基。又因为基变量只能有三个，因此必须从原有的基变量中选一个离开基转为非基变量，称为出基。谁出基？第七页，共七十三页，2022年，8月28日7又因为仍留作非基变量，故仍有（2）式变为再让从零增加，能取得的最大值为此时，已经从24降到了0，达到了非基的取值，变成非基变量。从而得到新的可行基。由此得到一个新的基本可行解：第八页，共七十三页，2022年，8月28日8目标函数值：从目标函数值明显看出，比明显地得到了改善。此基本可行解对应可行域的将（2）式（2）可行基留在左边，非基变量移到右边第九页，共七十三页，2022年，8月28日9（3）用代入法得：（4）第十页，共七十三页，2022年，8月28日10代入目标函数得：这一过程用增广矩阵的行初等变换表示为：×1/6×（-1）×（2）按最小非负比值规则：主元素第十一页，共七十三页，2022年，8月28日11目标函数系数行按最小非负比值规则：第十二页，共七十三页，2022年，8月28日12×3/2×（-5）×（-1/3）×（1/3）第十三页，共七十三页，2022年，8月28日13所对应的LP问题第十四页，共七十三页，2022年，8月28日14可行基令非基变量为0，得到最优解最优值：第十五页，共七十三页，2022年，8月28日15总结：①在迭代过程中要保持常数列向量非负，这能保证基可行解的非负性。最小比值能做到这一点。②主元素不能为0。因为行的初等变换不能把0变成1。③主元素不能为负数。因为用行的初等变换把负数变成1会把常数列中对应的常数变成负数。此基本可行解对应可行域的其结果与图解法一致。第十六页，共七十三页，2022年，8月28日16例2解LP问题：对单纯形矩阵作初等行变换，有：按最小非负比值原则：确定主元素。×（-1）×（1）1、无穷多个解三、其他解的情况第十七页，共七十三页，2022年，8月28日17至此，检验行已没有负数，当前解即为最优解。此时对应的LP问题为：0第十八页，共七十三页，2022年，8月28日18此时对应的LP问题为：0第十九页，共七十三页，2022年，8月28日19此时对应的LP问题为：01第二十页，共七十三页，2022年，8月28日20当时，不管取何值，均有目标函数取得最大值1。此时约束方程为：其中为基变量。用非基变量表示出基变量：其中，为自由变量。设为有:其中c是满足非负性的任意常数。第二十一页，共七十三页，2022年，8月28日21再由的非负性，知：解出（其中）最优解为：最优值为：第二十二页，共七十三页，2022年，8月28日222、无最优解的两种情况：⑴无界解例3解LP问题：解：对单纯形矩阵作初等行变换，有：第二十三页，共七十三页，2022年，8月28日23×1/2×（2）注意到－6所在的列无正元素，将基变量及目标函数用非基变量表示为第二十四页，共七十三页，2022年，8月28日24从目标函数看，若令非基变量无限增大，Z也无限性，即该LP问题所追求的目标函数是无界的，即无最小值，于是该LP问题无最优解。减小，且没有影响的非负第二十五页，共七十三页，2022年，8月28日25⑵无可行解例4求解LP问题解：可行域为空集，无可行解。第二十六页，共七十三页，2022年，8月28日26下面先把此LP问题化为标准型，然后用单纯形法求解。对单纯形矩阵作初等行变换，有：第二十七页，共七十三页，2022年，8月28日27×1/2从最后一个矩阵可看出，此LP问题无可行基，当然就无可行解。×（-1）×（-1）×（1）第二十八页，共七十三页，2022年，8月28日28LP当前解已是最优的四大特征：⑴存在一组(初始)可行基（其系数矩阵为单位阵）。⑵检验行的基变量系数=0。⑶检验行的非基变量系数≥0。全部〉0⇒唯一解。存在=0⇒无穷多个解。⑷常数列向量≥0。下面的问题是：所给LP的标准型中约束矩阵中没有现成的可行基怎么办？第二十九页，共七十三页，2022年，8月28日29人工变量法（也称大M法）针对标准形约束条件的系数矩阵中不含单位矩阵的处理方法。例6用单纯形法求解LP问题

单纯形的进一步讨论第三十页，共七十三页，2022年，8月28日30解：先将其化为标准形式再强行加上人工变量，使其出现单位矩阵：第三十一页，共七十三页，2022年，8月28日31但这样处理后：①不易接受。因为是强行引进，称为人工变量。它们与不一样。称为松弛变量和剩余变量，是为了将不等式改写为等式而引进的，而改写前后两个约束是等价的。②人工变量的引入一般来说是前后不等价的。只有当最优解中，人工变量都取值零时（此时人工变量实质上就不存在了）才可认为它们是等价的。处理办法：把人工变量从基变量中赶出来使其变为非基变量。为此，发明者建议把目标函数作如下处理：第三十二页，共七十三页，2022年，8月28日32其中M为任意大的实数，“M”称为“罚因子”。用意：只要人工变量取值大于零，目标函数就不可能实现最优。对此单纯形矩阵作初等行变换，有：第三十三页，共七十三页，2022年，8月28日33×－M×－M×（-1）×（-3）×（4M）×1/6第三十四页，共七十三页，2022年，8月28日34×3/2×（-1/3）×（3）第三十五页，共七十三页，2022年，8月28日35至此，检验行已没有负数，当前解即为最优解。最优值为：去掉人工变量，即得原LP问题的最优解：第三十六页，共七十三页，2022年，8月28日36⑴

最优解判别定理：所有检验数≥0；人工变量为0⑵

无穷多最优解判别定理：所有检验数≥

0；人工变量为0；存在某个非基变量的检验数为0⑶

无可行解判别：所有检验数≥

0；人工变量≠0(4)无界解判别定理：有一个非基变量的检验数＜0,但该数对应的列中没有正元素；人工变量为0解的判别定理：第三十七页，共七十三页，2022年，8月28日37单纯形法步骤一、构造初始可行基1、引入附加变量，化为标准型2、必要时引入人工变量3、目标函数中，附加变量系数为0，人工变量则为M二、求基本可行解1、用非基变量表示基变量和目标函数式2、求出一个基本可行解及相应Z值三、最优性检验依据:检验数及判别定理四、基变换1、换入基的确定：检验数负值中最小的2、换出基的确定：最小非负比值规则返回步骤二第三十八页，共七十三页，2022年，8月28日382.2单纯形法的表格形式

书例2.1P18第三十九页，共七十三页，2022年，8月28日39作业P791.3（2），1.7（1）第四十页，共七十三页，2022年，8月28日40大M法目标是尽快把人工变量从基变量中全部“赶”出去（如果能全部“赶”出去的话）。所用方法除了大M法外，还有下面的两阶段法。

两阶段法用大M法处理人工变量时，若用计算机处理，必须对M给出一个较大的具体数据，并视具体情况对M值作适当的调整。为了克服这一麻烦，下面的两阶段法将问题拆成两个LP问题分两个阶段来计算：2.3大M法和两阶段法第四十一页，共七十三页，2022年，8月28日41两阶段法的第一阶段求解一个目标中只包含人工变量的LP问题，即令目标函数中其它变量的系数取零，人工变量的系数取某个正的常数（一般取1），在保持原问题约束不变的情况下求这个目标函数极小化的解。显然在第一阶段中，当人工变量取值为0时，目标函数值也为0。这时候的最优解就是原问题的一个基可行解。如果第一阶段求解结果最优解的目标函数值不为0，也即最优解的基变量中含有非零的人工变量，表明原LP问题无可行解。第四十二页，共七十三页，2022年，8月28日42第二阶段：求解原线性规划问题的最优解。以第一阶段的最终单纯形表为基础，去掉人工变量，目标函数换为原问题的目标函数，得到第二阶段的初始表，继续迭代求解。第四十三页，共七十三页，2022年，8月28日43⑴若求得的单纯形矩阵中，所有人工变量都处在非基变量的位置。即及。则从第1阶段去掉人工变量后，即为原问题的初始单纯形矩阵。并进入第2阶段。第一阶段求解第一个线性规划：第四十四页，共七十三页，2022年，8月28日44⑵若第一阶段所求得的单纯形中仍含有（解）非零的人工变量，则说明原问题无可行解。不再进入第2阶段。因此两阶段法的第1阶段求解有两个目的：一为判断原问题有无可行解。二，若有，则得原问题的一个初始可行基，再对原问题进行第2阶段的计算。第四十五页，共七十三页，2022年，8月28日45对单纯形矩阵作初等行变换，有：例：第1阶段：第四十六页，共七十三页，2022年，8月28日46×（-1）×（-1）第四十七页，共七十三页，2022年，8月28日47×（-3）×（4）×1/6×（-1）第四十八页，共七十三页，2022年，8月28日48×（-3）×（6）×2转入第2阶段：3-1×（-3）第四十九页，共七十三页，2022年，8月28日49×3/2×（-1/3）×（3）第五十页，共七十三页，2022年，8月28日50书例：表格形式大M法:P25表2.2.1两阶段法:P27表；第五十一页，共七十三页，2022年，8月28日51作业P801.8（1）第五十二页，共七十三页，2022年，8月28日522.4退化问题退化问题：按最小比值θ来确定换出基变量时，有时出现两个以上相同的最小比值，从而使下一个表的基可行解中出现一个或多个基变量等于零的退化解。循环问题：退化解出现的原因是模型中存在多余的约束，使多个基可行解对应同一个顶点。当存在退化解时，就有可能出现迭代计算的循环。即从一个可行基经有限次迭代后又回到原来的可行基。尽管可能性及其微小（直到目前为止，还没有见到一个实际应用问题产生循环的例子），但在理论上讲是存在的。第五十三页，共七十三页，2022年，8月28日53E.Beale曾给出一个循环的例子这个例子用单纯形法经过6次迭代后，又回到了初始状态，得不到最优解。有兴趣的同学可自行用单纯形法验证本题产生的循环现象。而实际上本题有最优解。解决方法：摄动法；勃兰特法。第五十四页，共七十三页，2022年，8月28日542.5改进单纯形法单纯形法计算的特点是每迭代一次，就要把整个单纯形表重新计算一遍。从计算机的角度来讲，单纯形法并不是一种经济高效的方法。首先是要占用大量的存贮空间，其次，由于每次计算都利用上一次的单纯形表，当计算次数较多时，容易造成误差的积累，直接影响计算精度和收敛速度。改进单纯形法的基本计算步骤和单纯形法基本相同，但在上述两方面有所改进。第五十五页，共七十三页，2022年，8月28日55在单纯形法的迭代过程中，我们实际需要的只有以下各项：1、检验数,以判断是否最优或确定换入基变量。2、换入变量所在列的各元素和基变量的值，根据决定换出基变量。第五十六页，共七十三页，2022年，8月28日56

Minz

=

CX

s.t.

AX=b

X

≥0单纯形法的矩阵形式第五十七页，共七十三页，2022年，8月28日57第五十八页，共七十三页，2022年，8月28日58第五十九页，共七十三页，2022年，8月28日59在单纯形法的矩阵形式中我们可以发现，单纯形表中的其它数字可利用和原始系数进行运算直接得到：这就是改进单纯形法的出发点。令向量Y表示，即称其为单纯形乘子。第六十页，共七十三页，2022年，8月28日60求解步骤1、第0次迭代：初始可行基检验数如不是最优解，确定换入基，换出基。

2、计算：三种方法

3、计算第i＋1次迭代的常数列和检验数

4、最优性检验：如最优，结束。否则下一步。

5、计算第i＋1次迭代中的换入列

6、确定第i＋1次迭代中换出基的下标，返回步2。①初等变换法②取主变换③逆的乘积形式第六十一页，