Metodi duali del simplesso -...

Politecnico di Torino Ricerca Operativa

R. Tadei 4. Metodi duali del simplesso1

4. METODI DUALI DELSIMPLESSO



Una piccola introduzione



METODI DUALI DEL SIMPLESSO

L’obiettivo del capitolo è illustrare e giustificare i metodi dualidel simplesso. Entrambi i metodi (simplesso duale e simplessoprimale-duale), partono da una soluzione non ammissibileprimale e cercano iterativamente una soluzione ammissibile. Sequesta esiste sarà anche ottima. I due metodi sono applicabilise la soluzione non ammissibile primale è ammissibile duale esono soddisfatte le condizioni di complementarietà dellesoluzioni ottime primali e duali cioè ( AT λλ’ - c )T x’ = 0 e ( A x’ -b )T λλ’ = 0.

Intuitivamente ciò significa che la soluzione di partenza è“potenzialmente ottima” ma non è ottima per il primale inquanto non ammissibile. Si tratta quindi di mantenere la“potenziale ottimalità” (cioè non perdere l’ammissibilità duale ela validità delle condizioni di complementarietà) avvicinandosiall’ammissibilità primale.



Tipiche situazioni in cui si applicano i metodi duali sono larisoluzione di un problema di programmazione lineare contermini noti diversi e la risoluzione di un problema diprogrammazione lineare dopo aver reintrodotto dei vincoliprecedentemente omessi.

Il primo caso, tipico nell’analisi di sensibilità delle soluzioniottime e nell’analisi parametrica, si incontra quando, dopo averrisolto un problema di programmazione lineare trovando labase ottima (B), si utilizza un altro vettore dei termini noti (b')che rende qualche elemento della soluzione ottima negativo.(Ricordiamo che xB = B-1 b' )

Il secondo caso, tipico quando si applica il rilassamento deivincoli, si incontra quando, dopo aver risolto un problema diprogrammazione lineare trovando la soluzione ottima, siintroducono dei vincoli in precedenza omessi, che portano allaviolazione dell’ammissibilità primale.



Esponendo i metodi vedremo :

· la giustificazione teorica dell’algoritmo del simplesso duale

· l’algoritmo del simplesso duale

· la giustificazione teorica dell’algoritmo del simplesso primaleduale

· l’algoritmo del simplesso primale duale

· un esempio di applicazione dell’algoritmo del simplessoprimale duale



Applicabilità degli algoritmi :

I metodi duali del simplesso partono da una soluzione nonammissibile primale.

I due algoritmi sono applicabili se :

• la soluzione non ammissibile primale è ammissibile duale

• sono soddisfatte le condizioni di complementarietà dellesoluzioni ottime primali e duali, cioè

( AT λλ’ - c )T x’ == 0

e

( A x’ - b )T λλ’ == 0

Gli algoritmi cercano iterativamente una soluzione ammissibileprimale che, se esiste, sarà ottima.



4.1 SIMPLESSO DUALE



Giustificazione dell’algoritmo :

Situazione di partenza:Nel tableau finale del simplesso alcuni termini noti variano ilsegno (può derivare da un cambiamento di b) cioè ∃∃ j tale chexj < 0 , questo rende la soluzione ottima precentemente trovatanon ammissibile.

è associata una soluzione ammissibile per il duale, e lecondizioni di complementarietà sono rispettate grazie al valoredegli rj (vedi passo 0 dell’algoritmo esposto più avanti).

rj ≥≥ 0

> 0

< 0> 0

> 0> 0



Idea dell’algoritmo :

Si lavora sul tableau finale primale, con operazioni di pivot,mantenendo l'ottimalità primale data dall'ultima riga cioè ∀∀j rj≥≥0e muovendosi verso l'ammissibilità primale data dall’ultimacolonna, per avere bi≥≥0 ∀ ∀ i. Vista nell’ottica del problema dualesignifica mantenere l'ammissibilità duale muovendosi versol'ottimalità duale.

Criterio d’uscita :

Si sceglie xp che deve uscire dalla base tra quelle nonammissibili cioè tra quelle che assumono un valore negativo(Ricordiamo che xp==bp)

Es. p tale che bp = = yp0 = = min { yi0 tale che yp0 < < 0 }i



Test sull’esistenza della s.a. primale :

Essendo in ogni caso xp = = yp0 − Σ − Σ ypj xi

(dove yp0 = = bp < 0 per come si è scelto xp)

