运筹学 (单纯形法原理)课件

1、运筹学 (单纯形法原理),复习 由图解法得到的启示：,1.求解线性规划问题时，解的情况有：唯一解；无穷多最优解；无界解；无可行解。,2.若线性规划问题的可行域存在，则可行域是一个凸集。,3.若线性规划问题的最优解存在，则最优解或最优解之一（有无穷多最优解）一定是可行域的凸集的某个顶点。,4.解题思路是，先找出凸集的任一顶点，计算在顶点处的目标函数值。比较周围相邻顶点的目标函数值是否比这个值大，如果为否，则该顶点就是最优解的点或最优解的点之一，否则转到比这个点的目标函数值更大的另一顶点，重复上述过程，一直到找出使目标函数值达到最大的顶点为止。,运筹学 (单纯形法原理),单纯形法的计算步骤,单纯形

2、法的思路,找出一个初始可行解,是否最优,转移到另一个基本可行解 （找出更大的目标函数值）,最优解,是,否,循 环,核心是：变量迭代,结束,如何改善？ 如何判断没有有限最优解？,运筹学 (单纯形法原理),线性规划问题的代数运算形式,例：用单纯形法的代数运算形式求解下列线性规划问题,运筹学 (单纯形法原理),求解步骤,（1）化为标准型,（2）找一个初始基本可行解X（0）,运筹学 (单纯形法原理),B0为一个可行基， x3 、 x4 、 x5为关于可行基B0的基变量， x1 、 x2 为关于可行基B0的非基变量，为求初始基本可行解，令非基变量x1 = x2 =0。从而有x3 =12， x4 =16，

3、 x5 =15，于是得到初始基本可行解：,X （0） =（0，0，12，16，15） T,其对应的目标函数值,z0=20+30=0,（3）检验X（0）是否为最优解。由目标函数的表达式：,z =2x1 +3x2,可知，非基变量x1 和 x2 的系数为正，如果把非基变量x1 或x2转换为基变量，则会使目标函数的值增加。可见 X（0）不是最优解,运筹学 (单纯形法原理),（4）第一次迭代。,每一次迭代，得到一个新的基本可行解。因此，哪些变量作为基变量，哪些非基变量，就要发生变化。,由于目标函数中x2的系数大于x1的系数，因此，可以选择x2使它作为基变量，而且让它取尽可能大的值，同时， x1仍作为非基

4、变量取值为零。从原来的基变量x3 、 x4 、 x5中选出一个作为非基变量。 x2的取值不能任意地增加，它要受到约束方程的限制：,2x1 +2x2 + x3 = 12 4x1 + x4 = 16 5x2 + x5 = 15,x3 = 12 2x1 2x2 x4= 16 4x1 x5 = 15 5x2,运筹学 (单纯形法原理),将x1 = 0， x2 = 代入上面约束方程，为了让取尽可能大的值，同时又要考虑到x3 、 x4 、 x5必须满足非负约束，从而的值应满足：,x3 = 12 2 0 x4 = 16 0 x5 = 15 5 0,即：,x2 = =min12/2，15 /5=3,相应地有：,

5、x3 = 12 2 3=6 x4 = 16 x5 = 15 5 3=0,可见，从原来的基变量x3 、 x4 、 x5中选出x5作为非基变量，得第一次迭代后的基本可行解：,X （1） =（0，3，6，16，0） T,运筹学 (单纯形法原理),其对应的目标函数值：,z1=20+33=9,（5）检验X （1） 是否为最优解,将约束方程组改为用非基变量x1 、 x5来表示基变量x2、 x3 、 x4的表达式。可用高斯消去法得到：,2x1 + x3 2 /5x5 = 6 4x1 + x4 = 16 x2 + 1 /5 x5 = 3,移项后得到：,x3 = 6 2x1 + 2/5x5 x4 = 16 4x

6、1 x2 = 3 1/5 x5,运筹学 (单纯形法原理),将上式代入目标函数，得目标函数用非基变量x1 、 x5表示的表达式,z =9+2x1 3/5x5,由于非基变量x1的系数是正数，如果把非基变量转换为基变量，则会使目标函数的值增加。可见X （1）不是最优解。,（6）第二次迭代,和第一次迭代同样的道理，应选取非基变量x1使它成为基变量，而且让它取尽可能大的值，同时， x5仍作为非基变量取值为零。从原来的基变量x2 、 x3 、 x4中选出一个作为非基变量。 x1的取值也按同样的方法确定：,x3 = 6 2x1 + 2/5x5 x4 = 16 4x1 x2 = 3 1/5 x5,将x1 =

