文章目錄

• 一、單純形法原理
• 二、單純形法流程
• 三、初始的基可行解查找

一、單純形法原理

---

單純形法的理論基礎(chǔ) :

定理 $1$ ( 可行域是凸集 ) : 如果線性規(guī)劃的問題 存在可行解 , 其 可行域 必定是 凸集 ;

定理 $2$ ( 基可行解是凸集頂點(diǎn) ) : 線性規(guī)劃的 基可行解 $X_B$ 對應(yīng)了上述 可行域 ( 凸集 ) 的頂點(diǎn)位置 ;

定理 $3$ ( 某個(gè)基可行解是最優(yōu)解 ) : 如果線性規(guī)劃問題 存在最優(yōu)解 , 那么 一定存在一個(gè)基可行解是最優(yōu)解 ;

參考上一篇博客 【運(yùn)籌學(xué)】線性規(guī)劃 圖解法 ( 唯一最優(yōu)解 | 無窮最優(yōu)解 | 無界解 | 無可行解 ) 進(jìn)行分析 :

給定線性規(guī)劃 :

$$\begin{array}{l}maxZ=2x_1+x_2\\ \\ s.t=?\begin{array}{l}{x}_1+1.9x_2\ge 3.8\\ \\ x_1?1.9x_2\le 3.8\\ \\ x_1+1.9x_2\le 10.2\\ \\ x_1?1.9x_2\ge ?3.8\\ \\ x_1,x_2\ge 0\end{array}\end{array}$$

使用圖解法進(jìn)行分析 , 得到如下結(jié)果 ;

使用迭代的思想進(jìn)行求解 :

• 無限個(gè)解中迭代 : 上圖中的 可行域 $D$ 中的點(diǎn)是無限的 , 可以在所有的無限個(gè)可行域 $D$ 解中進(jìn)行迭代 , 逐個(gè)迭代很難 ;

• 有限個(gè)解中迭代 : 因此選取 可行域 ( 凸集 ) 的頂點(diǎn) , 也就是 基可行解 進(jìn)行迭代 , 該線性規(guī)劃問題的基可行解是有限的 , 只有 $4$ 個(gè) , 即該凸集有 $4$ 個(gè)頂點(diǎn) ;

上圖的凸集中的 $4$ 個(gè)頂點(diǎn) , 必然有一個(gè)是最優(yōu)解 , 因此迭代的時(shí)候 , 不用從 $D$ 可行域中的無限個(gè)點(diǎn)中進(jìn)行迭代 , 只需要在有限個(gè)基可行解中進(jìn)行迭代 , 即可找到最優(yōu)解 ;

單純形法的原理的基礎(chǔ)就是源自上述理論 , 在線性規(guī)劃的有限個(gè)基可行解中 , 必定存在一個(gè)解釋最優(yōu)解 , 逐個(gè)迭代 , 將這個(gè)最優(yōu)解找出即可 ;

從無限個(gè)可行解中進(jìn)行迭代 , 到有限個(gè)基可行解中進(jìn)行迭代 , 簡單了很多 ;

但是對于 $m\times n$ 階的線性規(guī)劃系數(shù)矩陣 , 其基可行解的個(gè)數(shù)可能有 $C_n^m$ 個(gè) , 如果 $n$ 和 $m$ 很大的話 , 基可行解的數(shù)目還是很大 , 這是一個(gè)指數(shù)級的數(shù) , 因此使用多項(xiàng)式算法 , 完成上述操作 , 計(jì)算量還是很大的 ;

這里使用單純形法 , 進(jìn)行迭代 , 要比使用多項(xiàng)式法計(jì)算量更少 ;

二、單純形法流程

---

單純形法的基本流程 :

① 初始基可行解 : 首先找到初始的基可行解 ;

② 判定是否最優(yōu)解 : 需要一個(gè)準(zhǔn)則 , 判定該初始基可行解 , 是否是最優(yōu)解 ; 這里是單純形法最核心問題 ;

③ 是最優(yōu)解 : 如果該基可行解是最優(yōu)解 , 那么結(jié)束迭代 ;

④ 不是最優(yōu)解 : 如果該基可行解不是最優(yōu)解 , 那么迭代到下一個(gè)基可行解 , 繼續(xù)判定是否是最優(yōu)解 ; 如何迭代也需要一個(gè)準(zhǔn)則 ;

這里涉及到了兩個(gè)準(zhǔn)則 :

• 判斷最優(yōu)解 : 判斷一個(gè) 基可行解 是否是最優(yōu)解 ;
• 迭代原則 : 如何從一個(gè) 基可行解 迭代到下一個(gè)基可行解 ;

單純形法涉及到的問題 :

① 初始解 : 如何找到初始基可行解 ;

② 最優(yōu)解 : 如何找到一個(gè)準(zhǔn)則 , 用于判定基可行解是否是最優(yōu)解 ;

③ 迭代解 : 如果一個(gè)基可行解不滿足準(zhǔn)則 , 如何去選擇下一個(gè)基可行解進(jìn)行迭代 ;

解決上述 $3$ 個(gè)問題 , 基可行解的算法 , 也就可以得出 ;

三、初始的基可行解查找

---

如何去找初始的基可行解 , 首先要找到一個(gè) 基 , 并且該基是 可行基 ;

對于 $m\times n$ 階的系數(shù)矩陣 :

基 : 從 $C(n,m)$ 個(gè)子矩陣中找到基矩陣 , 基矩陣的條件是 該 $m$ 階方陣是可逆的 ;

