《运筹学》单纯形算法.ppt

《《运筹学》单纯形算法.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、二、线性规划问题的图解法对于简单的线性规划问题(只有两个决策变量的线性规划问题)，我们可以通过图解法对它进行求解。我们以例1－1具体给出求解的方法。例1－5用图解法求解线性规划问题maxZ=2x1+3x2解：对于上述具有两个变量的线性规划问题，图1-2中的OABCD部分描述了满足约束条件的区域；虚线为目标函数Z=2x1+3x2的等值线。沿箭头方向移动目标函数的等值线，平移等值线直至与可行域OABCD相切或融合为一条直线，此时就得到最优解为B点，其坐标可通过解方程组得到：2x1+2x2=143x2=15解

2、得：x1=2x2=5这就是本线性规划问题的最优解。此时相应的目标函数的最大值为：Z=2×2+3×5=19例1－6用图解法求解线性规划问题maxZ=40x1+80x2s.t.x1+2x2303x1+2x2602x224x1,x20解：如图1－3所示：求解最优解：BC线段B点X(1)=(6,12)；C点X(2)=(15,7.5)X=X(1)+(1-)X(2)(01)maxZ=1200即x1=6+(1-)·15x2=12+(1-)·7.5整理得：x1=15-9x2=7.5+4.5

3、(01)例1－7maxZ=2x1+4x2s.t.2x1+x28-2x1+x22x1，x20解：由于可行域无界，作目标函数等值线，如图1－4中虚线所示，并用箭头标出其函数值增加的方向，由此可以看出，该问题无有限最优解。若目标函数由maxZ=2x1+4x2改为minZ=2x1+4x2,则可行解所在的范围虽然无界，但有最优解x1=4，x2=0，即(4,0)点。通过以上各题图解法所得结论可以看出：（1）线性规划的所有可行解构成的可行域一般是凸多边形，有些可行域可能是无界的；（2）若存在最优解，则一定

4、在可行域的某顶点得到；（3）若在两个顶点上同时得到最优解，则在这两点的连线上的任一点都是最优解。（4）若可行域无界，则可能发生最优解无界的情况；（5）若可行域是空集，此时无最优解。上述理论具有普遍意义，对于两个以上变量的线性规划问题都是成立。图解法虽然具有直观、简便等优点，但在变量多的情况下，即在多维的情况下，它就无能为力了。因此，需要介绍一种代数方法——单纯型法，为了以后介绍方便，需要研究一下线性规划问题解的概念。三、基本定理1.凸集：假设K是n维欧氏空间的一个点集，若对于K中的任意两点X1、X2，其

5、连线上的所有点X1+(1-)X2，(01)都在集合K中，即：X1+(1-)X2K(01)则称K为凸集。从直观上讲，凸集无凹入部分，其内部没有洞。如实心圆、实心球、实心立方体等都是凸集。两个凸集的交集仍是凸集。2.凸组合：设X1，X2，···，Xk是n维欧氏空间En中的k个点，若存在1，2，···，k，且0i1，i=1,2,···,k，i=1，使X=1X1+2X2+···+kXk，则称X为由X1，X2，···，Xk所构成的凸组合。按照定义，凡是由x，y的凸组合表

6、示的点都在x，y的连线上，而且反之亦然。3.顶点：假设K是凸集，XK；X若不能用不同的两个点X1、X2K的线性组合表示为：X=X1+(1-)X2，(0<<1)则称X为凸集K的一个顶点（或称为极点）。顶点不位于凸集K中的任意不同两点的连线内。定理1.1若线性规划问题存在可行域，则其可行域：D={X

7、AX=b,X0}，是凸集。引理1.1线性规划问题的可行解X为基本可行解的充要条件是X的正分量所对应的系数列向量是线性无关的。定理1.2线性规划问题的基本可行解对应于可行域的顶点。定理1.3若可行域有

8、界，则线性规划问题的目标函数一定可以在其可行域的顶点上达到最优解。定理1.4若线性规划问题在k个顶点上达到最优解（k2），则在这些顶点的凸组合上也达到最优解。根据以上讨论得到如下的结论：（1）线性规划问题的所有可行解的集合一般是凸集，它可以是有界的，也可以是无界的区域；仅有有限个顶点。(2)线性规划问题的每一个基本可行解对应于可行域的一个顶点。若线性规划问题有最优解，必定可在某顶点处取到。(3)如果一个线性规划问题存在多个最优解，那么至少有两个相邻的顶点处是线性规划的最优解。虽然可行域的顶点个数是有限

9、的(它们不超过Cnm个)，采用“枚举法”可以找出所有基本可行解，然后一一比较它们的目标函数值的大小，最终可以找到最优解。但当m、n的数目相当大时，这种办法实际上是行不通的。因此，我们还要继续讨论一种方法，通过逐步迭代保证能逐步改进并最终求出最优解。第三节单纯形算法单纯形算法的基本思路是：根据问题的标准型，从可行域中某个基本可行解(顶点)开始，转换到另一个基本可行解(顶点)，并使得每次的转换，目标函数值均有所改善，最终达到最大值时就得到最优解