线性规划——规范型，标准型，基阵、基本解、基本可行解、基变量、非基变量.... 概念梳理_综合

文章目录

前言
最优化—线性规划
- 模型问题
- - 线性规划模型的一般形式（min）
  - 线性规划规范形式
  - 线性规划标准型
  - 模型的转换
  - 线性规划中的规律
  - - 规范形式顶点的数学描述
    - 标准形式顶点的数学描述
    - 标准形式顶点的等价描述之一
    - 标准形式顶点的等价描述之二
  - 线性规划标准形式的一些基本概念
  - 线性规划标准形式的基本定理

前言

此总结参考清华王焕刚老师的课，本人只是渣渣辉。

最优化—线性规划

模型问题

线性规划模型的一般形式（min）

$∑j=1naijxj=bi,?1≤i≤p∑j=1naijxj≥bi,?p+1≤i≤mxj≥0,?1≤j≤q∞>xj>?∞,?q+1≤j≤n\begin{array}{l} \min \sum_{j=1}^{n} c_{j} x_{j} \\ \text { s.t. } \quad \sum_{j=1}^{n} a_{i j} x_{j}=b_{i}, \quad \forall 1 \leq i \leq p \\ \quad \sum_{j=1}^{n} a_{i j} x_{j} \geq b_{i}, \quad \forall p+1 \leq i \leq m \\ \quad x_{j} \geq 0, \forall 1 \leq j \leq q \\ \quad \infty>x_{j}>-\infty, \forall q+1 \leq j \leq n \end{array}$

线性规划规范形式

在这里插入图片描述

线性规划标准型

$\left.\begin{array}{ll} \max \quad c_{1} x_{1}+c_{2} x_{2}+\cdots+c_{n} x_{n} & \text { 目标函数 } \\ \text { s.t. } \quad a_{11} x_{1}+a_{12} x_{2}+\cdots+a_{1 n} x_{n}=b_{1} \\ \quad \quad \quad a_{21} x_{1}+a_{22} x_{2}+\cdots+a_{2 n} x_{n}=b_{2} \\ \quad \quad \quad \quad \quad \quad \quad \vdots \\ \quad \quad \quad a_{m 1} x_{1}+a_{m 2} x_{2}+\cdots+a_{m n} x_{n}=b_{m} \end{array}\right\} \text { 等式约束 }$

$x1≥0x2≥0?xn≥0}决策变量具有非负约束\left.\begin{array}{c} x_{1} \geq 0 \\ x_{2} \geq 0 \\ \vdots \\ x_{n} \geq 0 \end{array}\right\} \text {决策变量具有非负约束}$

$AX=b?xj≥0,?1≤j≤nX≥0C=(c1?cn)X=(x1?xn)A=(a11?a1n???am1?amn)b?=(b1?bm)\begin{array}{l} \min (\text { or } \max ) \sum_{j=1}^{n} c_{j} x_{j} \quad\quad\quad\quad\quad\quad\quad\quad \min (\text { or } \max ) C^{T} X \\ \text { s.t. } \sum_{j=1}^{n} a_{i j} x_{j}=b_{i}, \quad \forall 1 \leq i \leq m \quad \Rightarrow \quad \text { s.t. } \quad A X=\vec{b} \\ x_{j} \geq 0, \forall 1 \leq j \leq n \quad \quad \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad X\geq0\\ C=\left(\begin{array}{c} c_{1} \\ \vdots \\ c_{n} \end{array}\right) \quad X=\left(\begin{array}{c} x_{1} \\ \vdots \\ x_{n} \end{array}\right) \quad A=\left(\begin{array}{ccc} a_{11} & \cdots & a_{1 n} \\ \vdots & \ddots & \vdots \\ a_{m 1} & \cdots & a_{m n} \end{array}\right) \quad \vec{b}=\left(\begin{array}{c} b_{1} \\ \vdots \\ b_{m} \end{array}\right) \end{array}$

以后我们所考虑的线性规划标准型为:
$AX=b?X≥0\begin{array}{c} \max C^{T} X \\ \text { s.t. } A X=\vec{b} \\ X \geq 0 \end{array}$
其中 $\in R^{n}, X \in R^{n}, A \in R^{m \times n}, \vec{b} \in R^{m},$ 并假定

