Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica La Corte in Rete
 
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

Paola Festa » 3.Problemi di PL


Forma standard di un problema di PL, 1

Definizione: Un problema di PL si dice formulato in forma standard se si tratta di minimizzare una funzione obiettivo lineare soggetta a vincoli di uguaglianza, se le variabili di decisione sono vincolate ad essere nonnegative e il vettore dei termini noti è nonnegativo.

Osservazione: Ogni problema di PL può essere formulato in forma standard applicando, qualora necessario, opportune trasformazioni alla funzione obiettivo, ai vincoli ed alle variabili.

Nel prosieguo della trattazione di problemi di PL, faremo sempre riferimento a problemi formulati in forma standard.

Forma standard di un problema di PL, 2

  • Trasformazione della funzione obiettivo: se è richiesto individuare una soluzione cui corrisponda una valore max di funzione obiettivo, è banale la trasformazione, essendo la funzione lineare nelle variabili di decisione.
  • Nonnegatività dei termini noti: se un termine noto è negativo, basta moltiplicare per (-1) entrambi i membri del vincolo ed eventualmente cambiare verso della disuguaglianza se il vincolo corrispondente non è un vincolo di uguaglianza.
  • Trasformazioni delle variabili: se per qualche j=1,2,\ldots,n risulta che x_j\leq 0 , allora basta effettuare nella formulazione matematica la sostituzione x_j = - x'_j ,\  x'_j\geq 0 ; se x_j non è vincolata in segno, allora basta effettuare nella formulazione matematica la sostituzione x_j = x^+_j - x^-_j , x^+_j\geq 0, x^-_j\geq 0 .

Forma standard di un problema di PL, 3

Trasformazioni dei vincoli: un qualsiasi vincolo può essere trasformato in vincolo di uguaglianza introducendo opportune variabili aggiuntive nonnegative.

Infatti, un vincolo del tipo
\displaystyle{\sum_{j=1}^n a_{ij}x_j\leq b_i}

può essere equivalentemente riscritto nella seguente forma:

		\displaystyle{\sum_{j=1}^n a_{ij}x_j + x_{n+1}= b_i},\ \ x_{n+1}\geq 0,

dove x_{n+1} rappresenta la differenza non negativa tra il secondo ed il primo membro della disuguaglianza e viene detta variabile di slack.

Forma standard di un problema di PL, 3 (segue)

Un vincolo del tipo

\displaystyle{\sum_{j=1}^n a_{ij}x_j\geq b_i}

può, invece, essere equivalentemente riscritto nella seguente forma:

		\displaystyle{\sum_{j=1}^n a_{ij}x_j - x_{n+1}= b_i},\ \ x_{n+1}\geq 0,

dove x_{n+1} rappresenta la differenza nonnegativa tra il primo ed il secondo membro della disuguaglianza e viene detta variabile di surplus.

Forma standard di un problema di PL, 4

\[ \begin{array}{lll}\mbox{{\rm max}} z(x) = &-3x_1-2x_2+5x_3+x_4\\\mbox{{\rm s.a}} \\(1) &-x_1+x_2 &\geq 1\\(2) &x_2+3x_3 &= 4\\(3) &x_1+2x_3-x_4 & \geq -2\\(4) &x_2+x_3+5x_4 & \leq 3\\&x_j\geq 0 &j=1,2,3.\end{array} \]

Forma standard di un problema di PL, 4

Effettuando le seguenti operazioni:

  • trasformare la funzione obiettivo;
  • moltiplicare per (-1) entrambi i membri del vincolo (3) e cambiare verso della disuguaglianza;
  • introdurre la variabile di surplus x_5 nel vincolo (1);
  • introdurre le variabili di slack x_6,\ x_7 rispettivamente nei vincoli (3) e (4);
  • sostituire la variabile x_4 non vincolata in segno con la differenza x_4-x_8,\  x_4\geq 0,\   x_8\geq 0 , si ottiene la seguente formulazione standard del problema:

\[  \begin{array}{lll} \mbox{{\rm - min}} \ z(x) = &3x_1+2x_2-5x_3-x_4+x_8 \\ \mbox{{\rm s.a}} \\ (1)   &-x_1+x_2-x_5          & = 1\\ (2)   &x_2+3x_3              & = 4\\ (3)   &-x_1-2x_3+x_4+x_6-x_8 &= 2\\ (4)   &x_2+x_3+5x_4+x_7-5x_8 &= 3\\ &x_j\geq 0             &j=1,2,\ldots,8. \end{array} \]

Forma standard di un problema di PL, 5

La formulazione standard di un generico problema di PL è, dunque, la seguente:

\[ \begin{array}{llll}\mbox{{\rm min}} & z(x) = c_1x_1+c_2x_2+\cdots+c_nx_n \\\mbox{{\rm s.a}} \\& a_{11}x_1 + a_{12} x_2 + \ldots + a_{1n}x_n & = b_1 & (1.1)\\& a_{21}x_1 + a_{22} x_2 + \ldots + a_{2n}x_n & = b_2 & (1.2)\\& \ldots \ldots \ldots \ldots & & \ldots\\& a_{m1}x_1 + a_{m2} x_2 + \ldots + a_{mn}x_n & = b_m & (1.m)\\& x_j\geq 0\ \ j=1,2,\ldots,n,\end{array} \]

