Che materia stai cercando?

Anteprima

ESTRATTO DOCUMENTO

PLI

Tagli di Gomory

Richiamiamo i concetti di parte intera e parte decimale di un numero

reale.

Definizione ∈

Dato un numero x indichiamo

R

bxc

con la parte intera (inferiore) di x, cioè il più grande numero

intero non superiore a x,

{x} {x} − bxc.

con la parte decimale di x, cioè x

= bxc {x}.

Per definizione ogni numero x si può scrivere x = +

13 13 13 3

b c { }

allora 2 e .

Se x = =

= 5 5 5 5 −3,

Attenzione ai numeri negativi: se x 2 allora

=

b−3, −4 {−3,

2c e 2} 0, 8

= = dsm

Marco Castellani (L’Aquila) Ricerca Operativa PL intera 12 / 38

PLI

Tagli di Gomory

x 0)

Sia una soluzione ottima di base del problema rilassato

= (b, ∈ S.

x

determinata con il metodo del simplesso e supponiamo che /

∈ b L’equazione relativa sarà

Allora esisterà i B tale che / N.

i X

x a x b

+ =

i ij j i

j∈N

Decomponiamo i coefficienti a e b come somma delle loro parti

ij i

intere e parti decimali

ba c {a } bb c {b }

a e b

= + = +

ij ij ij i i i

e sostituiamoli nell’equazione separando gli interi dai decimali

X X

ba cx − bb c {b } − {a }x

x + =

i ij j i i ij j

j∈N j∈N dsm

Marco Castellani (L’Aquila) Ricerca Operativa PL intera 13 / 38

PLI

Tagli di Gomory ∈ S;

x

Prendiamo un punto allora, sostituendolo nell’equazione

X

X {b

ba cx − bb c } − {a }x

x =

+ ij j i i ij j

i j∈N

j∈N

| {z }

appartiene a Z

P

{b } }x ≥

{a

Inoltre 1 e 0 quindi

<

i ij j

j∈N

X X

cx − bb c {b } − }x

ba {a

x =

+ ij j i i ij j

i j∈N j∈N

{z } {z }

| |

appartiene a risulta <1

Z

Mettendo assieme le due condizioni si ottiene la disuguaglianza

X {a }x ≥ {b }

ij j i dsm

j∈N

Marco Castellani (L’Aquila) Ricerca Operativa PL intera 14 / 38

PLI

Tagli di Gomory

La disuguaglianza ottenuta risulta essere un piano di taglio (taglio di

Gomory); infatti

per costruzione, ogni soluzione ammissibile del problema PLI la

verifica, x

la soluzione ottima di base del problema rilassato non la verifica

in quanto x 0 per ogni j N.

=

j

A questo punto si aggiunge il vincolo al problema rilassato e si risolve

il nuovo problema utilizzando l’algoritmo duale del simplesso.

I tagli di Gomory sono noti in letteratura anche come tagli frazionari. dsm

Marco Castellani (L’Aquila) Ricerca Operativa PL intera 15 / 38

PLI

Tagli di Gomory

Esempio 1 (continua). Riprendiamo il problema iniziale il cui

rilassamento ha la seguente tabella simpliciale

5 2 0 0

1 2 1 0 8

3 1 0 1 10

La tabella finale del simplesso è (determinatela)

−1/5 −9/5

0 0 −1/5

1 0 2/5 12/5

−1/5

0 1 3/5 14/5

12 14

x

con soluzione ottima 0, 0). La soluzione non è intera e la

= ( , ,

5 5

prima componente è quella che maggiormente si allontana

dall’interezza. dsm

Marco Castellani (L’Aquila) Ricerca Operativa PL intera 16 / 38

PLI

Tagli di Gomory x è il primo

Il vincolo relativo alla prima componente di

2 12

1

− x x

x + = .

3 4

1 5 5 5

Decomponiamo tutti i coefficienti in parte intera e parte decimale

4 2 2

−1

x x 0 x 2

+ + + + = +

1 3 4

5 5 5

e separiamo la parte decimale da quella intera

2 4 2

− − − −

x x 2 x x

=

1 3 3 4

5 5 5

Il taglio di Gomory si ottiene ponendo 0 la parte decimale

2x x 1

+ dsm

3 4

Marco Castellani (L’Aquila) Ricerca Operativa PL intera 17 / 38

PLI

Tagli di Gomory

Se vogliamo rappresentare il vincolo ≥

2x x 1

+

3 4

nel piano x e x , basta ricordare che

1 2

x 2x x 8 e 3x x x 10.

+ + = + + =

1 2 3 1 2 4

Mettendo in evidenza x e x e sostituendoli nella disequazione di

3 4

taglio si ottiene l’equivalente vincolo ma questa volta espresso nelle

variabili di partenza x e x

1 2 ≤

x x 5

+

1 2 dsm

Marco Castellani (L’Aquila) Ricerca Operativa PL intera 18 / 38

PLI

Tagli di Gomory

6

q A 0)

