PROGRAMMAZIONE LINEARE

PROBLEMA GENERALE:

max   (1

FORMA STANDARD

min c^Tx

Ax = b   (2

x

Ogni problema di PL si può mettere in questa forma con semplici artifici, come sostituire max c^Tx con min (- c^Tx) oppure introducendo variabili ausiliarie per trasformare vincoli di disuguaglianza in vincoli di uguaglianza, dato che a_i x + y_i = b_i è equivalente a a_i x b_i purché y_i

1-CASI SPECIALI RISOLUBILI SEMPLICEMENTE

a)       problema dello Zaino continuo

max   c^Tx

a^Tx b

x_j j = 1,2, .. ,n

Ordina gli n oggetti secondo rapporti c_j/a_j non-crescenti

Mettili nello zaino in questo ordine prendendo sempre il massimo possibile di ogni oggetto finché la capacità b è esaurita

b)      problemi di PL con due sole variabili possono essere risolti per via grafica

esempio: max 2x₁ + x₂

-x₁ + 4x₂

x₁ + x₂

3x₁ + x₂

x₁ , x₂

2-CASI PARTICOLARI

Problemi di PL inammissibili, cioè con regione di ammissibilità vuota, X = F

esempio: max

Problemi di PL illimitati, cioè con funzione obbiettivo

che può tendere a + per problemi di max o a - per quelli di min

esempio:     max

Problemi di PL con molti punti di ottimo alternativi:

ciò accade quando il vettore dei coefficienti della

funzione obbiettivo è un multiplo positivo di uno o

più vettori di coefficienti dei vincoli

esempio: max

3-OPERAZIONI ELEMENTARI SULLE RIGHE

moltiplicare una riga per una costante

aggiungere una riga ad un'altra o alla funzione

obbiettivo

Queste operazioni non cambiano l'insieme delle soluzioni ammissibili di (2) dato che tutti i vincoli sono sotto forma di eguaglianza. Con una serie di operazioni elementari di questo tipo ogni problema di PL espresso nella forma (2) può essere portato in una forma in cui c'è una sola variabile isolata per vincolo con coefficiente 1 e costo 0.

Esempio

min z(x) = (1,1,-8,6)x = x₁ + x₂ - 8x₃ + 6x₄

(2,1,-l4,10)x = 16

(1,1,-l1,7)x = 10

x

Sottraendo la seconda equazione di vincolo alla prima e alla funzione obbiettivo si ha

min z(x) = (0,0,3,-l) x + 10

(1,0,-3,3) x = 6

(1,1,-l1,7) x = 10

x

sottraendo ora il primo vincolo dal secondo si ottiene la forma richiesta

min z(x) = 0x₁ + 0x₂ + 3x₃ - x₄

x₁ - 3x₃ + 3x₄ = 6

x₂ - 8x₃ + 4x₄ = 4

x_i i = 1, . , 4

x = (6,4,0,0) è una soluzione di base ammissibile di costo z = 10.

4-METODO DEL SIMPLESSO

Facciamo riferimento al problema di PL in forma standard.

ASSUNZIONE 1: A è di rango pieno (= numero righe m)

DEFINIZIONE: si dice base di A una collezione di m colonne linearmente indipendenti cui corrisponde una matrice mxm non singolare B.

Riordinando opportunamente le variabili, poniamo A = [B N] e x^T= [x^T_B x^T_N]. Allora

Bx_B+ Nx_N = b

e

x_B = B^-lb - B^-lNx_N

soddisfa ai vincoli Ax = b.

DEFINIZIONE: ponendo x_N= 0 si ha la soluzione di base

x_B = B^-lb , x_N= 0

DEFINIZIONE: una soluzione di base si dice ammissibile (SBA) se x_B

ASSUNZIONE 2: la regione di ammissibilità

F = sia non-vuota.

ASSUNZIONE 3: l'insieme dei valori reali della funzione obbiettivo c^Tx sia limitato in F.

Geometricamente l'insieme di vincoli di un problema di PL definisce un politopo e ogni punto di esso può esprimersi come combinazione convessa dei suoi vertici. Condizione necessaria e sufficiente perché x sia una SBA è che x sia un vertice di tale politopo.

Un problema di PL potrebbe essere risolto in un numero finito (ma molto grande) di passi considerando a turno tutti i vertici del corrispondente politopo.

