Esercizi Ricerca operativa

O

. 4 x x 4(2 2 x x ) x 8 9 x 4 x

1 2 2 3 2 2 3

x

Costi ridotti negativi per la variabile 3

Proviamo con la base B=[A1,A3]

− = =

 

x x 2 x 2

=  

1 3 3

 

B [ A , A ] = =

1 3  

2 x 8 x 4

1 1

Esprimiamo le variabili in base (x , x ) in funzione di quelle fuori base (x , x )

1 3 2 4

+ − =

 

x 2 x x 2 x non compare nella F.O.



1 2 3 3

 

+ + = = − −

 

2 x 7 x x 8 2 x 8 7 x x

1 2 4 1 2 4

7 1

 = − −

x 4 x x

1 2 4

2 2  

7 1

 = − + = − − − + = − +

 

F .

O

. 4 x x 4 4 x x x 16 .....

1 2 2 4 2

 

2 2

Costi ridotti positivi:

 

= 

x

* 4 0 2 0

=

max

F .

O

. 16

Esercizio 3

Sia dato il seguente problema di PL e siano x4 e x5 le variabili aggiuntive per portare

rispettivamente il vincolo 1 e il vincolo 2 in forma standard. Considerando che la

all’ottimo la variabile x3 vale:

base ottima contiene la colonna A1,

+ +

min x 2 x 3 x

1 2 3

− + 

x 2 x x 2

1 2 3

+ − 

3 x x 2 x 5

1 2 3



x , x 0

1 2 + +

min x 2 x 3 x

1 2 3

− + − =

x 2 x x x 2

1 2 3 4

+ − + =

3 x x 2 x x 5

1 2 3 5



x , x , x , x 0

1 2 3 4

Abbiamo 4 possibili basi: [A1 A2] [A1 A3] [A1 A4] [A1 A5]

=

B [ A , A ]

1) 1 5

= =

 

x 2 x 2



1 1

  NO

+ = = −

 

3 x x 5 x 1

1 5 5

=

B [ A , A ]

2) 1 4  1

= − = −

 x x 2 x



− =

  

4 1

x x 2 4 3

 

1 4

   NO

5

= =



3 x 5 5

 

x =



1 1 x

3  1 3

=

B [ A , A ]

3) 1 2 = +



− =

  x 2 2 x

x 2 x 2  1 2

1 2

  ( )

+ + =

+ = 

 3 2 2 x x 5

3 x x 5  2 2

1 2

= + = +

 

x 2 2 x x 2 2 x

  

1 2 1 2

  NO

+ + = = −

 

6 6 x x 5 7 x 1

2 2 2

=

B [ A , A ]

4) 1 3 + =

 x x 2

=  1 3



B [ A , A ] − =

1 3 

3 x 2 x 5

1 3

= − = −

 

 x 2 x x 2 x



1 3 1 3

 

( )

− − = − − =

 

3 2 x 2 x 5 6 3 x 2 x 5

 3 3 3 3

= − = −

 

x 2 x x 2 x



1 3 1 3

 

− = − =

 

6 5 x 5 6 5 x 5

3 3

 9

= − =

 x 2 x x



 

1 3 1 5



 

1

= 1

 

x =

 3 x

5  3 5

 9

=

x

 1 9 1 12

5  = +  =

 F .

O

. 3

1 5 5 5

 =

x

 3 5

E se avessi avuto più di una base ammissibile???

Esercizio 4

Dato il seguente problema di PLI, all’ottimo la variabile x2 vale:

−

min x

2

− + 

x 2 x 4

1 2

+ 

2 x x 5

1 2



x , x 0 intero

1 2  x

− +   +

  1

x 2 x 4 x 2



1 2 2

  2

+ 

 2 x x 5   −



1 2 x 5 2 x

2 1

6

5

4

3

2

1

0 0 0.5 1 1.5 2 2.5 3 3.5

-1

-2 x2 x2

Esercizio 5

Dato il seguente problema di PNL non vincolata, all'ottimo la variabile x2 vale:

( ) = + − −

2 2

min f x , x 2 x x x x 2 x

1 2 1 2 1 2 2

