王树尧老师运筹学课程笔记 06 线性规划与单纯形法（几何意义）

第6讲 线性规划与单纯形法（几何意义）

线性规划的几何意义

图解法

线性规划的维度	变量	可行域维度	图像维度
1	$x_1$	1（线段）	1
2	$x_1、x_2$	2（平面）	2
3	$x_1、x_2、x_3$	3（立体）	3
n	$x_1、x_2、\dots 、x_n$	n（n维超立方体）	n

图解法有很大局限性，在二维情况下最好用，三维理论上可以，但很难操作，基本不使用。因此，当维度较高时需要使用单纯形法。

单纯形法

单纯形法的核心思想

1. 解出所有约束方程的交点，包括可行域的顶点和非可行域的顶点。（只要约束条件有限，交点个数一定是有限的。）
2. 把所有交点的坐标带入目标函数中，其对应的函数值中最大的就是最大值，最小的就是最小值。

局限性：当交点数量过多时，计算量过大。

试点法

由于枚举法的工作量较大，因此采用试点法，即先选择一个点，然后研究其周边的点，如果最开始的点对应的函数值最大或最小，则其为最优解。

单纯形

在某个维度下面数最少或边数最少的线性几何图形。

维度	单纯形
0	点
1	线段
2	三角形
3	四面体

解的情况

线性规划问题的求解结果有3种：无穷多最优解（多重最优解）、无界解和无解。

如果可行域是封闭的则一定有最优解，可能有唯一最优解或无穷多个最优解。如果可行域是无界的，可能在无界处取到无界解，也可能有唯一最优解或无穷多个最优解。如果画不出可行域，则无解。

几个定理

定理1（教材P24）：若线性规划问题存在可行域，则其可行域是凸集。

定理2（教材P25）：线性规划问题的基可行解$X$对应于可行域$D$的顶点。

定理3（教材P26）：若可行域有界，线性规划问题的目标函数一定可以在其可行域的顶点上达到最优。

总结

对于线性规划问题，由于图解法在处理三维及以上的情况时会失效，因此需要使用单纯形法。同时由于枚举法的工作量较大，因此采用试点法，即先选择一个点，然后研究其周边的点，如果最开始的点对应的函数值最大或最小，则其为最优解。

如果可行域是封闭的则一定有最优解，可能有唯一最优解或无穷多个最优解。如果可行域是无界的，可能在无界处取到无界解，也可能有唯一最优解或无穷多个最优解。如果画不出可行域，则无解。

可行域是凸集。