一、线性规划求解

在上一篇博客 【运筹学】线性规划数学模型 ( 求解基矩阵示例 | 矩阵的可逆性 | 线性规划表示为 基矩阵 基向量 非基矩阵 非基向量 形式 ) 中 , 将线性规划的等式表示为以下形式 :

$$B{X}_B+N{X}_N=b$$

写成上述形式之后 , 就可以表示出上述等式的解 , 如果上述等式解满足线性规划约束变量的要求 , 即所有的变量都大于等于 0 , 那么该解就是线性规划的解 ;

上述式子中 , $X_N$ 非基变量 , 是可以随意取值的变量 ;

只要非基变量 $X_N$ 取定一组解 , 基变量 $X_B$ 就可以被唯一确定 ;

( X B X N )

二、根据非基变量的解得到基变量解

如何根据非基变量 $X_N$ 的解 , 确定基变量 $X_B$ 的解 ?

基矩阵 $B$ 是可逆的 , 那么 $B$ 的逆矩阵 $B^{-1}$ 是存在的 , 上述方程 $B{X}_B+N{X}_N=b$ 左右两端 , 都乘以 $B^{-1}$ , 如下计算 :

B X B + N X N = b ( B X B + N X N ) × B − 1 = B − 1 b I × X B + B − 1 N X N = B − 1 b X B = B − 1 b − B − 1 N X N

其中 $I$ 是单位阵 , 单位阵乘以矩阵 $X_B$ 其结果还是 $X_B$ ;

关于单位阵 , 参考 单位矩阵 - 百度百科

上述式子最终得到 $X_B=B^{-1}b-B^{-1}N{X}_N$ , 此时 如果非基变量的值 $X_N$ 已经解出来 , 那么 基变量 $X_B$ 可以通过上述表达式表示出来 ;

三、基解

给定一个基矩阵 $B$ , 约束方程可以转化成 $X_B=B^{-1}b-B^{-1}N{X}_N$ 形式 , 只要给定一组 $X_N$ 的解 , 就可以 得到一组 $X_B$ 的解 ;

非基变量 $O$ 解 : 找到 $X_N$ 的一组最简单的解 , 这里随意找一组 $X_N$ 的解都可以 , 最简单的一组解就是 $X_N$ 的所有值都是 $0$ , 即让所有的非基变量等于 $0$ , 此时 $X_N$ 为零矩阵 , 使用 $O$ 表示 ;

对应基变量的解 : 将所有的非基变量等于 $0$ , 即 $X_N=O$ 的条件代入 $X_B=B^{-1}b-B^{-1}N{X}_N$ 中 , 有 :

$$X_B=B^{-1}b$$

此时线性规划的解为 : ( B − 1 b O )

基矩阵 $B$ -> 非基变量解 $O$ -> 基变量解 $B^{-1}b$ : 基解最根本是先确定基矩阵 $B$ , 确定 基矩阵 $B$ 之后 , 就可以将变量分为基变量 和 非基变量 , 此时将非基变量取值为零矩阵 $O$ , 得到基变量的解 $B^{-1}b$ ;

基解 $X_B$ 是由基矩阵 $B$ 唯一确定的 ; 只要给定基矩阵 , 就可以唯一确定基解 ;

基解个数 : 一个线性规划中的基解个数 , 就是基矩阵可数 , 就是可逆矩阵个数 ;

通常情况下的基解个数 : 系数矩阵 $A$ , 是 $m\times n$ 维的矩阵 , $m$ 行等式 , $n$ 个变量 , 其任意 $m$ 列向量 , 组成的 $m$ 阶方阵 , 都是可逆矩阵 , 其有 $C(n,m)$ 个基矩阵 , 也有 $C(n,m)$ 组基解 ;

基解定义 : 确定一个 $m\times n$ 阶系数矩阵的基矩阵 $B$ , 令非基变量 $X_N$ 等于 $0$ , 有约束条件 $X_B=B^{-1}b-B^{-1}N{X}_N$ 可以解出其基变量 $X_B$ , 这组 ( B − 1 b O )

四、基可行解

完整的线性规划标准形式如下 :

m a x Z = ∑ j = 1 n c j x j s . t { ∑ j = 1 n a i j x j = b i i = 1 , 2 , ⋯   , m x j ≥ 0 j = 1 , 2 , ⋯   , n

上述的基解 , 只是根据 ${\sum }_{j=1}^n{a}_{ij}{x}_j=b_i(i=1,2,\cdots ,m)$ 约束条件等式解出的 ;

还需要满足 $x_j\ge 0(j=1,2,\cdots ,n)$ 条件 ;

基可行解定义 : 满足线性规划中的 $x_j\ge 0(j=1,2,\cdots ,n)$ 约束条件的 基解 , 称为 基可行解 ;

给定线性规划系数矩阵 $m\times n$ 阶 :

• 其可行解个数是无限的 , 因为其非基变量 $X_N$ 可以有无限种取值 , 对应的基变量 $X_B$ 也有无限种取值 ;
• 其基解个数是有限的 , 因为非基变量只能取 $O$ 零矩阵 , 对应的基变量也是有限的 , 不超过 $C_n^m$ 个 ;

可行解有无穷多个 , 基解是有限个 , 如果一个解既是基解 , 又是可行解 , 那么称该解是基可行解 ;

基解个数是有限的 , 基可行解 是 基解 与 可行解 的交集 , 基可行解的个数必然也是有限的 ;

迭代思想 : 在解里面找到一个解 , 看该解是否是最优的 , 如果不是 , 就迭代到下一个解 , 继续重复查看该解是否是最优 ; 如果迭代的集合是有限的 , 其肯定要比无限的集合简单很多 ;

因此线性规划中 , 在有限个基可行解中 , 迭代查找最优解 , 将搜索范围从无限个可行解 , 变成了有限个基可行解 ;

五、可行基

可行基 : 基可行解 对应的 基矩阵 $B$ , 就是 可行基 ;

使用 $X_B=B^{-1}b-B^{-1}N{X}_N$ , 代入 $X_N=O$ , 解出其基变量 $X_B$ , 这组 ( B − 1 b O )

文章来源: hanshuliang.blog.csdn.net，作者：韩曙亮，版权归原作者所有，如需转载，请联系作者。

原文链接：hanshuliang.blog.csdn.net/article/details/107305467