解决线性方程组和线性不等式系统

7

我需要在Python中获取线性表达式的最小值和最大值,这个表达式受一些线性不等式的限制。

你可以在这里看到我已经输入到Desmos中的方程和不等式:

3x+12y = 1000
x > 30
x < 160
y < 60
y > 10
x + y > 180

Desmos equation + inequalities

我可以通过手动绘制和划掉不等式来解决它们。但是我不能在Python中这么做。 到目前为止,我在Python中尝试的方法是当x=0时得到y=83.33;当y=0时得到x=333.33; 在获取最小和最大的x,y之后,我就逐个应用不等式。但是对于每个不等式,我都必须添加先前的不等式,并且还要检查x或y是否超过了某个范围,迄今为止几乎可以确定我会错过一个检查。

我看了numpy和sympy,但是无法弄清楚如何使用它们来解决此问题。您能建议我使用什么/如何使用才能获得白色箭头在图片上显示的范围吗?


1
这是线性规划中的一个问题,其中等式和不等式是限制条件,您希望最小化和最大化表达式 y。在Python中搜索线性规划,如果您在实现它时遇到特定问题,请告诉我们。您可以从 scipy.optimize.linprog 开始。当您查看scipy时,是否研究过它? - Rory Daulton
3个回答

17

你面临的是线性规划问题,其中等式和不等式是限制条件,并且你想要最小化(然后最大化)表达式y。等式、不等式和表达式都是线性的,因此这是线性规划问题。使用scipy.optimize.linprog函数的scipy包可以解决这种线性规划问题。

以下是可实现您需求的注释代码。请注意,所有不等式都稍作更改以包括等式,这对于具有最大或最小值y是必要的。为了找到y的最大值,该代码将寻找-y的最小值,然后打印其加法逆元,因为linprog会最小化目标函数。最后,linprog的不等式约束必须是“小于等于”,因此我将不等式x + y> 180的两侧都乘以-1,得到一个新的不等式-x+-y <= -180。如果您有任何问题,请随时提出。

from scipy.optimize import linprog

# Set up values relating to both minimum and maximum values of y
coefficients_inequalities = [[-1, -1]]  # require -1*x + -1*y <= -180
constants_inequalities = [-180]
coefficients_equalities = [[3, 12]]  # require 3*x + 12*y = 1000
constants_equalities = [1000]
bounds_x = (30, 160)  # require 30 <= x <= 160
bounds_y = (10, 60)  # require 10 <= y <= 60

# Find and print the minimal value of y
coefficients_min_y = [0, 1]  # minimize 0*x + 1*y
res = linprog(coefficients_min_y,
              A_ub=coefficients_inequalities,
              b_ub=constants_inequalities,
              A_eq=coefficients_equalities,
              b_eq=constants_equalities,
              bounds=(bounds_x, bounds_y))
print('Minimum value of y =', res.fun)

# Find and print the maximal value of y = minimal value of -y
coefficients_max_y = [0, -1]  # minimize 0*x + -1*y
res = linprog(coefficients_max_y,
              A_ub=coefficients_inequalities,
              b_ub=constants_inequalities,
              A_eq=coefficients_equalities,
              b_eq=constants_equalities,
              bounds=(bounds_x, bounds_y))
print('Maximum value of y =', -res.fun)  # opposite of value of -y

那段代码的输出结果为:

Minimum value of y = 43.3333333333
Maximum value of y = 51.1111111111

这是在浮点精度范围内正确的。如果您需要对应的x值,请查看res.x的值,它是一个数组,给出所需点上xy的值- xres.x [0],而yres.x [1]


1
非常感谢,我已经解决了实际问题(它有更多的不等式)。但不幸的是,我要循环运行这段代码大约1500次,需要大约8秒钟。是否有一种方法只检查在给定不等式中是否存在x在y中的根(我认为这样做会更快,而不是最小化和最大化)。 顺便说一下,我将您的答案标记为解决方案。 - random12231
我喜欢复制并运行100%工作的例子,而这就是其中之一。非常出色的工作。 - Peter Trcka
我喜欢COPY & RUN 100%可行的例子。而这就是其中之一。干得好。 - undefined

1

根据评论中提供的提示,您可以使用scipy.optimize.linprog来解决您的问题,具体操作如下...

In [1]: import numpy as np

In [2]: from scipy import optimize

In [3]: c = np.zeros(2)

In [4]: A_ub = np.array([[-1, -1]])

In [5]: b_ub = np.array([-180])

In [6]: A_eq = np.array([[3, 12]])

In [7]: b_eq = np.array([1000])

In [8]: bounds = [(30, 160), (10, 60)]

In [9]: optimize.linprog(c, A_ub, b_ub, A_eq, b_eq, bounds, method="simplex")
Out[11]: 
     fun: -0.0
 message: 'Optimization terminated successfully.'
     nit: 5
   slack: array([ 31.11111111,  98.88888889,   0.        ,  41.11111111,   8.88888889])
  status: 0
 success: True
       x: array([ 128.88888889,   51.11111111])

技巧在于注意到解方程组可以用一个常数为零的优化问题来表示。这就是我在上面设置c=np.zeros(2)的原因。该问题与编程有关。

似乎OP想要“获取最小值和最大值y”,而不仅仅是一个可行点。 - user6655984

0
你可以尝试使用cvxpy。它是一个用于解决凸问题的求解器,所以对于你的需求来说可能有些过头了。我喜欢使用它来编码问题的简易性。大多数其他库需要你将问题编码成多个矩阵。

(1) cvxpy没有自己的求解器,除了无约束LS。所有其他求解器都是外部求解器。(2) cvxpy是一个建模工具,但不能表达所有凸问题。它只能构建符合纪律凸规划(DCP < Convex)的问题。(3) 我喜欢cvxpy,但我不认为在这里使用它有意义。用一般锥形规划方法来处理LP会失去性能和鲁棒性(我忽略了alpha版本1.0及其缩减;但即使有这些:在现实世界中有助于变量边界的概念也不存在)。 - sascha
我同意你的第一个观点,在那里我应该更清楚。使用cvxpy编写和运行求解器,我能够比使用scipy更快地解决问题。 - Jacques Kvam

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接