(17)--2.3.1基本原理运筹学运筹学.pdf

基本原理

一、相关定义

定义1：如果集合C中任意两点x,x，其连线上的所

12

有点也都是集合C中的点，则称C为凸集，其中x,x

12

的连线可以表示为x+(1-)x(01).

12

数学语言可表为：对任意x,xC,均有

12

x+(1-)xC(01),

12

则称C为凸集。

定义2：如果集合C中不存在任何两个不同的点x,x,使

12

x为这两点连线上的一个点，即对任何不同的x1C,

xCxx+(1-)x(01),

2，不存在12

x

则称为凸集的顶点。

二、基本定理

定理1线性规划问题的可行域是凸集。

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

引理线性规划问题的可行解为基可行解的充要条件是它的正

分量所对应的系数列向量线性无关。

定理3若线性规划问题有最优解,一定存在一个基可行解是最

优解。

三、主要结论

★线性规划问题的可行域是一个凸集，可行域可能有界也

可能无界，但其顶点（极点）的个数是有限个；

★线性规划问题的每个基可行解对应于可行域的顶点；

★若线性规划问题有最优解，则其最优解必在可行域的某

个（或多个）顶点上达到。

▓寻求线性规划问题最优解的途径：在基可行解中寻求最优

解，而基可行解的个数有限，不会超过基解的个数，而基解

Cm

的个数不超过，其中m,n分别为线性规划问题约束条件中

n

系数矩阵A的行数和列数。

四、单纯形法原理

基本思想：开始于某一个基可行解，从一个基可行解迭代

到另一个基可行解，并且使目标函数值不断增大（单调不

减），经过有限步必能求得线性规划问题的最优解或者判

定线性规划问题无有界的最优解。

计算步骤：

初始基可行解

最优否？Y停止

N

新的基可行解

小结

▪凸集和顶点的定义

▪三个基本定理

▪单纯形法的基本思想和计算步骤