7、， x5 = 0代入：,x3 = 6 2 0 x4 = 16 4 0 x2 = 3 0,运筹学 (单纯形法原理),即：,x1 = =min6/2，16 /4 ，=3,相应地有：,可见，从原来的基变量x2 、 x3 、 x4中选出x3作为非基变量，得第二次迭代后的基本可行解：,X （2） =（3，3，0，4，0） T,x3 = 6 2 3 =0 x4 = 16 4 3=4 x2 = 3,其对应的目标函数值：,z1=23+33=15,（7）检验X （2） 是否为最优解,运筹学 (单纯形法原理),将约束方程组改为用非基变量x3 、 x5来表示基变量x1、 x2 、 x4的表达式。可用高斯消去法得到：

8、,x1 + 1/2 x3 1/5x5 = 3 2 x3 + x4 + 4/5x5 = 4 x2 + 1/5 x5 = 3,移项后得到：,x1 = 3 1/2 x3 + 1/5x5 x4 = 4 + 2 x3 4/5x5 x2 = 3 1/5 x5,将上式代入目标函数，得目标函数用非基变量x3 、 x5表示的表达式,z =15 x3 1/5x5,这时,目标函数中非基变量的系数都不大于零，可见目标函数的值不可能再继续增大,目标函数已经取得最大值15 ，故为X （2）最优解。,运筹学 (单纯形法原理),总 结,通过以上例题的分析，可以归纳出单纯形法的步骤：,（1）建立实际问题的线性规划数学模型；,（

9、2）把一般的线性规划问题化为标准型；,（3）确定初始基本可行解；,（4）检验所得到的基本可行解是否为最优解；,（5）迭代，求得新的基本可行解。,单纯形法的三个关键部分：,（1）初始基本可行解的确定；,（2）最优性检验；,（3）如何进行迭代: 确定入基变量,出基变量,运筹学 (单纯形法原理),单纯形法一般步骤,1.初始基本可行解的确定（观察法）；,基本可行解,基,运筹学 (单纯形法原理),2.从约束中解出基变量；,运筹学 (单纯形法原理),3.代入目标消去基变量，得到非基变量xj的检验数 j,运筹学 (单纯形法原理),4.判断最优； 最优性判别定理：若 是对应于B的基本可行解， j是用非基变量表

10、示目标函数的表达式 中非基变量xj的检验数，若对于一 切非基变量的角指数j均有j 0 则当前基本可行解为最优解。,对于任意可行解X，,对于基本可行解X0，,无穷多最优解的判定?,若对于一 切非基变量的角指数j均有j 0, 并且存在一个j =0, 则线性规划问题有无穷多最优解,运筹学 (单纯形法原理),5.没有有限最优解的判断； 无最优解判别定理：若 是对应于B的基本可行解， 非基变量x k的检验数k 0 , 且对于i=1,2,m 均有aik 0, 则原问题没有有限最优解。,该证明留作课后练习,运筹学 (单纯形法原理),6.改进目标 若k 0，则选xk进基; 用最小比值法确定xk的最大值， 使基

11、变量xl取0值，其它基变量非负；,即xl出基，换基过程 若不存在, 则Z，没有有限最优解。,运筹学 (单纯形法原理),7.主元变换（枢变换或旋转变换） xk进基， xl出基，解出新的基变量,运筹学 (单纯形法原理),表格单纯形法,标准型：,运筹学 (单纯形法原理),表格单纯形法,标准型：,运筹学 (单纯形法原理),表格单纯形法,运筹学 (单纯形法原理),表格单纯形法,基变量,检验数,最小比值列,基变量系数,右端常数,运筹学 (单纯形法原理),表格单纯形法,例5 用单纯形法求解线性规划问题,解 先将上述问题化成标准形式有,运筹学 (单纯形法原理),表1-7,运筹学 (单纯形法原理),运筹学 (单纯形法原理),练习2：求解线