运筹学演示课件单纯形法的计算的步骤.ppt

本节重点： 单纯形表（特别是检验数行） 单纯形法的计算步骤 大M法 两阶段法 解的存在情况判别;4．1 单纯形表 用表格法求解LP，规范的表格——单纯形表如下： ;计算步骤; 2 3 0 0 0; 2 3 0 0 0; 2 3 0 0 0;§5 单纯形法的进一步讨论;其中第2、3个约束方程中无明显基变量，分别加上人工变x6, x7;这时，初始基和初始基可行解很明显。X(0)=(0，0，0，11，0，3，1)T不满足原来的约束条件。如何使得可从X(0)开始，经迭代逐步得到x6=0，x7=0 的基可行解，从而求得问题的最优解，有两种方法：;反之，若加了人工变量的问题解后最优解中仍含人工变量为基变量，便说明原问题无可行解。例3的单纯形表格为：;3-6M M-1 3M-1 0 -M 0 0 ;2.两阶段法 ;;;;5. 2 线性规划问题解的讨论;;例: max z=3x1+4x2 x1 +x2 ?40  2x1+x2?60  x1-x2 =0 x1 ,x2 ?0;; 例 max z=3x1+5x2 3x1 +5x2 ?15  2x1 + x2 ?5  2x1+2x2 ?11  x1 ,x2 ?0;四、无（有）界解 max z=x1+x2 -2x1+x2 ?4  x1- x2 ?2  -3x1+x2?3  x1 ,x2 ?0; 线性规划解除有唯一最优解的情况外，还有如下几种情况;; 对目标函数求标准型线性规划问题，用单纯形法计算步骤的框图如下：;唯一最优解