文章目錄

• • • • I . 單純形法 引入
      • II . 單純形法 基本原理
      • III . 線性規劃 標準形式
      • IV . 線性規劃 標準形式 普通形式公式
      • V . 線性規劃 標準形式 展開完整形式公式
      • VI . 線性規劃 標準形式 矩陣形式公式 ( 矩陣 C | 矩陣 X | 矩陣 b | 矩陣 A )
      • VII . 線性規劃 標準形式 向量形式公式 ( 向量 Pj )

I . 單純形法 引入

---

1. 方程組的解個數 :

• ① 唯一解 : 如果方程組的方程個數 等于 變量的個數 , 變量的解是唯一的 ;
• ② 多個解 : 如果方程組的方程個數 大于 變量的個數 , 變量的解可能會出現多個 ;

2. 單純形法引入 : 在線性規劃中 , 約束方程個數 , 一般情況下會小于變量個數 , 因此會有多個解 , 單純形法就是針對這種情況求解的方法 , 可以得到符合要求的線性規劃的最優解 ;

II . 單純形法 基本原理

---

單純形法原理 :

• ① 初始單純形 : 先從線性規劃 約束方程 中找出單純形 , 每個單純形可以解出一組變量的解 ;
• ② 判定趨勢 ( 是否最優 ) : 然后判斷這個解 影響的 目標函數的趨勢 , 使目標函數增大 還是 減小 ;
• ③ 找到更優可行解 : 根據該趨勢選擇下一個單純形 , 不斷迭代 , 直到找到一個單純形 , 使目標函數達到最大值或最小值 ;

單純形法 執行方案 :

• ① 初始可行解 : 先找到 一個 初始可行解 , 判定其是否是最優解 , 如果是到此為止結束 ;
• ② 判定 : 是否最優解 , 如果是 , 到此結束 ; 如果不是 , 繼續執行 ③ ;
• ③ 轉化更優的可行解 : 那么按照一定法則 , 轉換成另一組優化后的 可行解 , 跳轉到 ② 繼續判定 ;

III . 線性規劃 標準形式

---

線性規劃標準形式 : 使用單純形法 求解 線性規劃問題 , 這里要求線性規劃數學模型必須是標準形式 , 有如下要求 :

• ① 目標函數 : 變量組成的目標函數 , 求解極大值 ;
• ② 約束方程 : 所有的約束方程都必須是等式 , 并且右側的常數都必須 大于等于 0 ;
• ③ 變量約束 : 所有的變量取值都必須大于等于 0 ;

線性規劃標準形式轉換方式 : 【運籌學】線性規劃數學模型標準形式 ( 標準形式 | 目標函數轉化 | 決策變量轉化 | 約束方程轉化 | 固定轉化順序 | 標準形式轉化實例 ) , 參考上一篇博客內容 ;

IV . 線性規劃 標準形式 普通形式公式

---

線性規劃標準形式公式 : $n$ 個變量 , $m$ 個約束方程 , $n>m$ 變量數大于方程數 , 解有多個 ;

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

V . 線性規劃 標準形式 展開完整形式公式

---

線性規劃標準形式 展開式 : $n$ 個變量 , $m$ 個約束方程 , $n>m$ 變量數大于方程數 , 解有多個 ;

$$\begin{array}{l}maxZ=c_1{x}_1+c_2{x}_2+?+c_n{x}_n\\ \\ s.t?\begin{array}{l}{a}_{11}{x}_1+a_{12}{x}_2+?+a_{1n}{x}_n=b_1\\ \\ a_{21}{x}_1+a_{22}{x}_2+?+a_{2n}{x}_n=b_2\\ \\ ???\\ \\ a_{m1}{x}_1+a_{m2}{x}_2+?+a_{mn}{x}_n=b_m\\ \\ x_1,x_2,?,x_n\ge 0\\ \\ b_1,b_2,?,b_n\ge 0\end{array}\end{array}$$

VI . 線性規劃 標準形式 矩陣形式公式 ( 矩陣 C | 矩陣 X | 矩陣 b | 矩陣 A )

---

1. 線性規劃標準形式 矩陣形式 : $n$ 個變量 , $m$ 個約束方程 , $n>m$ 變量數大于方程數 , 解有多個 ;

$$\begin{array}{l}maxZ=CX\\ \\ AX=b,X\ge 0\end{array}$$

