【运筹学】线性规划 单纯形法 ( 基矩阵 | 基变量 | 非基矩阵 | 非基变量 | 矩阵分块形式 | 逆矩阵 | 基解 | 基可行解 )

文章目录

• • • • I . 基矩阵 B
      • II . 基向量 $P_j$
      • III . 基变量
      • IV . 非基矩阵 $N$
      • V . 系数矩阵分块形式 $A=(BN)$
      • VI . 基变量向量 $X_B$ 非基变量向量 $X_N$ 及 分块形式
      • VII . 分块形式的计算公式
      • VIII . 逆矩阵
      • IX . 解基变量
      • X . 基解
      • XI . 基可行解

I . 基矩阵 B

---

线性规划标准形式 , 约束方程的系数矩阵是 $A$ , 如下 :

$$\begin{gathered} A=\left[\begin{array}{cccccc} \\ & & & & & \\ & a_{11}& a_{12}& \cdots & a_{1n}& \\ & & & & & \\ & a_{21}& a_{22}& \cdots & a_{2n}& \\ & & & & & \\ & ⋮& ⋮& \ddots & ⋮& \\ & & & & & \\ & a_{m1}& a_{m2}& \cdots & a_{mn}& \\ & & & & & \end{array}\right] \end{gathered}$$

该矩阵 $A$ 是 $m\times n$ 阶矩阵 , 有 $m$ 行 , $n$ 列 , 代表 $m$ 个约束方程 , $n$ 个变量 , 并且 $n>m$ ;

基矩阵 $B$ :

• ① 满秩子矩阵 : 矩阵 $A$ 的 满秩子矩阵 $B$ , 矩阵 $B$ 的秩是 $m$ ;
• ② 列向量线性无关 : 该矩阵中的 列向量 线性无关 , 即 每一列不能通过 乘以系数 加减的方式得到另外一列列向量 ,
• ③ 基矩阵 $B$ : 这样的 系数矩阵 $A$ 的 $m\times m$ 阶满秩矩阵 $B$ 就是基矩阵 ;

$$\begin{gathered} B=\left[\begin{array}{cccccc} \\ & & & & & \\ & a_{11}& a_{12}& \cdots & a_{1m}& \\ & & & & & \\ & a_{21}& a_{22}& \cdots & a_{2m}& \\ & & & & & \\ & ⋮& ⋮& \ddots & ⋮& \\ & & & & & \\ & a_{m1}& a_{m2}& \cdots & a_{mm}& \\ & & & & & \end{array}\right]=\left[\begin{array}{cccccc}& P_1& P_2& \cdots & P_m& \end{array}\right] \end{gathered}$$

II . 基向量 $P_j$

---

基向量 :

• ① 概念 : 基矩阵 $B$ 中的每个列向量 , 都是一个 基向量 , 记作 $P_j$ , 其中 $j=1,2,\cdots ,m$ ;
• ② 基向量个数 : 每个基矩阵中有 $m$ 个列向量 ;

III . 基变量

---

基变量 : 每个基向量都对应一个变量 , 基向量是列向量 , 该列向量是 $x_j$ 变量的系数组成 , 这个对应的 $x_j$ 变量就是基变量 ;

IV . 非基矩阵 $N$

---

非基矩阵 $N$ : 确定一个基矩阵 , 剩下的列向量就是 非基向量 , 这些非基向量 组成 非基矩阵 $N$ ;

$$\begin{gathered} N=\left[\begin{array}{cccccc} \\ & & & & & \\ & a_{1m+1}& a_{1m+2}& \cdots & a_{1n}& \\ & & & & & \\ & a_{2m+1}& a_{2m+2}& \cdots & a_{2n}& \\ & & & & & \\ & ⋮& ⋮& \ddots & ⋮& \\ & & & & & \\ & a_{mm+1}& a_{mm+2}& \cdots & a_{mn}& \\ & & & & & \end{array}\right]=\left[\begin{array}{cccccc}& P_{m+1}& P_{m+2}& \cdots & P_n& \end{array}\right] \end{gathered}$$

V . 系数矩阵分块形式 $A=(BN)$

---

系数矩阵 $A$ , 可以写成分块形式 :

$$\begin{gathered} A=\left[\begin{array}{cccccc} \\ & & & & & \\ & a_{11}& a_{12}& \cdots & a_{1n}& \\ & & & & & \\ & a_{21}& a_{22}& \cdots & a_{2n}& \\ & & & & & \\ & ⋮& ⋮& \ddots & ⋮& \\ & & & & & \\ & a_{m1}& a_{m2}& \cdots & a_{mn}& \\ & & & & & \end{array}\right]=\left[\begin{array}{cccc}& B& N& \end{array}\right] \end{gathered}$$

VI . 基变量向量 $X_B$ 非基变量向量 $X_N$ 及 分块形式

---

基变量向量 $X_B$ :

$$\begin{gathered} X_B=\left[\begin{array}{ccc} \\ & & \\ & x_1& \\ & & \\ & x_2& \\ & & \\ & ⋮& \\ & & \\ & x_m& \\ & & \end{array}\right] \end{gathered}$$

非基变量向量 $X_N$ :

$$\begin{gathered} X_B=\left[\begin{array}{ccc} \\ & & \\ & x_{m+1}& \\ & & \\ & x_{m+2}& \\ & & \\ & ⋮& \\ & & \\ & x_n& \\ & & \end{array}\right] \end{gathered}$$

向量 $X$ 可以写成 $X_B$ 和 $X_N$ 分块形式 :

$$\begin{gathered} X=\left[\begin{array}{ccc} \\ & & \\ & x_1& \\ & & \\ & x_2& \\ & & \\ & ⋮& \\ & & \\ & x_n& \\ & & \end{array}\right]=\left[\begin{array}{ccc} \\ & & \\ & x_B& \\ & & \\ & x_N& \\ & & \end{array}\right] \end{gathered}$$

VII . 分块形式的计算公式

---

矩阵分块形式方程代入 : 约束方程组 $AX=b$ ;

$b$ 是大于 $0$ 的常数组成的向量 ;

将上述分块形式的 矩阵 $A$ 和 矩阵 $X$ 代入 上述 $AX=b$ 公式 ;

$$A=\left[\begin{array}{cccc}& B& N& \end{array}\right]$$
$$\begin{gathered} X=\left[\begin{array}{ccc} \\ & & \\ & X_B& \\ & & \\ & X_N& \\ & & \end{array}\right] \end{gathered}$$

得到

$$\begin{gathered} \left[\begin{array}{cccc}& B& N& \end{array}\right]\times \left[\begin{array}{ccc} \\ & & \\ & X_B& \\ & & \\ & X_N& \\ & & \end{array}\right]=b \end{gathered}$$

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

VIII . 逆矩阵

---

逆矩阵 : 其中矩阵 $B$ 是满秩的 $m\times m$ 阶矩阵 , 该矩阵是可逆的 ( 非奇异矩阵 ) , 必定存在一个 $B^{-1}$ , 使得
$$B\times B^{-1}=E$$

单位矩阵 : 这里的 矩阵 $E$ 是单位矩阵 , 即 左上角到右下角 对角线 上 的元素 为 $1$ , 其它元素为 $0$ ;
主对角线 : 左上角 到 右下角 的对角线称为 主对角线 ;
单位矩阵 示例 如下 :
$$E=\left[\begin{array}{ccccc}& 1& 0& 0& \\ & & & & \\ & 0& 1& 0& \\ & & & & \\ & 0& 0& 1& \end{array}\right]$$

IX . 解基变量

---

解基变量 :

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

将 $N{X}_N$ 提到公式右边 :

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

公式两边乘以 $B^{-1}$ :

$$B{X}_B\times B^{-1}=(b-N{X}_N)\times B^{-1}$$

$$X_B=B^{-1}b-B^{-1}N{X}_N$$

X . 基解

---

引入基解 : 令非基变量 $X_N$ 中所有变量为 $0$ , 此时上述公式为 :

$$X_B=B^{-1}b$$
约束方程的解为
$$X=\left[\begin{array}{ccc}& X_B& \\ & & \\ & 0& \end{array}\right]=\left[\begin{array}{ccc}& B^{-1}b& \\ & & \\ & 0& \end{array}\right]$$
上述解为基解 , 矩阵 $B$ 是满秩的 , 其秩为 $m$ , 将非基变量赋值 $0$ , 剩余的 $m$ 个变量 , $m$ 个等式 , 必能解出一组唯一解 ; 即
$$\sum _{j=1}^m{p}_j{x}_j=b$$
方程组有唯一解

$$X_B=\left[\begin{array}{ccc}& x_1& \\ & & \\ & x_2& \\ & & \\ & ⋮& \\ & & \\ & x_m& \end{array}\right]$$
该解 $X_B$ 是线性规划的一个基解 ;

XI . 基可行解

---

基可行解 : 如果上述解出的基解 $X_B$ , 满足线性规划数学模型 标准形式 的变量非负约束 , 即所有的变量都大于等于 $0$ , 该解称为基可行解 ;

并不是所有的基解都是基可行解 , 只有部分基解是基可行解 ;

总结

以上是生活随笔为你收集整理的【运筹学】线性规划 单纯形法 ( 基矩阵 | 基变量 | 非基矩阵 | 非基变量 | 矩阵分块形式 | 逆矩阵 | 基解 | 基可行解 )的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。