Lecture on Linear Programming 2

线性规划的解

1. 可行解：满足约束条件和变量非负要求的解 ；

2. 可行域（集）：全体可行解构成的区域（集合）；

3. 最优解：使目标函数取得最值的可行解；

4. 基：线性约束方程组的系数矩阵$A\in R^{m\ast n},m\le nA\backslash in\; R^\{m*n\},m\backslash leq\; n$的秩为m，则$AA$的满秩子阵$B\in R^{m\ast m}B\backslash in\; R^\{m*m\}$为一个基；

   • 基变量

   • 非基变量

   • 基向量

   • 基解：通过一确定的基，令非基变量为0，由约束方程组解出来的基变量，称为基解；

   • 基可行解：满足变量非负条件的基解，基解不一定是基可行解；

   • 可行基：对应于基可行解的基；

图解法

1. 适用二维的线性规划问题，但几何直观

2. 步骤：

   • 画出可行域
     • 线性规划若存在可行域，则是个凸集
   • 画出目标函数
   • 确定最优解：如果最优解存在，则一定在可行域的顶点取到
     • 唯一最优解
     • 无穷多最优解：目标函数平行于可行域的边界
     • 无可行解：可行域和目标最值方向不一致
     • 无界解：可行域是无界的

单纯性法

1. 凸集的顶点：不能用凸组合表示的点