单纯形法基本原理课件.pdfVIP

单纯形法基本原理

单纯形法基本原理Page1

凸集：如果集合C中任意两个点X1、X2，其连线上的所有点

也都是集合C中的点，称C为凸集。

凸集凸集不是凸集

顶点

单纯形法基本原理

单纯形法基本原理Page2

定理1：若线性规划问题存在可行解，则该问题的可行域是

凸集。

定理2：线性规划问题的基可行解X对应可行域(凸集)的顶点。

定理：线性规划问题的基可行解对应可行域凸集的顶点。

2X()

定理3：若问题存在最优解，一定存在一个基可行解是最优

解。（或在某个顶点取得）

单纯形法的计算步骤

单纯形法的计算步骤Page3

单纯形法的思路

单纯形法的思路

找出一个初始可行解

找出一个初始可行解

是

是

是否最优

是否最优最优解

最优解

循

循

否

环否

环结束

结束

转移到另一个基本可行解

转移到另一个基本可行解

（找出更大的目标函数值）

（找出更大的目标函数值）

核心是：变量迭代

核心是：变量迭代

单纯形法的计算步骤

单纯形法的计算步骤Page4

单纯形表

单纯形法的计算步骤

单纯形法的计算步骤Page5

例1.8用单纯形法求下列线性规划的最优解

解：1）将问题化为标准型，加入松驰变量x3、x4则标准型为:

单纯形法的计算步骤

单纯形法的计算步骤Page6

2）求出线性规划的初始基可行解，列出初始单纯形表。

c3400

j