數學建模(一):用python解決線性規劃問題

最近準備去美賽觀光一波，於是了解了一下數學建模的相關知識，我準備以復現代碼為目的學習，在此寫點東西與大家共同探討一下。

線性規劃說起來很高端，但實際上在高中學習過數學的同學應該對此不陌生。

舉個慄子，工廠生產甲、乙兩種商品，其需要A、B、C三種資源，每種產品資源消耗量及單位產品銷售後所能獲得的利潤值以及這三種資源的儲備如下表所示：

消耗資源
A
B

C

銷售利潤
甲
9
4
370
乙
4
610
120
資源儲備
360200300

線性規劃問題可以表述為一個目標函數與一系列約束條件：

其中c、x為n行列向量，G是m*n的實數矩陣，A是p*n的實數矩陣，⪯是廣義不等號。

那麼對於這道例題，設甲生產x_1單位，乙生產x_2單位，則可將其表述為：

            

(第一次用latex，打的好醜）

這樣的題我想大多數人看一眼就知道了思路，但當數據過大，或變量過多時，人腦就難以對問題進行處理了。

二、python代碼實現

由於你航榮獲matlab背刺，我也懶得再學，所以決定使用泛用性最強的python來解決這類問題。

from scipy import optimize as opimport numpy as npc=np.array([70,120])A_ub=np.array([[9,4],[4,6],[3,10]])B_ub=np.array([360,200,300])x1=(0,None)x2=(0,None)res=op.linprog(-c,A_ub,B_ub,bounds=(x1,x2),options={"disp": True})print(res)
首先我解釋一下linprog中各參數的含義：
c：minimize中的x的係數向量，但該函數是用來求最小值的，所以想求最大值就得加個負號，在例題程序中我在最後使用了-c。
A_ub:  各小於等於式子中x的係數向量，如果題給約束是大於等於那就乘個負號。
B_ub:  各小於等於式子中右側的常數項。
A_eq:  等式約束中的x係數向量。
B_eq:  等式約束中的右側常數項。
bounds：x的範圍矩陣，如例題，沒有就填None
這樣一運行，就可以得出結果
函數最大值
要生產9.0909個甲和27.2727個乙實在是太為難工人師傅了，然而這串代碼並不能求得整數解，這個我再用其他的庫嘗試一下。

三、思考及延申

線性規劃問題即約束和目標函數都是線性的，用簡單的矩陣就能解釋。那麼當其為非線性的時候呢？這時又該怎麼處理，怎麼計算？（見下篇）
本篇中的代碼無法求出整數解，x少時還可以就近試一下，如果變量賊多那實在不行就撿起matlab用linprog吧。