参考博客：用python解决线性规划
模型标准型：
所需库：scipy、pulp(可选)
例题1转化为标准形：
{
−
x
+
y
≤
5
−
x
−
y
≤
0
x
≤
3
begin{cases}-x+yle 5\-x-yle 0\xle 3end{cases}
⎩⎪⎨⎪⎧−x+y≤5−x−y≤0x≤3
import numpy as np
from scipy import optimize
#以下符号与标准形对应
z = np.array([4,-1]) #z = 4x-y
A = np.array([[-1,1],
[-1,-1]]) # 约束条件系数矩阵
b = np.array([5,0])
x = (None,3) #x<=3
y = (None,None)
res = optimize.linprog(z,A,b,bounds=(x,y))
res
con: array([], dtype=float64)
fun: -12.499999999587356
message: 'Optimization terminated successfully.'
nit: 4
slack: array([1.52723167e-10, 2.05568895e-11])
status: 0
success: True
x: array([-2.5, 2.5])
例题2
转化为标准型：
{
−
2
x
1
+
5
x
2
−
x
3
≤
−
10
x
1
+
3
x
2
+
x
3
≤
12
x
1
+
x
2
+
x
3
=
7
x
1
,
x
2
,
x
3
≥
0
begin{cases}-2x_1+5x_2-x_3le-10\x_1+3x_2+x_3le 12\x_1+x_2+x_3=7\x_1,x_2,x_3ge 0end{cases}
⎩⎪⎪⎪⎨⎪⎪⎪⎧−2x1+5x2−x3≤−10x1+3x2+x3≤12x1+x2+x3=7x1,x2,x3≥0
import numpy as np from scipy import optimize z = np.array([2,3,-5]) #要求最大值，只要在最后调用函数时乘一个-1就行，系数不用改 A = np.array([[-2,5,-1],[1,3,1]]) b = np.array([-10,12]) Aeq = np.array([[1,1,1]]) #注意是二维数组 beq = np.array([7]) x1 = (0,None) x2 = (0,None) x3 = (0,None) res = optimize.linprog(-z,A,b,Aeq,beq,(x1,x2,x3)) res
con: array([1.80712245e-09])
fun: -14.571428565645084
message: 'Optimization terminated successfully.'
nit: 5
slack: array([-2.24599006e-10, 3.85714286e+00])
status: 0
success: True
x: array([6.42857143e+00, 5.71428571e-01, 2.35900788e-10])
pulp库可选学，此不附，可参见参考博客
总结步骤：
- 列出标准型方程
- 调包（doge）
- 根据方程列出价值向量、约束条件的系数矩阵、常数向量（注意是小于等于条件下的），等于条件分开列，以及决策变量的范围
- 调用函数，依次输入价值向量、系数矩阵、常数向量、等式条件的系数矩阵、常数向量、决策向量
习题来源:《数学建模算法与程序》司守奎
分析题目，可知决策向量为每个货舱内各个货物的质量，可视为三行四列的矩阵
(
a
11
a
12
a
13
a
14
a
21
a
22
a
23
a
24
a
31
a
32
a
33
a
34
)
begin{pmatrix}a_{11}&a_{12}&a_{13}&a_{14}\a_{21}&a_{22}&a_{23}&a_{24}\a_{31}&a_{32}&a_{33}&a_{34}end{pmatrix}
⎝⎛a11a21a31a12a22a32a13a23a33a14a24a34⎠⎞
行分别代表前舱、中仓、后舱，列分别代表货物1、2、3、4
然后根据题意建立约束方程组：
m
a
x
z
=
3100
(
a
11
+
a
21
+
a
31
)
+
3800
(
a
12
+
a
22
+
a
32
)
+
3500
(
a
13
+
a
23
+
a
33
)
+
2850
(
a
14
+
a
24
+
a
34
)
{
a
11
+
a
12
+
a
13
+
a
14
≤
10
a
21
+
a
22
+
a
23
+
a
24
≤
16
a
31
+
a
32
+
a
33
+
a
34
≤
8
480
a
11
+
650
a
12
+
580
a
13
+
390
a
14
≤
6800
480
a
21
+
650
a
22
+
580
a
23
+
390
a
24
≤
8700
480
a
31
+
650
a
32
+
580
a
33
+
390
a
34
≤
5300
4
a
11
+
4
a
12
+
4
a
13
+
4
a
14
−
5
a
31
−
5
a
32
−
5
a
33
−
5
a
34
=
0
a
21
+
a
22
+
a
23
+
a
24
−
2
a
31
−
2
a
32
−
2
a
33
−
2
a
34
=
0
a
11
+
a
21
+
a
31
≤
18
a
12
+
a
22
+
a
32
≤
15
a
13
+
a
23
+
a
33
≤
23
a
14
+
a
24
+
a
34
≤
12
a
i
j
≥
0
maxquad z=3100(a_{11}+a_{21}+a_{31})+3800(a_{12}+a_{22}+a_{32})+3500(a_{13}+a_{23}+a_{33})+2850(a_{14}+a_{24}+a_{34})\ begin{cases}a_{11}+a_{12}+a_{13}+a_{14}le 10\a_{21}+a_{22}+a_{23}+a_{24}le 16\a_{31}+a_{32}+a_{33}+a_{34}le 8\480a_{11}+650a_{12}+580a_{13}+390a_{14}le 6800\480a_{21}+650a_{22}+580a_{23}+390a_{24}le 8700\480a_{31}+650a_{32}+580a_{33}+390a_{34}le 5300\4a_{11}+4a_{12}+4a_{13}+4a_{14}-5a_{31}-5a_{32}-5a_{33}-5a_{34}=0\a_{21}+a_{22}+a_{23}+a_{24}-2a_{31}-2a_{32}-2a_{33}-2a_{34}=0\a_{11}+a_{21}+a_{31}le 18\a_{12}+a_{22}+a_{32}le15\a_{13}+a_{23}+a_{33}le23\a_{14}+a_{24}+a_{34}le 12\a_{ij}ge 0 end{cases}
maxz=3100(a11+a21+a31)+3800(a12+a22+a32)+3500(a13+a23+a33)+2850(a14+a24+a34)⎩⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎧a11+a12+a13+a14≤10a21+a22+a23+a24≤16a31+a32+a33+a34≤8480a11+650a12+580a13+390a14≤6800480a21+650a22+580a23+390a24≤8700480a31+650a32+580a33+390a34≤53004a11+4a12+4a13+4a14−5a31−5a32−5a33−5a34=0a21+a22+a23+a24−2a31−2a32−2a33−2a34=0a11+a21+a31≤18a12+a22+a32≤15a13+a23+a33≤23a14+a24+a34≤12aij≥0
代码求解
import numpy as np
from scipy import optimize
z = np.array([3100,3800,3500,2850,3100,3800,3500,2850,3100,3800,3500,2850])#这里把矩阵展平了
A = np.array([[1,1,1,1,0,0,0,0,0,0,0,0],[0,0,0,0,1,1,1,1,0,0,0,0],[0,0,0,0,0,0,0,0,1,1,1,1],[480,650,580,390,0,0,0,0,0,0,0,0],
[0,0,0,0,480,650,580,390,0,0,0,0],[0,0,0,0,0,0,0,0,480,650,580,390],[1,0,0,0,1,0,0,0,1,0,0,0],[0,1,0,0,0,1,0,0,0,1,0,0],
[0,0,1,0,0,0,1,0,0,0,1,0],[0,0,0,1,0,0,0,1,0,0,0,1]])#变量数目要一一对应
b = np.array([10,16,8,6800,8700,5300,18,15,23,12])
Aeq = np.array([[4,4,4,4,0,0,0,0,-5,-5,-5,-5],[0,0,0,0,1,1,1,1,-2,-2,-2,-2]])
beq = np.array([0,0])
#函数默认决策变量大于等于0可不设
res = optimize.linprog(-z,A,b,Aeq,beq)
res
con: array([1.02306806e-09, 1.02196437e-09])
fun: -121515.78945373134
message: 'Optimization terminated successfully.'
nit: 9
slack: array([1.39241330e-09, 2.84060064e-09, 9.09317954e-10, 3.99943085e+02,
1.70148996e-06, 2.10056916e+02, 1.80000000e+01, 3.12322612e-09,
7.05263158e+00, 8.94736842e+00])
status: 0
success: True
x: array([2.97828159e-10, 8.57224165e+00, 1.42775835e+00, 1.11221250e-10,
4.78770013e-09, 1.35813159e-10, 1.29473684e+01, 3.05263158e+00,
5.24598931e-10, 6.42775835e+00, 1.57224165e+00, 1.88054946e-10])
