Dopo averlo opportunamente trasformato in forma standard, si risolva il seguente problema di PLI usando l’algoritmo di taglio di Gomory

APPELLO DEL 25/03/04

Esercizio 1

Dopo averlo opportunamente trasformato in forma standard, si risolva il seguente problema di PLI usando l’algoritmo di taglio di Gomory

max 3x

1

+ x

2

x

1

≤

¹¹₄

x

2

≤

¹¹₄

x

1

+ x

2

≤

⁹₂

x

1

, x

2

≥ 0 x

1

, x

2

∈ I,

partendo nella risoluzione del rilassamento lineare dalla base ammissibile B

0

= {x

1

, x

4

, x

5

} rispetto alla quale si ha la seguente riformulazione del problema.

max z =

³³₄

−

³₄

x

3

+x

2

x

1

=

¹¹₄

−

¹₄

x

3

x

4

= 11 −4x

2

x

5

=

⁷₂

+

¹₂

x

3

−2x

2

x

1

, . . . , x

5

≥ 0 (12 punti)

Esercizio 2

Sia dato il seguente problema di PL

max x

1

+ 2x

2

x

1

+ 3x

2

≤ 6 x

1

− x

2

≤ 1

−x

1

+ x

2

≤ 1 x

1

, x

2

≥ 0 1) Lo si risolva graficamente (4 punti)

2) Dopo averlo portato alla forma standard, se ne scriva il duale (2 punti)

3) Utilizzando le condizioni di complementarit´ a si calcoli la soluzione ottima del duale (4 punti)

4) ´ E possibile modificare i coefficienti di x

1

e x

2

nell’obiettivo in modo che il duale abbia regione ammissibile vuota? Motivare la risposta. (2 punti)

Esercizio 3

Sia dato il grafo non orientato rappresentato dalla seguente matrice di incidenza:

a b c d e f g





















1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 1 0 0 1 0 0 0 1 0 0 0 1 1 0 0 0 0 1 0 0 0 0 1 0 0 0 1





















1

Si stabilisca se il grafo ´e connesso e se ´e bipartito. (4 punti) Esercizio 4

(1) Sia dato un problema di PL in forma standard con obiettivo illimitato. ´ E possibile aggiungere un vincolo a tale problema in modo che nel suo duale si abbia D

ott

6= ∅, ovvero il duale abbia soluzioni ottime? Ed ´e possibile ottenere lo stesso risultato, cio´e D

ott

6= ∅, modificando i termini noti dei vincoli del primale?

(2) Sia dato il problema di PL in forma standard

max P

n

j=1

c

j

x

j

P

n

j=1

a

ij

x

j

= b

i

i = 1, . . . , m x

j

≥ 0 j = 1, . . . , n

Si supponga che la variabile x

k

faccia parte della base ottima e che la variabile x

h

sia fuori dalla base ottima. Quali delle seguenti affermazioni sono sempre vere (motivare le risposte)

1): Ogni variazione ∆c

h

≤ 0 del coefficiente di x

h

nell’obiettivo non cambia la base ottima.

2): Ogni variazione ∆c

k

≥ 0 del coefficiente di x

k

nell’obiettivo non cambia la base ottima.

3): Dato il vincolo r-esimo del problema, si supponga che una modifica

∆b

r

> 0 del termine noto del vincolo non cambi la base ottima. In tal

caso la variazione fa crescere il valore ottimo del problema.

Soluzioni

1. Riformulando rispetto alla base iniziale B

0

= {x

1

, x

4

, x

5

} e risolvendo si ottiene max z =

³³₄

−

³₄

x

3

+x

2

x

1

=

¹¹₄

−

¹₄

x

3

x

4

= 11 −4x

2

x

5

=

⁷₂

+

¹₂

x

3

−2x

2

x

1

, . . . , x

5

≥ 0

=⇒ B

1

= B

0

− {x

5

} ∪ {x

2

} ;

max z = 10 −

¹₂

x

3

−

¹₂

x

5

x

1

=

¹¹₄

−

¹₄

x

3

x

4

= 4 −x

3

+2x

5

x

2

=

⁷₄

+

¹₄

x

3

−

¹₂

x

5

x

1

, . . . , x

5

≥ 0

=⇒ B

1

ottima.

Derivando il taglio di Gomory 1 4 x

3

≥ 3

4 =⇒ 1

4 x

3

− y

1

= 3

4 dalla prima riga si prosegue:

max z = 10 −

¹₂

x

3

−

¹₂

x

5

x

1

=

¹¹₄

−

¹₄

x

3

x

4

= 4 −x

3

+2x

5

x

2

=

⁷₄

+

¹₄

x

3

−

¹₂

x

5

y

1

= −

³₄

+

¹₄

x

3

x

1

, . . . , x

5

≥ 0

=⇒ B

2

= B

1

− {y

1

} ∪ {x

5

} ;

max z =

¹⁷₂

−2y

1

−

¹₂

x

5

x

1

= 2 −y

1

x

4

= 1 −4y

1

+2x

5

x

2

=

⁵₂

+y

1

−

¹₂

x

5

x

3

= 3 +4y

1

x

1

, . . . , x

5

, y

1

≥ 0.

Infine si aggiunge il taglio 1

2 x

5

≥ 1

