RICERCA OPERATIVA

Soluzione dell’esercizio del 12 marzo 2003

 

1.   (D)   max   –2y1 + 5y3

                        –y1 + 5y2 + 2y3  =  3

                        4y1 +   y2 – 2y3  <  2

                          y1 – 2y2 + 2y3  >  1

                                   y1, y2  >  0

 

2.   (D)   min    13y1 + 2y2 + 2y3

                        6y1  +  y2 + y3  >  1

                        6y1 + 4y2 – y3  =  2

                          y1 – 2y2 – y3  =  7

                             y2  >  0

 

3.   Il problema di programmazione lineare

 (P)    max    x1 – x2 + 3x3

                        2x1 + 3x2 + x3  <  10

                             x1  >  0

 

(A)    è illimitato superiormente

(B)    è illimitato inferiormente

(C)    non ammette soluzione

e dunque il suo duale, che è

 

  (D)   min  10y

                    2y  >  1

                    3y  =  –1

                      y   =   3

                      y   >   0

 

(A)    ammette una soluzione ottima

(B)    non ammette soluzione

(C)    è illimitato inferiormente

 

4.   Il vettore

                        2

            x*  =  ( 0 )

4

è ovviamente una soluzione ammissibile del problema

      (P)          max   4x1 + 2x2 + x3

                                   6x1 + 5x2 + 4x3  <  30

                                           x1, x2, x3  >  0

Il duale di (P) si scrive

      (D)          min    28y

                                 y  >  2/3

                                 y  >  2/5

                                 y   >  1/4

                                 y   >   0

 

e siccome la sua soluzione ottima y* = 2/3 ha valore 20 > cx* = 4×2 + 2×0 + 1×4 = 12

(B)    Il duale di (P) non ammette soluzioni che dimostrino l’ottimalità di x*