运筹学教学演示系统⑴课件.pptVIP

运筹学教学Operational Research Teaching 教学内容提要 绪论 第一章 线性规划及单纯形法 第二章 对偶问题及灵敏度分析 第三章 运输问题 第四章 整数规划 第五章 动态规划 第六章 图与网络 绪论 第四节 人工变量法确定初始可行基 单纯形表是从一个初始基可行解开始的，如果在线性规划问题的系数矩阵中不存在一个 m阶单位矩阵，也即很难找到一个初始可行基怎么办？ 一、人工变量的引入 设线性规划问题为： 第一章——线性规划及单纯形法 若A中不存在m阶单位矩阵，为了形成一个m阶单位矩阵，可给每个约束方程人为地加上一个人工变量，则模型调整为： 新规划与原规划是否一致呢？什么样情况下一致呢？ 人工变量等于零！ 二、大M法 为了对人工变量进行处理，在模型的目标函数中也引入人工变量，其系数为（-M）（M为任意大的正数），即 M很大很大，-M就很小很小。显然，若人工变量不为零，目标函数不可能得到最大值，也不可能获得最优解。一般称M为惩罚因子。 例4 用大M法求解下列规划问题（书上的例子） 解题应注意的问题； ①引入几个人工变量 ②如何确定初始单纯形表的检验数 ③若存在最优解，最终表的目标函数值不可能包含M 三、两阶段法 始终包含一个M进行单纯形表的运算是不方便的。两阶段法就是将引入人工变量后的规划问题分为两个阶段来求解： ①利用辅助规划，判断原规划是否存在基可行解，并给出基可行解。 ②从求得的基可行解出发，对原问题继续迭代，求最优解。 两阶段法的辅助规划为： 例5 用两阶段法求解下列线性规划问题，注意其改进！ -W -Z X2 X1 X2 X7 0 0 0 0 -1 -3 -2 0 -Z -W -Z 0 0 -1 -1 2 6 4 14 -W 0 1 1 0 0 -1 -1 0 2 0 4 2 1 3 8 6 X6 X7 X7 X6 X5 X4 X3 X2 X1 b XB -1 -1 0 0 0 0 0 0 -1 1/2 -1 0 5/2 2 -W 0 0 -3/4 1/2 0 -5/4 6 -Z 1/10 -2/5 -3/10 1/5 3/5 -2/5 1 0 0 1 9/5 4/5 X2 X1 0 1 0 -1 -1/4 1/2 1/2 -1 1 0 1/4 5/2 2 2 X2 X7 0 0 0 0 -1 -3 -2 0 -Z 0 0 0 0 0 0 -W -1/2 -1/2 0 0 0 7 -Z 0 0 -1 -1 2 6 4 14 -W 0 1 1 0 0 -1 -1 0 2 0 4 2 1 3 8 6 X6 X7 X7 X6 X5 X4 X3 X2 X1 b XB -1 -1 0 0 0 0 0 解： ㈠化标准型 ㈡确定初始基可行解并判别是否为最优解 第一章——线性规划及单纯形法 为了方便求解,用非基变量表示基变量,即 目标函数用非基变量表示为 令非基变量为0得一基可行解为 第一章——线性规划及单纯形法 从上述目标函数Z可知，只要目标函数中变量（非基变量）的取值不为零，目标函数值将增大。因此，该基可行解不是最优解。 如何使非基变量取值不为零？ 非基变量取非零的值，意味着非基变量成为基变量。而基变量的个数一定，则只能将非基变量和基变量进行替换。这一替换将得到第二个基可行解。 第一章——线性规划及单纯形法 ㈢迭代——确定第二个基可行解 所谓迭代，就是一个非基变量和一个基变量的交换。 选哪个非基变量成为基变量呢？ 从目标函数看： 选X2进基， X1仍然为非基变量，必须解决两个问题： ①哪个出基呢？——哪个成为非基变量？ ②X2=?，当然越大越好，应考虑什么？ 还是从约束条件来解决这个问题。 第一章——线性规划及单纯形法 考查约束条件 第一章——线性规划及单纯形法 仍按上述方法,用非基变量来表示基变量如下 目标函用非基变量表示为: 令非基变量为零,得基解为 第一章——线性规划及单纯形法 从上述目标函数Z可知，目标函数中x1的系数为2,当其取值不为零，目标函数值将增大。因此，该基可行解仍不是最优解。还需要迭代。 只要目标函数中变量X1（非基变量）的取值不为零，目标函数值将增大。因此，该基可行解不是最优解。 ㈣迭代——确定第三个基可行解 …… 二、单纯形法的基本原理 单纯形法是以基可行解的迭代及判别为核心内容