线性规划

基解与基可行解

它们对于理解和求解线性规划问题至关重要。

一、原理与定义

1. 基解（Basic Solution）

• 原理：基解是线性规划问题在特定基下的解，它是满足约束方程组的解，但不一定满足非负约束条件。
• 定义：在线性规划问题中，将约束方程组的系数矩阵A进行初等行变换，得到一个m阶非奇异子矩阵B（称为基矩阵），然后令非基变量等于零，通过求解方程组得到的解称为基解。

2. 基可行解（Basic Feasible Solution）

• 原理：基可行解是满足非负约束条件的基解，它是线性规划问题可行解的一个重要子集。
• 定义：在线性规划问题中，既满足约束方程组又满足非负约束条件的基解称为基可行解。

二、性质

• 基解与基可行解的关系：基解不一定是可行解，但基可行解一定是基解且是可行解。
• 存在性：如果线性规划问题有可行解，则必有基可行解。
• 有限性：基可行解的个数是有限的，因为基矩阵B的选取方式有限。

三、公式与计算

1. 基解的公式

• 基解的计算通常涉及对增广矩阵进行初等行变换，将约束方程组化为标准形式，然后令非基变量等于零，求解得到的基变量值即为基解。

2. 基可行解的判断

• 在得到基解后，需要判断其是否满足非负约束条件。如果满足，则该基解即为基可行解。

四、例子与例题

例子：

假设有一个简单的线性规划问题，目标函数为max Z = 2x1 + 3x2，约束条件为x1 + x2 ≤ 3，x2 ≤ 2，x1 ≥ 0，x2 ≥ 0。

• 选择基矩阵B：例如，选择x1和x2作为基变量，则基矩阵B为[1 1; 0 1]。
• 计算基解：令非基变量（本例中无非基变量）等于零，通过求解方程组[1 1; 0 1] [x1; x2] = [3; 2] 得到基解x1 = 3 - x2，x2 = 2。
• 判断基可行解：由于x1和x2都需要满足非负约束条件，因此只有当x2取值为2时（此时x1也非负），基解才成为基可行解，即x1 = 1，x2 = 2。

例题：

例题：求解线性规划问题max Z = 2x1 + 3x2，约束条件为x1 + 2x2 ≤ 8，2x1 + x2 ≤ 10，x1 ≥ 0，x2 ≥ 0。

• 选择基矩阵B：例如，选择x1和x2作为基变量，则基矩阵B为[1 2; 2 1]。
• 计算基解：通过引入松弛变量将不等式约束转化为等式约束，并令非基变量等于零，求解得到的基解可能涉及多个情况（因为基的选择不唯一）。
• 判断基可行解并优化：对于每个基解，判断其是否满足非负约束条件。然后，利用单纯形法等方法进一步迭代优化，以找到使目标函数值最大的基可行解。

请注意，上述例题的计算过程相对复杂，实际求解时通常需要使用专门的线性规划软件或算法（如单纯形法）来高效准确地找到最优解。

基解与基可行解定理

一、基解与基可行解的定义

1. 基解：

   • 定义：在线性规划问题中，将约束方程组的系数矩阵A进行初等行变换，得到一个m阶非奇异子矩阵B（称为基矩阵），然后令非基变量等于零，通过求解方程组得到的解称为基解。
   • 特点：基解只满足约束方程，但不一定满足非负约束条件。

2. 基可行解：

   • 定义：在线性规划问题中，既满足约束方程组又满足非负约束条件的基解称为基可行解。
   • 特点：基可行解是线性规划问题可行解的一个重要子集，也是寻找最优解的关键。

二、基解与基可行解的定理

1. 定理一：线性规划问题有可行解则必有基可行解

   • 解释：如果线性规划问题存在可行解，那么一定可以通过选择合适的基矩阵，找到一个基可行解。这一定理保证了在求解线性规划问题时，我们总可以在基可行解的集合中进行搜索。

