0920__第四次课_大M法.pptVIP

故用大M法使① ②满足 下面用单纯性法求解该新LP问题 证明： * Page * * 第四节 大M法(人工变量法) 解决初始基本可行解不存在问题 基本思想 单纯形法是从一个初始基可行解开始的， 解决办法: 引入人工变量 接下来修改目标函数, 从而得到新的线性规划模型. 最后通过单纯性法求解新LP模型而得到原LP模型的最优解. 但以上条件有时是不满足的,即原LP问题的初始基本可行解不易找出或不存在,此时怎么办？ ①中心部位具有m阶单位子块 ②右列元素非负 首先利用容许的运算使②满足, 即使右列元素非负; 然后在中心部位人工添加一些单位列向量, 使中心 部位具有m阶单位子块, 也就是使①满足. 即要求标 准形对应的单纯性表满足： 分析: 对应表格 引例 -4 -1 2 -1 0 6 -3 1 2 3 2 -3 可见,r(A)=2. 但① ②不满足. 4 1 -2 1 0 1 0 6 -3 1 2 3 2 -3 1 0 4 1 -2 1 0 6 -3 1 2 3 2 -3 使 ② 满足 人工变量 人工变量 人工变量的系数 M M 4 1 -2 1 0 1 0 6 -3 1 2 M M 3 2 -3 1 0 人工变量 人工变量 其中M0为足够大的正常数. 一. 人工变量的处理—大M法 对于线性规划问题 引入人工变量 构造新的线性规划问题 其中M0为 足够大的数 假设r(A)=m, 且对应的初始单纯形表②满足, ①不满足. 那么： 反之, 若 是(4.1)的最优解, 是(4.2)的最优解. 定理4.1 是(4.2)的最优解. 若 的最优解；若 则(4.1)没有可行解. 人工变量全是自由变量 二、算法（大M法）-- 已知初始表不满足① ② 1.大M法的求解步骤 3）将目标函数修改为 的正常数. 从而得到新的LP模型. 1）经初等行变换 使右列元素非负; 2）在中心部位人工地添加一个m阶单位子块, 即引入 得到新的约束方程组； 引入人工变量 4）用单纯形求解新的LP模型，试图将 变成自由变量，最终将出现5)或6)两种情况： 6）新LP无界(无最优解)，则原LP问题也无最优解. 5）设求得新的LP模型的最优解为 则 则原LP问题无最优解. 说明：在上面5)中提到的 的情况属于下面情形： 用单纯形法求解新LP得到的新表格满足① ② ③ ④， 但人工变量并没有完全成为自由变量。此时说明 原LP问题是无可行解，因此原LP无最优解. 是原LP问题的最优解. 解: 该LP已是标准形，画出对应表格： 2. 例题解析 -4 -1 2 -1 0 6 -3 1 2 3 2 -3 可见,r(A)=2. 但① ②不满足. 4 1 -2 1 0 1 0 6 -3 1 2 M M 3 2 -3 1 0 人工变量 人工变量 下面用单纯形法求解这个新LP问题. 4 1 -2 1 0 1 0 6 -3 1 2 M M 3 2 -3 1 0 4 1 -2 1 0 1 -