《线性规划的图解法与单纯形解法》由会员分享，可在线阅读，更多相关《线性规划的图解法与单纯形解法（60页珍藏版）》请在金锄头文库上搜索。
1、运筹学 Operations Research吴清烈东南大学经济管理学院 电子商务系暨管理工程研究所 02583795358, 13337835398, 线性规划的图解法与单纯形解法 p线性规划问题的图解法 p线性规划单纯形解法的原理p线性规划单纯形解法的计算步骤 p单纯形法计算的矩阵描述 p线性规划单纯形求解的大M法p线性规划单纯形求解的两阶段法p线性规划单纯形求解可能的循环现象p线性规划单纯形法的改进线性规划问题的图解法p图解法，就是用作图的方法求解线性规划问题。p简单、直观的图解法一般只适用于具有两个决策变量的线 性规划问题。p用图解法求解实际线性规划问题，一般按照如下基本步骤 ：Ste
2、p1 画直坐标系；Step2 根据约束条件画出可行域；Step3 画过坐标原点的目标函数线；Step4 确定目标函数值的增大方向(目标函数线法线方向)Step5 目标函数线沿着增大方向平行移动，与可行域相交且有最大目标函数值的顶点，即为线性规划问题的最优解。线性规划问题的图解法举例max z =2 x1+x23x1+x2 12 x1+x2 5x2 3 x1，x2 0线性规划问题求解的几种可能结局 p存在唯一最优解。如上例。p存在无穷多个最优解。如在上例中，将目标函数改为max z=3x1+x2,这时Q1 与Q2 以及Q1 与Q2之间的所有点均为最优解。p存在无界解（有可行解但无有界最优解）。如
3、在上例中，只含有x2 3一个约束，可行域为无界，z 的取值可无穷大。p无解或无可行解。如下述线性规划问题max z=2 x1+x2x1+x22-x1+x25x1，x20，约束条件矛盾，因而无可行解。由图解法得到的启示 p线性规划问题求解的基本依据是：线性规划问题的最优 解总可在可行域的顶点中寻找。寻找线性规划问题的最优 解只需比较有限个顶点处的目标函数值。p线性规划问题求解时可能出现四种结局：唯一最优解、 无穷多个最优解、无有界解、无解或无可行解。p如果某一线性规划问题有最优解，我们可以按照这样的 思路来求解：先找可行域中的一个顶点，计算顶点处的目 标函数值，然后判别是否有其它顶点处的目标函数
4、值比这 个顶点处的目标函数值更大，如有，转到新的顶点，重复 上述过程，直到找不到使目标函数值更大的新顶点为止。线性规划单纯形解法的原理 p单纯形方法的基本思想从可行域中的一个基可行解出发，判别它是否已 经是最优解，如不是，寻找下一个基可行解，并且同 时努力使目标函数得到改进，如此迭代下去，直到找 到最优解或判定问题无解为止。p单纯形算法必须解决三个方面的问题：1. 如何确定初始的基可行解？2. 如何进行解的最优性判别？3. 如何寻找改进的基可行解？确定初始的基可行解p标准型的线性规划问题系数矩阵中存在一个单位阵 以单位阵为一初始可行基。令非基变量取值为零， 便得到一基可行解。 最优性检验和解的
5、判别 对标准型的一般线性规划问题，经过变换、迭代 总可将线性规划约束条件中非基变量移至。方程右 边，得如下形式： 最优性检验和解的判别将上式代入目标函数式中，整理得 令 最优性检验和解的判别再令 称为检验数。在线性规划模型中，可以用检验数 替代目标函 数中的价值系数cj。 最优解的判别定理p定理1 最优解的判别定理 p定理2 有无穷多最优解的判别定理最优解的判别定理p定理3 有无界解的判别定理寻找改进的基可行解 p当检验某个基可行解不是最优、也非无界，那么 就应该从该顶点（基可行解）处出发，寻找一个新 的能使目标函数值改进的相邻顶点（基可行解）。注：称两个基可行解为相邻的，是指它们之间变 换且
6、仅变换一个基变量。p具体的方法是：在基变量中，选出一个，让它变 为非基变量；同时，从非基变量中，选出一个，让 它变为基变量，从而构造一个新基。p我们希望：每变换一次，就得到一个新的基可行 解，并且是尽可能使目标函数值改进的基可行解。 换入变量的确定 如果存在多个j 0, 则取 假定存在一个我们取为换入变量。 换出变量的确定 换出变量的确定若 我们选为换出变量。寻找改进的基可行解p可以证明( x1, x2, xl-1, xl+1, ,xm, xm+k)所对应的m个 列向量P1, P2, Pl-1, Pl+1, ,Pm, Pm+k线性无关，因而 B=(P1, P2, Pl-1, Pl+1, ,Pm
7、, Pm+k)是一个新基。p最佳换入换出变量确定单纯形表单纯形算法的计算步骤 将线性规划问题化成标准型。找出或构造一个m阶单位矩阵作为初始可行基，建立初始单纯形 表。 计算各非基变量xj的检验数j，若所有j0，则问题已得到最优 解，停止计算，否则转入下步。在大于0的检验数中，若某个k所对应的系数列向量Pk0，则此 问题是无界解，停止计算，否则转入下步。根据maxjj0=k原则，确定xk为换入变量(进基变量)，再 按规则计算：=minbi/aik| aik0=bl/ aik 确定xl为换出变量。建立新 的单纯形表，此时基变量中xk取代了xl的位置。以aik为主元素进行迭代，把xk所对应的列向量变
8、为单位列向量， 即aik变为1，同列中其它元素为0，转第 步。 单纯形算法计算举例单纯形法计算举例P1 P2 P3 P4 P5 b单纯形法计算举例单纯形法计算举例单纯形法计算举例单纯形法计算的矩阵描述单纯形法计算的矩阵描述单纯形法计算的矩阵描述 单纯形法计算的矩阵描述单纯形法计算的矩阵描述单纯形法计算的矩阵描述单纯形法计算的矩阵描述线性规划求解的人工变量法p人工变量法引用人工变量是用单纯形法求解线性规划问题时解决可行 解问题的常用方法。p人工变量法的基本思路是：若原线性规划问题的系数矩阵中没有单位向量，则在每个 约束方程中加入一个人工变量便可在系数矩阵中形成一个单 位向量。由于单位阵可以作为基
9、阵，因此，可选加入的人工变量为 基变量。然后，再通过基变换，使得基变量中不含非零的人 工变量。如果在最终单纯形表中还存在非零的人工变量，这 表示无可行解。 线性规划求解的人工变量法线性规划求解的人工变量法p为了使加入人工变量后线性规划问题的最优 目标函数值不受影响，我们赋予人工变量一个 很大的负价值系数-M (M为任意大的正数)。p由于人工变量对目标函数有很大的负影响， 单纯形法的寻优机制会自动将人工变量赶到基 外，从而找到原问题的一个可行基。p这种方法我们通常称其为大M法。 线性规划求解的大M法线性规划求解的大M法线性规划求解的大M法举例线性规划求解的大M法举例线性规划求解的大M法举例线性规
10、划求解的两阶段法线性规划求解的两阶段法然后用单纯形法求解所构造的新模型，若得到w=0， 这时，若基变量中不含人工变量，则说明原问题存在 基可行解，可进行第二步计算； 否则，原问题无可行解，应停止计算。第二阶段，单纯形法求解原问题 第一阶段计算得到的最终单纯形表中除去人工变量 ，将目标函数行的系数，换成原问题的目标函数后， 作为第二阶段计算的初始表，继续求解。 线性规划求解两阶段法举例线性规划求解两阶段法举例线性规划求解两阶段法举例单纯形法计算可能的循环现象单纯形法计算可能的循环现象p在求解线性规划单纯形方法的计算过程循 环极少出现，但还是可能的。p为防止出现循环现象，先后有人提出了一 些方法。如：勃兰特法；字典序法；摄动法。 勃兰特(Bland)法线性规划单纯形法的改进 线性规划单纯形法的改进 线性规划单纯形法的改进 线性规划单纯形法的改进 线性规划单纯形法的改进举例 线性规划单纯形法的改进举例线性规划单纯形法的改进举例线性规划单纯形法的改进举例线性规划单纯形法的改进举例复习举例复习举例复习举例
