运筹学 (单纯形法原理)

.,复习由图解法得到的启示：,1.求解线性规划问题时，解的情况有：唯一解；无穷多最优解；无界解；无可行解。,2.若线性规划问题的可行域存在，则可行域是一个凸集。,3.若线性规划问题的最优解存在，则最优解或最优解之一（有无穷多最优解）一定是可行域的凸集的某个顶点。,4.解题思路是，先找出凸集的任一顶点，计算在顶点处的目标函数值。比较周围相邻顶点的目标函数值是否比这个值大，如果为否，则该顶点就是最优解的点或最优解的点之一，否则转到比这个点的目标函数值更大的另一顶点，重复上述过程，一直到找出使目标函数值达到最大的顶点为止。,.,单纯形法的计算步骤,单纯形法的思路,找出一个初始可行解,是否最优,转移到另一个基本可行解（找出更大的目标函数值）,最优解,是,否,循环,核心是：变量迭代,结束,如何改善？如何判断没有有限最优解？,.,线性规划问题的代数运算形式,例：用单纯形法的代数运算形式求解下列线性规划问题,.,求解步骤,（1）化为标准型,（2）找一个初始基本可行解X（0）,.,B0为一个可行基，x3、x4、x5为关于可行基B0的基变量，x1、x2为关于可行基B0的非基变量，为求初始基本可行解，令非基变量x1=x2=0。从而有x3=12，x4=16，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仍作为非基变量取值为零。从原来的基变量x3、x4、x5中选出一个作为非基变量。x2的取值不能任意地增加，它要受到约束方程的限制：,2x1+2x2+x3=124x1+x4=165x2+x5=15,x3=122x12x2x4=164x1x5=155x2,.,将x1=0，x2=代入上面约束方程，为了让取尽可能大的值，同时又要考虑到x3、x4、x5必须满足非负约束，从而的值应满足：,x3=1220 x4=160 x5=1550,即：,x2=min12/2，15/5=3,相应地有：,x3=1223=6x4=16x5=1553=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+x32/5x5=64x1+x4=16x2+1/5x5=3,移项后得到：,x3=62x1+2/5x5x4=164x1x2=31/5x5,.,将上式代入目标函数，得目标函数用非基变量x1、x5表示的表达式,z=9+2x13/5x5,由于非基变量x1的系数是正数，如果把非基变量转换为基变量，则会使目标函数的值增加。可见X（1）不是最优解。,（6）第二次迭代,和第一次迭代同样的道理，应选取非基变量x1使它成为基变量，而且让它取尽可能大的值，同时，x5仍作为非基变量取值为零。从原来的基变量x2、x3、x4中选出一个作为非基变量。x1的取值也按同样的方法确定：,x3=62x1+2/5x5x4=164x1x2=31/5x5,将x1=，x5=0代入：,x3=620 x4=1640 x2=30,.,即：,x1=min6/2，16/4，=3,相应地有：,可见，从原来的基变量x2、x3、x4中选出x3作为非基变量，得第二次迭代后的基本可行解：,X（2）=（3，3，0，4，0）T,x3=623=0 x4=1643=4x2=3,其对应的目标函数值：,z1=23+33=15,（7）检验X（2）是否为最优解,.,将约束方程组改为用非基变量x3、x5来表示基变量x1、x2、x4的表达式。可用高斯消去法得到：,x1+1/2x31/5x5=32x3+x4+4/5x5=4x2+1/5x5=3,移项后得到：,x1=31/2x3+1/5x5x4=4+2x34/5x5x2=31/5x5,将上式代入目标函数，得目标函数用非基变量x3、x5表示的表达式,z=15x31/5x5,这时,目标函数中非基变量的系数都不大于零，可见目标函数的值不可能再继续增大,目标函数已经取得最大值15，故为X（2）最优解。,.,总结,通过以上例题的分析，可以归纳出单纯形法的步骤：,（1）建立实际问题的线性规划数学模型；,（2）把一般的线性规划问题化为标准型；,（3）确定初始基本可行解；,（4）检验所得到的基本可行解是否为最优解；,（5）迭代，求得新的基本可行解。,单纯形法的三个关键部分：,（1）初始基本可行解的确定；,（2）最优性检验；,（3）如何进行迭代:确定入基变量,出基变量,.,单纯形法一般步骤,1.初始基本可行解的确定（观察法）；,基本可行解,基,.,2.从约束中解出基变量；,.,3.代入目标消去基变量，得到非基变量xj的检验数j,.,4.判断最优；最优性判别定理：若是对应于B的基本可行解，j是用非基变量表示目标函数的表达式中非基变量xj的检验数，若对于一切非基变量的角指数j均有j0则当前基本可行解为最优解。,对于任意可行解X，,对于基本可行解X0，,无穷多最优解的判定?,若对于一切非基变量的角指数j均有j0,并且存在一个j=0,则线性规划问题有无穷多最优解,.,5.没有有限最优解的判断；无最优解判别定理：若是对应于B的基本可行解，非基变量xk的检验数k0,且对于i=1,2,m均有aik0,则原问题没有有限最优解。,该证明留作课后练习,.,6.改进目标若k0，则选xk进基;用最小比值法确定xk的最大值，使基变量xl取0值，其它基变量非负；,即xl出基，换基过程若不存在,则Z，没有有限最优解。,.,7.主元变换（枢变换或旋转变换）xk进基，xl出基，解出新的基变量,.,表格单纯形法,标准型：,.,表格单纯形法,标准型：,.,表格单纯形法,.,表格单纯形法,基变量,检验数,最小比值列,基变量系数,右端常数,.,表格单纯形法,例5用单纯形法求解线性规划问题,解先将上述问题化成标准形