[管理学]单纯形法.pptVIP

线性规划的单纯形法 The Simplex Method §4.1 线性规划模型的几种表示 1.标准形式 max z = c1 x1 + c2 x2 + … + cn xn s.t. a11 x1 + … a1j xj+ … + a1n xn = b1 a21 x1 + … a2j xj+ … + a2n xn = b2 …… am1 x1 + … amj xj + … + amn xn = bm x1 ， … , xj ，… ，xn ≥ 0 2.向量形式 其中， 3.矩阵形式 其中， §4.2 线性规划解的概念 设线性规划为 A为m × n矩阵, n m, Rank( A) = m (A为行满秩矩阵） 3. 基 ( Basis ) 取B为A中的m × m子矩阵，Rank (B) = m，则称B为线性 规划问题的一个基。 取 B = (p1 , p2 , ··· , pm ) pj = (a1j , a2j , ··· , amj )T 则称变量x1 , x2 ,···, xm为基变量(basic variable )，其它的变量 为非基变量(non-basic variable)。 4.基本解(Basic solution) 设B =(p1 , p2 , ···, pm )为线性规划问题的一个基，XB为基变 量；N 为非基，XN为非基变量，则 BXB + NXN=b 若令XN=0, 则有 基本解： 基本解的个数 5.基本可行解(Basic feasible solution ) 满足(3)式要求的基本解。 如右图所示，各边交点O,Q1,Q2,Q3,Q4均为基本可行解；而 其延长线的交点Q5为基本解，但不是基本可行解。 各类解之间的关系图 §4.3 线性规划问题的几何意义 4.3.1 基本概念 1、凸集(convex set)： 设K为En(n维欧式空间)的一点集，X(1)∈K，X(2)∈K。若 αX(1)+(1-α)X(2)∈K，则称K为凸集。（ 0 ? ? ? 1 ） 2、顶点(vertex)： X∈K，X(1)∈K，X(2)∈K (任意两点)。若X不能 用αX(1)+(1-α)X(2)表示，则称X为K的一个顶点。(0α1) §4.4 单纯形法原理 基本思路： 从可行域的一个顶点到另一个顶点迭代求最优解。 需要解决的三个问题： (1)如何确定一个初始基本可行解？ (2)如何判断一个基本可行解是否为最优解？ (3)如何从一个基本可行解变换到另一个基本可行解？ 单纯形法引例 4.4.1 初始基可行解的确定 1、观察法 2. 松弛变量法 3. 人工变量法 4.4.2 最优性的检验与解的判别 对于 设 为基变量， 为非基变量。 将 代入目标函数，则目标函数表示为： 其中， 称为变量 的检验数。 解的判别准则： 定理4.1(最优解的判别准则) 若 为对应于基B 的基本可行 解,且对于一切的 有 ,则 为最优解。 解的判别准则： 定理4.2(无最优解的判别准则) 若 为一基本可行解，有一 个 ，并且对于一切 有 ，则该线 性规划问题没有有限最优解(也称无最优解)。 无有限最优解判别准则的证明： 构造一个新解 ，分量如下：