〔2〕无界解
如果有如下线性规划问题：
maxz?x1?x2??2x1?x2?4 ??x1?x2?2?x,x?0?12x2 4 ?2x1?x2?4 x1?x2?2
x1 从图中可以看出，这个线性规划的可行域是无界的，目标函数等值线在目标值增大方向上可以无限制地平移都不会超过可行域，目标函数值可以趋于无穷大，目标函数值无上界，这种线性规划问题有可行解，但无最优解，称为无界解或无有限最优解。出现这种情况一般是建立模型遗漏某些约束条件造成的。
〔3〕无可行解
如果有下列线性规划问题 x2
x1?2x2?14 maxz?2x?3x12?2x1?2x2?12??x1?2x2?14?x,x?0?12
x1 2x1?2x2?12
从图中可以看出，这几个约束条件不能形成一个公共区域，也就是说，可行域是空集，这个线性规划将没有可行解，也就没有最优解。出现这种情况主要是建模本身有错误，约束条件之间相矛盾。
注意的是，线性规划的求解结果情况，要将约束条件和目标函数求极值情况结合起来分析，如上面第1或2种情况，如果线性规划是求最小化问题，还是有唯一最优解，而不是多重解或无界解。
17
从线性规划的图解法，可以得出一个很重要的结论：线性规划有最优解，它一定是在可行域某个顶点(极点)得到，而不是在可行域内某个点，而可行域顶点数总是有限的，这就给求解带来了简便。可行域的顶点对应于基可行解。
如果在两个顶点得到最优解，则它们连线上任一点都是最优解，因而有多重解。
第三节 单纯形法
一.基本概念和基本定理 1. 基本概念
凸集 设K是n维欧氏空间的一点集，若任意两点X1?K,X2?K 的连线上的一切点?X1?(1??)X2?K,(0???1)；则称K为凸集。
凸组合 设X1,X2,?,Xk是n维欧氏空间En中的k个点，若存在
?1,?2,?,?k,且0??i?1,i?1,2,?,k;??i?1，使
i?1kX??1X1??2X2????KXK
则称X为X1,X2,?,Xk的凸组合。
顶点 设K是凸集，X?K；若X不能用不同的两点X1?K和
X2?K 的线性组合表示为
X＝?X1?(1??)X2?K,(0???1)
则称X为K的一个顶点(或极点)。 2. 基本定理：
定理1 若线性规划问题存在可行域，则其可行域
n??D??X?Pjxj?b,xj?0?是凸集。
?j?1?
18
引理1 线性规划问题的可行解X??x1,x2,?,xn?为基可行解的充要条件是X的正分量的系数列向量是线性独立的。
定理2 线性规划问题的基本可行解X对应于可行域D的顶点。 引理2 若K是有界凸集，则任何一点X?K可表示为K的顶点的凸组合。
定理3 若可行域有界，线性规划问题的目标函数一定可以在其可行域的顶点上达到最优。
结论：线性规划问题的所有可行解构成的集合是凸集，它有有限个顶点，线性规划问题的每个基可行解对应可行域的一个顶点；若线性规划问题有最优解，一定是在某个顶点上得到。 二.单纯形法原理
从前面的结论知道，线性规划的最优解一定是在可行域的极点上得到，这样就避免了从可行域中无穷多个点来寻找最优解，使得问题求解大为简单。而且可行域的每个极点又和基可行解一一对应。
所以，单纯形法求解思想就是先将线性规划问题化为标准型，求出一个基可行解，称为初始基可行解，再检验这个解是否最优(解的检验)，如果不是，则从这个初始基可行解开始，沿着凸集的边缘寻找下一个极点或基可行解（基变换），并判断得到的基可行解是否最优，如果是最优解，目标函数值达到最优值，计算结束，否则，在这个基础上，再继续寻找和判断，直到求出最优解。
从一个基可行解得到另一个基可行解，需要进行基变换。由于基可行解的数目是有限的，所以这样求下去总能得到最优解，但并不需要求出所有的基可行解。
下面通过一个简单例子来说明单纯形法的基本思想。
maxz?2x1?3x2Tmaxz?2x1?3x2?0x3?0x4?0x5?x1?2x2?x3?8?x1?2x2?8??例： 4x?16??4x1?x4?16?1s.t.?s.t.?4x?x5?12?2?4x2?12?xj?0j?1,2,?,5??x1、x2?0?
求基可行解，必须要找出一个基，从约束方程的系数矩阵中，可以看出，
19
?1?A??4?0?2041000100??0???p1,1??p2,p3,p4,p5?
基矩阵应是3×3阶，x3,x4,x5的系数列向量是单位向量，线性独立，构成一个单位阵，可作为一个基矩阵，即
?1?B??0?0?0100??0???p31??p4p5?
p3,p4,p5三个基向量对应的基变量是x3,x4,x5，非基变量是x1,x2，通过改写约束方程，将基变量用非基变量表示，
?x3?8?x1?2x2? 令非基变量x1?x2?0，可得到一个基可行?x4?16?4x1?x?12?4x2?5解：X?0???0,0,8,16,12?，将上式代入目标函数，得，
Tz?0?2x1?3x2，相应的目标值为Z＝0。
显然，这个解不是最优解，工厂的利润为0(两种产品没有安排生产，x1?x2?0)。
对z?0?2x1?3x2进行分析，可以看到，非基变量x1,x2的系数为正，如果安排任意一种产品的生产都可以使目标值增大，使得工厂的利润增大，也就是要使变量x1或x2的取值由零变成一个正值，由非基变量变成基变量。
所以，在目标函数中只要还有正系数的非基变量，目标值就还有
20
相关推荐：
loading