Home

Federica EU

1/11

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 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, 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:

Il problema ammette un’unica soluzione ottima.
Il problema ammette soluzioni multiple e l’insieme delle soluzioni ottime può essere limitato o illimitato.
Il costo ottimo è $-\infty$ e nessuna soluzione ammissibile è ottima.
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.