$n > m$
$A$ 的行向量线性无关

模型的转换

对于模型间的转换，其实就是一些变量的添加和符号的改变
在这里插入图片描述

线性规划中的规律

一维、二维、三维规划中：

可行集中任意两点的连线都在可行集内：凸集
最优解都不在两个不同点的连线上：顶点
所有顶点的个数有限：有限集

线性规划的可行集是凸集，标准线性规划问题也是凸集。

所以高纬要解决的问题是：1 可行集是否是凸集，2 顶点集为有限集 3 在顶点集中找到最优解

如果这些问题确定了后，关键就是找到顶点了

规范形式顶点的数学描述

规范形式可行集 $Ω:∑j=1naijxj≥bi,?1≤i≤m\Omega: \sum_{j=1}^{n} a_{i j} x_{j} \geq b_{i}, \quad \forall 1 \leq i \leq m$
$xj≥0,?1≤j≤nx_{j} \geq 0, \forall 1 \leq j \leq n$
对任意的 $\in \Omega,$ 将所有的线性不等式进行如下划分
$∑j=1naijxj=bi,i=k(1),?,k(m^),xj=0,j=k(m^+1),?,k(n^)∑j=1naijxj>bi,?i?{k(1),?,k(m^)},xj>0,?j?{k(m^+1),?,k(n^)}\begin{array}{l} \sum_{j=1}^{n} a_{i j} x_{j}=b_{i}, i=k(1), \cdots, k(\hat{m}), x_{j}=0, j=k(\hat{m}+1), \cdots, k(\hat{n}) \\ \sum_{j=1}^{n} a_{i j} x_{j}>b_{i}, \forall i \notin\{k(1), \cdots, k(\hat{m})\}, x_{j}>0, \forall j \notin\{k(\hat{m}+1), \cdots, k(\hat{n})\} \end{array}$
那么当且仅当等式方程组的解唯一时 $X$ 是 $Ω\Omega$ 的顶点

标准形式顶点的数学描述

$Ω:∑j=1naijxj=bi,?1≤i≤mxj≥0,?1≤j≤n\begin{aligned} \Omega: & \sum_{j=1}^{n} a_{i j} x_{j}=b_{i}, \quad \forall 1 \leq i \leq m \\ & x_{j} \geq 0, \forall 1 \leq j \leq n \end{aligned}$

由于由等式方程约束条件产生的只能是等式，所以对任意的 $\in \Omega$ 可进行如下划分（注意 $n > m ）$
$∑j=1naijxj=bi,?1≤i≤m,xj>0,j=k(1),?,k(m^)xj=0,j=k(m^+1),?,k(n)\sum_{j=1}^{n} a_{i j} x_{j}=b_{i}, \forall 1 \leq i \leq m, \begin{array}{c} x_{j}>0, j=k(1), \cdots, k(\hat{m}) \\ x_{j}=0, j=k(\hat{m}+1), \cdots, k(n) \end{array}$
当且仅当上面的等式方程组解唯一时 $X$ 是 $Ω\Omega$ 的顶点

总结：如果一个点 $\in \Omega$ ，使得一些约束求作用（使得一些不等式的等号成立），若对于这些成立的约束构成的线性方程组来说，它的解不只是 $X$ ，那么 $X$ 不是 $Ω\Omega$ 的顶点。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Yh711aPx-1607047943335)(最优化—线性规划.assets/image-20201204092908344.png)]

标准形式顶点的等价描述之一