2 =⇒ 1

2 x

5

− y

2

= 1

2 dalla terza riga, riottimizzando.

max z =

¹⁷₂

−2y

1

−

¹₂

x

5

x

1

= 2 −y

1

x

4

= 1 −4y

1

+2x

5

x

2

=

⁵₂

+y

1

−

¹₂

x

5

x

3

= 3 +4y

1

y

2

= −

¹₂

+

¹₂

x

5

x

1

, . . . , x

5

, y

1

≥ 0

=⇒ B

3

= B

2

− {y

2

} ∪ {x

5

} ;

max z = 8 −2y

1

−y

2

x

1

= 2 −y

1

x

4

= 3 −4y

1

+4y

2

x

2

= 2 +y

1

−y

2

x

3

= 3 +4y

1

x

5

= 1 +2y

2

x

1

, . . . , x

5

, y

1

, y

2

≥ 0.

2. (1) La Figura 1 rappresenta la regione S

a

. L’ottimo `e localizzato in B(x

^∗₁

=

⁹₄

, x

^∗₂

=

5

4

), con valore z

^∗

=

¹⁹₄

.

A

B

C O

D

r t s

x

1

x

2

r : x

1

+ 3x

2

= 0 s : x

1

− x

2

= 1

t : − x

1

+ x

2

= 1 A  3

4 , 7 4



B  9 4 , 5

4

 C (1, 0) D (0, 1)

Figura 1. S

a

per l’esercizio 2.

(2) Il programma in forma standard risulta max x

1

+ 2x

2

soggetto a

x

1

+3x

2

+x

3

= 6

x

1

−x

2

+x

4

= 1

−x

1

+x

2

+x

5

= 1

x

1

, . . . , x

5

≥ 0,

dove x

3

, x

4

, x

5

sono variabili di slack. Il duale risulta min 6u

1

+ u

2

+ u

3

soggetto a

u

1

+u

2

−u

3

≥ 1 3u

1

−u

2

+u

3

≥ 2 u

1

≥ 0

u

2

≥ 0 u

3

≥ 0

(3) All’ottimo primale si ha che −x

^∗₁

+ x

^∗₂

< 1; il terzo vincolo `e l’unico ad essere soddisfatto come disuguaglianza stretta, quindi si deve avere u

3

= 0. Inoltre x

^∗1

> 0 e x

^∗₂

> 0 implicano le uguaglianze

u

1

+ u

2

= 1 3u

1

− u

2

= 2

(dove si `e gi` a tenuto conto di u

3

= 0). Risulta quindi u

^∗₁

=

³₄

, u

^∗₂

=

¹₄

. Si noti che z

^∗

= 6 · 3

4 + 1 4 = 19

4 ,

coincidente con l’ottimo primale, come previsto.

(4) No, per la seguente ragione. Sappiamo che modificare la funzione obiettivo non cambia S

a

, quindi S

a

6= ∅, con qualunque funzione obiettivo. Inoltre il vincolo x

1

+ 3x

2

≤ 6 implica che il primale `e sempre limitato. Quindi si avr`a sempre S

ot

6= ∅, il che implica (teorema della dualit`a) che D

ot

6= ∅.

3. Applicando gli algoritmi visti a lezione si verifica che il grafo `e non-connesso e

bipartito.

4. (1) Se il problema illimitato `e max

n

X

j=1

c

j

xj soggetto a

n

X

j=1

a

ij

x

ij

= b

i

i = 1, . . . , m x

1

, . . . , x

n

, ≥ 0,

`e possibile rendere D

ot

6= ∅ in vari modi; uno dei pi` u semplici consiste nel consid- erare una soluzione ammissibile ¯ x con valore ¯ z = P

n

j=1

c

j

x ¯

j

(ne esiste sicuramente una, per ipotesi) ed aggiungere al problema il vincolo

n

X

j=1

c

j

x

j

≤ ¯ z.

Questo rende sicuramente il problema limitato (z non pu` o tendere a +∞); inoltre S

a

6= ∅ in quanto ¯ x continua ad essere ammissibile. Allora S

ot

6= ∅, e questo implica (teorema della dualit` a) D

ot

6= ∅.

Non `e possibile ottenere lo stesso risultato agendo sui termini noti b

i

, in quanto se i vincoli del duale

m

X

i=1

a

ij

u

i

≥ c

j

j = 1, . . . , n

sono incompatibili, lo rimangono per qualunque valore si possa assegnare ai b

i

. (2) Le affermazioni sono:

(1) Vera. Se x

h

`e fuori dalla base ottima, la variazione ∆c

h

trasforma il costo ridotto γ

h

< 0 in

γ

_y⁰

= γ

h

+ ∆c

h

≤ γ

h

≤ 0,

e non compromette le condizioni di ottimalit` a.

(2) Falsa. Essendo il vettore dei coefficienti di costo ridotto γ = c

N

− c

B

A

⁻¹_B

A

N

,

la variazione positiva di c

k

pu` o rendere positivi alcuni coefficienti di costo ridotto, e quindi compromettere l’ottimalit` a della base.

(3) Falsa. Il segno della variazione del valore ottimo di funzione obiettivo

dipende dal segno di u

^∗_i

, che in questo caso pu` o essere sia positivo che

negativo.