計算機軟體求解線性規劃模型--Python

線性規劃簡介

線性規劃（Linear programming,簡稱LP），是運籌學中研究較早、發展較快、應用廣泛、方法較成熟的一個重要分支，它是輔助人們進行科學管理的一種數學方法，研究線性約束條件下線性目標函式的極值問題的數學理論和方法，英文縮寫LP，

線性規劃是運籌學的一個重要分支，廣泛應用于軍事作戰、經濟分析、經營管理和工程技術等方面，為合理地利用有限的人力、物力、財力等資源作出的最優決策，提供科學的依據，

線性規劃模型的三要素

線性規劃模型主要包括三個部分：決策變數、目標函式、約束條件

決策變數
決策變數是指問題中可以改變的量，例如生產多少貨物，選擇哪條路徑等；線性規劃的目標就是找到最優的決策變數，
在線性規劃中決策變數包括實數變數，整數變數，0-1變數等，

目標函式
目標函式就是把問題中的決策目標量化，一般分為最大化目標函式和最小化目標函式，在線性規劃中，目標函式為一個包含決策變數的線性函式，例如
max x 1 + x 2 \text{max}\quad x_1 +x_2 maxx1?+x2?
約束條件

約束條件是指問題中各種時間，空間，人力，物力等限制，在線性規劃中約束條件一般表示為一組包含決策變數的不等式，例如
x 1 + 2 x 2 ≤ 10 4 x 1 + 3 x 2 ≤ 24 \begin{array}{r} x_{1}+2 x_{2} \leq 10 \\ 4 x_{1}+3 x_{2} \leq 24 \end{array} x1?+2x2?≤104x1?+3x2?≤24?
此外，決策變數的取值范圍稱為符號約束，例如：
x 1 ≥ 0 , x 2 ≥ 0 x_1 \geq 0,x_2\geq 0 x1?≥0,x2?≥0

線性規劃模型的數學表示

線性規劃模型可以寫成如下形式：
max ? z = x 1 + x 2 s.t. x 1 + 2 x 2 ≤ 10 4 x 1 + 3 x 2 ≤ 24 x 1 , x 2 ≥ 0 \begin{aligned} &\max \quad z=x_{1}+x_{2}\\ &\text { s.t. } \quad x_{1}+2 x_{2} \leq 10\\ &\begin{array}{r} \quad \quad 4 x_{1}+3 x_{2} \leq 24 \\ \quad x_{1}, x_{2} \geq 0 \end{array} \end{aligned} ?maxz=x1?+x2? s.t. x1?+2x2?≤104x1?+3x2?≤24x1?,x2?≥0??
其中， s . t . s.t. s.t. 表示 s u b j e c t ?? t o subject \; to subjectto 的縮寫，

上述模型的矩陣形式如下：
max ? z = c T x s.t. A x ≤ b x ≥ 0 \begin{array}{rr} \max & z=c^{T} x \\ \text { s.t. } & A x \leq b \\ & x \geq 0 \end{array} max s.t. ?z=cTxAx≤bx≥0?
對于有 n n n 個決策變數， m m m 個約束的線性規劃模型， c , x c,x c,x 為 n n n 維列向量， b b b 為 m m m 為列向量， A A A 為 m ? n m*n m?n 維系數矩陣，

單純型法標準型與編程程序的“標準型”

單純型法：

? 單純型法思路就是在 可行域的一個頂點處找到一個初始可行解，判斷該解是不是最優，若不是，則迭代到下一個頂點處進行重復判斷，因為最優解的搜索范圍從整個可行域縮小到了可行域的有限個頂點，演算法的效率得到了極大的提升，

在單純型法中，我們通過增加變數等將約束條件變成等式，在編程中，一般支持直接寫等式約束和小于等于約束，

在單純型法中，我們將最大化目標函式視為標準型，在編程中，我們將最小化目標函式作為標準型，

Python 求解線性規劃模型

編程思路：

1. 選擇適當的決策變數

在解決實際問題時，把問題歸結成一個線性規劃數學模型是很重要的一步，但往往也是困難的一步，模型建立得是否恰當，直接影響到求解，而選適當的決策變數，是我們建立有效模型的關鍵之一，

