1-4(2)两阶段法(2学时)(OK).ppt

第一章 线性规划1.1 线性规划的数学模型 1.2 基本概念和基本定理 1.3 图解法及几何理论 1.4 单纯形法 1.5 改进单纯形法第一章 线性规划第四节 单纯形法n典式n迭代原理n单纯形法举例n两阶段法线性规划1-4四.两阶段法：否初始顶点转移到新顶点(目标值下降)是否最优？停止 迭代是初始基本可行解新的基本可行解单纯形法的 迭代原理：何时使用两阶段法：标准形是典式初始基本可行解用单纯形法求解不是典式两阶段法初始基本可行解线性规划1-4例1-11标准形注意：例：用两阶段法求解用单纯形法求解还有很多标准 形不是典式以 为基变量的典式线性规划1-4两阶段法的思想：两阶段法：第一阶段：第二阶段：建立辅助(LP)，求出原(LP)的 一个初始基本可行解再用单纯形法去求原 的最优解线性规划1-4第一阶段：建立辅助 ，求原 的一个初始基本 可行解人工变量典式用单纯形法求解 线性规划1-4线性规划1-4000001 100100初始单纯形 表0 0 0 1 1 11 11用单纯形法求得辅助问题的最优解。

1)若 ，则原(LP)无可行解辅助(LP)的最优解与原(LP)的初始基本可行解的关系：反证法：设辅助(LP)的最优解为若原(LP)有可行解 ，则是辅助(LP)的可行解所以原(LP)无可行解辅助(LP)线性规划1-42)若 ,可得到原(LP)的一个初始基本可行解辅助(LP)的最优解与原(LP)的初始基本可行解的关系：设辅助(LP)的最优解为辅助(LP)是原(LP)的可行解1)若 ，原(LP)无可行解线性规划1-4都是非基变量，则m个基变量都在中 ，1)若 ，原(LP)无可行解辅助(LP)的最优解与原(LP)的初始基本可行解的关系：设辅助(LP)的最优解为辅助(LP)2)若 ,可得到原(LP)的一个初始基本可行解在辅助(LP)的最优解 中，是原(LP)的初始基本可行解若线性规划1-4000001 100100初始单纯形 表都是非基变量，则m个基变量都在中 ，2)若 ,则可得到原(LP)的一个初始基本可行解在辅助(LP)的最优解 中，是原(LP)的初始基本可行解。

若线性规划1-4则可将 与某个非基变量 交换若有某个 仍是基变量，1)若 ，原(LP)无可行解辅助(LP)的最优解与原(LP)的初始基本可行解的关系：设辅助(LP)的最优解为辅助(LP)2)若 ,可得到原(LP)的一个初始基本可行解在辅助(LP)的最优解 中，交换后可得到原(LP)的一个退化的初始基本可行解线性规划1-4=01 00000在 中，若有某个 仍是基变量，则 中只有m-1个基变量，则可将 与 交换交换后可得到原(LP)的一个退化的初始基本可行解辅助(LP)得最优表线性规划1-4都是非基变量，则1)若 ，则原(LP)无可行解辅助(LP)的最优解与原(LP)的初始基本可行解的关系：辅助(LP)2)若 ,则可得到原(LP)的一个初始基本可行解在辅助(LP)的最优解 中，是原(LP)的初始基本可行解若设最优解为则可将 与某个非基变量 交换若有某个 仍是基变量，在辅助(LP)的最优解 中，交换后可得到原(LP)的一个退化的初始基本可行解 。

