當前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

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

發布時間：2024/10/14 编程问答 274 豆豆

生活随笔收集整理的這篇文章主要介紹了线性规划——规范型，标准型，基阵、基本解、基本可行解、基变量、非基变量.... 概念梳理小編覺得挺不錯的,現在分享給大家,幫大家做個參考.

文章目錄

前言
最優化—線性規劃
- 模型問題
- - 線性規劃模型的一般形式（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}$

線性規劃規范形式

線性規劃標準型

$max?c1x1+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 { 等式約束 }$

$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 {決策變量具有非負約束}$

$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 \\ 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=\left(\begin{array}{c} b_{1} \\ \vdots \\ b_{m} \end{array}\right) \end{array}$

以后我們所考慮的線性規劃標準型為:
$max?CTXs.t.?AX=b?X≥0\begin{array}{c} \max C^{T} X \\ \text { s.t. } A X=\vec \\ X \geq 0 \end{array}$
其中 $\in R^{n}, X \in R^{n}, A \in R^{m \times n}, \vec \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 \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 \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, 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 \geq 0, \quad x_{k(j)}=0, \forall m+1 \leq j \leq n$
主要理由 $:∑j=1mPk(j)xk(j)=b??正分量對應的系?數向量線性無關?\large : \sum_{j=1}^{m} P_{k(j)} x_{k(j)}=\vec \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, x_{k(j)}=0, \forall m+1 \leq j \leq n$
稱可行的基本解為基本可行解 稱基陣對應變量為基變量，其余變量為非基變量
標準線性規劃的基本可行解就是可行集的頂點
標準線性規劃的可行集的頂點個數總是有限的

線性規劃標準形式的基本定理

【定理1】一個標準形式線性規劃問題若有可行解，則至少存在一個基本可行解
【定理2】一個標準形式線性規劃問題若有有限的最優目標值，則一定存在一個基本可行解是最優解
【定理3】如果標準線性規劃問題的某個基可行解的相鄰的基可行解都不比它好，那么這個基可行解就是最優解

綜上所述：對于線性規劃，只用求得它的基本可行解，就能在有限的基本可行解中找到最優解。

總結

以上是生活随笔為你收集整理的线性规划——规范型，标准型，基阵、基本解、基本可行解、基变量、非基变量.... 概念梳理的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。

上一篇：强化学习2——有模型强化学习MDP（搬砖
下一篇：强化学习1——策略，价值函数，模型