如何在Numpy/MatplotLib中可视化线性规划（带任意不等式）的可行区域？

Question

我需要实现一个线性规划问题的求解器。所有限制条件都是<=，例如：

5x + 10y <= 10

这些限制条件可以是任意数量。同时，x>=0，y>=0。

我需要找到最优解（最大值），并在matplotlib中显示可行域。我已经通过实现单纯形法找到了最优解，但我无法绘制图形。

我发现了一些方法：

1. 此链接 找到每个函数中y点的最小值，并使用plt.fillBetween()绘制区域。但是当我改变方程的顺序时它就不起作用了。我不确定要使minimize()哪些y值。因此，我不能将其用于任意限制条件。

2. 求出每对限制条件的解并绘制多边形。不高效。

- Arturo

Answer 1

一个更简单的方法可能是让 matplotlib 自行计算可行域（只需您提供约束条件），然后在其上方简单地叠加“约束”线条。

# plot the feasible region
d = np.linspace(-2,16,300)
x,y = np.meshgrid(d,d)
plt.imshow( ((y>=2) & (2*y<=25-x) & (4*y>=2*x-8) & (y<=2*x-5)).astype(int) , 
                extent=(x.min(),x.max(),y.min(),y.max()),origin="lower", cmap="Greys", alpha = 0.3);


# plot the lines defining the constraints
x = np.linspace(0, 16, 2000)
# y >= 2
y1 = (x*0) + 2
# 2y <= 25 - x
y2 = (25-x)/2.0
# 4y >= 2x - 8 
y3 = (2*x-8)/4.0
# y <= 2x - 5 
y4 = 2 * x -5

# Make plot
plt.plot(x, 2*np.ones_like(y1))
plt.plot(x, y2, label=r'$2y\leq25-x$')
plt.plot(x, y3, label=r'$4y\geq 2x - 8$')
plt.plot(x, y4, label=r'$y\leq 2x-5$')
plt.xlim(0,16)
plt.ylim(0,11)
plt.legend(bbox_to_anchor=(1.05, 1), loc=2, borderaxespad=0.)
plt.xlabel(r'$x$')
plt.ylabel(r'$y$')

- Stelios

---

我在这些方面是一个彻头彻尾的新手，所以希望你不介意我的问题。我没有在Python中使用任何类型转换。.asType()是用于根据点是否遵循限制生成0和1数组的吗？ - Arturo

如果您评估这些不等式，您会发现Python(实际上是Numpy)返回一个包含True/False条目的数组，而plt.imshow无法理解。使用.astype(int)可以将这些条目翻译成0/1，以便imshow能够理解。 - Stelios

我知道np是来自于numpy，但是我应该从哪里获取plt呢？ - Lori

@Lori import matplotlib.pyplot as plt @Lori 导入matplotlib.pyplot作为plt - Stelios

Answer 2

这是一个顶点枚举问题。您可以使用函数lineqs来可视化不等式系统Ax>=b的任意数量的行。该函数还会显示绘制图形的顶点。

最后两行意味着x，y>=0。

from intvalpy import lineqs
import numpy as np

A = -np.array([[5, 10],
               [-1, 0],
               [0, -1]])
b = -np.array([10, 0, 0])

lineqs(A, b, title='Solution', color='gray', alpha=0.5, s=10, size=(15,15), save=False, show=True)

视觉化解决方案链接

- AndrosovAS