ESERCITAZIONIDIRICERCAOPERATIVA1
ESERCIZIO1. Dato il seguente programma lineare
max 2x1+ 4x2 x3 2x4 (1)
soggetto a
x
1 2x2+ 4x35 (2)
x
2+x3+x48 (3)
x
1
;:::;x
4
0; (4)
si richiede di:
(1) scrivere e risolvere il programma duale;
(2) dalla soluzione ottima duale, determinare una soluzione ottima di (1){(4).
Inoltre:
Determinare di quanto puo aumentare il costo della variabile x3 senza compromettere l'ottimalita della soluzione ottima primale determinata al punto (1).
Dire se, cambiando i termini noti di (1){(4), e possibile rendere il program- ma illimitato.
ESERCIZIO2. Dato il programma lineare
max x1 x2 2x3 (5)
soggetto a
2x1+x2+x3+x4= 8 (6)
3x1+x2 x34 (7)
x
1
;:::;x
4
0; (8)
si richiede di
(1) formulare il programma in forma standard e risolverlo senza impostare il problema di prima fase;
(2) scrivere il duale rispetto alla forma standard, e dedurre la sua soluzione ottima dall'ottimo di (5){(8);
(3) senza ricominciare dall'inizio, aggiungere a (5){(8) il vincolo
x
4
1 (9)
e determinare la nuova soluzione ottima.
Soluzioni
1.(1) Il programmaduale di (1){(4)si ricava applicando le regole di riscrittura primale- duale per il caso generale.
min 5u1+ 8u2 (10)
soggetto a
u
1
2 (11)
2u1+u24 (12)
4u1+u2 1 (13)
u
2
2 (14)
u
1
;u
2
0: (15)
Poiche (10){(15) e un programma in due sole variabili, si puo risolvere sempli- cemente con il metodo gra co. La regione di ammissibilitaDa del duale e rap- presentata dal settore (illimitato) ombreggiato di vertice A in Figura 1. La retta tratteggiata rappresenta una retta isocosto; il punto a costo minimodiDae proprio
A(u1= 2;u2= 8), a cui corrisponde il costo duale minimoz= 74.
(2) Per ricavare una soluzione primale dalla soluzione del duale, si possono usare le condizioni di complementarieta primale-duale:
(uA c)x= 0: (16)
u
(b Ax) = 0; (17)
La (16) e la condizione gia nota; la (17) e l'analoga ottenuta per il caso generale (primale non in forma standard) osservando che si possono scambiare i ruoli di programma primale e programma duale.
Per (1){(4) e (10){(15) le due condizioni (16) e (17) si scrivono rispettivamente come
x
1(u1 2) +x2( 2u1+u2 4) +x3(4u1+u2+ 1) +x4(u2+ 2) = 0;
u
1[5 (x1 2x2+ 4x3)] +u2[8 (x2+x3+x4)] = 0: Questo permette di dedurre che
4u2+u2> 1 =) x3= 0;
u
2
> 2 =) x4= 0:
u
1 = 2>0 =) x1 2x2+ 4x3= 5
u
2 = 8>0 =) x2+x3+x4= 8
NB: non valgono in generale le implicazioni inverse.
Quindi la soluzione ottima di (1){(4) deve soddisfare
x
1 2x2= 5
x
2= 8
x
3=x4= 0 =)
x
1= 21;
x
2= 8;
x
3=x4= 0
Si noti che la funzione obiettivo primale ha valorez = 42 + 32 = 74, coincidente con l'ottimo duale,come previsto dalla teoria.
Aumentare il costo della variabile x3 (c3) signi ca aumentare il termine noto del terzo vincolo duale, e quindi spostare verso Nord-Est la retta 4u1+u2= 1.
La soluzione ottima duale, e quindi anche quella primale, non viene perturbata da
questo spostamento, no a quando la retta non giunge a toccare il puntoA, quindi quando
c
3= 4u1+u2= 16:
Quindi il costo c3 puo crescere al piu di 16 ( 1) = 17 unita; ogni ulteriore variazione perturba l'ottimo:
1<c317:
Si ricordi che un programma primale con obiettivo illimitato implica un duale privo di soluzioni ammissibili; inoltre si e gia veri cato che Da 6= ;, e che (1){(4) e (10){(15) hanno entrambi soluzione ottima nita. Cambiare i termini noti di (1){
(4) signi ca cambiare i coecienti della funzione obiettivo duale, il che non puo rendere Da = ;. Quindi il primale non puo diventare illimitato in seguito a tali modi che.
A(2;8)
u
1 u
2
u
2= 2 2u1+u2= 4
4u1+u2= 1
u
1= 2
Figura 1. Regione di ammissibilita di (10){(15).
2.(1) Il problema in forma standard e max z= x1 x2 2x3 soggetto a
2x1 +x2 +x3 +x4 = 8 3x1 +x2 x3 x5 = 4
x
1
;:::;x
5
0;
con x5 variabile di surplus. Per i particolari coecienti in funzione obiettivo, la base B0 =fx4;x5grisulta ottima, benche non ammissibile. Si puo quindi partire dalla riformulazione
max z= 0 x1 x2 2x3
x
4= 8 2x1 x2 x3
x
5= 4 +3x1 +x2 x3
x
1
;:::;x
5
0; B0 =fx4;x5g;
da questo punto, avendo ottimalita duale, si puo procedere utilizzando ilsimplesso duale. Si sceglie quindi una variabile che causa inammissibilita (x5 < 0) come variabile uscente, e si determina la variabile entrante scegliendo il pivot duale. Si considerano percio i rapporti
13; 1 1;
tra i quali il piu piccolo in valore assoluto identi ca il pivot duale. La variabile entrante e quindix1; si ottiene allora
max z= 43 13x5 23x2 73x3
x
4= 163 23x5 13x2 53x3
x
1= 43 +13x5 13x2 +13x3
x
1
;:::;x
5
0; (B1=B0nfx5g[fx1g): La base B1 risulta ottima e ammissibile.
(2) Il duale del programma in forma standard e min 8u1+ 4u2
soggetto a
2u1+ 3u2 1
u
1+u2 1
u
1 u
2
2
u
1
0
u
2
0:
Dalla soluzione ottima del programma primale si puo dedurre la soluzione ottima del duale applicando le condizioni di complementarieta
(uA c)x= 0; e quindi
x
1
>0 =) 2u1+ 3u2= 1;
x
4
>0 =) u1= 0:
Quindi u1 = 0, u2 = 13 la funzione obiettivo del duale vale z = 134 = 43, coincidente con il valore ottimo primale, come previsto dalla teoria.
(3) L'introduzione di un vincolo in modo incrementale puo essere gestita in mo- do ecace per mezzo del simplesso duale. Il punto chiave da ricordare e che la riformulazione nale (rispetto a B1, in questo caso) continua ad essere una rap- presentazione di (1){(4). Si considera quindi un programma lineare formato dalla riformulazione e dal vincolo addizionale x4 1. Riformulando il nuovo vincolo rispetto alla baseB1si ottiene
x
4= 163 2 3x1 1
3x2 5 3x31;
cioe
23x1 1 3x2 5
3x3 13
in ne, per avere una forma standard, si aggiunge una variabile di slack3 ; y, ottenendo 23x1 1
3x2 5
3x3+y= 133:
A questo punto si introduce il vincolo nel programma lineare riformulato rispetto aB1, cony in base.
max z= 43 13x1 23x2 73x3
x
4= 163 23x1 13x2 53x3
x
1= 43 +13x1 13x2 +13x3
y= 133 +23x1 +13x2 +53x3
x
1
;:::;x
5
0; (B10 =fx4;x1;y g) e quindi
max z= 72 12y 12x2 32x3
x
4= 1 y
x
1= 72 +12y 12x2 12x3
x
5= 132 +32y 12x2 52x3
x
1
;:::;x
5
;y0; (B2=B01nfy g[fx5g): La base B2e ottima per il programma modi cato.
