文章目錄

• 一、基矩陣 + 非基矩陣 約束條件
• 二、基矩陣 + 非基矩陣 線性規劃
• 三、線性規劃 可行解
• 四、目標函數 推導
• 五、$X_N=O$ 目標函數最大 分析
• 六、總結

在上一篇博客 【運籌學】線性規劃數學模型 ( 單純形法原理 | 單純形法流程 | 查找初始基可行解 ) 中 , 講解到了使用單純形法求解線性規劃問題 , 需要解決以下三個主要問題 :

• 查找初始基可行解
• 判定是否是最優解
• 如何迭代

該博客中已經講解了如何查找初始基可行解 , 查找初始基可行解時 , 優先選擇單位陣作為基矩陣 , 單位陣 $I$ 對應的基解 , 必定是基可行解 ;
( 如果沒有單位陣 $I$ , 那么后續在討論 )

本博客開始講解 , 如何 判定最優解 ( 最優解是如何確定出來的 ) , 和 如何迭代到下一個基可行解 ;

一、基矩陣 + 非基矩陣 約束條件

---

目標函數 , 用于判定 $1$ 個基可行解是否是最優解 ;

在 【運籌學】線性規劃數學模型 ( 求解基矩陣示例 | 矩陣的可逆性 | 線性規劃表示為 基矩陣 基向量 非基矩陣 非基向量 形式 ) 博客中 , 根據推導 , 線性規劃的約束條件 , 可以表示為 :

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

二、基矩陣 + 非基矩陣 線性規劃

---

將上述約束條件代入線性規劃標準形式中

$$\begin{array}{l}maxZ={\sum }_{j=1}^n{c}_j{x}_j\\ \\ ?\begin{array}{ll}{\sum }_{j=1}^n{a}_{ij}{x}_j=b_i& (i=1,2?m)\\ & \\ x_j\ge 0& (i=1,2?n)\end{array}\end{array}$$

得到如下形式 :

$$\begin{array}{l}maxZ=C_B^T{X}_B+C_N^T{X}_N\\ \\ ?\begin{array}{ll}B{X}_B+N{X}_N=b& \\ & \\ x_j\ge 0& (i=1,2?n)\end{array}\end{array}$$

假設得到基解 $?\begin{array}{l}{X}_B=B^{?1}b\\ \\ X_N=O\end{array}$ , 其中 $O$ 表示零矩陣 , 矩陣張紅每個元素的值都是 $0$ ;

判斷該基解 $\left(\begin{array}{c}{X}_B\\ X_N\end{array}\right)$ 是否是最優解 , 需要從目標函數 $maxZ=C_B^T{X}_B+C_N^T{X}_N$ 開始分析 ;

三、線性規劃 可行解

---

從現在開始不再討論基解了 , 回到之前 , 討論可行解 , $X_N$ 可以取值任意合法值 , 而不是取 $O$ 矩陣值 , 查看取值其它值的時候 , 目標函數是否有最大值 , 這里 重新進行解的推導 :

在 【運籌學】線性規劃數學模型 ( 線性規劃求解 | 根據非基變量的解得到基變量解 | 基解 | 基可行解 | 可行基 ) 二、根據非基變量的解得到可行解 博客章節 , 在 $B{X}_B+N{X}_N=b$ 兩端都乘以 $B^{?1}$ , 然后移項得到了 :

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

將上述可行解 , 列舉出來 :

$?\begin{array}{l}{X}_B=B^{?1}b?B^{?1}N{X}_N\\ \\ X_N\end{array}$

四、目標函數 推導

---

此時進行判定線性規劃可行解 $?\begin{array}{l}{X}_B=B^{?1}b?B^{?1}N{X}_N\\ \\ X_N\end{array}$ 中 , $X_N$ 取值 $O$ 矩陣 , 是否是最好的情況 , 即目標函數達到最大值 , 目標函數如下 :

$$maxZ=C_B^T{X}_B+C_N^T{X}_N$$

將 $X_B=B^{?1}b?B^{?1}N{X}_N$ 代入上述目標函數 :

$$\begin{array}{lcl}maxZ& =& C_B^T(B^{?1}b?B^{?1}N{X}_N)+C_N^T{X}_N\\ & & \\ & =& C_B^T{B}^{?1}b?C_B^T{B}^{?1}N{X}_N+C_N^T{X}_N\end{array}$$

$C_B^T{B}^{?1}b$ 計算結果是一個數值常量 , 可以寫成 $b_0$ , 與 $X$ ( $n$ 個決策變量 ) 無關 ;

