第5章-1单纯形法2007-10-09

第五章 单纯形法v 在求解 LP问题时 ,有人给出了图解法 ,但对多维变量时 ,却无能为力 ,于是v 美国数学家 GBDantgig(丹捷格 )发明了一种 “单纯形法 ”的代数算法，尤其是方便于计算机运算。这是运筹学史上最辉煌的阶段。本章主要内容v 线性规划问题解的基本概念v 单纯形解法v 解的最优性检验v 表解形式的单纯形法v 单纯形解法的一些问题及其处理方法第 1节 单纯形解法的基本原理与思路v 线性规划问题解的基本概念v 单纯形解法v 解的最优性检验一、线性规划问题解的基本概念v 可行解v 最优解v 基及基本解v 可行基及基本可行解v 代数解与几何解的关系v 单纯形法的要点最 优 解一、线性规划问题解的基本概念v 可行解 :满足所有约束条件 (包括非负条件)的解称为可行解 .即可行域内所有点 .x1+ x23002x1+x2400x1 0, x20s.t. x2250x12000200300可行域内的所有点称为 : 可行解可行解 .max z=50x1+100x2一、线性规划问题解的基本概念v 可行解 :满足所有约束条件 (包括非负条件 )的解称为可行解 .即可行域内所有点 .v 最优解 : 达到最优的可行解 .最优解 .v 基本 可行解 :可行域内的顶点 (边界 ).基本可行解v初始基本可行解 : 由于求最优解是一个循环迭代的过程 ,那么 ,我们将第一次找到的可行域的顶点。一、线性规划问题解的基本概念基及基本解 :目目 标标 函数：函数：max z=50x1+100x2x1+ x23002x1+x2400x1 0, x20s.t.x2250max z=50x1+100x2x1+ x2+s1=3002x1+x2+s2=400x1 0, x20, si0s.t.x2+s3 =250一、线性规划问题解的基本概念基及基本解 :max z=50x1+100x2+0s1+0s2+0s31x1+1 x2+1s1+0s2+0s3 =3002x1+1 x2+0s1+1s2+0s3 =400x1 0, x20, s10， s20， s30s.t.0x1+1x2+0s1+0s2+1s3 =250基及基本解 :s.t.1x1+1 x2+1s1+0s2+0s3 =3002x1+1 x2+0s1+1s2+0s3 =400x1 0, x20, si00x1+1x2+0s1+0s2+1s3 =250基及基本解 : 1x1+1 x2+1s1+0s2+0s3 =3002x1+1 x2+0s1+1s2+0s3 =400x1 0, x20, si00x1+1x2+0s1+0s2+1s3 =250这是一个 3X5的矩阵 :其中 :基及基本解 :这是一个 3X5的矩阵 :从 A中任取一个 mxm的子矩阵 B,只要 B的秩为 m,则称 B为线性规划问题中的一个基 .基及基本解 :基中每一列 (一个向量 )称为该 基 的一个 基向量 (对 B而言 )。是基 的三个基向量。A中基之外的其它列称为 B的非基向量。是基 的三个基向量.又如 :B而 A中其它两列 ,则称为 B的非基向量 .原模型为 :s.t.P3与变量 s1对应 , P4与变量 s2对应 , P5与变量 s3对应 ,故称 s1,s2 ,s3为基 B的 基变量 ,相应地 ,x1,x2成为 B的非基变量 .s1 s2 s3基及基本解 :s.t.基及基本解 :s.t.基及基本解 :s.t.此方程有无穷多个解 ,为找最优解 ,可先令非基变量 :x1=x2=0S1=300, s2=400, s3=250 ,外加 x1=0, x2=0基及基本解 :x1=0,x2=0,S1=300, s2=400,s3=250 ,本解是从基 B中求出的 ,故被称为线性规划的基本解 .(要求令非基变量为 0, 然后从基中解出而得 )再看另一个基本解 :s.t.此方程有无穷多个解 ,为找最优解 ,可先令非基变量 :s2=s3=0x1=100, x2=250, s1= -50 ,外加 s2=0, s3=0求得满足约束条件的解 : 基本解S1=300, s2=400,s3=250 ,x1=0,x2=0,求得约束条件的解 : 基本解S1=300, s2=400,s3=250 ,x1=0,x2=0,S1= -50 为负 ,超出可行域的范围 ;无效 , 所有决策量非负 ,在可行域内 ,称为 基本可行解基本可行解 .相应地 , B被称为 可行基可行基 .线性规划求解流程 :确定初始基本可行解最优解？否转移到新的基本可行解给出最优解是基及基本解 :在求解最优解时 ,往往会首先找到一个 可行基 ,求出基本可行解 ,然后通过基本可行解 ,逐步迭代求出最优解 .一般经验认为 ,可找 A中的单位矩阵 .作为 (初始 )可行基 .二、最优性检验求出的基本可行解是否最优。还要进行检验！怎么检验？1。最优性检验的依据 -检验数 j是否最优，一般与目标函数的值有关，大家先来看目标函数的值：在目标函数中，有基变量，也有非基变量；由于基变量可以用非基变量代换掉，这样，目标式中只留下了非基变量。二、最优性检验目标式中只留下了非基变量。或者说，基变量的目标系数化为 0。在目标式中， Z0为常量（不变）， Xj0，只要看系数 j的情况，2。最优解判别定理定理：在求最大目标函数时，对于某个基本可行解，如果所有检验数 j0，则这个可行解就是最优解。其中，最大值就是 Z0。在求最小目标函数时，对于某个基本可行解，如果所有检验数 j0，则这个可行解就是最优解。其中，最小值就是Z0。三、基变换如果初始可行解不是最优解，那么，我们将要重新选择可行基，求出基本可行解，再检验。具体过程为 ：（ 1） 先确定入基变量。根据检验系数 j的大小确定把非基变量调入基中；一般认为，从 j0中挑选最大的非基变量替换到基变量中，这一过程称为入基变量过程。（ 2）同时，要从可行基中挑选出一个向量，作为出基变量。换出的原则是求出的决策变量非负；或者挑选比值最小的行的原基变量为出基变量。要求例 子例子的标准型标准型标准型化原则 :1.目标为 min型的 ,价值系数一律反号