线性规划——规范型，标准型，基阵、基本解、基本可行解、基变量、非基变量.... 概念梳理 -凯发k8官方网
文章目录
- 前言
- 最优化—线性规划
- 模型问题
- 线性规划模型的一般形式（min）
- 线性规划规范形式
- 线性规划标准型
- 模型的转换
- 线性规划中的规律
- 规范形式顶点的数学描述
- 标准形式顶点的数学描述
- 标准形式顶点的等价描述之一
- 标准形式顶点的等价描述之二
- 线性规划标准形式的一些基本概念
- 线性规划标准形式的基本定理
此总结参考 清华 王焕刚老师的课，本人只是渣渣辉。
模型问题
线性规划模型的一般形式（min）
min∑j=1ncjxjs.t. ∑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} min∑j=1ncjxj s.t. ∑j=1naijxj=bi,∀1≤i≤p∑j=1naijxj≥bi,∀p1≤i≤mxj≥0,∀1≤j≤q∞>xj>−∞,∀q1≤j≤n
线性规划规范形式
线性规划标准型
maxc1x1 c2x2 ⋯ cnxn目标函数 s.t. a11x1 a12x2 ⋯ a1nxn=b1a21x1 a22x2 ⋯ a2nxn=b2⋮am1x1 am2x2 ⋯ amnxn=bm}等式约束 \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 { 等式约束 } maxc1x1c2x2⋯cnxn s.t. a11x1a12x2⋯a1nxn=b1a21x1a22x2⋯a2nxn=b2⋮am1x1am2x2⋯amnxn=bm 目标函数 ⎭⎪⎪⎪⎪⎪⎬⎪⎪⎪⎪⎪⎫ 等式约束
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 {决策变量具有非负约束} x1≥0x2≥0⋮xn≥0⎭⎪⎪⎪⎬⎪⎪⎪⎫决策变量具有非负约束
min(or max)∑j=1ncjxjmin(or max)ctxs.t. ∑j=1naijxj=bi,∀1≤i≤m⇒s.t. 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} min( or max)∑j=1ncjxjmin( or max)ctx s.t. ∑j=1naijxj=bi,∀1≤i≤m⇒ s.t. ax=bxj≥0,∀1≤j≤nx≥0c=⎝⎜⎛c1⋮cn⎠⎟⎞x=⎝⎜⎛x1⋮xn⎠⎟⎞a=⎝⎜⎛a11⋮am1⋯⋱⋯a1n⋮amn⎠⎟⎞b=⎝⎜⎛b1⋮bm⎠⎟⎞
以后我们所考虑的线性规划标准型为:
maxctxs.t. ax=b⃗x≥0\begin{array}{c} \max c^{t} x \\ \text { s.t. } a x=\vec{b} \\ x \geq 0 \end{array} maxctx s.t. ax=bx≥0
其中 c∈rn,x∈rn,a∈rm×n,b⃗∈rm,c \in r^{n}, x \in r^{n}, a \in r^{m \times n}, \vec{b} \in r^{m},c∈rn,x∈rn,a∈rm×n,b∈rm, 并假定
模型的转换
对于模型间的转换，其实就是一些变量的添加和符号的改变
线性规划中的规律
一维、二维、三维规划中：
线性规划的可行集是凸集，标准线性规划问题也是凸集。
所以高纬要解决的问题是：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ω:∑j=1naijxj≥bi,∀1≤i≤m
xj≥0,∀1≤j≤nx_{j} \geq 0, \forall 1 \leq j \leq n xj≥0,∀1≤j≤n
对任意的 x∈ω,x \in \omega,x∈ω, 将所有的线性不等式进行如下划分
∑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} ∑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^)}
那么当且仅当等式方程组的解唯一时 xxx 是 ω\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} ω:j=1∑naijxj=bi,∀1≤i≤mxj≥0,∀1≤j≤n
由于由等式方程约束条件产生的只能是等式，所以 对任意的 x∈ωx \in \omegax∈ω 可进行如下划分（注意 n>m）n>m ）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} j=1∑naijxj=bi,∀1≤i≤m,xj>0,j=k(1),⋯,k(m^)xj=0,j=k(m^1),⋯,k(n)
当且仅当上面的等式方程组解唯一时 xxx 是 ω\omegaω 的顶点
总结：如果一个点x∈ωx \in \omegax∈ω，使得一些约束求作用（使得一些不等式的等号成立），若对于这些成立的约束构成的线性方程组来说，它的解不只是xxx，那么xxx不是ω\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} ∑j=1naijxj=bi,∀1≤i≤m⇒∑j=1n⎝⎜⎛a1j⋮amj⎠⎟⎞xj=⎝⎜⎛b1⋮bm⎠⎟⎞⇒∑j=1npjxj=bpj=(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
当且仅当 x∈ωx \in \omegax∈ω 的正分量对应的系数向量线性无关
标准形式顶点的等价描述之二
如果 (p1,⋯,pn)\left(p_{1}, \cdots, p_{n}\right)(p1,⋯,pn) 是行满秩矩阵，那么 xxx 是可行集
ω={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\} ω={x=(x1,⋯,xn)t∣j=1∑npjxj=b,xj≥0,∀1≤j≤n}
的顶点充要条件是：存在可逆方阵 (pk(1),⋯,pk(m))\left(p_{k(1)}, \cdots, p_{k(m)}\right)(pk(1),⋯,pk(m)), 可以把 xxx 的分量划分为 xk(j),j=1,⋯,n,x_{k(j)}, j=1, \cdots, n,xk(j),j=1,⋯,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⎝⎜⎛xk(1)⋮xk(m)⎠⎟⎞=(pk(1),⋯,pk(m))−1b≥0,xk(j)=0,∀m1≤j≤n
主要理由 :∑j=1mpk(j)xk(j)=b⃗⇒正分量对应的系 数向量线性无关 \large : \sum_{j=1}^{m} p_{k(j)} x_{k(j)}=\vec{b} \rightarrow \begin{array}{l}\text { 正分量对应的系 } \\ \text { 数向量线性无关 }\end{array}:∑j=1mpk(j)xk(j)=b⇒ 正分量对应的系 数向量线性无关
线性规划标准形式的一些基本概念
基阵、基本解、基本可行解、基变量、非基变量
称可逆矩阵 (pk(1),⋯,pk(m))\left(p_{k(1)}, \cdots, p_{k(m)}\right)(pk(1),⋯,pk(m)) 为基阵
称其分量由下式决定的 xxx 为基本解
(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 ⎝⎜⎛xk(1)⋮xk(m)⎠⎟⎞=(pk(1),⋯,pk(m))−1b,xk(j)=0,∀m1≤j≤n
称可行的基本解为基本可行解 称基阵对应变量为基变量，其余变量为非基变量
标准线性规划的基本可行解就是可行集的顶点
标准线性规划的可行集的顶点个数总是有限的
线性规划标准形式的基本定理
【定理1】 一个标准形式线性规划问题若有可行解，则至少存在一个基本可行解
【定理2】 一个标准形式线性规划问题若有有限的最优目标值，则一定存在一个基本可行解是最优解
【定理3】 如果标准线性规划问题的某个基可行解的相邻的基可行解都不比它好，那么这个基可行解就是最优解
综上所述：对于线性规划，只用求得它的基本可行解，就能在有限的基本可行解中找到最优解。
总结
以上是凯发k8官方网为你收集整理的线性规划——规范型，标准型，基阵、基本解、基本可行解、基变量、非基变量.... 概念梳理的全部内容，希望文章能够帮你解决所遇到的问题。
- 上一篇： 强化学习2——有模型强化学习mdp（搬砖
- 下一篇： 强化学习1——策略，价值函数，模型