提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  后端

当前栏目

【运筹学】线性规划数学模型 ( 线性规划求解 | 根据非基变量的解得到基变量解 | 基解 | 基可行解 | 可行基 )

变量 根据 得到 求解 可行 运筹学 线性规划 数学模型
2023-06-13 09:17:43 时间

文章目录

一、线性规划求解

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

BX_B + NX_N = b

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

上述式子中 ,

X_N

非基变量 , 是可以随意取值的变量 ;

只要非基变量

X_N

取定一组解 , 基变量

X_B

就可以被唯一确定 ;

\begin{pmatrix} X_B \\ X_N \\ \end{pmatrix}

就是 方程组完整的解 ;

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

如何根据非基变量

X_N

的解 , 确定基变量

X_B

的解 ?

基矩阵

B

是可逆的 , 那么

B

的逆矩阵

B^{-1}

是存在的 , 上述方程

BX_B + NX_N = b

左右两端 , 都乘以

B^{-1}

, 如下计算 :

\begin{array}{lcl} BX_B + NX_N &=& b\\\\ ( BX_B + NX_N ) \times B^{-1} &=& B^{-1}b \\\\ I \times X_B + B^{-1}NX_N &=& B^{-1}b\\\\ X_B & = & B^{-1}b - B^{-1}NX_N \end{array}

其中

I

是单位阵 , 单位阵乘以矩阵

X_B

其结果还是

X_B

;

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

上述式子最终得到

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

, 此时 如果非基变量的值

X_N

已经解出来 , 那么 基变量

X_B

可以通过上述表达式表示出来 ;

三、基解

给定一个基矩阵

B

, 约束方程可以转化成

X_B = B^{-1}b - B^{-1}NX_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}NX_N

中 , 有 :

X_B = B^{-1}b

此时线性规划的解为 :

\begin{pmatrix} B^{-1}b \\ O \\ \end{pmatrix}

, 其中

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}NX_N

可以解出其基变量

X_B

, 这组

\begin{pmatrix} B^{-1}b \\ O \\ \end{pmatrix}

解 , 称为基解 ; 基解中的变量取非

0

值的个数 , 不超过等式个数

m

, 基解总数不超过

C(n,m)

;

四、基可行解

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

\begin{array}{lcl}max Z = \sum_{j = 1}^{n} c_j x_j\\\\ s.t \begin{cases} \sum_{j = 1}^{n} a_{ij} x_j = b_i & i = 1,2,\cdots,m \\ \\ x_j \geq 0 & j= 1, 2,\cdots,n \end{cases}\end{array}

上述的基解 , 只是根据

\sum_{j = 1}^{n} a_{ij} x_j = b_i \quad ( i = 1,2,\cdots,m)

约束条件等式解出的 ;

还需要满足

x_j \geq 0 \quad ( j= 1, 2,\cdots,n)

条件 ;

基可行解定义 : 满足线性规划中的

x_j \geq 0 \quad ( j= 1, 2,\cdots,n)

约束条件的 基解 , 称为 基可行解 ;

给定线性规划系数矩阵

m \times n

阶 :

  • 其可行解个数是无限的 , 因为其非基变量
X_N

可以有无限种取值 , 对应的基变量

X_B

也有无限种取值 ;

  • 其基解个数是有限的 , 因为非基变量只能取
O

零矩阵 , 对应的基变量也是有限的 , 不超过

C_n^m

个 ;

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

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

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

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

五、可行基

可行基 : 基可行解 对应的 基矩阵

B

, 就是 可行基 ;

使用

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

, 代入

X_N = O

, 解出其基变量

X_B

, 这组

\begin{pmatrix} B^{-1}b \\ O \\ \end{pmatrix}

基解 ,

X_N

中的非基变量解肯定是大于等于

0

的 , 如果

B^{-1}b

中有负分量 , 那么该解不是基可行解 , 对应的基矩阵

X_B

不是可行基 ;

相关文章