第一章 线性规划第四节 单纯形法n典式n迭代原理n单纯形法举例n两阶段法线性规划1-4四.两阶段法：否初始顶点转移到新顶点(目标值下降)是否最优？停止 迭代是初始基本可行解新的基本可行解单纯形法的 迭代思想：线性规划1-4何时使用两阶段法：标准形是典式初始基本可行解用单纯形法求解不是典式两阶段法初始基本可行解线性规划1-4例1-11标准形注意：例：用两阶段法求解用单纯形法求解还有很多标准 形不是典式以 为基变量的典式线性规划1-4两阶段法的思想：两阶段法：第一阶段：第二阶段：建立辅助(LP)，求出原(LP)的 一个初始基本可行解再用单纯形法去求原 的最优解线性规划1-4第一阶段：建立辅助 ，求原 的一个初始基本 可行解人工变量典式用单纯形法求解线性规划1-4000001 100100初始单纯形 表0 0 0 1 1 11 11用单纯形法求得辅助问题的最优解1)若 ，则原(LP)无可行解线性规划1-4辅助(LP)的最优解与原(LP)的初始基本可行解的关系：反证法：设辅助(LP)的最优解为若原(LP)有可行解 ，则是辅助(LP)的可行解。
矛盾所以原(LP)无可行解辅助(LP)2)若 ,可得到原(LP)的一个初始基本可行解线性规划1-4辅助(LP)的最优解与原(LP)的初始基本可行解的关系：设辅助(LP)的最优解为辅助(LP)是原(LP)的可行解1)若 ，原(LP)无可行解都是非基变量，则m个基变量都在中 ，1)若 ，原(LP)无可行解线性规划1-4辅助(LP)的最优解与原(LP)的初始基本可行解的关系：设辅助(LP)的最优解为辅助(LP)2)若 ,可得到原(LP)的一个初始基本可行解在辅助(LP)的最优解 中，是原(LP)的初始基本可行解若线性规划1-4000001 100100初始单纯形 表都是非基变量，则m个基变量都在中 ，2)若 ,则可得到原(LP)的一个初始基本可行解在辅助(LP)的最优解 中，是原(LP)的初始基本可行解若则可将 与某个非基变量 交换若有某个 仍是基变量，1)若 ，原(LP)无可行解。
线性规划1-4辅助(LP)的最优解与原(LP)的初始基本可行解的关系：设辅助(LP)的最优解为辅助(LP)2)若 ,可得到原(LP)的一个初始基本可行解在辅助(LP)的最优解 中，交换后可得到原(LP)的一个退化的初始基本可行解线性规划1-4=01 00000在 中，若有某个 仍是基变量，则 中只有m-1个基变量，则可将 与 交换交换后可得到原(LP)的一个退化的初始基本可行解辅助(LP)得最优表都是非基变量，则1)若 ，则原(LP)无可行解线性规划1-4辅助(LP)的最优解与原(LP)的初始基本可行解的关系：辅助(LP)2)若 ,则可得到原(LP)的一个初始基本可行解在辅助(LP)的最优解 中，是原(LP)的初始基本可行解若设最优解为则可将 与某个非基变量 交换若有某个 仍是基变量，在辅助(LP)的最优解 中，交换后可得到原(LP)的一个退化的初始基本可行解。
线性规划1-4两阶段法：第一阶段：第二阶段：建立辅助 求出原 的一个初始基本可行解再用单纯形法去求原 的最优解两阶段法的思想：线性规划1-4第二阶段： 用单纯形法去求原 的最优解线性规划1-4000第二阶段：辅助 的最优表(退化)001在辅助 (LP) 的最优表中删去人工列及检验数行， 补上原 (LP)的检验数行，即得到原 (LP) 的初始单 纯形表(对应初始基本可行解)，再用单纯形法求原 (LP) 的最优解原 的初始单纯形表用单纯形法去求原 的最优解线性规划1-4000第二阶段：辅助 的最优表(退化)01原 的初始单纯形表用单纯形法去求原 的最优解初始表最优表线性规划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 辅助辅助 单纯形表第一阶段3 3 1 0 1 线性规划1-4例1-132 1 2 1 0 -5 -4 -3 0 0 34-7111第一阶段初始表表1表2最优表初始表1 1 0 线性规划1-4例1-132 1 2 1 0 -5 -4 -3 0 0 14-70-2-12第一阶段1 1 0 线性规划1-4例1-130 -1 1 -5 -4 -3 0 0 12-7051-2第一阶段线性规划1-4例1-131 1 0 12010-20-1 11第一阶段表1线性规划1-4例1-131 1 0 1010-2010第一阶段线性规划1-4例1-13010-2010100110第一阶段线性规划1-4例1-130010010101第一阶段最优表辅助 (LP) 有最优解：都已出基，所以得到原(LP)的初始基本可行解。
进行第二阶段线性规划1-4例1-13第二阶段01011000014114100最优表初始表在上面最优表中删去人工列和检验数行， 添加原(LP)的检验数行，得到原(LP)的初始 单纯形表线性规划1-4例1-13第二阶段0101001线性规划1-4例1-13第二阶段0100010线性规划1-4例1-13第二阶段1000100线性规划1-4例1-13第二阶段100100最优表得到原(LP)的最优解：-5 11 -18 0 0 -20线性规划1-4例1-14 求解线性规划问题：1 -2 4 1 0 4 -9 14 0 1 4161 10 0 0 1 1 辅助辅助 单纯形表第一阶段初始表1 -2 4 1 0 线性规划1-4例1-144 -9 14 0 1 164第一阶段-511-1800-20501 2 5 0初始表1 -2 4 1 0 线性规划1-4例1-144 -9 14 0 1 164第一阶段0 1 2500-40-1-2-400 -1 -2 -4 1 用 替换 为基变量。
但人工变量 仍是基变量，为使它离基，线性规划1-4例1-141 -2 4 1 0 04第一阶段0 1 250 0-1124-1最优表已得辅助(LP)的最优表，所在第二行中的非零元均可做主元，如-1为主元，0 1 2 4 -1 线性规划1-4例1-141 -2 4 1 0 04第一阶段0 1 250 02089-20 1 2 4 -1 线性规划1-4例1-141 0 8 9 -2 04第一阶段0 1 250-1001100 1 2 4 -1 线性规划1-4例1-141 0 8 9 -2 04第一阶段0 0 011 0最优表得到原(LP)的退化的初始基本可行解线性规划1-4例1-141 0 8 04第二阶段0 0 0 00 1 2 1941-2-1最优表在上面最优表中删去人工列和检验数行，线性规划1-4例1-14第二阶段1 0 8 040 1 2 1231200-9-4初始表在上面最优表中删去人工列和检验数行， 添加原(LP)的检验数行，得到原(LP)的初始单纯形表。
0 1 2 线性规划1-4例1-14第二阶段1 0 8 0400-9-40 1 2 线性规划1-4例1-14第二阶段1 0 8 0400-9-41线性规划1-4例1-14第二阶段1 0 8 0400-9-40 1 -8-40线性规划1-4例1-14第二阶段1 -4 0 0400-9-40 1 90得到原(LP)的最优解：线性规划1-4例1-14第二阶段1 -4 0 0400-40 1 最优表线性规划1-4例1-14第二阶段0 1 2 1 0 8 0400-9-4在退化情况下,负检验数相应的非基变量进基得到的 新的基本可行解目标值未必一定下降。
初始表原(LP)的初始。