D = (0,

H

H @

HH @ 10

B 0)

= ( ,

H 3

@

HH

q q q

H

@

H c

C

HH

@ 12 14

C = ( , )

c 5 5

@ E

B

@

B B

@

q q q D 4)

= (0,

B @

B

B P 1)

= (3,

B

q q q q

B

P B 5 52

E = ( , )

2

B B B B

q q q q c

B -

A dsm

Marco Castellani (L’Aquila) Ricerca Operativa PL intera 19 / 38

PLI

Tagli di Gomory

Aggiungiamo il nuovo vincolo alla tabella finale del simplesso con

l’aggiunta di una nuova variabile di scarto x 5

−1/5 −9/5

0 0 0

−1/5

1 0 2/5 0 12/5

−1/5

0 1 3/5 0 14/5

−1

0 0 2 1 1

−1,

Moltiplicando l’ultima riga per possiamo applicare l’algoritmo duale

−2

del simplesso alla terza riga facendo pivot in a =

33

−1/5 −9/5

0 0 0

−1/5

1 0 2/5 0 12/5

−1/5

0 1 3/5 0 14/5

−2 −1 −1

0 0 1 dsm

Marco Castellani (L’Aquila) Ricerca Operativa PL intera 20 / 38

PLI

Tagli di Gomory

Attraverso operazioni di riga otteniamo la seguente tabella ottima

−17/10 −1/10

0 0 0 −1/10

1 0 0 1/2 5/2

−1/2

0 1 0 3/10 5/2

−1/2

0 0 1 1/2 1/2

52 5 1 ∈ S

x x

con soluzione ottima 0, 0). Poiché dobbiamo