L'algoritmo del simplesso (Dantzig, 1947) è quasi sempre molto più efficiente dato che esplora solo una piccola parte dei vertici (ovvero di SBA)

DEFINIZIONE: due SBA distinte si dicono adiacenti se si possono ottenere l'una dall'altra scambiando due colonne. Ciò corrisponde geometricamente a passare da un vertice ad uno adiacente nel politopo.

IDEA DI FONDO DELL'ALGORITMO: data una SBA di partenza, passare ad un'altra adiacente di costo minore fino a trovare quella ottima.

Si sceglie di solito tra tutti gli scambi possibili quello più vantaggioso dal punto di vista della funzione obbiettivo.

LEMMA 1: una SBA è di costo minimo se i costi ridotti

c_N = c_N - c_BB^-lN

sono tutti non-negativi.

LEMMA 2: se in corrispondenza di una SBA esiste una variabile non di base x_s con costo ridotto negativo tale che la corrispondente colonna [a_is] della matrice B^-lA abbia tutti i suoi elementi non-positivi, allora la funzione obbiettivo è illimitata (si viola l'assunzione 3).

LEMMA 3: se in corrispondenza di una SBA esiste una variabile non di base x_s con costo ridotto negativo e per almeno un valore dell'indice i, a_is>0, allora si può costruire una nuova SBA di costo inferiore.

Algoritmo del Simplesso (semplificato):

nopt:= V ; limit := V ;

while nopt limit do

if c_j j then nopt := F else

begin

4. scegli j tale che c_j<0 ;

if a_ij i then limit := F else

begin

6. q := min_i = b_r/a_rj ;

s := j ; scambia colonne s e r

end

end

TEOREMA: se non si presentano SBA degeneri, (cioè con qualche variabile di base di valore nullo) il metodo del simplesso termina in un numero finito di iterazioni.

METODO DI BLAND

Quando si incontra una base degenere si procede con le varianti seguenti.

Al passo 4:

s := min

al passo 6:

r := min }

NOTA: tali scelte comportano una minore efficienza e vanno eseguite solo in caso di SBA degenere.

RICERCA DI UNA SBA (metodo delle due fasi)

FASE 1 - risolvere (e = vettore di tutti 1, I matrice identità):

z = min

se z=0 si ha una SBA da cui partire con la

FASE 2 - applicare il metodo del simplesso al problema originale.

5-DUALITA'

Problema primale (P): min

Problema duale (D):   max

TEOREMA (della dualità debole) : per qualunque coppia di vettori x,u ammissibili rispettivamente per P e per D, c^Tx ub.

COROLLARIO: se x* e u* sono ammissibili e avviene che c^Tx* = u*b, allora x* è ottimo per P e u* è ottimo per D.

TEOREMA (della dualità forte): se le rispettive regioni di ammissibilità sono non-vuote, esistono sempre due vettori x* e u* tali che c^Tx* = u*b.

TEOREMA (degli scarti complementari): due vettori x ed u rispettivamente ammissibili per P e per D sono ottimi se e solo se

u(Ax - b) = 0 e (c - uA)x = 0.

DUALITA' IN GENERALE

min c^Tx max ub

a_ix b_i   u_i

a_ix b_i   u_i

a_ix = b_i   u_i non vincolata

x_j uA_j c_j

x_j uA_j c_j

x_j non vincolata  uA_j = c_j

CASI POSSIBILI (X) E NO

Duale  

ottimo illimitato regione

finito   vuota

Primale

ottimo X

finito

illimitato X

regione X X

vuota

6-MATRICI TOTALMENTE UNIMODULARI

In alcuni casi di PL (es. flusso di costo minimo) le condizioni di integralità sono superflue, cioè la soluzione risulta intera senza doverlo imporre. Un caso importante di PL per cui ciò accade è illustrato qui.

Min

dove assumiamo che A e b siano rispettivamente un matrice e un vettore interi. La soluzione x* ottenuta ignorando il vincolo di integralità ad esempio col metodo del Simplesso assegna i valori B^-lb alle variabili in base e 0 alle altre e avrà quindi componenti frazionarie solo se ne ha B^-lb. Ciò può accadere solo se det(B) è diverso da +1 o -l (non potendo essere nullo, dato che B è per ipotesi non-singolare).

