运筹学 第一章 第三节 单纯形法.pdf

第一章 线性规划及其单纯形法 44-1 第一章 线性规划与单纯形法 §1 线性规划问题及其数学模型 §1 线性规划问题及其数学模型 §2 线性规划问题的几何意义 §3 单纯形法 单纯形法 §4 单纯形法的计算步骤 单纯形法的计算步骤 §5 单纯形法的进一步讨论 单纯形法的进一步讨论 §6 应用举例 第一章§3 单纯形法 44-2 §3 单纯形法 单纯形法 若线性规划问题有最优解，必在某顶点上得 到。虽然顶点数目是有限的，若采用“枚举法”找所 有基可行解，然后一一比较，最终必然能找到最优 解。但当n , m 较大时，这种办法是行不通的，所 以要继续讨论如何有效寻找最优解的方法。本节将 主要介绍单纯形法。 第一章§3 单纯形法 44-3 由线性代数知，对LP标准型问题，理论上可以求出 所有基解（枚举法），再通过观察找出其中基可行解， 进而找出最优解。但如果变量和方程较多，比如m=50， 29 n=100，所有基解有可能达10 个，即使计算机每秒能 求解1亿个这样的方程组，也需要30万亿年！因此，必 须寻求有效的算法。 为加快计算速度，算法必须具有两个功能，一是每得到 一个基可行解，就能检验是否已经最优，若是，停止。二是 若不是最优，要保证下一步得到的基可行解不劣于当前解。 基于线性代数原理，并将上述功能贯穿于算法过程，这就是 线性规划的单纯形法。 第一章§3 单纯形法 44-4 例 以例1来讨论如何用单纯形法求解。 解：已知本例的标准型为： max z 2x1 +3x2 +0x3 +0x4 +0x5 (1) + + ⎧ x1 2x 2 x3 8 ⎪ ⎪ 4x1 + +x 4 16 s.t . ⎨ (2) 4x +x 12 ⎪ 2 5 ⎪⎩ xj ≥0 j 1, 2,, 5 约束条件(2)式的系数矩阵为 ⎛1 2 1 0 0⎞ ⎜ ⎟ A (P , P , P , P , P ) 4 0 0 1 0 1 2 3 4 5 ⎜ ⎟ ⎜⎝0 4 0 0 1⎟⎠ （一）x , x , x