= ( , , , /

2 2

effettuare un nuovo taglio relativo, ad esempio, all’ultimo vincolo

1 1 1

x x x

+ =

5

3 4

2 2 2 ≥

Verificate che il nuovo piano di taglio è x x 1 corrispondente a

+ 5

4

4x 3x 17.

+ dsm

1 2

Marco Castellani (L’Aquila) Ricerca Operativa PL intera 21 / 38

PLI

Tagli di Gomory

6

q

D 13 11

F = ( , )

H 5 5

H @ S

HH @

S

H HH

@

S

q q q

H

@

S

H c

C

HH

@

S e così via. . .

c

@

S E

B

B

@

S

=

c

B

@

S

q q q F B @

S

B S

B S

B S

q q q q

B

P B B B B B

q c

q q q B -

A dsm

Marco Castellani (L’Aquila) Ricerca Operativa PL intera 22 / 38

PLI

Tagli di Gomory

Il metodo dei tagli di Gomory è scarsamente efficiente!

Esistono alcuni espedienti che permettono di ottenere una

maggiore efficienza; ad esempio, in presenza del vincolo

− ≤

2x 4x 3

1 2

potremmo riscriverlo 3

− ≤

x 2x .

1 2 2

∈ − ∈

Essendo x x segue che x 2x e quindi potremmo

, N Z

1 2 1 2

riscrivere il vincolo in maniera equivalente

− ≤

x 2x 1

1 2 S.

che è maggiormente aderente alla regione dsm

Marco Castellani (L’Aquila) Ricerca Operativa PL intera 23 / 38

PLI

Il metodo Branch & Bound

Gli algoritmi maggiormente implementati nei software commerciali per

la PLI sono quelli di enumerazione implicita. Tra questi, forse i più

famosi, sono quelli di tipo Branch & Bound.

Il verbo TO BRANCH significa ramificare,

il verbo TO BOUND significa limitare.

Il metodo determina sottoinsiemi disgiunti di soluzioni (branching) e li

valuta sulla base di una stima della funzione obiettivo (bounding),

eliminando quegli insiemi di soluzioni che non contengono la soluzione

ottima. dsm

Marco Castellani (L’Aquila) Ricerca Operativa PL intera 24 / 38

PLI

Il metodo Branch & Bound

Lo schema dell’algoritmo di Branch & Bound è il seguente.

0

x

Determiniamo la soluzione del problema rilassato ed il

(P )

1 0

valore di massimo z .

0

0 ∈ S ∈ ∈

x

Se allora esiste i B tale che x e z è un limite

/ /

2 N

i 0

superiore del massimo del problema di PLI (upper bound).

Generiamo due problemi rilassati (branching)

3 | |

 

c x c x

max max

 

 

Ax b Ax b

= =

 

&

(P ) (P )

1 2

≤ bx ≥ bx

c c

x x 1

+

i i

i i

 

 

≥ ≥

x 0 x 0

 

Risolviamo i due problemi. Si presenteranno vari casi

4 (analizziamo solamente quelli relativi a che ripeteremo per

(P )

1

tutti i problemi che si presenteranno). dsm

Marco Castellani (L’Aquila) Ricerca Operativa PL intera 25 / 38

PLI

Il metodo Branch & Bound

Se ha regione ammissibile vuota non esploreremo

(P )

1

ulteriormente quel ramo. 1

x

Se ha soluzione ottima intera allora il valore di massimo z

(P )

1 1

è un limite inferiore del massimo del problema di PLI (lower

`

bound) e non esploreremo ulteriormente quel ramo.

1

x

Se ha soluzione ottima non intera allora

(P )

1 1

bz c ≤

se che è il più grande lower bound determinato non

`

I esploreremo ulteriormente quel ramo;

altrimenti ripeteremo la procedura ripartendo dal punto 3

I (branching).

L’algoritmo ha termine quando non ci saranno più rami da esplorare ed

il più grande lower bound determinato è la soluzione del problema di

PLI iniziale. dsm

Marco Castellani (L’Aquila) Ricerca Operativa PL intera 26 / 38

PLI

Il metodo Branch & Bound

Esempio 1 (continua). Applichiamo il metodo di Branch & Bound al

problema iniziale. Invece di risolvere i vari problemi algebricamente ci

limiteremo a determinarne le soluzione geometricamente.

0 12 14

x Il punto

La soluzione del problema rilassato è , ).

(P ) = (

1 0 5 5

0 88

∈ S

x ed inoltre il valore ottimo è z .

/ =

0 5

01 12 ∈

Scegliamo la prima componente x = /

2 N.

5

Individuiamo due nuovi sottoproblemi rilassati

3  

max 5x 2x max 5x 2x

+ +

1 2 1 2

 

 

≤ ≤

x 2x 8 x 2x 8

+ +

 

1 2 1 2

 

 

≤ ≤

3x x 10 3x x 10

&

+ +

(P ) (P )

1 2 1 2

1 2

≤ ≥

x 2 x 3

 

1 1

 

 

 

≥ ≥

x x 0 x x 0

, ,

 

1 2 1 2

Determiniamo le due soluzioni geometricamente. dsm

4 Marco Castellani (L’Aquila) Ricerca Operativa PL intera 27 / 38

PLI

Il metodo Branch & Bound 88

z =

0 5

6

q HH

H

H

j

H

HH z 16 z 17

= =

1 2

H HH L STOP STOP

q q q

H L !

*

H ! 0

c x

1 H

L

x H

L B

B

L B 2

q q q x

La soluzione ottima è

B B

B

1

S B

L

r

q q q q

B

L !

*

!

2 B

L

x B

L

B

L

2

B S

q c

q q q r

B - dsm

Marco Castellani (L’Aquila) Ricerca Operativa PL intera 28 / 38


PAGINE

38

PESO

341.16 KB

AUTORE

Atreyu

PUBBLICATO

+1 anno fa


DESCRIZIONE DISPENSA

In questo materiale didattico vengono trattati i seguenti argomenti. Programmazione lineare intera (PLI): introduzione e definizioni; problema rilassato associato ad un problema di ottimizzazione di programmazione lineare (PL); interezza della soluzione per il rilassato: condizione sufficiente per la totale unimodularità; tagli di Gomory: applicazioni ed esempi; il metodo Branch & Bound: applicazioni ed esempi.


DETTAGLI
Corso di laurea: Corso di laurea in economia e amministrazione delle imprese
SSD:
Università: L'Aquila - Univaq
A.A.: 2011-2012

I contenuti di questa pagina costituiscono rielaborazioni personali del Publisher Atreyu di informazioni apprese con la frequenza delle lezioni di Ricerca Operativa e studio autonomo di eventuali libri di riferimento in preparazione dell'esame finale o della tesi. Non devono intendersi come materiale ufficiale dell'università L'Aquila - Univaq o del prof Castellani Marco.

Acquista con carta o conto PayPal

Scarica il file tutte le volte che vuoi

Paga con un conto PayPal per usufruire della garanzia Soddisfatto o rimborsato

Recensioni
Ti è piaciuto questo appunto? Valutalo!

Altri appunti di Ricerca operativa

Programmazione lineare
Dispensa
Algoritmi su grafi - Prima parte
Dispensa
Modelli
Dispensa
Analisi numerica - Metodo delle secanti
Dispensa