$∑j=1naijxj=bi,?1≤i≤m?∑j=1n(a1j?amj)xj=(b1?bm)?∑j=1nPjxj=b?Pj=(a1j,?,amj)T,?1≤j≤nxj>0,j=k(1),?,k(m^)∑j=1naijxj=bi,?1≤i≤m,xj=0,j=k(m^+1),?,k(n)?xk(j)>0,?1≤j≤m^,∑j=1mPk(j)xk(j)=b?\begin{array}{l} \sum_{j=1}^{n} a_{i j} x_{j}=b_{i}, \forall 1 \leq i \leq m \Rightarrow \sum_{j=1}^{n}\left(\begin{array}{c} a_{1 j} \\ \vdots \\ a_{m j} \end{array}\right) x_{j}=\left(\begin{array}{c} b_{1} \\ \vdots \\ b_{m} \end{array}\right) \\ \Rightarrow \sum_{j=1}^{n} P_{j} x_{j}=\vec{b} \quad P_{j}=\left(a_{1 j}, \cdots, a_{m j}\right)^{T}, \forall 1 \leq j \leq n \\ \qquad \begin{array}{c} x_{j}>0, \quad j=k(1), \cdots, k(\hat{m}) \\ \sum_{j=1}^{n} a_{i j} x_{j}=b_{i}, \forall 1 \leq i \leq m, x_{j}=0, \quad j=k(\hat{m}+1), \cdots, k(n) \\ \Rightarrow x_{k(j)}>0, \forall 1 \leq j \leq \hat{m}, \quad \sum_{j=1}^{m} P_{k(j)} x_{k(j)}=\vec{b} \end{array} \end{array}$

当且仅当 $\in \Omega$ 的正分量对应的系数向量线性无关

标准形式顶点的等价描述之二

如果 $(P1,?,Pn)\left(P_{1}, \cdots, P_{n}\right)$ 是行满秩矩阵，那么 $X$ 是可行集
$Ω={X=(x1,?,xn)T∣∑j=1nPjxj=b?,xj≥0,?1≤j≤n}\Omega=\left\{X=\left(x_{1}, \cdots, x_{n}\right)^{T} \mid \sum_{j=1}^{n} P_{j} x_{j}=\vec{b}, x_{j} \geq 0, \forall 1 \leq j \leq n\right\}$
的顶点充要条件是：存在可逆方阵 $(Pk(1),?,Pk(m))\left(P_{k(1)}, \cdots, P_{k(m)}\right)$ , 可以把 $X$ 的分量划分为 $xk(j),j=1,?,n,x_{k(j)}, j=1, \cdots, n,$ 使满足
$(xk(1)?xk(m))=(Pk(1),?,Pk(m))?1b?≥0,xk(j)=0,?m+1≤j≤n\left(\begin{array}{c}x_{k(1)} \\ \vdots \\ x_{k(m)}\end{array}\right)=\left(P_{k(1)}, \cdots, P_{k(m)}\right)^{-1} \vec{b} \geq 0, \quad x_{k(j)}=0, \forall m+1 \leq j \leq n$
主要理由 $\large : \sum_{j=1}^{m} P_{k(j)} x_{k(j)}=\vec{b} \Rightarrow \begin{array}{l}\text { 正分量对应的系 } \\ \text { 数向量线性无关 }\end{array}$

线性规划标准形式的一些基本概念

基阵、基本解、基本可行解、基变量、非基变量
称可逆矩阵 $(Pk(1),?,Pk(m))\left(P_{k(1)}, \cdots, P_{k(m)}\right)$ 为基阵
称其分量由下式决定的 $X$ 为基本解
$(xk(1)?xk(m))=(Pk(1),?,Pk(m))?1b?,xk(j)=0,?m+1≤j≤n\left(\begin{array}{c} x_{k(1)} \\ \vdots \\ x_{k(m)} \end{array}\right)=\left(P_{k(1)}, \cdots, P_{k(m)}\right)^{-1} \vec{b}, x_{k(j)}=0, \forall m+1 \leq j \leq n$
称可行的基本解为基本可行解 称基阵对应变量为基变量，其余变量为非基变量
标准线性规划的基本可行解就是可行集的顶点
标准线性规划的可行集的顶点个数总是有限的

线性规划标准形式的基本定理

【定理1】一个标准形式线性规划问题若有可行解，则至少存在一个基本可行解
【定理2】一个标准形式线性规划问题若有有限的最优目标值，则一定存在一个基本可行解是最优解
【定理3】如果标准线性规划问题的某个基可行解的相邻的基可行解都不比它好，那么这个基可行解就是最优解

综上所述：对于线性规划，只用求得它的基本可行解，就能在有限的基本可行解中找到最优解。