线性规划的图解法与单纯形解法.ppt

运筹学Operations Research 王　慧 线性规划的图解法与单纯形解法 线性规划问题的图解法 线性规划单纯形解法的原理 线性规划单纯形解法的计算步骤 单纯形法计算的矩阵描述 线性规划单纯形求解的大M法 线性规划单纯形求解的两阶段法 线性规划单纯形求解可能的循环现象 线性规划问题的图解法 图解法，就是用作图的方法求解线性规划问题。 简单、直观的图解法一般只适用于具有两个决策变量的线性规划问题。 用图解法求解实际线性规划问题，一般按照如下基本步骤： Step1 画直坐标系； Step2 根据约束条件画出可行域； Step3 画过坐标原点的目标函数线； Step4 确定目标函数值的增大方向(目标函数线法线方向) Step5 目标函数线沿着增大方向平行移动，与可行域相交且有最大目标函数值的顶点，即为线性规划问题的最优解。 由图解法得到的启示 线性规划问题求解的基本依据是：线性规划问题的最优解总可在可行域的顶点中寻找。寻找线性规划问题的最优解只需比较有限个顶点处的目标函数值。 线性规划问题求解时可能出现四种结局：唯一最优解、无穷多个最优解、无有界解、无解或无可行解。 如果某一线性规划问题有最优解，我们可以按照这样的思路来求解：先找可行域中的一个顶点，计算顶点处的目标函数值，然后判别是否有其它顶点处的目标函数值比这个顶点处的目标函数值更大，如有，转到新的顶点，重复上述过程，直到找不到使目标函数值更大的新顶点为止。 线性规划单纯形解法的原理 单纯形方法的基本思想 从可行域中的一个基可行解出发，判别它是否已经是最优解，如不是，寻找下一个基可行解，并且同时努力使目标函数得到改进，如此迭代下去，直到找到最优解或判定问题无解为止。 单纯形算法必须解决三个方面的问题： 1. 如何确定初始的基可行解？ 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，转第③ 步。 最优解的判别定理 定理1 最优解的判别定理 最优解的判别定理 定理3 有无界解的判别定理 单纯形法计算的矩阵描述 单纯形法计算的矩阵描述 单纯形法计算的矩阵描述 单纯形法计算的矩阵描述 单纯形法计算的矩阵描述 单纯形法计算的矩阵描述 单纯形法计算的矩阵描述 线性规划求解的人工变量法 人工变量法 引用人工变量是用单纯形法求解线性规划问题时解决可行解问题的常用方法。 人工变量法的基本思路是： 若原线性规划问题的系数矩阵中没有单位向量，则在每个约束方程中加入一个人工变量便可在系数矩阵中形成一个单位向量。 由于单位阵可以作为基阵，因此，可选加入的人工变量为基变量。然后，再通过基变换，使得基变量中不含非零的人工变量。如果在最终单纯形表中还存在非零的人工变量，这表示无可行解。 线性规划求解的人工变量法 线性规划求解的人工变量法  为了使加入人工变量后线性规划问题的最优目标函数值不受影响，我们赋予人工变量一个很大的负价值系数-M (M为任意大的正数)。 由于人工变量对目标函数有很大的负影响，单纯形法的寻优机制会自动将人工变量赶到基外，从而找到原问题的一个可行基。 这种方法我们通常称其为大M法。 线性规划求解的大M法 线性规划求解的两阶段法 线性规划求解的两阶段法 然后用单纯形法求解所构造的新模型，若得到w=0，这时，若基变量中不含人工变量，则说明原问题存在基可行解，可进行第二步计算； 否则，原问题无可行解，应停止计算。 第二阶段，单纯形法求解原问题 第一阶段计算得到的最终单纯形表中除去人工变量，将目标函数行的系数，换成原问题的目标函数后，作为第二阶段计算的初始表，继续求解。 单纯形法计算可能的循环现象 单纯形法计算可能的循环现象 在求解线性规划单纯形方法的计算过程循环极少出现，但还是可能的。 为防止出现循环现象，先后有人提出了一些方法。 如：勃兰特法；