6x + 4y <= 24
x + 2y <= 6
-x + y <= 1
y <= 2
我需要找到由这些不等式描述的区域,并在图表中进行阴影处理,同时跟踪该区域边界线的顶点,并用不同颜色绘制边界线。请参见下面的图表,以了解我要寻找的示例。
.
6x + 4y <= 24
x + 2y <= 6
-x + y <= 1
y <= 2
我需要找到由这些不等式描述的区域,并在图表中进行阴影处理,同时跟踪该区域边界线的顶点,并用不同颜色绘制边界线。请参见下面的图表,以了解我要寻找的示例。
.
更新: 过去4年时间里,本回答的内容已经有些过时了,现在您有许多选择:
如果您不一定非要使用Python,那么使用建模语言实现会更容易,可以参考Any good tools to solve integer programs on linux?
我个人现在使用的是Gurobi 的Python API。它是一个商业闭源产品,但对于学术研究免费。
使用PuLP,您可以创建MPS和LP文件,然后通过它们的命令行接口使用GLPK、COIN CLP/CBC、CPLEX或XPRESS进行求解。这种方法有其优点和缺点。
Google的OR-Tools是一个用于优化的开源软件套件,专门针对车辆路径规划、流量、整数线性规划和约束编程等世界上最棘手的问题。
Pyomo是一个基于Python的开源优化建模语言,具有多种优化功能。
SciPy提供线性规划:scipy.optimize.linprog。(我从未尝试过这个。)
显然,CVXOPT 提供了一个Python与GLPK交互的接口,我之前并不知道。我已经使用GLPK八年了,我强烈推荐GLPK。CVXOPT的示例和教程看起来很好!
您可以在维基书中的GLPK/Python中找到其他可能性。请注意,其中许多并不一定局限于GLPK。
import numpy as np
import matplotlib.pyplot as plt
m = np.linspace(0,5,200)
x,y = np.meshgrid(m,m)
plt.imshow(((6*x+4*y<=24)&(x+2*y<=6)&(-x+y<=1)&(y<=2)&(x>=0)&(y>=0)).astype(int),
extent=(x.min(),x.max(),y.min(),y.max()),origin='lower',cmap='Greys',alpha=0.3);
# plot constraints
x = np.linspace(0, 5, 2000)
# 6*x+4*y<=24
y0 = 6-1.5*x
# x+2*y<=6
y1 = 3-0.5*x
# -x+y<=1
y2 = 1+x
# y <= 2
y3 = (x*0) + 2
# x >= 0
y4 = x*0
plt.plot(x, y0, label=r'$6x+4y\leq24$')
plt.plot(x, y1, label=r'$x+2y\leq6$')
plt.plot(x, y2, label=r'$-x+y\leq1$')
plt.plot(x, 2*np.ones_like(x), label=r'$y\leq2$')
plt.plot(x, y4, label=r'$x\geq0$')
plt.plot([0,0],[0,3], label=r'$y\geq0$')
xv = [0,0,1,2,3,4,0]; yv = [0,1,2,2,1.5,0,0]
plt.plot(xv,yv,'ko--',markersize=7,linewidth=2)
for i in range(len(xv)):
plt.text(xv[i]+0.1,yv[i]+0.1,f'({xv[i]},{yv[i]})')
plt.xlim(0,5); plt.ylim(0,3); plt.grid(); plt.tight_layout()
plt.legend(loc=1); plt.xlabel('x'); plt.ylabel('y')
plt.show()
Maximize x+y
),那么许多能力强大的Python求解器可以处理这个问题。这是一个线性规划的例子,在GEKKO中,还支持混合整数、非线性和微分约束。from gekko import GEKKO
m = GEKKO(remote=False)
x,y = m.Array(m.Var,2,lb=0)
m.Equations([6*x+4*y<=24,x+2*y<=6,-x+y<=1,y<=2])
m.Maximize(x+y)
m.solve(disp=False)
大规模的线性规划问题通常以矩阵形式或稀疏矩阵形式解决,只存储矩阵的非零部分。这里有一个线性规划解决方案教程,其中包含我为一门大学课程开发的几个示例。
对我来说,lpsolve 是最容易的。无需安装单独的求解器,它已经包含在软件包中了。
-x + x <= 1
是一个无操作,因为它可以简化为0 <= 1
,这对于所有的 x 和 y 都是成立的。 - Eric