Algoritmo di eliminazione di Fourier Motzkin
Nella programmazione lineare l'algoritmo di eliminazione di Fourier Motzkin semplifica il modello, riducendo il numero di equazioni e di variabili tramite la proiezione o l'eliminazione.
Tramite l'algoritmo si arriva a una soluzione ammissibile del problema per eliminazione successiva.
Talvolta si arriva anche alla soluzione ottimale del problema senza bisogno di elaborare l'algoritmo del simplesso.
Nota. In generale, l'algoritmo di Fourier Motzkin si applica prima del simplesso per ridurre la complessità computazionale. Permette di trovare una soluzione ammissibile. A volte trova una soluzione ottimale o sub-ottimale accettabile senza calcolare il simplesso.
Caso 1
Se in un modello una variabile ha coefficiente non nullo in un'equazione, può essere proiettata sulle altre equazioni o disequazioni per sostituzione.
Esempio
Questo modello è composto da tre variabili e tre vincoli (un'equazione e due disequazioni).
$$ \begin{cases} 2x_1 + 4x_2 + x_3 \ge 3 \\ x1 + 3 x_3 = 2 \\ x_1 - x_2 - 2x_3 \le 10 \end{cases} $$
La variabile x1 compare nell'equazione con coefficiente non nullo.
Quindi, metto in evidenza la variabile x1 nell'equazione.
$$ \begin{cases} 2x_1 + 4x_2 + x_3 \ge 3 \\ x1 = 2 - 3 x_3 \\ x_1 - x_2 - 2x_3 \le 10 \end{cases} $$
Poi sostituisco la variabile x1 negli altri vincoli ed elimino sia l'equazione che x1 dal modello.
$$ \begin{cases} 2(2 - 3 x_3) + 4x_2 + x_3 \ge 3 \\ (2 - 3 x_3) - x_2 - 2x_3 \le 10 \end{cases} $$
$$ \begin{cases} 4 - 6 x_3 + 4x_2 + x_3 \ge 3 \\ 2 - 3 x_3 - x_2 - 2x_3 \le 10 \end{cases} $$
$$ \begin{cases} 4 - 5 x_3 + 4x_2 \ge 3 \\ 2 - 5 x_3 - x_2 \le 10 \end{cases} $$
Ora il sistema ha due disequazioni e due variabili ed è più semplice.
Caso 2
A volte due diseguaglianze con una stessa variabile possono essere unite tra loro.
Esempio
Questo modello è composto da due disequazioni e due variabili
$$ \begin{cases} 2 + x_3 - 3x_2 \ge 3 \\ 4 + x_3 - x_2 \le 10 \end{cases} $$
La variabile x3 ha coefficiente non nullo e compare nelle due disequazioni.
Posso metterela in evidenza
$$ \begin{cases} x_3 \ge 3 -2 + 3x_2 \\ x_3 \le 10 - 4 + x_2 \end{cases} $$
$$ \begin{cases} x_3 \ge 1 + 3x_2 \\ x_3 \le 6 + x_2 \end{cases} $$
Poi unire le due disequazioni
$$ \begin{cases} 1 + 3x_2 \le 6 + x_2 \end{cases} $$
$$ \begin{cases} 3x_2 - x_2 \le 6 - 1 \end{cases} $$
$$ \begin{cases} 2x_2 \le 5 \end{cases} $$
In questo modo ottengo un solo vincolo con una sola variabile.
Caso 3
Può capitare che due diseguaglianze esprimano lo stesso vincolo, quindi una diseguaglianza è ridondante e può essere eliminata.
Esempio
$$ \begin{cases} x_1 + 2x_2 \le 6 \\ x_1 + 4x_2 \ge 5 \\ x_2 \ge 0 \\ x_2 \le 5 \\ x_2 \le 10 \end{cases} $$
E' evidente che i vincoli x2≤5 e x2≤10 sono entrambi soddisfatti solo se il primo è soddisfatto.
Pertanto, la seconda diseguaglianza è ridondante e posso eliminarla.
$$ \begin{cases} x_1 + 2x_2 \le 6 \\ x_1 + 4x_2 \ge 5 \\ x_2 \ge 0 \\ x_2 \le 5 \end{cases} $$
In questo modo ottengo il range dei valori della variabile x2 ∈ [ 0, 5]
$$ x_2 \in [0,5] $$
A questo punto posso capire anche il range di variazione della variabile x1.
Sostituisco l'estremo inferiore di x2=0 nel modello.
$$ \begin{cases}x_1 + 2x_2 \le 6 \\ x_1 + 4x_2 \ge 5 \\ x_2 = 0 \end{cases} $$
$$ \begin{cases}x_1 + 2(0) \le 6 \\ x_1 + 4(0) \ge 5 \\ x_2 = 0 \end{cases} $$
$$ \begin{cases}x_1 \le 10 \\ x_1 \ge 5 \\ x_2 = 0 \end{cases} $$
Pertanto, se x2=0 la variabile x1 è compresa tra 5 e 10.
Questo mi permette di affermare che una soluzione ammissibile del problema è
$$ x =\begin{pmatrix} x_1 \\ x_2 \end{pmatrix} = \begin{pmatrix} 5 \\ 0 \end{pmatrix} $$
Un'altra soluzione ammissibile è
$$ x =\begin{pmatrix} x_1 \\ x_2 \end{pmatrix} = \begin{pmatrix} 6 \\ 0 \end{pmatrix} $$
Caso 4
Si trasforma la funzione obiettivo in un'equazione dei vincoli aggiungendo una variabile z. Poi si cerca il valore ottimo di z.
Esempio
Questo modello è composto da tre variabili e tre vincoli (un'equazione e due disequazioni).
$$ \min x_1 + x_2 \\ \begin{cases} 2x_1 + 2x_2 \ge 4 \\ x1 + x_2 \le 2 \\ x_1 + 3x_2 \le 4 \\ x_1, x_2 \ge 0 \end{cases} $$
Lo trasformo in
$$ \min z \\ \begin{cases} z = x_1 + x_2 \\ 2x_1 + 2x_2 \ge 4 \\ x1 + x_2 \le 2 \\ x_1 + 3x_2 \le 4 \\ x_1, x_2 \ge 0 \end{cases} $$
Metto in evidenza x1 nell'equazione
$$ \min z \\ \begin{cases} x_1 = z - x_2 \\ 2x_1 + 2x_2 \ge 4 \\ x1 + x_2 \le 2 \\ x_1 + 3x_2 \le 4 \\ x_1, x_2 \ge 0 \end{cases} $$
Poi sostituisco x1 con z-x2 nelle altre due disequazioni
$$ \min z \\ \begin{cases} x_1 = z - x_2 \\ 2(z - x_2) + 2x_2 \ge 4 \\ (z - x_2) + x_2 \le 2 \\ (z - x_2) + 3x_2 \le 4 \\ x_1, x_2 \ge 0 \end{cases} $$
$$ \min z \\ \begin{cases} x_1 = z - x_2 \\ 2z \ge 4 \\ z \le 2 \\ z + 2x_2 \le 4 \\ x_1, x_2 \ge 0 \end{cases} $$
$$ \min z \\ \begin{cases} x_1 = z - x_2 \\ z \ge 2 \\ z \le 2 \\ z + 2x_2 \le 4 \\ x_1, x_2 \ge 0 \end{cases} $$
Ne consegue che il valore ottimo di z è z*=2.
Sapendo che z=2 posso ricavare x2 nella terza disequazione.
$$ \min z \\ \begin{cases} x_1 = z - x_2 \\ z = 2 \\ 2 + 2x_2 \le 4 \\ x_1, x_2 \ge 0 \end{cases} $$
$$ \min z \\ \begin{cases} x_1 = z - x_2 \\ z = 2 \\ x_2 \le 1 \\ x_1, x_2 \ge 0 \end{cases} $$
Quindi la variabile x2 è minore o uguale a 1.
Sapendo che x2 è anche maggiore o uguale a zero, ne deduco che il range di variazione della variabile è x2 ∈ [0,1]
Unendo le informazioni z=2 e x2 ∈ [0,1] calcolo il range della variabile x1 nella prima disequazione.
$$ \min z \\ \begin{cases} x_1 = 2 - x_2 \\ z = 2 \\ x_2 \le 1 \\ x_1, x_2 \ge 0 \end{cases} $$
Quindi, x1=2 se x2=0 e x1=1 se x2=1.
In conclusione, due soluzioni del problema sono:
$$ x = \begin{pmatrix} x_1 \\ x_2 \end{pmatrix} = \begin{pmatrix} 1 \\ 0 \end{pmatrix} $$
$$ x = \begin{pmatrix} x_1 \\ x_2 \end{pmatrix} = \begin{pmatrix} 0 \\ 1 \end{pmatrix} $$
E così via