N.B. questa condizione non è necessaria, ma per ogni matrice A contenente una base B con determinante diverso da 0, +1, o -l esiste un problema di PL con b intero e x* frazionario.

DEF. Una matrice mxn A con m n si dice unimodulare se ogni sottomatrice mxm B ha determinante di valore 0, +1, o -l.

TEOREMA Sia A unimodulare e b intero. Allora il poliedro P = ha solo vertici interi.

(dimostrazione ovvia, dato che per ogni vertice x di P esiste una base B tale che x_B = B^-lb e x_N = 0.)

Si consideri adesso:

Min

in forma standard:

Min

Per ogni base B di A' = [A,-I] possiamo scrivere permutando opportunamente righe e colonne

B = -I' F

O Q

dove le prime colonne sono quelle nella base B provenienti da -I, mentre le successive sono colonne di A.

Abbiamo allora che det(B) det(Q) e quindi A' sarà unimodulare se e solo se det(Q) può prendere solo valori 1, 0 e -l per ogni sottomatrice quadrata Q di A.

DEF. Una matrice m x n intera A si deice totalmente unimodulare (totally unimodular matrix, TUM) se il determinante di ogni sottomatrice quadrata Q di A può prendere solo valori 1, 0 e -l.

TEOREMA: Se A è TUM e b è intero, il poliedro

P =

ha solo vertici a coordinate intere.

DIM. I vertici di P sono quelli del poliedro P' ottenuto introducendo le variabili ausiliarie e il risultato segue dal Teorema precedente applicato a P'.

Come fare a sapere se una matrice A è o no TUM ?

Enumerare tutte le sottomatrici quadrate richiede evidentemente troppo tempo. Ci sono metodi polinomiali, ma molto sofisticati (derivanti dai risultati di P. Seymour). Una condizione sufficiente e di larga applicabilità è la seguente.

TEOREMA: Sia A una matrice con elementi 1, 0 e -l. A è TUM se

ogni colonna ha al massimo due elementi diversi da 0;

esiste una partizione delle righe di A in due gruppi tali che ogni colonna con due elementi diversi da 0 li colloca su righe appartenenti a gruppi diversi se e solo se i due elementi hanno lo stesso segno.

7-SCARTI COMPLEMENTARI E SIMPLESSO

Il metodo del Simplesso risolve il problema primale

Min

Sappiamo che la soluzione ottima x*,u* si ha quando:

Ax* = b , x* (ammissibilità primale)

c u*A  (ammissibilità duale)

(c - u*A)x* = 0 (ortogonalità)

Ad ogni iterazione il metodo del Simplesso calcola:

• x' = (B^-lb | 0)

• u' = c B^-l

• c' = c - u'A

Quando c' 0 il metodo ha trovato l'ottimo.

Quindi il metodo del Simplesso (primale) soddisfa ad ogni iterazione alle condizioni (1) e (3), mentre la condizione (2) è soddisfatta solo alla fine.

SIMPLESSO DUALE

In questa versione del metodo ad ogni iterazione si soddisfa alle relazioni (2) e (3), mentre la relazione (1) viene soddisfatta solo alla fine. Cioè si soddisfa sempre all'ammissibilità duale e all'ortogonalità, mentre l'ammissibilità primale viene soddisfatta dopo: da qui il nome.

Geometricamente ad ogni iterazione x' è più che ottimo ma è inammissibile e si avvicina sempre più alla regione di ammissibilità.

ESEMPIO

Min z = 3x₁ + 4x₂ + 5x₃

2x₁ + 2x₂ + x₃

x₁ + 2x₂ + 3x₃

x₁, x₂, x₃

In forma standard

Min z = 3x₁ + 4x₂ + 5x₃

-2x₁ - 2x₂ - x₃ + x₄ = -6

-x₁ - 2x₂ - 3x₃ + x₅ = -5

x₁, x₂, x₃

TABLEAU INIZIALE

x₁ x₂ x₃ x₄ x₅

__________ ______ ____ _______

-z 0 3 4 5 0 0

x₄ -6 -2 -2 -l 1 0

x₅ -5 -l -2 -3 0 1

NUOVO TABLEAU

x₁ x₂ x₃ x₄ x₅