volendo far entrare in base una xj devo avere ypj < 0

perchè la soluzione divenga ammissibile (cioè con xj >0).

In sintesi :

Se ∀ ∀ j∈∈[m+1..n] ypj≥≥0 = > non esiste soluz. ammissibile

primale (cioè l’insieme delle

soluzioni ammissibili duali è illimitato)

Se ∃ ∃ j∈∈[m+1..n] ypj<<0 = > xj può entrare in base al posto di xp

j = = m+1

n



Criterio d’entrata :

Vogliamo mantenere l’ottimalità primale (ammissibilità duale)

= > Vogliamo dopo il pivot ∀ ∀ j ∈ ∈ [1..n] r’j ≥ ≥ 0

Visto che dopo il pivot su p,q r’j = = rj − − ypj rq / ypq = >

= > ∀ ∀ j∈∈[1..n] rj − − ypj rq // ypq ≥ ≥ 0 < = > ∀ ∀ j∈∈[1..n] rj ≥ ≥ ypj rq // ypq

< = > ∀ ∀ j∈∈[1..n] rj // ypj ≤ ≤ rq // ypq (“<“ perché deve essere ypj< < 0)

= > Si sceglie xq che deve entrare in base tale che :

j rq / / ypq = = min { rj / / ypj tale che ypj < 0 }



I passi dell'algoritmo0. è data una soluzione non ammissibile primale, ammissibileduale che soddisfa le condizioni di complementarietà cioè

∀∀ a j ∈∈ B rj == 0

∀∀ a i ∉∉ B ri = = ci −− λλT a i ≥≥ 0

e inoltre ∃∃ a i ∈∈ B | xi << 0 (non ammissibile primale)

1. se xj ≥≥ 0 , ∀∀ j STOPSTOP ; la s.a.b. corrente è ottima

2. scegliere riga p tale che bp < 0 per determinare la variabile dafar uscire dalla base (1 ≤≤ p ≤≤ m)

3. calcolare i rapporti rj / ypj , con ypj < 0 , j = 1 , ... , n.

SeSe ypj ≥ ≥ 0 , j = 1 , ... , n , STOPSTOP; problema duale illimitato,

non esiste s.a. primale.

AltrimentiAltrimenti, scegliere q = indice j corrispondente al rapporto

rj / / ypj minimo ( q è la variabile che entra nella base )

4. (p,q) è il pivot. Aggiornare il tableau con le operazioni di pivot.

Ritornare al passo 1



x1 x2 x3 x4 x5 y0

x4 -1 0 -1 1 0 -2

x5 -1 -1 4 0 1 -1

5 2 0 0 0 0

ESEMPIO

min z = 5 x1 + 2 x2

s.t. x1 + x3 > 2 x1 + x2 - 4x3 > 1

x1 , x2 , x3 > 0



Applicando il simplesso duale viene scelto come elemento dipivot a13 = -1 , da cui si ottiene il nuovo tableau :

x1 x2 x3 x4 x5 y0

x3 1 0 1 -1 0 2

x5 -5 -1 0 4 1 -9

5 2 0 0 0 0

Confrontando la soluzione, dopo un passo di pivot delsimplesso duale si nota come i valori delle variabili di basedel duale (pur essendo variate queste ultime) non sonocambiati.Ciò è dovuto al fatto che la variabile x3 che è entrata in baseaveva già prima costo ridotto uguale a zero.



Dopo una nuova operazione di pivot sull’elemento a21 = -5 , siottiene il tableau seguente :

x1 x2 x3 x4 x5 y0

x3 0 -1/5 1 -1/5 1/5 1/5

x1 1 1/5 0 -4/5 -1/5 9/5

0 1 0 4 1 -9

Ora le soluzioni primali sono ammissibili, quindi termino ilprocedimento ottenendo :

x1 = 9/5 x2 = 0 x3 = 1/5

z = 9



4.2 SIMPLESSO PRIMALE - DUALE



Giustificazione dell’algoritmo :

Situazione di partenza:

Avendo da risolvere il problema A cui corrisponde

di programmazione lineare in il problema duale :

forma standard :

Si conosce una soluzione ammissibile di PD λλ .

min cT x

s.t. (PP)

A x == b

x ≥ ≥ 0

max bT λλs.t. (PD)

AT λλ ≤≤ c



Problemi ristretti associati :

Sia J l'insieme dei vincoli di PD soddisfatti all'uguaglianza,ossia

