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

编程问答

【运筹学】线性规划人工变量法 ( 单纯形法总结 | 人工变量法引入 | 人工变量法原理分析 | 人工变量法案例 )

發布時間：2025/6/17 编程问答 24 豆豆

生活随笔收集整理的這篇文章主要介紹了【运筹学】线性规划人工变量法 ( 单纯形法总结 | 人工变量法引入 | 人工变量法原理分析 | 人工变量法案例 ) 小編覺得挺不錯的,現在分享給大家,幫大家做個參考.

文章目錄

一、單純形法總結
二、人工變量法引入
三、人工變量法案例
四、線性規劃標準型
五、人工變量法
六、人工變量法解分析

一、單純形法總結

求解線性規劃 , 使用的是單純形法 ;

迭代轉化 : 其將在無窮多個可行解中迭代 , 轉化為了在有限個基可行解中進行迭代 ;

單純形法理論基礎 : 將迭代范圍由大集合轉為小集合 , 不會漏掉最優解 , 根據線性規劃定理 , 只要有最優解 , 該最優解一定是基可行解 ;

單純形法求解流程 :

① 找到單位陣
② 最優準則 : 計算檢驗數
③ 迭代準則 : 先根據檢驗數找到入基變量 , 再根據常量除以入基變量大于 $0$ 系數 , 選擇小的值對應的基變量作為出基變量 ;
④ 中心元 : 找到入基變量與出基變量交叉點元素 , 這是中心元 , 中心元轉為 $1$ , 同一列另一個系數轉為 $0$ ; 然后繼續根據最優準則計算檢驗數 , 轉到步驟 ② ;

二、人工變量法引入

上述單純形的解法是從單位陣出發的 , 所有的前提是有單位陣 , 線性規劃中可能不存在單位陣 , 如果線性規劃轉化為單位陣時 , 沒有單位陣 , 就需要使用 人工變量法 , 構造一個單位陣 ;

下面通過一個案例來介紹人工變量法的使用 ;

三、人工變量法案例

求解線性規劃 : 使用人工變量法求解線性規劃 ;

