运筹学_1.1.4 线性规划问题-解的概念

一、可行解与最优解

可行解：满足所由约束条件的解【全部可行解的集合称为可行域】
最优解：使目标函数最大的可行解
因此最优解包含于可行解

二、基的概念

基：设A是约束方程组（2）的m×n阶系数矩阵（设n>m，变量的个数大于方程的个数），其秩为m。
B是A中的一个m×m阶的满秩子矩阵（|B|≠0的非奇异子矩阵），则称B为线性规划问题的一个基。
B实际上就是A的一个极大线性无关组

问题1：为什么秩就为m？
实际过程中，在建模时列约束条件，默认列出来的方程为独立方程（而不会出现两个方程化简后相同的无效方程情况）

问题2：为什么n>m?
实际情况中，决策变量的个数通常也是大于方程的个数

三、基变量、基向量；非基变量、非基向量；基解、基可行解；

设方程组有m个方程，n个变量，其中n>m.R(A)=m,方程组有n-m个自由未知量，即方程组一定有无穷多个解。
n=m时只有唯一解，实际情况很少出现。

假设：方程组中前m个变量的系数列向量就是它的基向量（极大线性无关组）
则把（n-m）个非基向量移项到右边

非基变量可以是任意常数，因此令所有非基变量为0，又因为|B|≠0，据克莱姆法则，可求出唯一解；
从而得到第一个初始解XB
则X=（XB，XN）

因此，在约束方程组中的系数矩阵中找到一个基，就能求出一组基解

基解不一定是可行解
基解：根据基求得的解
基可行解：基解中所有分量都满足非负条件的解
可行基：对应于基可行解的基

四、最优解与可行解、基可行解的关系

最优解一定在可行解当中，那最优解一定包含在基可行解中吗？
1、当最优解唯一时，最优解也是基最优解；
2、当最优解不唯一时，最优解不一定是基最优解

五、用例题（枚举法）巩固基解、基可行解、最优解三个概念

基的数目为：C（m,n）－ 行列式为0的矩阵数，
基可行解为:分量都为非负的基解

1、例1

2、例2

六、解之间的关系归纳

可以用图解法辅助理解