2.將求解目標簡化為求一個目標函式的最大/最小值

能把要求解的問題簡化為一個最值問題是能否使用線性規劃模型的關鍵，如果這一點不能達到，之后的作業都有沒有意義的，

3. 根據實際要求寫出約束條件（正負性，資源約束等）

線性規劃的約束條件針對不同的問題有不同的形式，總結來說有以下三種：等式約束、不等式約束、符號約束

考慮以下線性規劃問題：
max ? z = 2 x 1 + 3 x 2 ? 5 x 3 s.t. x 1 + x 2 + x 3 = 7 2 x 1 ? 5 x 2 + x 3 ≥ 10 x 1 + 3 x 2 + x 3 ≤ 12 x 1 , x 2 , x 3 ≥ 0 \begin{array}{r} \max z=2 x_{1}+3 x_{2}-5 x_{3} \\ \text { s.t. } \quad x_{1}+x_{2}+x_{3}=7 \\ 2 x_{1}-5 x_{2}+x_{3} \geq 10 \\ x_{1}+3 x_{2}+x_{3} \leq 12 \\ x_{1}, x_{2}, x_{3} \geq 0 \end{array} maxz=2x1?+3x2??5x3? s.t. x1?+x2?+x3?=72x1??5x2?+x3?≥10x1?+3x2?+x3?≤12x1?,x2?,x3?≥0?
Step1：匯入相關函式庫：

import numpy as np 
from scipy import optimize as op 

Step2: 定義決策變數：

# 給出變數取值范圍
x1=(0,None)  
x2=(0,None)
x3=(0,None)

Step3: 將原問題化為標準形式

注意：編程時默認為最小化目標函式，因此這里改為 ；第二個約束為大于等于約束，這里化為小于等于約束；

Step4: 定義目標函式系數和約束條件系數

c=np.array([-2,-3,5])   # 目標函式系數,3x1列向量

A_ub=np.array([[-2,5,-1],[1,3,1]]) # 不等式約束系數A，2x3維矩陣
B_ub=np.array([-10,12])  # 等式約束系數b, 2x1維列向量
A_eq=np.array([[1,1,1]])  # 等式約束系數Aeq，3x1維列向量
B_eq=np.array([7])   # 等式約束系數beq，1x1數值

Step5: 求解

res=op.linprog(c,A_ub,B_ub,A_eq,B_eq,bounds=(x1,x2,x3)) #呼叫函式進行求解
print('結果如下：\n',res)

完整代碼如下：

import numpy as np 
from scipy import optimize as op 
# 給出變數取值范圍
x1=(0,None)  
x2=(0,None)
x3=(0,None)
c=np.array([-2,-3,5])   # 目標函式系數,3x1列向量

A_ub=np.array([[-2,5,-1],[1,3,1]]) # 不等式約束系數A，2x3維矩陣
B_ub=np.array([-10,12])  # 等式約束系數b, 2x1維列向量
A_eq=np.array([[1,1,1]])  # 等式約束系數Aeq，3x1維列向量
B_eq=np.array([7])   # 等式約束系數beq，1x1數值
res=op.linprog(c,A_ub,B_ub,A_eq,B_eq,bounds=(x1,x2,x3)) #呼叫函式進行求解
print('結果如下：\n',res)

結果如下：

結果如下：
      con: array([1.80712334e-09])
     fun: -14.571428565645078
 message: 'Optimization terminated successfully.'
     nit: 5
   slack: array([-2.24570584e-10,  3.85714286e+00])
  status: 0
 success: True
       x: array([6.42857143e+00, 5.71428571e-01, 2.35900788e-10])

即，當 x 1 = 6.42857143 , x 2 = 0.571428571 , x 3 = 2.35900788 × 1 0 ? 10 x_1=6.42857143,x_2=0.571428571,x_3=2.35900788\times10^{-10} x1?=6.42857143,x2?=0.571428571,x3?=2.35900788×10?10 時候目標函式取得最大值，

部分內容參考其他文章
分享自微信公眾號 - 資料科學CLUB（jiji8215）
作者：少年吉