用Python实现线性规划

使用python库中scipy中的函数linprog来求解线性规划

linprog函数中线性规划的标准形式为

\[\min c^Tx\\ s.t\left\{\begin{aligned}Auq\cdot x&\le b\\ Aeq\cdot x&=beq\\ lb\le x&\le ub\end{aligned}\right. \]

其中c和x为n维向量，A、Aeq为适当维度的矩阵，b、beq为适当维度的列向量。（Aeq对应约束条件中的等式约束得系数矩阵，A为不等式约束的系数矩阵。

scipy.optimize.linprog(c, A_ub=None, b_ub=None, A_eq=None, b_eq=None, bounds=None, method='simplex', callback=None, options=None)

求解最大化问题

\[\max 2x_1+3x_2-5x_3\\ s.t\left\{\begin{aligned}x_1+x_2+x_3&=7\\ 2x_1-5x_2+x_3&\ge10\\ x_1+3x_2+x_3&\le12\\ x_1, x_2,x_3 &\ge0 \end{aligned}\right. \]

将问题转换为标准形式

\[\min-2x_1-3x_2+5x_3\\ s.t\left\{\begin{aligned} x_1+x_2+x_3&=7\\ -2x_1+5x_2-x_3&\le-10\\ x_1+3x_2+x_3&\le12\\ x_1,x_2,x_3&\ge0 \end{aligned}\right. \\ c=\begin{pmatrix}-2&-3&5\end{pmatrix}\\ A_{uq}=\begin{pmatrix}-2&5&-1\\1&3&1\end{pmatrix}\\ b_{uq}=\begin{pmatrix}-10&12\end{pmatrix}\\ A_{eq}=\begin{pmatrix} 1&1&1 \end{pmatrix}\\ b_{eq}=\begin{pmatrix}7\end{pmatrix} \]

代码

from scipy import optimize as op
import numpy as np

c = np.array([-2, -3, 5])
A_ub = np.array([[-2, 5, -1], [1, 3, 1]])
b_ub = np.array([-10, 12])
A_eq = np.array([[1, 1, 1]])
b_eq = np.array([7])
x1 = [0, np.inf]
x2 = [0, np.inf]
x3 = [0, np.inf]
res = op.linprog(c, A_ub, b_ub, A_eq, b_eq, bounds=(x1, x2, x3)) # bounds为每个为每个未知量的范围
print(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])

所求最小值为-14.571428565645084，故得所求最大值为14.571428565645084