线性规划1-4两阶段法：第一阶段：第二阶段：建立辅助 求出原 的一个初始基本可行解再用单纯形法去求原 的最优解两阶段法的思想：线性规划1-4第二阶段： 用单纯形法去求原 的最优解线性规划1-4000第二阶段：辅助 的最优表(退化)001在辅助 (LP) 的最优表中删去人工列及检验数行， 补上原 (LP)的检验数行，即得到原 (LP) 的初始单 纯形表(对应初始基本可行解)，再用单纯形法求原 (LP) 的最优解原 的初始单纯形表用单纯形法去求原 的最优解线性规划1-4例1-13 求解线性规划问题：-5 -4 -3 0 0 2 1 2 1 0 3 3 1 0 1 -7431 10 0 0 1 1 辅助辅助 单纯形表第一阶段线性规划1-43 3 1 0 1 例1-132 1 2 1 0 -5 -4 -3 0 0 34-7111第一阶段初始表表1表2最优表初始表×(1/3)1/31/3线性规划1-41 1 1/3 0 1/3 例1-132 1 2 1 0 -5 -4 -3 0 0 14-70-12第一阶段×(-2)4/3-2/3线性规划1-4×5例1-130 -1 4/3 1 -2/3 -5 -4 -3 0 0 12-701-2第一阶段1 1 1/3 0 1/3 -4/35/3线性规划1-4例1-131-2第一阶段表11 1 1/3 0 1/3 0 -1 4/3 1 -2/3 20 1 -4/3 0 5/3 ×3/4-3/413/4-1/23/2线性规划1-4例1-131-2第一阶段表11 1 1/3 0 1/3 3/2 0 -3/4 1 3/4 -1/2 0 1 -4/3 0 5/3 ×(-1/3)5/4 0-1/4 1/21/2线性规划1-4第一阶段例1-13-2 0表13/2 0 -3/4 1 3/4 -1/2 1/2 1 5/4 0 -1/4 1/2 ×4/30 1 -4/3 0 5/3 0011线性规划1-4线性规划1-4例1-13001001第一阶段辅助 (LP) 有最优解：都已出基，所以得到原(LP)的初始基本可行解。

进行第二阶段表1最优表1/2 1 5/4 0 -1/4 1/2 3/2 0 -3/4 1 3/4 -1/2 例1-13第二阶段0 -3/4 11 5/4 000004114100最优表初始表在上面最优表中删去人工列和检验数行， 添加原(LP)的检验数行，得到原(LP)的初始 单纯形表3/21/213/4-1/41-1/21/2-7/2-13/4线性规划1-4例1-13第二阶段0 -13/4 0初始表1 5/4 01/20 -3/4 13/2-7/2×4/54/5 12/5线性规划1-4例1-13第二阶段4/5 1 0初始表0 -3/4 13/20 -13/4 0-7/22/5×3/43/5 09/5线性规划1-4例1-13第二阶段3/5 0 1 初始表4/5 1 02/50 -13/4 0-7/29/5×13/40- 11/513/5线性规划1-44/5 1 0例1-13第二阶段得到原(LP)的最优解：初始表最优表2/53/5 0 1 9/5- 11/513/5 0 0 线性规划1-4-5 11 -18 0 0 -20例1-14 求解线性规划问题：1 -2 4 1 0 4 -9 14 0 1 4161 10 0 0 1 1 辅助辅助 单纯形表第一阶段初始表线性规划1-41 -2 4 1 0 例1-144 -9 14 0 1 164第一阶段-511-1800-20 01 2 5 0初始表×5线性规划1-41 -2 4 1 0 例1-144 -9 14 0 1 164第一阶段0 1 25000-1-2-40初始表×(-4)线性规划1-40 -1 -2 -4 1 用 替换 为基变量。

但人工变量 仍是基变量，为使它离基，例1-141 -2 4 1 0 04第一阶段0 1 250 0124-1已得辅助(LP)的最优表，所在第二行中的非零元均可做主元，如-1为主元，初始表最优表×(-1)线性规划1-40 1 2 4 -1 例1-141 -2 4 1 0 04第一阶段0 1 250 0089-2最优表×2线性规划1-40 1 2 4 -1 例1-141 0 8 9 -2 04第一阶段0 1 25000110最优表×(-1)线性规划1-40 1 2 4 -1 例1-141 0 8 9 -2 04。