Maggio 2017 Archive

Inizializzazione

Si comincia dall'origine: (0, 0) per un problema a due dimensioni.

Test di ottimalità

Ci si sposta verso un altro vertice per verificare se quello preso in considerazione non è ottimale.

Di solito si sceglie la direzione verso cui il miglioramento è più marcato, e ci si ferma arrivati al vertice determinato da uno dei vincoli.

Arrivati a un nuovo vertice, verificare se esiste uno dei vertici adiacenti migliore di quello attuale, e se c'è, andare in quella direzione.

Idee risolutive

1. Ridurre il numero di soluzioni candidate a essere ottimali da tutte quelle ammissibili ai soli vertici
2. Il simplesso è una procedura iterativa, cioè è ripetuta finché non si arriva alla soluzione ottimale:
   1. inizializzazione
   2. test di ottimalità
   3. fine o reiterazione
3. Se possibile, scegliere sempre l'origine come punto di partenza. Questo riduce il numero di calcoli.
4. Quando ci si muove, il metodo del simplesso lo fa sempre verso vertici adiacenti, sempre per ridurre il numero di calcoli. Il metodo del simplesso però non dice se il vertice adiacente è migliore di quello corrente, ma solo se il tasso di miglioramento in quella direzione è positivo o negativo (anche se questo equivale a dire se il vertice è migliore o no)
5. Dire che il tasso di miglioramento per tutti i vertici adiacenti è negativo equivale a dire che il vertice corrente è la soluzione ottimale.

Trattare i vincoli