參考 【運(yùn)籌學(xué)】線性規(guī)劃數(shù)學(xué)模型 ( 求解基矩陣示例 | 矩陣的可逆性 | 線性規(guī)劃表示為 基矩陣 基向量 非基矩陣 非基向量 形式 ) 一、求解基矩陣示例 博客章節(jié) , $?\begin{array}{ccccccc}& 5& 1& ?1& 1& 0& \\ & & & & & & \\ & ?10& 6& 2& 0& 1& \end{array}?$ 系數(shù)矩陣 , 有 $C(5,2)=10$ 個(gè)子矩陣 , 但是只有 $9$ 個(gè)是可逆的 ;

基矩陣如下 :

$B_1=?\begin{array}{cccc}& 5& 1& \\ & & & \\ & ?10& 6& \end{array}?$ , $B_2=?\begin{array}{cccc}& 1& ?1& \\ & & & \\ & 6& 2& \end{array}?$ , $B_3=?\begin{array}{cccc}& 5& 0& \\ & & & \\ & ?10& 1& \end{array}?$ ,

$B_4=?\begin{array}{cccc}& 1& 1& \\ & & & \\ & 6& 0& \end{array}?$ , $B_5=?\begin{array}{cccc}& 5& 1& \\ & & & \\ & ?10& 0& \end{array}?$ , $B_6=?\begin{array}{cccc}& ?1& 0& \\ & & & \\ & 2& 1& \end{array}?$ ,

$B_7=?\begin{array}{cccc}& ?1& 1& \\ & & & \\ & 2& 0& \end{array}?$ , $B_8=?\begin{array}{cccc}& 1& 10& \\ & & & \\ & 6& 1& \end{array}?$ , $B_9=?\begin{array}{cccc}& 1& 0& \\ & & & \\ & 0& 1& \end{array}?$ ;

選擇一個(gè)基矩陣 , 每個(gè)基矩陣都唯一對應(yīng)一個(gè)基解 , 如果該解大于等于 $0$ , 說明該解是基可行解 , 那么該選擇的基矩陣 , 就是可行基 ;

參考 【運(yùn)籌學(xué)】線性規(guī)劃數(shù)學(xué)模型 ( 線性規(guī)劃求解 | 根據(jù)非基變量的解得到基變量解 | 基解 | 基可行解 | 可行基 ) 三、基解 博客章節(jié) , 基解的公式是

$$X_B=B^{?1}b$$

使用 $B_1=?\begin{array}{cccc}& 5& 1& \\ & & & \\ & ?10& 6& \end{array}?$ 矩陣作為基矩陣 , 求出其對應(yīng)的基可行解 , 代入上述公式 :

$$\begin{array}{l}{X}_B=B^{?1}b\\ \\ X_B={?\begin{array}{cccc}& 5& 1& \\ & & & \\ & ?10& 6& \end{array}?}^{?1}\times ?\begin{array}{ccc}& 3& \\ & & \\ & 2& \end{array}?\end{array}$$

如果上述 $X_B$ 的兩個(gè)分量 $\left(\begin{array}{c}{x}_1\\ x_2\end{array}\right)$ 都大于 0 , 說明該解釋基可行解 , 該基矩陣 $B_1$ 是可行基 ;

使用算法進(jìn)行迭代 , 一個(gè)個(gè)判斷太浪費(fèi)時(shí)間 , 選擇 $B_1$ 作為基矩陣 , 計(jì)算很復(fù)雜 , 這里選擇 $B_9=?\begin{array}{cccc}& 1& 0& \\ & & & \\ & 0& 1& \end{array}?$ 作為基矩陣 , 這是個(gè)單位陣 , 其逆矩陣還是其單位陣本身 ;

$B_9$ 基矩陣對應(yīng)的基變量是 $X_B=\left(\begin{array}{c}{x}_4\\ x_5\end{array}\right)$ , 將基矩陣代入 $X_B=B^{?1}b$ 公式 ;

$$\begin{array}{l}{X}_B=B^{?1}b\\ \\ X_B={?\begin{array}{cccc}& 1& 0& \\ & & & \\ & 0& 1& \end{array}?}^{?1}\times ?\begin{array}{ccc}& 3& \\ & & \\ & 2& \end{array}?\\ \\ X_B=?\begin{array}{cccc}& 1& 0& \\ & & & \\ & 0& 1& \end{array}?\times ?\begin{array}{ccc}& 3& \\ & & \\ & 2& \end{array}?\\ \\ X_B=?\begin{array}{ccc}& 3& \\ & & \\ & 2& \end{array}?\end{array}$$

由上述計(jì)算過程得到 $X_B=\left(\begin{array}{c}{x}_4\\ x_5\end{array}\right)=\left(\begin{array}{c}3\\ 2\end{array}\right)$ 結(jié)果 , $x_4$ 和 $x_5$ 都大于 $0$ , $?\begin{array}{c}0\\ 0\\ 0\\ 3\\ 2\end{array}?$是基可行解 , 該 $X_B$ 是可行基 ;

使用 $B_1$ 作為基矩陣 , 不好計(jì)算 , 還需要求 $B_1$ 矩陣的逆矩陣 , $B_9$ 是單位陣 , 所有的 單位陣 $I$ 都是可行基 , 初始基可行解選取時(shí) , 優(yōu)先選擇單位陣 ;

總結(jié)

以上是生活随笔為你收集整理的【运筹学】线性规划数学模型 ( 单纯形法原理 | 单纯形法流程 | 查找初始基可行解 )的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。