[管理学]第二章 图解法与单纯形法.ppt

第二章 线性规划的图解法与单纯形解法 1 线性规划问题的图解法 线性规划单纯形法的原理与计算步骤 线性规划单纯形法的进一步讨论 线性规划单纯形法的改进 线性规划特例—运输问题 2.1 线性规划问题的图解法 图解法是用作图的方法求解线性规划问题，一般只适用于具有两个决策变量的线性规划问题。 步骤1 画直角坐标系 步骤2 根据约束条件画出可行域 步骤3 画过坐标原点的目标函数线 步骤4 确定目标函数的增大方向 步骤5 让目标函数沿着增大方向平行移动，与可行域相交且有最大目标函数值的顶点，即为线性规划问题的最优解。 2.1 线性规划问题的图解法 用图解法求解如下线性规划问题： 2.1 线性规划问题的图解法 2.1 线性规划问题的图解法 本例中我们用图解法得到的问题的最优解是惟一的。 但在线性规划问题的计算中,解的情况还可能出现下列几种: 1 无穷最优解。如将本例的目标函数改变为 则目标函数的图形恰好与(1)平行。因此该线性规划问题有无穷多个最优解,也称具有多重最优解。 2.1 线性规划问题的图解法 2. 无界解 (有可行解但无有界最优解)。 如果本例中约束条件只剩下(2)和(4),其他条件(1)、(3)不再考虑。 用图解法求解时, 可以看到变量的取值可以无限增大, 因而目标函数的值也可以一直增大到无穷。这种情况下称问题具有无界解或无最优解。 其原因是由于在建立实际问题的数学模型时遗漏了某些必要的资源约束。 2.1 线性规划问题的图解法 3. 无可行解。如下述线性规划模型： 用图解法求解时找不到满足所有约束条件的公共范围，这时问题无可行解。其原因是模型本身有错误, 约束条件之间相互矛盾, 应检查修正。 单纯形法的计算步骤： 步骤1：求初始基可行解，列出初始单纯形表。 对非标准形式的线性规划问题首先要化成标准形式。 由于我们总可以设法使约束方程的系数矩阵中包含一个单位矩阵[P1,P2,…,Pm] ，以此作为基即可求得问题的一个初始基可行解。首先经过变化迭代可将线性规划约束条件变成如下形式： 列出单纯形表 单纯形法的计算步骤： 步骤2 最优性检验 在单纯形表中，若所有的检验数 表中的基可行解即为最优解。若存在 并且有 ，则问题无有界解。计算结束。否则转入下一步。 步骤3 从一个基可行解转换到相邻的目标函数更大的基可行解，列出新的单纯形表。 单纯形算法的计算步骤 ①将线性规划问题化成标准型。 ②找出或构造一个m阶单位矩阵作为初始可行基，建立初始单纯形表。 ③计算各非基变量xj的检验数?j，若所有?j≤0，则问题已得到最优解，停止计算，否则转入下步。 ④在大于0的检验数中，若某个?k所对应的系数列向量Pk≤0，则此问题是无界解，停止计算，否则转入下步。 ⑤根据max{?j｜?j＞0}=?k原则，确定xk为换入变量(进基变量)，再按?规则计算：?=min{bi/aik| aik＞0}=bl/ aik 确定xl为换出变量。建立新的单纯形表，此时基变量中xk取代了xl的位置。 ⑥以aik为主元素进行迭代，把xk所对应的列向量变为单位列向量，即aik变为1，同列中其它元素为0，转第③ 步。 2.2 线性规划单纯形法的原理与计算步骤 单纯形法计算中可能出现以下两种情况： 出现两个以上 ，原则上可任取一 个 对应的为换入基的变量； 相持。 即计算值出现两个以上相同 的最小值。则可任选其中一个基变量作为换出变量。 单纯形法的计算 用单纯形法求解线性规划问题： 最优解的判别定理 定理1 最优解的判别定理 单纯形法的计算 用单纯形法求解线性规划问题： 最优解的判别定理 定理3 有无界解的判别定理 单纯形法的计算 用单纯形法求解线性规划问题： 单纯形法计算的矩阵描述 单纯形法计算的矩阵描述 单纯形法计算的矩阵描述 单纯形法计算的矩阵描述 单纯形法计算的矩阵描述 单纯形法计算的矩阵描述 单纯形法计算的矩阵描述 人工变量法 人工变量法的基本思路是： 若原线性规划问题的系数矩阵中没有单位向量，则在每个约束方程中加入一个人工变量便可在系数矩阵中形成一个单位向量。 线性规划求解的人工变量法 线性规划求解的人工变量法 由于单位阵作为基阵，因此，选加入的人工变量为基变量。然后，再通过基变换，使得基变量中不含非零的人工变量。如果在最终单纯形表中还存在非零