__________ ______ ____ _______

-z -9 0 1 7/2 3/2 0

x₁ 3 1 1 1/2 -l/2 0

x₅ -2 0 -l -5/2 -l/2 1

NUOVO TABLEAU

x₁ x₂ x₃ x₄ x₅

_{__________ ______ ____ _____ _______ ______ ____________}

-z -l1 0 0 1 1 1

x₁ 1 1 0 -2 -l 1

x₂ 2 0 1 5/2 1/2 -l

Valori positivi delle variabili in base e quindi siamo nel punto ottimo.

SIMPLESSO DUALE

Passo 1 se x'_i i    allora STOP /ottimo/

Passo 2 altrimenti seleziona una variabile di base

x'_r < 0 /ad esempio quella più negativa/

Passo 3 se a'_rj 0 , j = m+1, . , n allora STOP

/non esiste soluzione primale ammissibile/

Passo 4 altrimenti trova una variabile non di base

x_s tale che

c'_s/|a'_rs| = min

Passo 5   fare PIVOT su a'_rs trovando una nuova base duale ammissibile di costo maggiore

Vai al Passo 1

IMPORTANTE: il Simplesso duale si presta molto bene ad introdurre i vincoli (e relative variabili ausiliarie) uno alla volta, dato che non cambia la situazione per quanto riguarda l' ammissibilità duale e l' ortogonalità.

8-SIMPLESSO PRIMALE E SIMPLESSO DUALE

Simplesso Primale

Step 1 - risolvi il sistema yB = c_B (calcolando B^-l) ;

Step 2 - (scelta della variabile entrante)

cerca una colonna a_j di N tale che ya_j > c_j : if una colonna siffatta non esiste then STOP (la soluzione corrente è ottima) ;

Step 3 - calcola d = B^-la_j ;

Step 4 - trova il valore massimo di q tale che x_B-qd

mantenendo Ax = b ;

if tale valore non esiste then STOP (problema illimitato) else almeno una componente di x_B-qd vale zero e la variabile corrispondente lascia la base ;

Step 5 - poni uguale a q il valore della variabile entrante e il

valore delle altre variabili uguale a quelli del vettore x_B-qd ;

sostituisci a_j in B alla colonna corrispondente alla variabile che lascia la base ;

go to STEP 1

N.B. lo Step 2 è formulato per un problema di minimo; se si tratta di un problema di massimo bisogna cercare una colonna tale che ya_j < c_j !

Il metodo del simplesso come visto fino a qui viene detto primale per le ragioni seguenti.

Per il problema in forma standard

min

un punto di ottimo x*,u* viene raggiunto quando

Ax* = b , x* ammissibilità primale

c u*A  ammissibilità duale

(c-u*A)x* = 0 ortogonalità

Ad ogni iterazione il metodo del simplesso primale calcola una SBA x' = (B^-lb, 0) 0 con variabili duali u' = c B^-l e costi ridotti c' = c-u'A. Il metodo si arresta quando i costi ridotti sono tutti non-negativi.

Quindi il simplesso primale soddisfa a (1) e (3) ad ogni iterazione mentre la (2) è soddisfatta solo alla fine.

Se ad ogni iterazione si soddisfa invece alle (2) e (3) arrivando a soddisfare alla (1) solo alla fine, si ha il cosiddetto Simplesso Duale.

N.B. Il metodo del simplesso duale NON è il simplesso applicato al problema duale !

Simplesso Duale

Step 1 - if tutte le componenti di b' = B^-lb sono non

-negative then STOP (soluzione ottima) else seleziona una variabile di base x_r tale che b'_r sia <0 (ad esempio b'_r = min ;

Step 2 - if a'_rj 0 , j = m+1, . ,n then STOP (non esistono

soluzioni ammissibili primali) else trova una variabile non in base x_s tale che

c'_s/|a'_rs| = min ;

Step 3 - fai PIVOT su a'_rs trovando una nuova soluzione di

base duale ammissibile di costo maggiore ;

go to STEP 1

Geometricamente nel simplesso primale ad ogni iterazione x' fornisce una soluzione ammissibile sub-ottima, mentre nel simplesso duale x' resta non ammissibile e super-ottimo fino alla fine, avvicinandosi ad ogni iterazione alla regione di ammissibilità.