Cum se poate vizualiza regiunea fezabilă pentru programarea liniară (cu inegalități arbitrare) în Numpy/MatplotLib? (Programare, Python 3.X, Numpy, Matplotlib, Programare Liniară)

Arturo a intrebat.

Trebuie să implementez un rezolvator pentru probleme de programare liniară. Toate restricțiile sunt <= unele de genul

5x + 10y <= 10

Poate exista o cantitate arbitrară de aceste restricții. De asemenea , x>=0 y>=0 implicit.

Trebuie să găsesc soluțiile optime(max) și să arăt regiunea fezabilă în matplotlib. Am găsit soluția optimă prin implementarea metodei simplex, dar nu-mi dau seama cum să desenez graficul.

Câteva abordări pe care le-am găsit:

  1. Acest link găsește minimul punctelor y din fiecare funcție și folosește plt.fillBetween() pentru a desena regiunea. Dar nu funcționează atunci când schimb ordinea ecuațiilor. Nu sunt sigur ce valori y să minimizez(). Deci nu o pot folosi pentru restricții arbitrare.
  2. Găsiți soluția pentru fiecare pereche de restricții și desenați un poligon. Nu este eficient.

2 răspunsuri
Stelios

O abordare mai ușoară ar putea fi ca matplotlib să calculeze singur regiunea fezabilă (cu tine furnizând doar constrângerile) și apoi să suprapui pur și simplu liniile de „constrângere” deasupra.

# 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'$2yleq25-x$')
plt.plot(x, y3, label=r'$4ygeq 2x - 8$')
plt.plot(x, y4, label=r'$yleq 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$')

Comentarii

  • Sunt un noob total când vine vorba de aceste lucruri, așa că sper că nu vă deranjează întrebările. Nu am folosit niciun fel de casting în python. Este .asType() pentru a genera o matrice de 0s și ones bazată pe faptul că punctul urmează sau nu restricțiile? –  > Por Arturo.
  • @Arturo Dacă evaluați inegalitățile, veți vedea că python (de fapt, nympy) returnează un array cu True/False intrări care plt.imshow nu înțelege. Cu .astype(int), , intrările sunt traduse în 0/1‘s care imshow înțelege. –  > Por Stelios.
AndrosovAS

Aceasta este o problemă de enumerare a vertexurilor. Puteți utiliza funcția lineqs care vizualizează sistemul de inegalități A x >= b pentru orice număr de linii. Funcția va afișa, de asemenea, vârfurile pe care a fost trasat graficul.

Ultimele 2 linii înseamnă că 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')

Soluție vizuală