《《大M两阶段》-精选课件（公开PPT）》由会员分享，可在线阅读，更多相关《《大M两阶段》-精选课件（公开PPT）（54页珍藏版）》请在金锄头文库上搜索。
1、,单纯形表复习小结,求解思想 顶点的逐步转移， 条件是 使目标函数值不断得到改善。,表格单纯形法求解步骤,第一步：将LP化为标准型，并加以整理。 引入适当的松驰变量、剩余变量和人工变量，使约束条件化为等式，并且约束方程组的系数阵中有一个单位阵。 确定初始可行基，写出初始基本可行解,第二步：最优性检验,计算检验数，检查： 所有检验数是否 0？ 是结束，写出最优解和目标函数最优值； 还有正检验数检查相应系数列 0？ 是结束，该LP无“有限最优解”！ 不属于上述两种情况，转入下一步基变换。 确定是停止迭代还是转入基变换？,选择（最大）正检验数对应的系数列为主元列，主元列对应的非基变量为换入变量； 最
2、小比值对应的行为主元行，主元行对应的基变量为换出变量。,第三步：基变换,确定进基变量和出基变量。,利用矩阵的初等行变换把主元列变成单位向量，主元素变为1，从而得到一张新的单纯形表，返回第二步。,第四步 换基迭代（旋转运算、枢运算),完成一次迭代，得到新的基本可行解和相应的目标函数值,该迭代过程直至下列情况之一发生时停止 检验数行全部变为非正值； （得到最优解）或 主元列 0 （最优解无界）,停止迭代的标志（停机准则）,标准型的单纯型算法,(1)变换主行 (2)变换主列 除主元保留为1，其余都置0 (3)变换非主行、主列元素 aij (包括 bi) 四角算法公式：,标准型的单纯型算法,5、迭代过
3、程 (4)变换CB，XB (5)计算目标函数、机会成本 zj 和检验数 cj zj 6、返回步骤 2,问题,线性规划问题化为 标准形时，若约束 条件的系数矩阵中 不存在单位矩阵， 如何构造初始可行 基？,单纯形法的进一步讨论,一、大M法 二、两阶段法,-人工变量法,人工变量法,加入 人工变量,设线性规划问题的标准型为：,加入人工变量,构造初始可行基.,人工变量法,系数矩阵为 单位矩阵， 可构成初始 可行基。,思路,因为人工变量 是为了构造初始基本可行解，人为加入原约束方程中的虚拟变量，只有当它们同时等于零，即在最终单纯形表中它们全部变换为非基变量时，加入人工变量的等式约束才与原约束条件相等。也
4、就是说，若经过基变换，基变量中不再含有人工变量，这表示原问题有解；若经过基变换，最终单纯形表中还存在人工变量，这表示原问题无可行解。,约束条件已改变， 目标函数如何调整？,人工变量法,“惩罚” 人工变量！,（1）大M法 （2）两阶段法,一、大 M 法,人工变量在目标函数中的系数为 -M, 其中，M 为任意大的正数。,目标函数中添加“罚因子” M（M是任意大的正数） 为人工变量系数，只要人 工变量0，则目标函数 不可能实现最优。,例: 求解线性规划问题,一、大 M 法,加入松弛变量x4,减去入松弛变量x5 加入人工变量x6,加入人工变量x7,一、大 M 法,解:,加入松弛变量和剩余变量进行标准
5、化, 加入人工变量构造初始可行基.,求解结果出现检验数非正,即 若最终表中仍存在非零人工变量， 则无可行解； 否则，有最优解。,一、大 M 法,用单纯形法求解（见下页）。,目标函数中添加“罚因子” M为人工变量系数，只要人 工变量0，则目标函数 不可能实现最优。,表1（初始单纯形表）,一、大 M 法（单纯形法求解）,一、大 M 法（单纯形法求解）,表2,表3,一、大 M 法（单纯形法求解）,表4,一、大 M 法（单纯形法求解）,最优解为 目标函数 值 z=2,检验数均非正，此为最终单纯形表, 最优表中，基变量不包含人工变量，则最优解就是原线性规划的最优解，不影响目标函数的取值； 最优表中，基变
6、量中仍含有人工变量，表明原线性规划的约束条件被破坏，线性规划没有可行解，也就没有最优解！,结 果,M在计算机上处理困难。 分阶段处理 先求初始基，再求解。,二、两阶段法,二阶段法的求解过程,第一阶段的任务是将人工变量尽快迭代出去，从而找到一个没有人工变量的基础可行解 第二阶段以第一阶段得到的基础可行解为初始解，采用原单纯型法求解 若第一阶段结束时，人工变量仍在基变量中，则原问题无解 为了简化计算，在第一阶段重新定义价值系数如下：,二、两阶段法,第一阶段: 构造如下的线性规划问题,人工变量的 系数矩阵为 单位矩阵， 可构成初始 可行基。,目标函数仅含人工变量，并要求实现最小化。 若其最优解的目标
7、函数值不为0，也即最优解的基变量中含有非零的人工变量，则原线性规划问题无可行解。,用单纯形法求解上述问题,若=0,进入第二阶段,否则,原问题无可行解。 第二阶段：去掉人工变量，还原目标函数系数，做出初始单纯形表。 用单纯形法求解即可。,二、两阶段法,下面举例说明，仍用大M法的例。,例：,二、两阶段法,加入人工变量x7,加入人工变量x6,二、两阶段法,构造第一阶段问题并求解,解：,用单纯形法求解,化为标准型 minmax,二、两阶段法（第一阶段、求min ）,表1,1 0 0 0 -1 1 0 0 0,0 -1 0,0 0 -1,x4 x5 x6,二、两阶段法（第一阶段、求min ）,表2,1
8、-2 2 0 -1 1 0 0 0,0 0 -1,0 0 -1,x4 x5 x6,二、两阶段法（第一阶段、求min ）,表3：最终单纯形表,第 二 阶 段,不含人工变量且=0,二、两阶段法,第二阶段,将去掉人工变量， 还原目标函数系数，做 出初始单纯形表。,1 0 0 0 -1,4 ,二、两阶段法,1/3 -2/3 0 -1 2/3 -4/3,0 0,x4 x5,第二阶段,0 0 0 -1/3 -1/3,最优解为 目标函数 值 z=2,几种特殊情况-无可行解,当前基本可行解：(0, 0, 0, 3, 4) , Z=-4M,当前基本可行解：(0, 3, 0, 0, 1) , Z=-M-3,无可行
9、解的判别准则,最优解时，人工变量仍为基变量,可行域无界,当前基本可行解：(0, 0, 0, 0, 4, 3) , Z=-7M,当前基本可行解：(0, 3, 0, 0, 1) , Z=-M-3,当前基本可行解：(0, 4, 0, 1, 0) , Z= -4,当前基本可行解：(8, 0, 0, 5, 0) , Z= 8,可行域无界的判别准则,存在非基变量，检验数0，技术系数均0,无穷多最优解,当前基本可行解：(0, 0, 150, 20, 300) , Z=0,8,当前基本可行解：(75/2, 0, 75/2, 20, 0) , Z=300,当前基本可行解：(30, 12, 0, 8, 0) ,
10、Z=300,无穷多解的判别准则,存在非基变量，检验数=0,单纯形法计算中的几个问题,1、目标函数极小化时解的最优性判断 只需用检验数 作为最优性的标志。,2、无可行解的判断 当求解结果出现所有 时，如基变量仍 含有非零的人工变量（两阶段法求解时第一阶 段目标函数值不等于0），则问题无可行解。,退化 基可行解中存在基变量=0的解退化解,单纯形法计算中的几个问题,退化问题的原因很复杂，当原问题存在平衡约束时 当单纯型表中同时有多个基变量可选作出变量时(存在两个以上相同最小比值) 退化的严重性在于可能导致死循环，克服死循环的方法有“字典序”法,换入变量和换出变量的Bland规则 选择 中下标最小的非基变量 为换入变量, 这里: 当按 规则计算存在两个和两个以上最小比值时,选下标最小的基变量为换出变量。,作业：书p43，1.6,
