两阶段法.pptVIP

证明： * Page * * 第五节 二阶段法(人工变量法二) 解决初始基本可行解不存在问题 则 是基变量， 是自由变量. 设基矩阵 并记 一、单纯形表的矩阵形式 记 底线 竖线 则 也称检验数. 其中 对于线性规划问题 二. 二阶段法（人工变量法二） 引入人工变量 构造辅助线性规划问题 该规划有可行解 (0,…,0,b1,…,bm)T 这说明可行域非空 目标函数显然有下界,因此该规划有最优解 （4-1） 假设r(A)=m, 且对应的初始单纯形表②满足, ①不满足. 那么： 定理4.2 则(4-1)无可行解. 是(4-3)的最优基本可行解. 设 （4-3） 矩阵形式 若 若 是(4-1)的一个基本可行解； 给出了求(4-1)的初始基本可行解的方法. 第一阶段的任务是求解LP(4-3), 得最优解。若最优解中人工变量取值为零，则进入第二阶段； 第二阶段是以第一阶段得到的基本可行解为初始解，采用单纯形法求解原LP(4-1)； 若第一阶段结束时， LP(4-3)的最优解中人工 变量取值不全为零，则原问题(4-1)无解。 二阶段法的解题思路 三、例题解析 例1（教材P60，例4.2） 解: 该LP已是标准形，画出对应表格： 3 3 3 1 0 4 4 1 1 2 1 2 容易验证 R(A)=2, 但特点①不满足。 下面构造如下新LP模型并用单纯形法求解： 人工变量 人工变量 3 3 3 1 0 1 0 4 0 0 0 1 1 2 1 2 1 0 3 3 3 1 0 1 -7 4 -5 -4 -3 0 0 2 1 2 1 0 满足① ② ③ 但 ④ 不 满足 它对应的单纯形表格为： 满足① ② 1 1 1 1/3 0 1/3 -2 2 0 1 -4/3 0 5/3 0 -1 4/3 1 -2/3 1/2 1 5/4 0 -1/4 1/2 0 3/2 0 0 0 1 1 0 -3/4 1 3/4 -1/2 满足① ② ③ 但 ④ 不 满足 满足① ② ③ ④ 人工变量的值为零 1/2 1 5/4 0 -7/2 3/2 0 -13/4 0 0 -3/4 1 所以，原问题的一个基本可行解为： 并且，此时对应于原问题的单纯形表应该为： 其中，底行及右下端元素是由下面的公式计算得到的. 1/2 1 5/4 0 -7/2 3/2 0 -13/4 0 0 -3/4 1 2/5 4/5 1 0 -11/5 9/5 13/5 0 0 3/5 0 1 满足① ② ③ 但 ④ 不 满足 满足① ② ③ ④ 接下来再用单纯形法求解原LP问题： 故原LP问题(I)的最优解为： 最优值为： （4-3） （4-1） 三. 定理4.2的证明 定理4.2 则(4-1)无可行解. 是(4-3)的最优基本可行解. 设 若 若 是(4-1)的一个基本可行解； 反证法： 是(4.3)的可行