线性规划单纯形法经典运筹学

1、上堂课的主要内容：1、线性规划的标准形式12. 线性规划问题的矩阵表达式：23、图解法的基本步骤：（一般是一个凸多边形）注意：若是求目标函数的最小值，目标函数直线向下移动34、线性规划解的结论：1、若（LP）问题有可行解，则可行域是一个凸多边形（或凸多面体）。它可能是有界的；也可能是无界的。2、若（LP）问题有最优解，则最优解可能是唯一的；也可能 是无穷多个。如果是唯一的，这个解一定在该凸多边形的某 个顶点上；如果是无穷多个，则这些最优解一定充满凸多边 形的一条边界（包括此边界的两个顶点）总之，若（LP）问题有最优解，则最优解一定可以在凸多边形的某个顶点达到3、若（LP）问题有可行解，但没有有

2、限最优解，此时凸多边形 是无界的（反之不成立）4、若（LP）问题没有可行解，则该问题没有最优解4定义1.3 在（LP）问题中，A的任意一个mm阶 的非奇异子方阵B（即|B|0）称为 （LP）问题的一个基设r(A)=m0基本可行解退化基本可行解：基本可行解中，存在取0值的基变量非退化基本可行解：基本可行解中，基变量的取值均0对应的基称为退化基对应的基称为非退化基线性规划问题：存在退化基：所有基均非退化m8若有可行解，则可行域是一个凸多边形若（LP）问题有最优解，则最优解一定可以在凸多边形的某个顶点达到基本可行解与可行域的顶点的关系?90结论:1.可行域为一个凸集2.凸集上有5个顶点3.最优解在顶

3、点产生基的个数=10基的个数=9基本可行解的个数=基的个数最优解10基本可行解0.凸多边形的顶点最优解11基本可行解0.120.该基本解不是基本可行解不在可行域中13基本可行解0.14基本可行解0.15基本可行解0.160.结论:顶点基本可行解17总结:1.若（LP）问题有可行解，则可行域是一个凸多边形2.若（LP）问题有最优解，则最优解一定可以在凸多边 形的某个顶点达到4.基本可行解的个数是有限的3.顶点与基本可行解是一一对应的若（LP）问题有最优解，则最优解一定可以在某个 基本可行解达到找最优解可从一个基本可行解入手，通过某种方法，调整基变量，转到另一个基本可行解，并使目标函数值不断增大，

4、通过有限次的迭代就能找到最优解单纯形法181.4单纯形法19单纯形法的基本思路：1、找出一个可行基，并得到一个基本可行解2、检验该基本可行解是否是最优解，即目标函数值 是否最大，或看看是否存在目标函数值比它大的 基本可行解3、换一个目标函数值比他大的基本可行解4、重复以上步骤，直至找不到更好的基本可行解2021第一步：寻找第一个基本可行解（初始基本可行解）22X0为基本可行解对应目标函数值三、换基迭代23取做非基变量24825五、循环迭代出基变量的确定：261.5105.530最优解27第一步：寻找初始基本可行解第三步：换基迭代（2）确定出基变量：28（2）确定出基变量：三、换基迭代在第4个方

5、程五、循环迭代：2930单纯形法的基本思想：（1）入基变量：设ck=maxci | ci 0,取xk为入基变量 得到新的非基变量目标函数表示成新非基变量的函数，4、把约束方程化为每个方程只含一个新的基变量令非基变量取零的一新的基本可行解X（2）出基变量：1、找到一个基本可行解X此时的约束方程每个方程只含一个基变量目标函数必须表示成非基变量的函数2、判断X是否为最优解：若目标函数中有非基变量的系数ci0,则X不是最优解。3、换基迭代31常数项2 3 1 0 0 0 6-3 2 0 1 0 0 30 2 0 0 1 0 52 1 0 0 0 1 4基变量4 3 0 0 0 0 z单纯形表主元素b1

6、 0.5 0 0 0 0.5 20 2 1 0 0 -1 20 3.5 0 1 0 1.5 90 2 0 0 1 0 50 1 0 0 0 -2 z-8检验行32b1 0.5 0 0 0 0.5 20 2 1 0 0 -1 20 3.5 0 1 0 1.5 90 2 0 0 1 0 50 1 0 0 0 -2 z-8b0 1 0.5 0 0 -0.5 10 0 -1.75 1 0 3.25 5.5 0 0 -1 0 1 1 31 0 -0.25 0 0 0.75 1.50 0 -0.5 0 0 -1.5 z-9为最优解33常数项 4 1 0 0 0 Z -1 1 1 0 0 21 -4 0 1

7、 0 41 -2 0 0 1 848341 -4 0 1 0 4 0 -3 1 1 0 60 2 0 -1 1 4 0 17 0 -4 0 Z-16 1 0 0 -1 2 12 0 0 1 -1/2 3/2 120 1 0 -1/2 1/2 2 0 0 0 9/2 -17/2 Z-48 无界!常数项 4 1 0 0 0 Z -1 1 1 0 0 21 -4 0 1 0 41 -2 0 0 1 848351 0 0 -1 2 12 0 0 1 -1/2 3/2 120 1 0 -1/2 1/2 2 0 0 0 9/2 -17/2 Z-48 对应的线性规划问题无界所以，该线性规划问题无界363、将

8、约束方程化为每个方程只含一个基变量 目标函数表示成非基变量的函数 单纯形法步骤：1、化标准型 2、选定一个可行基，并得一基本可行解X？5、判断X是否为最优解：若目标函数行中所有检验数ci0, 则X为 最优解。若存在某个cj0,且所有的aij 0,取xk为入基变量 （2）出基变量： 7、对单纯形表做初等行变换：把基变量对应的列化为 单位向量，目标函数的基变量系数化为零，得一新的基本可行解X。转第4步37可行典则形式38不是单纯形表初始单纯形表 1 0 0 2 2 z-10 11 0 0 0 8 z+50 39典则形式b 4 2 0 0 0 z2 1 0 1 0 42 5 1 0 0 12-1 1

9、 0 0 1 2 6 2b 0 0 0 -2 0 z-81 0.5 0 0.5 0 20 4 1 -1 0 80 1.5 0 0.5 1 4b 0 0 0 -2 0 z-8 1 0 -0.125 0.125 0 1 0 1 0.25 0.25 0 2 0 0 -0.375 0.375 0 1 40本题说明：1、最优解不唯一，但最优值唯一3、在实际应用中，有多种方案可供选择41单纯形法的矩阵形式：42B 可逆43关于可行基B的典则形式44=一个数Z0常数45行向量检验数4647初始单纯形表的矩阵形式：设B为一个可行基B的典则形式为：E0常数项48E0常数项0最优值 最优单纯形表49设B为一个可行

10、基B的典则形式为定理1.7 对非退化线性规划问题，单纯形法必然在有限次迭代内终止于下述两种情况之一：或者找到一个最优基本可行解；或者判断该问题无界。50练习:用单纯形法求下列线性规划问题的解：无界，即无最优解51b 4 3 0 0 0 z5 2.5 0 1 0 25002 2 1 0 0 16001 0 0 0 1 400800500400b1 0 0 0 1 4000 2.5 0 1 -5 500 0 2 1 0 -2 8000 3 0 0 -4 z-1600400200b0 1 0 0.4 2. 2001 0 0 0 1 4000 0 1 -0.8 2 4000 0 0 -1.2 2 z-2200b2004000 0 0.5 -0.4 1 2000 1 1 -0.4 0 6001 0 -0.5 0.4 0 2000 0 -1 0.4 0 z-260052b-1 1 1 0 0 2