运筹学

1.1.4 线性规划问题-解的概念

• 一、可行解与最优解
• 二、基的概念
• 三、基变量、基向量；非基变量、非基向量；基解、基可行解；
• 四、最优解与可行解、基可行解的关系
• 五、用例题（枚举法）巩固基解、基可行解、最优解三个概念
• • 1、例1
  • 2、例2
  • ��、解之间的关系归纳

    一、可行解与最优解

    可行解：满足所由约束条件的解【全部可行解的集合称为可行域】

    最优解：使目标函数最大的可行解

    因此最优解包含于可行解

    二、基的概念

    基：设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

    六、解之间的关系归纳

    可以用图解法辅助理解