$$\begin{array}{lcl}& =& b_0+(C_N^T?C_B^T{B}^{?1}N)X_N\\ & & \end{array}$$

之前的基解的策略是 , 將 $X_N$ 取值為 $O$ 零矩陣 , 現在討論 , 要使上述目標函數 $maxZ$ 最大 , 分析 $X_N=O$ 是否是最好的選擇 , 即分析 $X_N=O$ 是否是使 $maxZ$ 目標函數最大的值 ;

假設 $X_N$ 矩陣中的變量值為 $?\begin{array}{c}{x}_{m+1}\\ x_{m+2}\\ ?\\ x_n\end{array}?$ , $(C_N^T?C_B^T{B}^{?1}N)$ 的計算結果是 $\left(\begin{array}{c}{\sigma }_{m+1},{\sigma }_{m+2},?,{\sigma }_n\end{array}\right)$ , $(C_N^T?C_B^T{B}^{?1}N)X_N$ 結果是 ${\sigma }_{m+1}{x}_{m+1}+{\sigma }_{m+2}{x}_{m+2}+?+{\sigma }_n{x}_n$

$$\begin{array}{lcl}& =& b_0+(C_N^T?C_B^T{B}^{?1}N)X_N\\ & & \\ & =& b_0+{\sigma }_{m+1}{x}_{m+1}+{\sigma }_{m+2}{x}_{m+2}+?+{\sigma }_n{x}_n\\ & & \end{array}$$

五、$X_N=O$ 目標函數最大 分析

---

當上述 $X_N$ 矩陣中的變量值 $?\begin{array}{c}{x}_{m+1}\\ x_{m+2}\\ ?\\ x_n\end{array}?$ 都為 $0$ 時 , 假如上述公式取值最大值 , 即

$$b_0+{\sigma }_{m+1}{x}_{m+1}+{\sigma }_{m+2}{x}_{m+2}+?+{\sigma }_n{x}_n$$

取值最大值 ;

在線性規劃約束條件中 , 所有的變量都是大于等于 $0$ 的 , 每個 $x_j$ 約束變量取值都可以大于等于 $0$ , 目前是查看當所有的 $x_j$ 變量都取值 $0$ 時 , 目標函數達到最大值的情況 ;

當 $X_N$ 取值等于 $O$ 零矩陣時 , 目標函數值等于 $b_0$ , 當 $X_N$ 中有元素取值大于 $0$ 時 , 就會在 $b_0$ 基礎上加上一個值 , 如果這個值是 小于等于 $0$ 的 , 那么對應的 $x_j$ 取值越大 , 目標函數值越小 ;

因此這里得到 , 在 $X_N=?\begin{array}{c}{x}_{m+1}\\ x_{m+2}\\ ?\\ x_n\end{array}?$ 非基變量前的系數是小于等于 $0$ 時 , 才能滿足當 $X_N$ 中的元素取值等于 $0$ 時 , 目標函數是最大值 ;

因此
$$b_0+{\sigma }_{m+1}{x}_{m+1}+{\sigma }_{m+2}{x}_{m+2}+?+{\sigma }_n{x}_n$$

中的 ${\sigma }_{m+1},{\sigma }_{m+2},?,{\sigma }_n$ 系數值小于等于 $0$ , 其中每個系數對應的變量 $x_j$ 必定是大于等于 $0$ 的值 , 那么系數 ${\sigma }_{m+1}$ 小于等于 $0$ 時 , 每個變量取值 $x_j=0$ , 目標函數達到最小值 ;

六、總結

---

將線性規劃約束條件表示為 $B{X}_B+N{X}_N=b$

進行變換后得到 $X_B=B^{?1}b?B^{?1}N{X}_N$

這里可以寫出如下可行解 $?\begin{array}{l}{X}_B=B^{?1}b?B^{?1}N{X}_N\\ \\ X_N\end{array}$

將上述可行解代入目標函數 $maxZ=C_B^T{X}_B+C_N^T{X}_N$ 中

得到 $maxZ=b_0+(C_N^T?C_B^T{B}^{?1}N)X_N$

在該情況下 , 如果 $(C_N^T?C_B^T{B}^{?1}N)$ 系數小于等于 $0$ , 當 $X_N$ 取值為 $0$ 時 , 目標函數得到最大值 ;

總結

以上是生活随笔為你收集整理的【运筹学】线性规划数学模型 ( 单纯形法 | 最优解判定原则 | 可行解表示 | 目标函数推导 | 目标函数最大值分析 )的全部內容，希望文章能夠幫你解決所遇到的問題。

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