2. 矩陣 $C$ : 該矩陣是行向量 , 代表了目標函數中的系數 ;
$$C=\left[\begin{array}{cccccc}& c_1,& c_2,& ?,& c_m& \end{array}\right]$$*

3. 矩陣 $X$ : 該矩陣是列向量 , 表示目標函數中的變量 ;

$$\begin{gathered} X=?\begin{array}{c} \\ \\ x_1\\ \\ x_2\\ \\ ?\\ \\ x_m\\ \end{array}? \end{gathered}$$

4. 矩陣 $b$ : 該矩陣是列向量 , 表示約束方程的右側常數 ;

$$\begin{gathered} b=?\begin{array}{c} \\ \\ b_1\\ \\ b_2\\ \\ ?\\ \\ b_m\\ \end{array}? \end{gathered}$$

5. 矩陣 $A$ : 該矩陣是 $m\times n$ 矩陣 , 有 $m$ 行 $n$ 列 , $m$ 表示約束方程個數 , $n$ 表示變量個數 ; ( $n>m$ )

$m$ 同時也是 矩陣 $A$ 的秩 ; 該矩陣是 $m$ 個 約束方程的每個變量前的 系數 矩陣 ;

$$\begin{gathered} A=?\begin{array}{cccccc} \\ & & & & & \\ & a_{11}& a_{12}& ?& a_{1n}& \\ & & & & & \\ & a_{21}& a_{22}& ?& a_{2n}& \\ & & & & & \\ & ?& ?& ?& ?& \\ & & & & & \\ & a_{m1}& a_{m2}& ?& a_{mn}& \\ & & & & & \end{array}? \end{gathered}$$

VII . 線性規劃 標準形式 向量形式公式 ( 向量 Pj )

---

1. 向量概念 : 向量是特殊的矩陣 , $m$ 行 $1$ 列的矩陣 , 就是向量 ;

2. 線性規劃 向量形式 : 其中 矩陣 $C$ , 矩陣 $X$ , 矩陣 $b$ 與上面的矩陣形式內容一致 , 本公式之比上個公式多了一個 向量 $P_j$ ;

$$\begin{array}{l}maxZ=CX\\ \\ s.t?\begin{array}{l}{\sum }_{j=1}^n{P}_j{x}_j=b\\ \\ X\ge 0\end{array}\end{array}$$

3. 向量 $P_j$ 表示 : 該向量是 $m$ 行 $1$ 列的矩陣 , 表示 約束方程 $A$ 中的第 $j$ 行的列向量 , 其中 $j=1,2,?,n$ ;

$$\begin{gathered} P_j=?\begin{array}{c} \\ \\ a_{1j}\\ \\ a_{2j}\\ \\ ?\\ \\ a_{mj}\\ \end{array}? \end{gathered}$$

4. 矩陣 $A$ 與 向量$P_j$ 關系 :

$$\begin{gathered} A=?\begin{array}{cccccc} \\ & & & & & \\ & a_{11}& a_{12}& ?& a_{1n}& \\ & & & & & \\ & a_{21}& a_{22}& ?& a_{2n}& \\ & & & & & \\ & ?& ?& ?& ?& \\ & & & & & \\ & a_{m1}& a_{m2}& ?& a_{mn}& \\ & & & & & \end{array}?=\left[\begin{array}{cccccc}& P_1& P_2& ?& P_n& \end{array}\right] \end{gathered}$$

5. 系數替換方案 : 在線性規劃 普通公式中 , 約束方程系數 $a_{ij}$ 可以使用 $P_j$ 進行替換 ;

$$\begin{gathered} \sum _{j=1}^n{a}_{ij}{x}_j=b_i \\ i=1,2,?,m \\ j=1,2,?,n \end{gathered}$$

向量 $P_j$ 代替其中的 $a_{ij}$ , 替換完畢后為 :
$$\begin{gathered} \sum _{j=1}^n{P}_j{x}_j=b_i \\ j=1,2,?,n \end{gathered}$$

總結

以上是生活随笔為你收集整理的【运筹学】线性规划 单纯形法 ( 原理 | 约定符号 | 目标系数矩阵 C | 目标函数变量矩阵 X | 约束方程常数矩阵 b | 系数矩阵 A | 向量 | 向量符号 | 向量 Pj )的全部內容，希望文章能夠幫你解決所遇到的問題。

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