dove

  • b_i\geq 0 ,  i=1,2,\ldots,m è il vettore m -dimensionale dei termini noti;
  • A=[a_{ij}]\in {\mathbb R}^{m\times n} è la matrice dei coefficienti tecnologici;
  • c\in {\mathbb R}^n è il vettore n -dimensionale dei coefficienti della funzione obiettivo che possono essere coefficienti di costo oppure coefficienti di profitto (prob. di massimo).

Interpretazione e soluzione grafica di un problema di PL

Quando il problema di PL da dover risolvere caratterizzato da due sole variabili decisionali, è possibile risolverlo immediatamente per via grafica.

Si consideri il seguente problema

\[ \begin{array}{llll}\mbox{{\rm min}} \ z(x) = &-x_1-x_2 \\\mbox{{\rm s.a}} \\&x_1+2x_2 & \leq 3 & \mbox{{\rm (a)}}\\&2x_1+x_2 & \leq 3 & \mbox{{\rm (b)}}\\&x_j\geq 0 &j=1,2.\end{array} \]

L’insieme ammissibile S è la regione mostrata in grigio in Figura.

Al crescere di z l’equazione -x_1-x_2=z individua un fascio di rette che si muovono parallelamente a se stesse nella direzione individuata dal vettore (c_1,c_2)=(-1,-1) .

Dal momento che lo scopo è minimizzare z, si è interessati a muovere il fascio di rette nel verso del vettore -(c_1,c_2)=(1,1) senza mai abbandonare la regione ammissibile S.
Guardando la Figura, è facile rendersi conto che il minimo valore possibile per z è -2 e che il vettore x^*=(1,1) è la soluzione ottima cercata.

Soluzione grafica del problema. Tratta da D. Bertsimas e J.N. Tsitsiklis, Introduction to Linear Optimization, Belmont – Massachusetts (USA), Dynamic Ideas and Athena Scientific, 2008. Rilucidata da Paola Festa

Soluzione grafica del problema. Tratta da D. Bertsimas e J.N. Tsitsiklis, Introduction to Linear Optimization, Belmont - Massachusetts (USA), Dynamic Ideas and Athena Scientific, 2008. Rilucidata da Paola Festa


Soluzione di un problema di PL, 1

La regione ammissibile S del problema dell’esempio precedente è limitata e la soluzione ottima è unica.

Si consideri ora la regione ammissibile S descritta dai seguenti vincoli e rappresentata in Figura:

\[ \begin{array}{llll}&-x_1+x_2 & \leq 1 & \mbox{{\rm (a)}}\\&x_j\geq 0 &j=1,2.\end{array} \]

A seconda della funzione obiettivo da minimizzare, si possono presentare i seguenti vari casi:

1. Se c=(1,1) , x^*=(0,0) è l’unica soluzione ottima.
2. Se c=(1,0) , ogni vettore x^*=(0,x_2),\ 0\leq x_2\leq 1 è soluzione ottima del problema.
Si noti che l’insieme delle soluzioni ottime è limitato.
3. Se c=(0,1) , ogni vettore x^*=(x_1,0),\ x_1\geq 0 è soluzione ottima.

Si noti che l’insieme delle soluzioni ottime è illimitato.

Soluzione di un problema di PL. Tratta da D. Bertsimas e J.N. Tsitsiklis, Introduction to Linear Optimization, Belmont – Massachusetts (USA), Dynamic Ideas and Athena Scientific, 2008. Rilucidata da Paola Festa

Soluzione di un problema di PL. Tratta da D. Bertsimas e J.N. Tsitsiklis, Introduction to Linear Optimization, Belmont - Massachusetts (USA), Dynamic Ideas and Athena Scientific, 2008. Rilucidata da Paola Festa


Soluzione di un problema di PL, 1 (segue)

4. Se c=(-1,-1) , è possibile ottenere una sequenza di soluzioni ammissibili il cui costo converge a -\infty , per cui si dice che in tal caso il costo ottimo è -\infty .
Se viene imposto il seguente ulteriore vincolo

x_1+x_2\leq -2\ \ \ \mbox{{\rm (b)}}, allora il problema non ammette alcuna soluzione, essendo S vuota.

Soluzione di un problema di PL, 2

Riassumendo quanto visto nel precedente Esempio, nell’affrontare un problema di PL possono verificarsi i seguenti 4 casi:

  1. Il problema ammette un’unica soluzione ottima.
  2. Il problema ammette soluzioni multiple e l’insieme delle soluzioni ottime può essere limitato o illimitato.
  3. Il costo ottimo è -\infty e nessuna soluzione ammissibile è ottima.
  4. La regione ammissibile S è vuota.

Una importante osservazione che emerge dagli Esempi precedenti è che se il problema ammetteva almeno una soluzione ottima, allora una soluzione ottima era collocata ad un vertice della regione ammissibile S.

Nella prossima lezione verificheremo che questa è una caratteristica generale tipica dei problemi di PL la cui regione ammissibile abbia almeno un vertice.

I materiali di supporto della lezione

D. Bertsimas e J.N. Tsitsiklis, Introduction to Linear Optimization, Belmont - Massachusetts (USA), Dynamic Ideas and Athena Scientific, 2008.

M. Fischetti, Lezioni di Ricerca Operativa, Padova, Edizioni Libreria Progetto Padova, 1999.

S. Martello, Fondamenti di Ricerca Operativa L-A, Bologna, Società Editrice Esculapio, 2004.

S. Martello, Ricerca Operativa LS, Bologna, Società Editrice Esculapio, 2004.

Dispense ed Appunti del Corso.

  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion