10

I need to implement a solver for linear programming problems. All of the restrictions are <= ones such as

5x + 10y <= 10

There can be an arbitrary amount of these restrictions. Also , x>=0 y>=0 implicitly.

I need to find the optimal solutions(max) and show the feasible region in matplotlib. I've found the optimal solution by implementing the simplex method but I can't figure out how to draw the graph.

Some approaches I've found:

  1. This link finds the minimum of the y points from each function and uses plt.fillBetween() to draw the region. But it doesn't work when I change the order of the equations. I'm not sure which y values to minimize(). So I can't use it for arbitrary restrictions.
  2. Find solution for every pair of restrictions and draw a polygon. Not efficient.
Arturo
  • 191
  • 1
  • 1
  • 8

2 Answers2

17

An easier approach might be to have matplotlib compute the feasible region on its own (with you only providing the constraints) and then simply overlay the "constraint" lines on top.

# 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$')

enter image description here

Stelios
  • 5,271
  • 1
  • 18
  • 32
  • I a total noob when it comes to these things so I hope you don't mind the questions. I haven't used any sort of casting in python. Is the .asType() for generating an array of 0s and ones based on whether the point follows the restrictions? – Arturo Jul 13 '19 at 09:40
  • 1
    @Arturo If you evaluate the inequalities, you will see that python (actually, nympy) returns an array with `True`/`False` entries that `plt.imshow` does not understand. With `.astype(int)`, the entries are translated to `0`/`1`'s that `imshow` understands. – Stelios Jul 13 '19 at 09:47
  • I'm aware `np` comes from numpy, but where would I get `plt`? – Lori Feb 18 '22 at 00:15
  • 1
    @Lori `import matplotlib.pyplot as plt` – Stelios Feb 18 '22 at 02:48
3

This is a vertex enumeration problem. You can use the function lineqs which visualizes the system of inequalities A x >= b for any number of lines. The function will also display the vertices on which the graph was plotted.

The last 2 lines mean that 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)

Visual Solution

Visual Solution Link

AndrosovAS
  • 110
  • 1
  • 1
  • 8