$maxZ=3x1+2x2?x3s.t{?4x1+3x2+x3≥4x1?x2+2x3≤10?2x1+2x2?x3=?1xj≥0(j=1,2,3)\begin{array}{lcl} max Z = 3x_1 + 2x_2 - x_3 \\ \\ s.t\begin{cases} -4 x_1 + 3x_2 + x_3 \geq 4 \\\\ x_1 - x_2 + 2x_3 \leq 10 \\\\ -2x_1 + 2x_2 - x_3 = -1 \\\\ x_j \geq 0 & (j = 1 , 2 , 3 ) \end{cases}\end{array}$

四、線性規劃標準型

1 . 處理約束變量 : 所有的約束變量都大于等于 $0$ , 這里無需處理 ;

2 . 將不等式轉為等式 :

① 方程 $1$ 轉為等式 : 方程 $1$ 是大于等于不等式 , 需要在方程左側減去剩余變量 $x_4$ ;

$4 x_1 + 3x_2 + x_3 - x_4 = 4$

② 方程 $2$ 轉為等式 : 方程 $2$ 是小于等于不等式 , 需要在方程左側加上松弛變量 $x_5$ ;

$x_1 - x_2 + 2x_3 + x_5 = 10$

3 . 方程 $3$ 轉為符合要求的等式 : 方程 $3$ 是等式 , 但是其右側的常數小于 $0$ , 這里需要在等式兩邊都乘以 $? 1$ , 使右側的常數大于等于 $0$ ;

$2x_1 - 2x_2 + x_3 = 1$

4 . 處理目標函數取最大值 : 目標函數就是取最大值 , 無需處理 ;

5 . 最終的標準形結果是 :

$maxZ=3x1+2x2?x3s.t{?4x1+3x2+x3?x4=4x1?x2+2x3+x5=102x1?2x2+x3=1xj≥0(j=1,2,3,4,5)\begin{array}{lcl} max Z = 3x_1 + 2x_2 - x_3 \\ \\ s.t\begin{cases} -4 x_1 + 3x_2 + x_3 - x_4 = 4 \\\\ x_1 - x_2 + 2x_3 + x_5 = 10 \\\\ 2x_1 - 2x_2 + x_3 = 1 \\\\ x_j \geq 0 \quad (j = 1 , 2 , 3, 4, 5 ) \end{cases}\end{array}$

五、人工變量法

將上述轉化完畢的標準型的系數矩陣補全 :

$maxZ=3x1+2x2?x3+0x4+0x5s.t{?4x1+3x2+x3?x4+0x5=4x1?x2+2x3+0x4+x5=102x1?2x2+x3+0x4+0x5=1xj≥0(j=1,2,3,4,5)\begin{array}{lcl} max Z = 3x_1 + 2x_2 - x_3 + 0x_4 + 0x_5 \\ \\ s.t\begin{cases} -4 x_1 + 3x_2 + x_3 - x_4 + 0x_5 = 4 \\\\ x_1 - x_2 + 2x_3 + 0x_4 + x_5 = 10 \\\\ 2x_1 - 2x_2 + x_3 + 0x_4 + 0x_5 = 1 \\\\ x_j \geq 0 \quad (j = 1 , 2 , 3, 4, 5 ) \end{cases}\end{array}$

上述約束方程中沒有單位陣 , 無法找到初始基可行解 , 創建初始的單純形表 ;

上述線性規劃中 , 需要找到 $\times 3$ 的單位陣 $(100010001)\begin{pmatrix} \quad 1 \quad 0 \quad 0 \quad \\ \quad 0 \quad 1 \quad 0 \quad \\ \quad 0 \quad 0 \quad 1 \quad \\ \end{pmatrix}$ , 目前只有 $x_5$ 的系數列向量是 $(010)\begin{pmatrix} \quad 0 \quad \\ \quad 1 \quad \\ \quad 0 \quad \\ \end{pmatrix}$ , 這里需要進行如下操作 ;

人工變量法 : 目的是人為制造單位陣 , 添加 $2$ 個或 $3$ 個人工變量 ;

方程 $1$ 構造變量 $x_6$ : 該變量只出現在第 $1$ 個方程中 ;

$4 x_1 + 3x_2 + x_3 - x_4 + 0x_5 + x_6 = 4$

方程 $2$ 構造變量 $x 7$ : 該變量只出現在第 $3$ 個方程中 ;

$2x_1 - 2x_2 + x_3 + 0x_4 + 0x_5 + x_7 = 1$

添加了人工變量后 , 變量就變成了 $7$ 個 $(x1x2x3x4x5x6x7)\begin{pmatrix} \quad x_1 \quad \\ \quad x_2 \quad \\ \quad x_3 \quad \\ \quad x_4 \quad \\ \quad x_5 \quad \\ \quad x_6 \quad \\ \quad x_7 \quad \\ \end{pmatrix}$ , 原來的變量只有 $5$ 個 $(x1x2x3x4x5)\begin{pmatrix} \quad x_1 \quad \\ \quad x_2 \quad \\ \quad x_3 \quad \\ \quad x_4 \quad \\ \quad x_5 \quad \\ \end{pmatrix}$ ; 如果解出該線性規劃的 $7$ 個解 , 去掉后面的 $x_6 , x_7$ 之后 , 該最優解不一定滿足 $5$ 個變量的線性規劃 ;

如果解出的 $7$ 個解中 , $x_6 , x_7$ 都等于 $0$ , 此時該最優解的前 $5$ 個變量 , 滿足最初的線性規劃解 ;

引入大 $M$ : 在目標函數中 , 為 $x_6 , x_7$ 加上系數 $? M$ , $M$ 是一個抽象數值 , 沒有具體的值 , 其大于給定的任何一個值 ;

$max Z = 3x_1 + 2x_2 - x_3 + 0x_4 + 0x_5 - M x_6 - Mx_7$

引入大 $M$ 后最優解 $x_6 , x_7$ 必須為 $0$ : 如果上述 $x_6 , x_7$ 只要大于 $0$ , 即使很小 , 但是乘以一個很大的負數值 $? M$ , 也會極大降低目標函數大小 , 因此只有兩個變量取值為 $0$ 時 , 才能使該解稱為最優解 ;

添加 $2$ 個人工變量后 , 得到人工變量單純形法線性規劃模型 :

$maxZ=3x1+2x2?x3+0x4+0x5?Mx6?Mx7s.t{?4x1+3x2+x3?x4+0x5+x6+0x7=4x1?x2+2x3+0x4+x5+0x6+0x7=102x1?2x2+x3+0x4+0x5+0x6+x7=1xj≥0(j=1,2,3,4,5,6,7)\begin{array}{lcl} max Z = 3x_1 + 2x_2 - x_3 + 0x_4 + 0x_5 - M x_6 - Mx_7 \\\\ s.t\begin{cases} -4 x_1 + 3x_2 + x_3 - x_4 + 0x_5 + x_6 + 0x_7 = 4 \\\\ x_1 - x_2 + 2x_3 + 0x_4 + x_5 + 0x_6 + 0x_7 = 10 \\\\ 2x_1 - 2x_2 + x_3 + 0x_4 + 0x_5 + 0x_6 + x_7 = 1 \\\\ x_j \geq 0 \quad (j = 1 , 2 , 3, 4, 5 , 6 , 7 ) \end{cases}\end{array}$

其中的 $M$ 是一個很大的數值 , 沒有具體的值 , 可以理解為正無窮 $+∞+\infty$ , 具體使用單純形法進行計算時 , 將其理解為大于給出的任意一個確定的數值 ;

六、人工變量法解分析

原來的線性規劃稱為 $L P$ , 添加了人工變量后的新線性規劃為 $L P A$ ;

目標函數值有限 : 只要 $L P$ 線性規劃 , 可行域不為空集 $?\varnothing$ , 那么 $L P A$ 線性規劃一定能找到一個解 $x$ , 使得 $f (x)$ 是一個有限的數 , 該有限的數是與負無窮 $?∞-\infty$ 進行對比區分的 ;
只要 $L P$ 線性規劃有可行解 , 那么 $L P A$ 線性規劃中的目標函數一定不是負無窮 $?∞-\infty$ ;
兩個線性規劃解的關系 : $(x0)\begin{pmatrix} \quad x_0 \quad \\ \end{pmatrix}$ 是線性規劃 $L P$ 的可行解 , $(x000)\begin{pmatrix} \quad x_0 \quad \\ \quad 0 \quad \\ \quad 0 \quad \\ \end{pmatrix}$ 一定是 $L P A$ 線性規劃的可行解 , 將該解代入目標函數 , 目標函數一定是一個有限的數 , 不是負無窮 $?∞-\infty$ ;
解 $L P A$ 線性規劃 : 構造的 $L P A$ 輔助線性規劃問題有單位陣 , 選取該單位陣為可行解 , 得到基可行解 , 然后開始進行迭代 ;

只要線性規劃有初始基可行解 , 那么只可能有以下情況

① 有最優解
② 沒有最優解

最優解情況 : 在有最優解的前提下 ;

① 如果人工變量等于 $0$ , 將人工變量去掉 , 剩余的解就是原來線性規劃 $L P$ 的最優解 ;
② 如果有一個或多個人工變量大于 $0$ , 那么說明原線性規劃 $L P$ 沒有可行解 ;

沒有最優解的情況 :如果 $L P A$ 線性規劃沒有最優解 , 那么 $L P$ 線性規劃也沒有最優解 ;

總結

以上是生活随笔為你收集整理的【运筹学】线性规划人工变量法 ( 单纯形法总结 | 人工变量法引入 | 人工变量法原理分析 | 人工变量法案例 )的全部內容，希望文章能夠幫你解決所遇到的問題。

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

上一篇：【运筹学】线性规划单纯形法案例二 (
下一篇：【运筹学】线性规划人工变量法 ( 人工