python 求解线性规划问题
python 求解线性规划问题
用户6021899
发布于 2020-09-01 14:49:03
发布于 2020-09-01 14:49:03
一个线性规划的实例:
某机床厂生产甲、乙两种机床，每台销售后的利润分别为 4000 元与 3000 元。生产甲机床需用 A、B 机器加工，加工时间分别为每台 2 小时和 1 小时；生产乙机床需用 A、B、C 三种机器加工，加工时间为每台各一小时。若每天可用于加工的机器时数分别为 A 机器 10 小时、B 机器 8 小时和C 机器 7 小时，问该厂应生产甲、乙机床各几台，才能使总利润最大？
上述问题的数学模型：设该厂生产x1 台甲机床和 x2 乙机床时总利润最大，则x1 , x2应满足
这里变量x1 , x2 称之为决策变量，（1）式被称为问题的目标函数，（2）中的几个不等式是问题的约束条件，记为 s.t.(即 subject to)。由于上面的目标函数及约束条件均为线性函数，故被称为线性规划问题。总之，线性规划问题是在一组线性约束条件的限制下，求一线性目标函数最大或最小的问题。
我们中学学过用图解法解二维的线性规划问题：
由图解法可知上述问题的最优解释 x1,x2 = (2, 6)
在python中，我们可以通过调用scipy库中的optimize模块来求解线性规划问题。
上述问题的求解代码如下：
import numpy as np
from scipy import optimize
#定义目标函数
Z = np.mat([-4,-3])
#定义约束条件
A = np.mat([[2,1], [1,1],[0,1]])
B = np.mat([10,8,7])
x1_bound = x2_bound =(0, None)
#默认求最小值，且约束条件都为≤，否则可以通过式子两边乘以 -1 来转换。
res = optimize.linprog(Z, A_ub = A, b_ub= B,bounds=(x1_bound, x2_bound))
print(res)
print("最优解:",res.x)
print(res.fun)另一个更一般一点的问题：
只需要根据线性规划的标准型将目标函数和某些约束条件稍作变换。
#定义目标函数
Z = np.array([-2,-3,5])
A = np.array([[-2, 5, -1], [1, 3, 1]])
B = np.array([-10,12])
A_eq = [[1,1,1]]
b_eq = 7
x1_bound = x2_bound = x3_bound =(0, None)
#默认求最小值，且约束条件都为≤，否则可以通过式子两边乘以 -1 转换。
res = optimize.linprog(Z, A_ub= A, b_ub= B,A_eq= A_eq, b_eq= b_eq, bounds=(x1_bound, x2_bound,x3_bound))
print(res)很多看起来不是线性规划的问题也可以通过变换变成线性规划的问题来解决，如：
通过转换，即可把上述n维带绝对值符号的规划问题转换成2n维的线性规划问题。
=>
求解代码：
#定义目标函数
Z = np.array([2,2,3,3])
A = np.array([[-3,3,-4,4], [2,-2,-1,1],[1,-1,-3,3]])
B = np.array([-100,20,-25])
#x1_bound = x2_bound = x3_bound =x4_bound =(0, None)
#默认求最小值，且约束条件都为≤，否则可以通过式子两边乘以 -1 转换。
res = optimize.linprog(Z, A_ub= A, b_ub= B, bounds=((0, None), (0, None),(0, None),(0, None)))
x1 = res.x[0] - res.x[1]
x2 = res.x[2] - res.x[3]
print((x1,x2))本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2020-08-25，如有侵权请联系 cloudcommunity@tencent.com 删除
本文分享自 Python可视化编程机器学习OpenCV 微信公众号，前往查看
如有侵权，请联系 cloudcommunity@tencent.com 删除。
本文参与 腾讯云自媒体分享计划 ，欢迎热爱写作的你一起参与！
评论
登录后参与评论
推荐阅读