第三节 涤毳纯形法原理 .pptVIP

一、预备知识：凸集和顶点 二、几个基本定理 定理1 若线性规划问题存在可行解，则问题 的可行域是凸集。 证明思路：要证C中任意两点X1、X2连线上任 意点X＝a X1+(1-a) X2 (0a1)也在C中。 引理 线性规划问题可行解(x1,x2,···,xn)T 为基可行解的充要条件是X的正分量所对应的系 数列向量是线性独立的。 定理2 线性规划问题的基可行解X对应线性规 划问题可行域（凸集）的顶点。 定理3 若线性规划问题有最优解，一定存在一 个基可行解是最优解。 启示 ◆线性规划问题若存在最优解，一定可以在 基可行解中找到。 ◆单纯形法的基本思路是先找到一个基可行 解，如果不是最优解，设法转换到另一个基可 行解，并使目标函数值不断增大，一直找到最 优解为止。 三、初始基可行解的确定设给定线性规划问题: 四、从初始基可行解转换为另一基可行解设初始基可行解为 因P1 P2···Pm 是一个基，其他向量Pj可用这个基的线性组合表示有 (1.16) 由(1.18)式找到满足约束方程组 五、最优性检验和判别将基本可行解X(0) 和X(1)分别代入目标函数得  (1.21) * 2010年8月 管理工程学院 《运筹学》 * * 第三节 单纯形法原理 ◆初始基可行解的确定 ◆基可行解的转换 ◆最优性检验 凸集：如果集合中任意两个点X1、X2，其连线 上所有点也都是集合C中的点，称C为凸集。即 对任何X1∈ C 、X2 ∈ C ，有 a X1+(1-a) X2 ∈ C (0a1) 则称C为凸集。 顶点：凸集C中满足下列条件的点X称为顶点：如果C中不存在任何两个不同的点X1、X2，使得X成为这两个点连线上的一个点。 或者：对任何X1∈ C 、X2 ∈ C ，不存在X=a X1+(1-a) X2 (0a1)，则X称是凸集C的顶点。 在第i个约束条件上加上松弛变量xsi(i=1,···,m) 化为标准形式: 约束方程组系数矩阵为： a11 a12 ··· a1n 1 0 ··· 0 a21 a22 ··· a2n 0 1 ··· 0 ? ? ? ? ? ? ? ? am1 am2 ? amn 0 0 ? 1 由于这个系数矩阵中一个单位矩阵 (Ps1， Ps2，···， Psm)，只要以这个单位矩阵作为基，就可以立即解出基变量值xsi=bi (i=1 ,···,m)，因为有bi ≥0 (i=1 ,···,m)，即 (0, ···,0,b1 ···, bm )为一个基可行解。 不失一般设前m个坐标非零即 因有X(0)∈C，故有 (1.15) 单纯形法原理 第 1 页 由上面三、中方法，总可以使基矩阵是单位矩阵形式， (1.15)有增广矩阵 P1 P2···Pm Pm+1 ··· Pj ··· Pn b 1 0 ··· 0 a1,m+1 ··· a1j ··· a1n b1 0 1 ··· 0 a2,m+1 ··· a2j ··· a2n b2 ? ? ? ? ? ? ? ? ? 0 0 ? 1 am,m+1 ··· amj ? amn bm 将(1.16)式乘上一个正数θ0得 (1.17) (1.15)+(1.17)式并整理得 (1.18) 另一点X(1) =(x10-θa1j,…, xm0-θamj,0, …, θ …, 0) θ是X(1)的第j个坐标值。若xi0-θaij≥0