J = { j tale che λλT a j == cj } = { j tale che rj == cj - λλT a j == 0 }

Essendo λλ ammissibile duale , ne consegue che

∀ ∀ i ∉∉ J λλT a i < c iConsideriamo ora un nuovo problema che considera sia λλ che Je che definiamo problema primale ristretto associato :

min 1T y

s.t. (PPR)

A x ++ y == b

∀ ∀ i ∉∉ J xi == 0

x ≥ ≥ 0 , y ≥ ≥ 0

dove 1T indica il vettore di

m componenti [1, 1, ..., 1].



Il problema duale del problema primale ristretto associato lodefiniamo problema duale ristretto associato, ed è:

diseq. corrispondenti alle xi (*) ci = = 0

diseq. corrispondenti alle yi ci = = 1 (*) con i ∈ ∈ J

Teorema di ottimalità primale - duale :

Hp. : Sia λλ s.a. per (PD) e sia [ x , y = = 0 ]T s.a. per (PPR)

(e ovviamente ottima)

Th. : x è s.o. per (PP) λλ è s.o. per (PD)

max bT u

s.t. (PDR)

ajT u ≤≤ 0 ∀ ∀ j ∈∈ J

u ≤≤ 1



Dim :

A x ++ 0 == b e x ≥ ≥ 0 = > x soluzione ammissibile per (PP)

∀ ∀ i ∉∉ J xi == 0 e ∀ ∀ i ∈∈ J λλT ai == ci = >

= > cTx = Σ = Σ λλTaj xj + Σ + Σ cj 0 = = λλT Σ Σ aj xj = = λλT A x = = λλT b < = >

< = > cTx == bT λλ = > x è s.o. per (PP) λλ è s.o. per (PD)Per il teorema della dualità

j ∈∈ J j ∉∉ J j ∈∈ J

Idea dell’algoritmo :

Si parte da una s.a. del problema duale, poi si ottimizza ilproblema primale ristretto associato. Se la soluzione ottima delprimale ristretto associato è ammissibile anche per il primaleoriginale, si è trovato l'ottimo del primale originale, altrimenti lasoluzione ammissibile per il problema duale viene migliorata eviene generato un nuovo problema primale ristretto associato.



Il metodo itera fino al raggiungimento dell'ottimo oppure allaverifica dell'inesistenza di una soluzione ammissibile per ilprimale originale.

Giustificazione del calcolo del valore di εε :

λλ + ε + ε u è soluzione ammissiibile per (PD) SeSe

∀∀ j ajT ( λλ + ε + ε u ) ≤≤ cj < = > ∀∀ j aj

T λλ + ε + ε ajT u ≤≤ cj = >

1) = > ∀∀ j tale che ajT u << 0 , la diseq. è sempre verifificata

perchè λλ è s. a. per (PD).

2) = > ∀∀ j tale che ajT u >> 0 , la diseq. è verif. se e solo se

ε ε ajT u ≤≤ cj − − aj

T λλ < = > εε ≤≤ ( cj − − ajT λλ ) / ( aj

T u ) < = >

< = > ε = ε = min { ((cj − − ajT λλ)) // ((aj

T u)) tale che ajT u >> 0 }

J



Test sull’esistenza della s.a. primale :

SeSe ∀∀ j ajT u ≤≤ 0 = >

= > ∀∀ εε >> 0 λλ + ε + ε u è soluzione ammissiibile per (PD)

a cui corrisponde una f.o. :

bT ( λλ + ε + ε u ) = = bT λλ + ε + ε bT u = = bT λλ + ε + ε 1T y = >

= > Visto che y ≥≥ 0 al f.o. migliora all’aumentare di εε = >

= > Non esiste soluzione ammissibile per (PP)

(Cioè l’insieme delle soluzioni ammissibili di (PD) è illimitato)



I passi dell'algoritmo0. è data una soluzione non ammissibile primale, ammissibileduale λλ che soddisfa all’uguaglianza alcuni vincoli;

1. si costruisce il problema primale ristretto associato (PPR),come spiegato in precedenza, e lo si ottimizza :

se f.o. == 0 ==> STOPSTOP ; la s.o. di (PPR) è ottima per (PP) grazie al

teorema di ottimalità primale duale;

se f.o. > 0 ==> vai al passo 2;

2. si costruisce il duale del primale ristretto associato (PDR) edal tableau finale del primale ristretto si ricavano i valori deimoltiplicatori u ottimi del (PDR) (vedere slide 25 - CAP. 3).

