Vincoli per problemi di PL

  • Percentuale di composizione: x1 + x2 + ... + xn = 1
  • Costo fisso aggiuntivo: creo una variabile yi = 1 se xi > 0, 0 altrimenti. Devo dichiarare che y ≥ ∑x / M, con M ≫ 0
  • Almeno uno: dichiaro due variabili α e β che valgono o zero o uno e la cui somma è uno. In alternativa, dichiaro una variabile α e imposto x1> αM e x2 > (1-α)M, con M ≫ 0
  • Uno e uno solo: come almeno uno, ma dichiaro anche che α + β = 1
  • Esattamente tre: come uno e uno solo, ma dichiaro una yi = 1 se xi > 0, 0 altrimenti. Devo dichiarare che y ≥ ∑x / M, con M ≫ 0. A questo punto, la somma di tutti gli y è 3
  • Come minimo 5: 5 - x ≤ αM con M ≫ 0
  • Al massimo 8: x - 8 ≤ αM con M ≫ 0

Interpretare un problema di PL

I problemi di PL sono espressi nella seguente forma:

  • max cTx
  • soggetto a Ax = b
  • x ≥ 0

dove A ∈ ℝn x m, c ∈ ℝn, b ∈ ℝm sono i dati del problema e x ∈ ℝn è il vettore delle variabili.

Cosa significa tutto questo?

n rappresenta il numero di dimensioni del problema

m rappresenta il numero di vincoli del problema

c è un coefficiente a n dimensioni, cT è la notazione usata nella definizione del problema (che differenza c'è?)

A è l'insieme dei coefficienti dei vincoli per ciascuna dimensione per ciascun vincolo.

 

Prima applicazione del metodo del simplesso

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 x1 < 37, è necessario introdurre una variabile che rappresenta il delta tra il minimo di x1 e il numero di riferimento (nell'esempio, 37).

Scrivendo quindi x1 + x2 = 37, x2 > 0 si ottiene lo stesso risultato, ponendo x2 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 x1 è zero, x2 è 37, se x1 = 1, allora x2 = 36 e così via. Se x1 = 38, allora x2 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:

  • x1 ≤ 4
  • 2x2 ≤ 12
  • 3x1 + 2x2 ≤ 18
  • x1≥ 0, x2 ≥ 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:

10300402010123200118

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 = x1 + x2

anche come

Z - x1+ x2 = 0

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

  • Z = 3x1 + 5xc
  • x1 ≤ 4
  • 2x2 ≤ 12
  • 3x1 + 2x2 ≤ 18
  • x1≥ 0, x2 ≥ 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:

-3-5000010300402010123200118

Applicazione del metodo

Inizializzazione

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

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 x1 e x2 sono ancora positivi.
In base all'idea risolutiva 5, sceglieremo il coefficiente più alto per spostarci in quella direzione.

x2 diventa la variabile di base entrante.

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

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

Dal momento che x1 = 0 ⇒ x3 = 4
Inoltre bisogna scegliere i valori di x3, x4 e x5 in modo che siano maggiori di zero e permettano il valore di x2 più alto possibile in questo sistema:

  • 2x2 + x4 = 12
  • 3x1 + 2x2 + x5 = 18

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

  • x4 = 12 - 2x2
  • x5 = 18 - 2x2

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

Vediamo di quanto può essere aumentato x2

x3 = 4, che è maggiore di zero e non vincola x2

x4 e x5 devono essere maggiori di zero, ma il sistema deve essere visto dal "punto di vista" di x2

  • x4 = 12 - 2x2 ≥ 0 ⇒ x2 ≤ 12/2 = 6
  • x5 = 18 - 2x2≥ 0 ⇒ x2 ≤ 18/2 = 9

Quindi aumentare x2 fino a 6 rende x4 = 0, mentre aumentare x2 fino a 9 rende x5 = 0 ma x4 negativa.
x2 può essere aumentato fino a 6.

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

I coefficienti di x2 sono -5, 0, 2, 2 e quelli di x4 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 x2 sia x4, è possibile "liberare dal coefficiente" la variabile non di base x2 dividendo tutto per il suo reciproco:

2x2 + x4 = 12 ⇒ x2 + ½x4 = 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 x2 con un x4 corrispondente: x2 = -½x4

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

Ora possiamo calcolare la nuova BFS considerando x1 = 0 e x4 = 0, che è (0, 6, 4, 0, 18).

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

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

Z x1 x2 x3 x4 x5 C
Z -3x1 52x4 -(-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 52x4 -(-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 52x4 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 + 3x1

-54x4

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

Seconda iterazione

Dal momento che x1 ha un coefficiente positivo e

-54x4

no, consideriamo di quanto può essere incrementato x1 ponendo x4 a zero.

  • x3 =  4 - x1, che significa che x1 non può essere maggiore di 4
  • x2 = 6, che significa che non pone limiti superiori a x1
  • x5 = 6 - 3x1, che significa che x1 non può essere maggiore di 6/3 => 2

Da questo test otteniamo che x5 è la variabile uscente. x1 vale quindi

Modifichiamo la riga in cui è presente x5 dividendo tutta la riga per il coefficiente della variabile uscente x1

Z x1 x2 x3 x4 x5 C
Z -3x1 52x4 30
x1 x3 4
x2 ½x4 6
x1 -⅓x4 ⅓x5 ⅓6 = 2

Sostituiamo x1 con ⅓x4

Z x1 x2 x3 x4 x5 C
Z 52x4+-3·13x4 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 x1.

Il risultato è il seguente:

Z x1 x2 x3 x4 x5 C
Z 52x4+-3·13x4 30 - (-3*2)
x3 -⅓x4 4 - (1*2)
x2 ½x4 6
x1 -⅓x4 ⅓x5 2

Ora:

Z=36-32x4-x5

Tutti i coefficienti sono negativi, quindi la BFS migliore è questa, in cui x1 = 2 e x2 = 6.

 

 

Proprietà dei vertici

* 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):

(n+mn)

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.