用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