SeSe ∀∀ j (del primale) ajT u ≤≤ 0 ==> STOPSTOP ; non esiste s.a. per (PP)

AltrimentiAltrimenti ==> aggiornare il valore λλ = = λ λ + ε + ε u

dove

3. Ritornare al passo 1 (dove anche il (PPR) sarà aggiornato).

ε = ε = min { rj // ((ajT u)) tale che aj

T u >> 0 }

= = min { ((cj − − ajT λλ)) // ((aj


J

J



EsempioPrimale:

Duale:

min

. .

2 4

2 3

2 3 5

0

1 2 3

1 2 3

1 2 3

x x x

s t

x x

x x x

i

+ +

+ + =+ + =

≥

x

x

432

1

22

..

53max

21

21

21

21

≤λ+λ≤λ+λ

≤λ+λ

λ+λts

0

* 0

=λ

0

1

è sol. amm.per il duale esoddisfa allauguaglianza il

vincolo asteriscato



Passo 1)Considero il problema Primale Ristretto Associato (PPR)

Calcolo l'ottimo del primale ristretto, che vale:

x2 = 3 y1 = 0 y2 = 2 zPR = 2

zPR > 0 ⇒⇒ proseguo col passo 2

0,,

5

3

..

min

212

22

12

21

≥=+=+

+

yyx

yx

yx

ts

yy



Passo 2)Considero il Duale del Primale Ristretto Associato (PDR)

Dal tableau finale del primale ristretto ricavo il valore deimoltiplicatori ottimi per il duale ristretto

calcolo

max

. .

3 5

0

1

1

1 2

1 2

1

2

u u

s t

u u

u

u

+

+ ≤≤≤

u =−

1

1

ε = ε = min { rj // ((ajT u)) tale che aj

T u >> 0 }

= = min { ((cj − − ajT λλ)) // ((aj


J

J



Passo 1)Considero il nuovo primale ristretto associato

[ ]

[ ]

[ ]

[ ]( ) 12,1min

3

211

3

2014

,

2

111

2

1012

min ==

−

−

−

−

=ε

=

−+

=ε+λ=λ

1

0

1

11

0

1u

min

. .

y y

s t

x y

x x y

1 2

1 2 1

1 2 2

3

2 5

+

+ + =+ + =

x



Calcolo l'ottimo del nuovo primale ristretto associato che vale

x1 = 2 x2 = 1 ⇒⇒ zPR = 0

Ho trovato l'ottimo del primale P che è dato da:

x1 = 2, x2 = 1, x3 = 0 ⇒⇒ zP = 5.



Riassumendo



METODI DUALI DEL SIMPLESSO

Prima di presentare i metodi duali del simplesso abbiamopresentato le situazioni in cui si possono applicare (slide 6).

Abbiamo poi affrontato il metodo del simplesso duale (slide 7-11) presentando una tipica situazione di partenza e illustrandol’idea di base dell’algoritmo che ottimizza il problema duale perottenere la soluzione del problema primale. Continuandoabbiamo giustificato i criteri con cui le variabili devono entrareed uscire dalla base per avvicinarsi all’ottimalità duale e il testche rivela l’esistenza , o meno, di una soluzione ammissibileprimale. Abbiamo terminato con la presentazione dettagliata deipassi dell’algoritmo ed un esercizio in merito (slide 12-15).

Abbiamo, subito dopo, affrontato il metodo del simplessoprimale duale (Slide 16-20) presentando la situazione dipartenza, definendo i problemi ristretti associati e dimostrandoil teorema di ottimalità primale duale che ci permette di avere uncriterio per riconoscere di aver raggiunto l’ottimo primale nelleiterazioni dell’algoritmo.



Continuando (slide 20-22) abbiamo illustrando l’idea di basedell’algoritmo che alternativamente ottimizza il problemaprimale ristretto, e quindi migliora il problema primale, esostituisce la soluzione duale corrente, e quindi migliora ilproblema duale. Abbiamo, quindi, giustificato il calcolo dellanuova soluzione duale migliorante e il test che rivelal’esistenza, o meno, di una soluzione ammissibile primale.Abbiamo terminato con la presentazione dettagliata dei passidell’algoritmo (slide 23).

Infine abbiamo presentato un esempio di applicazionedell’algoritmo del simplesso primale duale (slide 24-28).

Metodi duali del simplesso -...

Documents

Transcript of Metodi duali del simplesso -...