2. 定理二：基可行解与可行域极点的等价性

   • 解释：线性规划的基可行解对应了可行域（凸集）的顶点位置。这意味着，我们可以通过搜索可行域的顶点（即基可行解）来找到线性规划问题的最优解。

3. 定理三：最优解的存在性与基可行解

   • 解释：如果线性规划问题存在最优解，那么一定存在一个基可行解是最优解。这一定理为我们使用单纯形法等算法在基可行解的集合中搜索最优解提供了理论依据。

三、基解与基可行解的计算与应用

1. 计算：

   • 基解的计算通常涉及对增广矩阵进行初等行变换，将约束方程组化为标准形式，然后令非基变量等于零，求解得到的基变量值即为基解。
   • 在得到基解后，需要判断其是否满足非负约束条件，以确定是否为基可行解。

2. 应用：

   • 基解与基可行解在线性规划的求解过程中起着至关重要的作用。它们不仅是理解线性规划问题几何特性的关键，也是设计求解算法（如单纯形法）的基础。
   • 通过搜索和迭代基可行解，我们可以高效地找到线性规划问题的最优解或判断其无最优解。

基解与基可行解更多定理的归纳：

一、线性规划可行域的性质

1. 定理一：线性规划可行域是凸集
   • 内容：若线性规划问题存在可行域，则其可行域D = { X | AX = b, X ≥ 0 }是一个凸集。
   • 解释：凸集的定义是集合中任意两点之间的连线上的点都属于该集合。线性规划问题的可行域满足这一性质，因为对于任意两个可行解X1和X2，以及任意的α∈[0,1]，αX1 + (1-α)X2也是可行解。

二、基可行解与顶点的关系

2. 定理二：基可行解对应于可行域的顶点
   • 内容：设线性规划问题的可行域为凸集，则X是可行域D的一个顶点的充分必要条件是X为线性规划问题的基可行解。
   • 解释：这一定理建立了基可行解与可行域顶点之间的一一对应关系。在线性规划中，我们可以通过搜索可行域的顶点（即基可行解）来找到最优解。

三、最优解的存在性与性质

3. 定理三：若线性规划问题有最优解，则必存在基可行解为最优解

   • 内容：若线性规划问题存在最优解，则一定存在一个基可行解是最优解。
   • 解释：这一定理保证了我们在求解线性规划问题时，可以通过搜索基可行解来找到最优解。单纯形法就是基于这一原理设计的。

4. 定理四：最优解位于可行域的顶点或边界上

   • 内容：若线性规划问题的可行域非空有界，则最优解一定存在于可行域的顶点或边界上。
   • 解释：这一定理是凸集性质和线性规划问题特性的直接结果。在凸集上，极值点（即最大值或最小值点）一定位于边界上，而在线性规划中，这些极值点对应于可行域的顶点或边界上的点。

四、线性规划问题的解的情况

5. 定理五：线性规划解的情况分类
   • 内容：
     • 线性规划有唯一解：此时，最优解恰好在可行域的某一个极点处取到。
     • 线性规划有无穷多个最优解：此时，最优解在可行域的某条棱上达到，这条棱上的所有点都是最优解。
     • 线性规划有可行解，但没有最优解：此时，可行域无界，目标函数无下界（对于最小化问题）或无上界（对于最大化问题）。
     • 线性规划无可行解：此时，可行域是空集。
   • 解释：这一定理对线性规划问题的解的情况进行了全面分类，有助于我们根据问题的具体情况选择合适的求解方法。

五、单纯形法的基本原理

6. 定理六（单纯形法的基本原理）
   • 内容：单纯形法通过迭代地选择进入基和离开基的变量，沿着改进目标函数值的方向移动，直至找到最优解或判断问题无界或无可行解。
   • 解释：单纯形法是求解线性规划问题的一种有效算法，其基本原理基于线性规划问题的几何特性和基可行解与顶点的对应关系。

这些定理共同构成了线性规划的理论基础，为我们理解和求解线性规划问题提供了有力的支持。在实际应用中，我们可以根据这些定理设计高效的求解算法，如单纯形法、对偶单纯形法等。

参考文献

1. 文心一言