T

 

 

f f

 = =

 

f ( x ) , 0

 

 

x x

1 2



 f = 0

 

 x

 1



f

 = 0

 

 x

2

  + − −

2 2

(2 x x x x 2 x ) =

1 2 1 2 2

 0



 x

 1

 + − −

2 2

 (2 x x x x 2 x ) =

1 2 1 2 2 0

 

 x

2

  + − −

2 2

(2 x x x x 2 x ) =

1 2 1 2 2

 0



 x

1

  + − −

2 2

 (2 x x x x 2 x ) =

1 2 1 2 2 0

 

 x

2

− = =

 

4 x x 0 x 4 x

 

1 2 2 1

 

− − = − − =

 

2 x x 2 0 8 x x 2 0

2 1 1 1

 8

=

x



=

 

x 4 x 2 7

 

2 1

 

=

 7 x 2 2

 =

1 x

 1 7

2 2

        

2 8 2 8 8

= + − − =

        

f ( x

*) 2 2

        

7 7 7 7 7

2

      

8 8 2 8 8

= + − − =

      

2

( )       

2 7 7 7 7

7

 

8 1 8 2

+ − − =

 

2

 

7 7 7 7

+ − −

   

8 1 8 2 14 8 7 8

= − = −

   

   

7 7 7 7 7

Matrice Hessiana:

 

 

2 2

f f

 

   −

 

2

x x x 4 1

 

 = =

1 1 2

2 

f ( x )   −

   

2 2 1 2

f f

 

   2

 

x x x

2 1 2

Minori di testa tutti positivi:

Hessiana definita positiva ovunque; quindi la funzione convessa (ovunque):

verifichiamo solo le condizioni del primo ordine

Esercizio 6

Sia dato il seguente problema di PNL vincolata. Considerando che all'ottimo è attivo

solo il primo vincolo, all'ottimo la variabile x1 vale:

− 2

min 3 x 4 x

1 2

− − 

2 2

4 x x 0

1 2

+ − 

x x 1 0

1 2

Condizioni KKT



 =

L ( x

*, *) 0

x = 

h ( x

*) 0 i E

i  

g ( x

*) 0 j I

j

 = 

* g ( x

*) 0 j I

j j

  

* 0 j I

j

Non abbiamo equazioni



 =

L ( x

*, *) 0

x  

g ( x

*) 0 j I

j

 = 

* g ( x

*) 0 j I

j j

  

* 0 j I

j

Scriviamo la Lagrangiana



 

= −

L ( x , ) f ( x ) g ( x )

j j



j I

  

= − − − − − + −

2 2 2

L ( x , ) 3 x 4 x (4 x x ) ( x x 1)

1 2 1 1 2 2 1 2

Imponiamo le KKT



 L  

= + − =

3 2 x 0

  1 1 2

x

 1



 L  

= − + − =

8 x 2 x 0

  2 1 2 2

x

 2

 − − 

2 2

 4 x x 0

1 2

 + − 

x x 1 0

 1 2

  − − =

2 2

(4 x x ) 0

 1 1 2

 + − =

 ( x x 1) 0

2 1 2

   0

 1

 

 0

2

Attivo solo il vincolo 1. Verifichiamo la condizione di qualificazione dei vincoli attivi (solo

vincolo 1).  

 = − −

T

g ( x ) 2 x 2 x . Si annulla nel punto (non regolare) C = [0 0] che NON è ammissibile

1 1 2 + − 

x x 1 0

in quanto non soddisfa il secondo vincolo . Quindi dobbiamo cercare il punto di

1 2

minimo tra i punti regolari (che sono tenuti a soddisfare le KKT).



+ =



3 2 x 0

 =  

1 1



0 

− + =

2  8 x 2 x 0

2 1 2



+ =



3 2 x 0

1 1

  − =

 2 x ( 4) 0

2 1 =

 x 0

 − =  2



2 x ( 4) 0  =

2 1  4

1

 = 4

CASO 1: 1

 =  + =

4 3 8 x 0

1 1

3

= −

x

1 8

Poiché è attivo solo il vincolo 1, è da quello che vado a ricavare x 2