运筹学 (单纯形法原理).ppt

《运筹学 (单纯形法原理).ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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，x5=15，于是得到初始基本可行解：X（0）=（0，0，12，16，15）T其对应的目标函数值z0=2×0+3×0=0（3）检验X（0）是否为最优解。由

3、目标函数的表达式：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=15x3=1

4、2–2x1–2x2x4=16–4x1x5=15–5x2将x1=0，x2=θ代入上面约束方程，为了让θ取尽可能大的值，同时又要考虑到x3、x4、x5必须满足非负约束，从而θ的值应满足：x3=12–2θ≥0x4=16≥0x5=15–5θ≥0即：x2=θ=min{12/2，~，15/5}=3相应地有：x3=12–2×3=6x4=16x5=15–5×3=0可见，从原来的基变量x3、x4、x5中选出x5作为非基变量，得第一次迭代后的基本可行解：X（1）=（0，3，6，16，0）T其对应的目标函数值：z1=2×0+3×3=9（5）检验X（1）是否为最优解将约束方程组改为用非基

5、变量x1、x5来表示基变量x2、x3、x4的表达式。可用高斯消去法得到：2x1+x3–2/5x5=64x1+x4=16x2+1/5x5=3移项后得到：x3=6–2x1+2/5x5x4=16–4x1x2=3–1/5x5将上式代入目标函数，得目标函数用非基变量x1、x5表示的表达式z=9+2x1–3/5x5由于非基变量x1的系数是正数，如果把非基变量转换为基变量，则会使目标函数的值增加。可见X（1）不是最优解。（6）第二次迭代和第一次迭代同样的道理，应选取非基变量x1使它成为基变量，而且让它取尽可能大的值，同时，x5仍作为非基变量取值为零。从原来的基变量x2、x3、x

6、4中选出一个作为非基变量。x1的取值也按同样的方法确定：x3=6–2x1+2/5x5x4=16–4x1x2=3–1/5x5将x1=θ，x5=0代入：x3=6–2θ≥0x4=16–4θ≥0x2=3≥0即：x1=θ=min{6/2，16/4，~}=3相应地有：可见，从原来的基变量x2、x3、x4中选出x3作为非基变量，得第二次迭代后的基本可行解：X（2）=（3，3，0，4，0）Tx3=6–2×3=0x4=16–4×3=4x2=3其对应的目标函数值：z1=2×3+3×3=15（7）检验X（2）是否为最优解将约束方程组改为用非基变量x3、x5来表示基变量x1、x2、x4的

7、表达式。可用高斯消去法得到：x1+1/2x3–1/5x5=3–2x3+x4+4/5x5=4x2+1/5x5=3移项后得到：x1=3–1/2x3+1/5x5x4=4+2x3–4/5x5x2=3–1/5x5将上式代入目标函数，得目标函数用非基变量x3、x5表示的表达式z=15–x3–1/5x5这时,目标函数中非基变量的系数都不大于零，可见目标函数的值不可能再继续增大,目标函数已经取得最大值15，故为X（2）最优解。总结通过以上例题的分析，可以归纳出单纯形法的步骤：（1）建立实际问题的线性规划数学模型；（2）把一般的线性规划问题化为标准型；（3）确定初始基本可行解；（4

8、）检验所得