运筹学(3)1-3_单纯形法第1部分

运 筹 学

运 筹 帷 幄 之 中

Operations Research

决 胜 千

线性规划Linear Programming

里 之 外

第四节 单纯形法

线性规划单纯形(Simplex)法单纯形法(Simplex Method)是美国人丹捷 格 (G.Dantzig)1947年创建的 这种方法简捷、规范，是举世公认的解决线 性规划问题行之有效的法。 单纯形法的表现形式：

代数法 表格法 矩阵法

一、单纯形法的基本思想 1、顶点的逐步转移即从可行域的一个顶点(基本可行解) 开始，转移到另一个顶点(另一个基本可行 解)的迭代过程，转移的条件是使目标函数 值得到改善 (逐步变优), 当目标函数达到最 优值时，问题也就得到了最优解。

顶点转移的依据？根据线性规划问题的可行域是凸多边形 或凸多面体，一个线性规划问题有最优解， 就一定可以在可行域的顶点上找到。 于是，若某线性规划只有唯一的一个最 优解，这个最优解所对应的点一定是可行域 的一个顶点；若该线性规划有多个最优解， 那么肯定在可行域的顶点中可以找到至少一 个最优解。

转移条件？

转移结果？

使目标函数值得到改善

得到LP最优解，目标函数达到最优值(单纯形法的由来？ )

2.需要解决的问题：(1)为了使目标函数逐步变优，怎么转移？

(2)目标函数何时达到最优—判断标准是什么？

二、单纯形法原理(用代数方法求解LP) 例1-6max Z 2 x1 3x 2 3x3 x1 x 2 x3 3 s.t. x1 4 x 2 7 x3 9 x , x , x 0 1 2 3 (劳动力约束) (原材料约束)

第一步：引入非负的松弛变量x4,x5, 将该 LP化为标准型max Z 2 x1 3x 2 3x3 0 x 4 0 x5 x1 x 2 x3 x 4 3 s.t. x1 4 x 2 7 x3 x5 9 x , x , x , x , x 0 1 2 3 4 5 (劳动力约束) (原材料约束)

第二步：寻求初始可行基，确定基变量 1 1 1 1 0 A 1 4 7 0 1 1 0 B P4 , P5 0 1

对应的基变量是

x4,x5;

第三步：写出初始基本可行解和相应 的目标函数值

两个关键的基本表达式：

①用非基变量表示基变量的表达式

x4 3 x1 x2 x3 x5 9 x1 4 x2 7 x3 (0) T 初始基本可行解 X (0,0,0,3,9)

②用非基变量表示目标函数的表 达式

Z 2 x1 3x2 3x3当前的目标函数值请解释结果的经济含义 ——不生产任何产品，资源全部节余

Z( 0)

0

(x4=3,x5=9), 三种产品的总利润为0!

第四步：分析两个基本表达式，看看目 标函数是否可以改善？① 分析用非基变量表示目标函数的表达式

Z 2 x1 3x2 3x3非基变量前面的系数均为正数，所以任何一 个非基变量进基都能使Z值

增加 通常把非基变量前面的系数叫“检验数”;

② 选哪一个非基变量进基？选x1为进基变量(换入变量) 问题：能否选其他的非基变量进基？ 任意一个

×

任意一个正检验数对应的非基变量

最大正检验数对应的非基变量

排在最前面的正检验数对应的非基变量

③ 确定出基变量：

问题讨论 x1进基意味着其取值从0变成一个正数(经济 意义——生产A产品),能否无限增大？ 当x1增加时，x4,x5如何变化？ 现在的非基变量是哪些？ 具体如何确定换出变量？

由用非基变量表示基变量的表达式 x 4 3 x1 x 2 x 3 x 5 9 x1 4 x 2 7 x 3

当x1增加时，x4,x5会减小，但有限度——必 须大于等于0,以保持解的可行性！于是 x4 3 x1 0 x5 9 x1 0 3 x1 1 9 x1 1 3 9 x1 min , 3 1 1

当x1的值从0增加到3时，x4首先变为 0,此时x5=6>0 因此选x4为出基变量(换出变量)(最小 θ值对应的基变量为出基变量).

这种用来确定出基变量的规则称为 “最小比值原则”(或θ原则)。 如果P1≤0,会出现什么问题？最小比值原则会失效！