用 scipy.optimize.linprog 实现线性规划

1. 概述

线性规划:在线性等式和不等式约束下最小化线性目标函数。
线性编程可解决以下形式的问题:

\[\begin{aligned} \min _{x} c^{T} x & \\text { such that } & A_{u b} x \leq b_{u b}, \& A_{e q} x =b_{e q}, \& l \leq x \leq u \end{aligned} \]

也就是说求解使得 \(c^{T} x\) 最小的x,同时x又要符合约束条件。
其中\(x\)是决策变量的向量;\(c\),\(b_{ub}\),\(b_{eq}\),\(l\)和\(u\)是向量;\(A_{ub}\)和\(A_{eq}\)是矩阵。

2. 实例

2.1 问题

要最小化 \(Z = 0.4X_{1} + 0.5X_{2}\),约束如下

\[\begin{aligned} &0.3 x_{1}+0.1 x_{2} \leq 2.7 \&0.5 x_{1}+0.5 x_{2}=6 \&0.6 x_{1}+0.4 x_{2} \geq 6 \&x_{1} \geq 0, \quad x_{2} \geq 0 \end{aligned} \]

2.2 求解

这里我们使用scipy中的linprog进行求解,其用法如下:

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

其中,c为要最小化的线性目标函数的系数。,A_ub和b_ub对应线性不等式约束,A_eq和b_eq对应线性等式约束,bounds确定边界,如x≥0为(0,None),x无约束则为(None,None),method是求解器的类型,‘simplex‘ 为单纯形法,其他的参数暂时可忽略。
要使用linprog,目标函数要变成求最小值,如果原题目要求求max(最大值),只需对目标函数取负,但要注意求解的最终值是取负后的目标函数的最小值,取负即为最大值。

最终分析如下:
用 scipy.optimize.linprog 实现线性规划
python代码如下:

import numpy as np
from scipy.optimize import linprog

c = np.array([0.4, 0.5])
A_ub = np.array([[0.3, 0.1], [-0.6, -0.4]])  # 不等式约束
b_ub = np.array([2.7, -6])
A_eq = np.array([[0.5, 0.5]])                # 等式约束
b_eq = np.array([6])
r = linprog(c, A_ub, b_ub, A_eq, b_eq, bounds=((0, None), (0, None)))
print(r)

运行结果如下所示:

     con: array([9.3865955e-09])
     fun: 5.2499999910145405
 message: ‘Optimization terminated successfully.‘
     nit: 5
   slack: array([2.67959077e-09, 2.99999992e-01])
  status: 0
 success: True
       x: array([7.5       , 4.49999999])

fun 为目标函数的最优值,slack 为松弛变量,status 表示优化结果状态,x 为最优解。
此模型的求解结果为:当 \(x_{1}=7.5\),\(x_2=4.49999999\) 时,函数取得最小值5.2499999910145405

参考

https://www.pianshen.com/article/39912031011/
https://www.freesion.com/article/98311054345/
https://blog.csdn.net/weixin_43638511/article/details/104236557

用 scipy.optimize.linprog 实现线性规划

上一篇:我可以排序向导列表并进行二进制搜索吗?


下一篇:安装激活JRebel热部署插件