Quando si trova un vincolo di disuguaglianza (per es. "il numero di xxx deve essere minore di 37), del tipo x₁ < 37, è necessario introdurre una variabile che rappresenta il delta tra il minimo di x₁ e il numero di riferimento (nell'esempio, 37).

Scrivendo quindi x₁ + x₂ = 37, x₂ > 0 si ottiene lo stesso risultato, ponendo x₂ compreso tra il valore minimo e 37. Per esempio, se il valore minimo è zero (es. non si può produrre una quantità negativa di beni), se x₁ è zero, x₂ è 37, se x₁ = 1, allora x₂ = 36 e così via. Se x₁ = 38, allora x₂ dovrebbe essere -1, che viola un vincolo dichiarato.

Queste variabili, introdotte per trasformare una disuguaglianza in un'uguaglianza con soli vincoli di non negatività, sono dette variabili slack.

Va da sé che se una variabile slack è a zero, ci stiamo trovando sulla frontiera per il vincolo che la usa.

BFS

Una BFS (basic feasible solution: soluzione di base ammissibile) è una soluzione di base in cui sono presenti le opportune variabili di slack e in cui i vertici sono ammissibili.

Una BFS è assimilabile a una matrice algebrica.

Per esempio, un problema del tipo:

• x₁ ≤ 4
• 2x₂ ≤ 12
• 3x₁ + 2x₂ ≤ 18
• x₁≥ 0, x₂ ≥ 0

si trasforma in una tabella, in cui tutte le variabili devono essere ≥ 0 (in rosa le variabili slack):

x1	x2	x3	x4	x5	C
x1		x3			4
	2x2		x4		12
3x1	2x2			x5	18

che si può trasformare in una matrice:

$\left(\begin{array}{cccccc}1& 0& 3& 0& 0& 4\\ 0& 2& 0& 1& 0& 12\\ 3& 2& 0& 0& 1& 18\end{array}\right)$

Ogni vincolo ha una variabile indicatrice, che - se posta a zero - assicura che l'equazione che definisce la frontiera per quel vincolo è soddisfatta dall'equazione.

La variabile posta a zero è una variabile non di base, mentre le altre sono dette variabili di base.

Una soluzione di base è ammissibile sse ogni variabile è maggiore o uguale a zero, altrimenti - il contrario di ammissibile - è detta degenere.

Il grado di libertà di una BFS è dato dal numero di variabili meno il numero di equazioni, quindi nell'esempio è 2.

Una soluzione di base ha le seguenti proprietà:

1. ogni variabile può essere di base o non di base
2. il numero delle variabili di base è uguale al numero di vincoli funzionali
3. le variabili non di base sono poste uguali a zero
4. i valori delle variabili di base sono le soluzioni del sistema di equazioni
5. se le variabili di base soddisfano i vincoli di non negatività, la soluzione di base è una BFS

Se il problema include una specifica per la massimizzazione, è necessario introdurlo alla stregua di un vincolo. Siccome è possibile scrivere il vincolo

Z = x₁ + x₂

anche come

Z - x₁+ x₂ = 0

è possibile introdurre questo come vincolo di uguaglianza e senza variabili slack.
P.E. se il problema è massimizzare 3x₁ + 5x_c, il prospetto diventa:

• Z = 3x₁ + 5x_c
• x₁ ≤ 4
• 2x₂ ≤ 12
• 3x₁ + 2x₂ ≤ 18
• x₁≥ 0, x₂ ≥ 0

si trasforma in una tabella:

Z	x1	x2	x3	x4	x5	C
Z	-3x1	-5x2				0
	x1		x3			4
		2x2		x4		12
	3x1	2x2			x5	18

che si può trasformare in una matrice:

$\left(\begin{array}{cccccc}-3& -5& 0& 0& 0& 0\\ 1& 0& 3& 0& 0& 4\\ 0& 2& 0& 1& 0& 12\\ 3& 2& 0& 0& 1& 18\end{array}\right)$

Applicazione del metodo

Inizializzazione

In base al concetto 3 (scegliere la base per iniziare il simplesso), si considerano variabili non di base x₁ e x₂.

I valori delle variabili sono, in questo caso:

x1	x2	x3	x4	x5
0	0	4	12	18

Criterio di arresto

Il valore di Z è in questo caso zero.
La soluzione non è ottimale, poiché i coefficienti di x₁ e x₂ sono ancora positivi.
In base all'idea risolutiva 5, sceglieremo il coefficiente più alto per spostarci in quella direzione.

x₂ diventa la variabile di base entrante.

In questo caso i criteri si modificano in modo da cercare di ottimizzare x₂:

x1	x2	x3	x4	x5	C
x1		x3			4
	2x2		x4		12
3x1	2x2			x5	18

Dal momento che x₁ = 0 ⇒ x₃ = 4
Inoltre bisogna scegliere i valori di x₃, x₄ e x₅ in modo che siano maggiori di zero e permettano il valore di x₂ più alto possibile in questo sistema:

• 2x₂ + x₄ = 12
• 3x₁ + 2x₂ + x₅ = 18

che corrisponde (x₁ = 0 ⇒ è rimosso dal sistema):

• x₄ = 12 - 2x₂
• x₅ = 18 - 2x₂

Dal momento che tutte le variabili hanno coefficiente positivo, la soluzione è ammissibile.

Vediamo di quanto può essere aumentato x₂

x₃ = 4, che è maggiore di zero e non vincola x₂

x₄ e x₅ devono essere maggiori di zero, ma il sistema deve essere visto dal "punto di vista" di x₂

• x₄ = 12 - 2x₂ ≥ 0 ⇒ x₂ ≤ 12/2 = 6
• x₅ = 18 - 2x₂≥ 0 ⇒ x₂ ≤ 18/2 = 9

Quindi aumentare x₂ fino a 6 rende x₄ = 0, mentre aumentare x₂ fino a 9 rende x₅ = 0 ma x₄ negativa.
x₂ può essere aumentato fino a 6.

Ora, posto x₂ = 6, la variabile con coefficiente zero è x₄, quindi si può costruire una nuova tabella con queste impostazioni. x₄ è ora una nuova variabile di base.

I coefficienti di x₂ sono -5, 0, 2, 2 e quelli di x₄ sono 0, 0, 1, 0

Z	x1	x2	x3	x4	x5	C
Z	-3x1	-5x2				0
	x1		x3			4
		2x2		x4		12
	3x1	2x2			x5	18

Utilizzando il vincolo in cui sono presenti sia x₂ sia x₄, è possibile "liberare dal coefficiente" la variabile non di base x₂ dividendo tutto per il suo reciproco:

2x₂ + x₄ = 12 ⇒ x₂ + ½x₄ = 12/2

Z	x1	x2	x3	x4	x5	C
Z	-3x1	-5x2				0
	x1		x3			4
		x2		½x4		6
	3x1	2x2			x5	18

Ora bisogna sostituire x₂ con un x₄ corrispondente: x₂ = -½x₄

Z	x1	x2	x3	x4	x5	C
Z	-3x1			$\frac{5}{2}{x}_4$		0
	x1		x3			4
		x2		½x4		6
	3x1			-x4	x5	18

Ora possiamo calcolare la nuova BFS considerando x₁ = 0 e x₄ = 0, che è (0, 6, 4, 0, 18).

Il valore costante (nell'esempio, 6, nel riquadro rosso) va moltiplicato per il coefficiente di x₂ e sottratto da C.

Nella prima riga, il coefficiente di x₂ è -5, C = 6 e quindi dalla prima riga va tolto -30:

Z	x1	x2	x3	x4	x5	C
Z	-3x1			$\frac{5}{2}{x}_4$		-(-30)
	x1		x3			4
		x2		½x4		6
	3x1			-x4	x5	18

Nell'ultima riga, il coefficiente è 2, C è 6 e quindi va tolto 12 dal valore corrente:

Z	x1	x2	x3	x4	x5	C
Z	-3x1			$\frac{5}{2}{x}_4$		-(-30)
	x1		x3			4
		x2		½x4		6
	3x1			-x4	x5	18-(+12)

Il risultato è la nuova BFS:

Z	x1	x2	x3	x4	x5	C
Z	-3x1			$\frac{5}{2}{x}_4$		30
	x1		x3			4
		x2		½x4		6
	3x1			-x4	x5	6

La nuova BFS è quindi (0, 6, 4, 0, 6) e Z = 30.

Z = 30 + 3x₁

$-\frac{5}{4}{x}_4$

poiché x₁ ha coefficiente positivo, il test di ottimalità non è superato, ed è necessaria una seconda iterazione.

Seconda iterazione

Dal momento che x₁ ha un coefficiente positivo e

$-\frac{5}{4}{x}_4$

no, consideriamo di quanto può essere incrementato x₁ ponendo x₄ a zero.

• x₃ =  4 - x₁, che significa che x₁ non può essere maggiore di 4
• x₂ = 6, che significa che non pone limiti superiori a x₁
• x₅ = 6 - 3x₁, che significa che x₁ non può essere maggiore di 6/3 => 2

Da questo test otteniamo che x₅ è la variabile uscente. x₁ vale quindi

Modifichiamo la riga in cui è presente x₅ dividendo tutta la riga per il coefficiente della variabile uscente x₁

Z	x1	x2	x3	x4	x5	C
Z	-3x1			$\frac{5}{2}{x}_4$		30
	x1		x3			4
		x2		½x4		6
	x1			-⅓x4	⅓x5	⅓6 = 2

Sostituiamo x₁ con ⅓x₄

Z	x1	x2	x3	x4	x5	C
Z				$\frac{5}{2}{x}_4+\left(-3\right)·\frac{1}{3}{x}_4$		30
			x3	-⅓x4		4
		x2		½x4		6
	x1			-⅓x4	⅓x5	2

Inoltre ovunque sia stata fatta la sostituzione bisogna togliere 2 per il coefficiente di x_1.

Il risultato è il seguente:

Z	x1	x2	x3	x4	x5	C
Z				$\frac{5}{2}{x}_4+\left(-3\right)·\frac{1}{3}{x}_4$		30 - (-3*2)
			x3	-⅓x4		4 - (1*2)
		x2		½x4		6
	x1			-⅓x4	⅓x5	2

Ora:

$Z=\mathrm{36}-\frac{3}{2}{x}_4-x_5$

Tutti i coefficienti sono negativi, quindi la BFS migliore è questa, in cui x₁ = 2 e x₂ = 6.

 

 

* per "vertice ammissibile" si intende un vertice che non sia su un segmento che collega soluzioni ammissibili. Quando un vertice riporta un asterisco, si intende vertice ammissibile.

In programmazione lineare, i vertici hanno le seguenti proprietà:

1. Se esiste una sola soluzione ottima, questa sarà un vertice. Se esistono più soluzioni, almeno due di queste sono vertici* adiacenti.
2. Il numero di vertici ammissibili è finito.
3. Se un vertice ammissibile non ha vertici adiacenti migliori, allora non ci sono vertici migliori. Quindi se il problema ha una soluzione ottima, questo vertice è la soluzione ottima.

La 1. si dimostra per assurdo. Se esiste una soluzione ottima che non è un vertice, significa che la soluzione è compresa tra due vertici*, ma in questo caso, poiché i vertici* sono ammissibili, anche essi sono soluzioni ammissibili, il che contraddice il fatto che la soluzione sia unica.

La 2. è dimostrabile perché il conteggio dei vertici è dato da una formula che restituisce solo risultati finiti, che è (n = numero di equazioni, m = numero di vincoli):

$\left(\genfrac{}{}{0ex}{}{n+m}{n}\right)$

La 3. è una diretta conseguenza della convessità del problema. Se il problema è convesso, ogni spostamento verso un vertice "migliore" è una garanzia che anche il risultato sarà migliore; viceversa se il problema non fosse convesso, sarebbe necessario calcolare ogni singolo punto e cercare per tentativi il risultato migliore.