Il metodo grafico: la programmazione lineare in due variabili

vincolo lineare

Il metodo grafico è il modo più semplice di affrontare un problema di programmazione lineare in due sole variabili.
Innanzitutto diciamo che un problema in due variabili si presenta nel modo seguente:
\begin{equation}
z = c_{1}x_{1} + c_{2}x_{2}
\end{equation}
con vincoli…
\begin{equation}
\{ \begin{array}{c}
a_{11}x_{1}+a_{12}x_{2} \leq b_{1} \\
a_{21}x_{1}+a_{22}x_{2} \leq b_{2} \\
…\\
a_{m1}x_{1}+a_{m2}x_{2} \geq b_{m} \\
…\\
a_{n1}x_{1}+a_{n2}x_{2} \geq b_{n} \\
x_{1} \geq 0 \\
x_{2} \geq 0
\end{array}
\end{equation}

Si vede immediatamente che in gioco ci sono soltanto due variabili (le due x), mentre tutti gli altri (le a, le b e le c) sono numeri. Siccome nessuna variabile compare con grado superiore al primo, tutte le equazioni associate alle disequazioni dei vincoli rappresentano delle rette (assi cartesiani compresi dovuti ai vincoli di segno delle variabili). Il problema si risolve in maniera molto semplice:

1. si rappresentano tutte le rette;
2. si determina la parte di piano che verifica tutte le disequazioni;
3. si valuta la funzione z nei punti di intersezione delle rette (ad esempio i vertici del poligono della figura in alto, rispettando ovviamente i vincoli di segno);
4. si sceglie come risultato il punto in cui la funzione z assume il valore più grande (se bisogna massimizzare, come nei casi di massimo profitto) o quello in cui la funzione assume il valore più piccolo (se bisogna minimizzare, come nei casi di minima spesa).
Da notare che, data la linearità del problema, non c’è bisogno di vincolare la funzione z ai lati ma basta soltanto valutarla nei vertici.

Esempio: avendo un vincolo come quello nella figura in alto, basta valutare la funzione z nei punti A, B, C, D, E.

ATuttoNet
  • Scrittore e Blogger
Suggerisci una modifica