ePerTutti


Appunti, Tesina di, appunto informatica

Ethernet

Ethernet


Scrivere la parola
Seleziona una categoria

PROGRAMMAZIONE LINEARE

PROBLEMA GENERALE:

max                       (1

FORMA STANDARD


min cTx


Ax = b                           (2


x


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




1-CASI SPECIALI RISOLUBILI SEMPLICEMENTE


a)       problema dello Zaino continuo


max           cTx


aTx b            


xj j = 1,2, …. ,n


Ordina gli n oggetti secondo rapporti cj/aj 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 2x1 + x2


-x1 + 4x2


x1 + x2


3x1 + x2


x1 , x2


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 = x1 + x2 – 8x3 + 6x4


(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) = 0x1 + 0x2 + 3x3 – x4


x1 – 3x3 + 3x4 = 6


x2 – 8x3 + 4x4 = 4


xi 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 xT= [xTB xTN]. Allora


BxB+ NxN = b

e

xB = B-lb – B-lNxN


soddisfa ai vincoli Ax = b.


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

xB = B-lb , xN= 0


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


ASSUNZIONE 2: la regione di ammissibilità

F = sia non-vuota.


ASSUNZIONE 3: l’insieme dei valori reali della funzione obbiettivo cTx 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

cN = cN – cBB-lN


sono tutti non-negativi.


LEMMA 2: se in corrispondenza di una SBA esiste una variabile non di base xs con costo ridotto negativo tale che la corrispondente colonna [ais] 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 xs con costo ridotto negativo e per almeno un valore dell’indice i, ais>0, allora si può costruire una nuova SBA di costo inferiore.


Algoritmo del Simplesso (semplificato):


nopt:= V ; limit := V ;

while nopt limit do

if cj j then nopt := F else

begin

4. scegli j tale che cj<0 ;

if aij i then limit := F else

begin

6. q := mini = br/arj ;

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, cTx ub.


COROLLARIO: se x* e u* sono ammissibili e avviene che cTx* = 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 cTx* = 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 cTx max ub

aix bi                           ui

aix bi                           ui

aix = bi               ui non vincolata

xj uAj cj

xj uAj cj

xj non vincolata                                  uAj = cj


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 xB = B-lb e xN = 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 = 3x1 + 4x2 + 5x3


2x1 + 2x2 + x3


x1 + 2x2 + 3x3


x1, x2, x3


In forma standard


Min z = 3x1 + 4x2 + 5x3


-2x1 - 2x2 - x3 + x4 = -6


-x1 - 2x2 - 3x3 + x5 = -5


x1, x2, x3

TABLEAU INIZIALE


x1 x2 x3 x4 x5



__________ ______ ____ _______

-z 0 3 4 5 0 0

x4 -6 -2 -2 -l 1 0

x5 -5 -l -2 -3 0 1


NUOVO TABLEAU


x1 x2 x3 x4 x5

__________ ______ ____ _______

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

x1 3 1 1 1/2 -l/2 0

x5 -2 0 -l -5/2 -l/2 1



NUOVO TABLEAU


x1 x2 x3 x4 x5

__________ ______ ____ _____ _______ ______ ____________

-z -l1 0 0 1 1 1

x1 1 1 0 -2 -l 1

x2 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

xs 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 = cB (calcolando B-l) ;

Step 2 – (scelta della variabile entrante)

cerca una colonna aj di N tale che yaj > cj : if una colonna siffatta non esiste then STOP (la soluzione corrente è ottima) ;

Step 3 – calcola d = B-laj ;

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

mantenendo Ax = b ;

if tale valore non esiste then STOP (problema illimitato) else almeno una componente di xB-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 xB-qd ;

sostituisci aj 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 yaj < cj !


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 xr 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 xs 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à.








Privacy

© ePerTutti.com : tutti i diritti riservati
:::::
Condizioni Generali - Invia - Contatta