Fino ad ora abbiamo affrontato problemi in cui le variabili potevano assu-mere valori reali. Ora invece ci concentreremo su problemi in cui le variabili possono assumere solo valori interi. Questi problemi vengono chiamati pro-blemi di Programmazione Lineare Intera (abbreviata con PLI nel seguito). Nel seguito ci occuperemo di alcuni risultati teorici sulla PLI e introdurremo due approcci di risoluzione per questo tipo di problemi.
6.1 Relazione tra un problema lineare intero
e il suo rilassamento lineare
Si consideri un problema di PLI in forma standard:
w∗= max cx
Ax= b
x≥ 0, x ∈ In
dove I denota l’insieme degli interi. Si indicher´a con Za la regione ammis-sibile di questo problema, e quindi
Za ={x ∈ In : Ax = b, x≥ 0}, e con Zott l’insieme delle sue soluzioni ottime:
Chiameremo rilassamento lineare del problema di PLI, il problema di PL ottenuto dal problema di PLI omettendo la richiesta che le variabili siano intere, e quindi
z∗= max cx
Ax= b
x≥ 0
Esempio 17 Si consideri il seguente problema di PLI:
max x1+ x2
x1+ 2x2≤ 4 2x1+ x2≤ 4 x1, x2≥ 0, x1, x2∈ I.
Si determinino per via grafica la soluzione del problema di PLI e del suo rilassamento lineare.
Come al solito, indicheremo con Sae Sottrispettivamente la regione ammis-sibile e l’insieme delle soluzioni ottime del rilassamento lineare del problema di PLI. Possiamo notare che
Za ⊆ Sa
e che i due problemi hanno la stessa funzione obiettivo cx. Da ci´o conse-guono le seguenti relazioni tra il problema di PLI e il problema di PL suo rilassamento lineare.
1. Se Sa =∅, allora Za=∅.
2. Se l’obiettivo del problema di PLI ´e illimitato, allora lo ´e anche quello del suo rilassamento lineare.
3. Se Sott 6= ∅ e Zott 6= ∅, allora il valore ottimo w∗ del problema di PLI non pu´o essere superiore al valore ottimo z∗del suo rilassamento lineare, ovvero
w∗≤ z∗
4. Se Sott 6= ∅ contiene un punto x∗ a coordinate tutte intere, allora x∗∈ Zotte w∗= z∗, come accade nel seguente esempio
max x2
x1+ 2x2≤ 4 2x1+ x2≤ 4 x1, x2≥ 0, x1, x2∈ I.
Altri casi possibili nelle relazioni tra un problema di PLI e il suo rilassa-mento lineare sono i seguenti.
1. Za=∅ ma Sott6= ∅, come nel seguente esempio:
max x2 x1≥1 4 x1≤3 4 x2≤ 2 x1, x2≥ 0, x1, x2∈ I.
2. Za =∅ ma l’obiettivo del rilassamento lineare ´e illimitato, come nel seguente esempio: max x2 x1≥14 x1≤3 4 x1, x2≥ 0, x1, x2∈ I.
3. Se A, b e c contengono solo valori razionali, allora Zott 6= ∅ implica Sott 6= ∅. Se vi sono coefficienti irrazionali allora pu´o accadere che Zott 6= ∅ ma il rilassamento lineare ha obiettivo illimitato, come nel seguente esempio:
max x2
x2=√ 2x1
x1, x2≥ 0, x1, x2∈ I.
dove Za (e quindi Zott) contiene la sola origine, ma l’obiettivo del rilassamento lineare ´e illimitato.
Un’importante osservazione ´e la seguente.
I problemi di PL sono in generale molto pi´u semplici e rapidi da risolvere dei problemi di PLI1. In particolare il rilassamento lineare di un problema di PLI ´e tipicamente molto pi´u facile da risolvere del problema di PLI stes-so.
Questa osservazione pu´o spingere a risolvere i problemi di PLI con la seguente procedura:
1
Nella teoria della complessit´a i problemi di PL sono classificati tra quelli risolvibili in tempo polinomiale, mentre quelli di PLI sono verosimilmente solo risolvibili in tempo esponenziale
• risolvo il rilassamento lineare del problema di PLI;
• arrotondo le variabili nella soluzione ottima che non hanno valore intero ma decimale (se ne esistono: nel caso in cui non ne esistano la soluzione del rilassamento lineare ´e anche soluzione del problema di PLI).
In realt´a questa procedura rischia di restituire risultati molto inesatti. Ad esempio, in precedenza abbiamo visto un caso dove il rilassamento linea-re ha soluzione ottima mentlinea-re il problema di PLI ha linea-regione ammissibile vuota. In tal caso, applicando la procedura vista sopra, restituiremmo una soluzione ottima per un problema che non ha neppure una soluzione ammis-sibile. Va detto comunque che una procedura di questo tipo ´e accettabile quando si ha a che fare con variabili che assumono valori molto elevati. Se nella soluzione ottima del rilassamento lineare ho una variabile con valore pari a 20000.4 e la arrotondo a 20000, posso introdurre un errore ma essen-do la parte decimale (0.4) quasi irrilevante rispetto al valore 20000.4 della variabile, tale errore ´e tipicamente trascurabile. Al contrario, con variabili intere che assumono valori piccoli, ad esempio 1.4, l’arrotondamento a 1 del valore di tale variabile pu´o causare errori non trascurabili, come conse-guenza del fatto che la parte decimale (0.4) non ´e affatto irrilevante rispetto al valore di 1.4. Questo ´e in particolare vero quando si ha a che fare con variabili binarie, con le quali la procedura vista sopra va certamente evitata. Restano allora da indicare procedure di risoluzione per i problemi di PLI applicabili in tutti i casi. Nel seguito introdurremo due metodologie di ri-soluzione per problemi di PLI: gli algoritmi di taglio e gli algoritmi branch-and-bound.
6.1.1 Un’importante osservazione: trasformazione di
un problema di PLI in forma standard
Come per i problemi di PL, `e sempre possibile ricondurre un problema di PLI in forma standard. Le regole per effettuare questa trasformazione sono le stesse gi`a viste per i problemi di PL ma occorre prestare attenzione ad un ulteriore aspetto. Vediamo di illustrare questo su un semplice esempio. Si consideri il seguente problema di PLI:
max x2 x1≤ 1 2 x2≤ 1 2 x1, x2≥ 0, x1, x2∈ I.
Se avessimo a che fare con un problema di PL potremmo trasformarlo molto semplicemente nella forma standard con l’aggiunta di due variabili y1e y2:
max x2
x1+ y1= 1 2
x2+ y2= 12
x1, x2, y1, y2≥ 0, x1, x2∈ I.
In questo modo ci ritroveremmo per`o con un problema in cui alcune varia-bili (x1 e x2) possono assumere solo valori interi e altre possono assumere anche valori non interi. Infatti, ad esempio, se scelgo x1 = x2 = 0, valori ammissibili per il nostro problema di PLI, il corrispondente valore di y1e y2
`e pari a 1/2. Per ovviare a questo inconveniente e fare in modo che anche le nuove variabili possano assumere solo valori interi quando quelle originarie hanno valori interi, `e sufficiente trasformare i vincoli in modo tale che in essi compaiano solo coefficienti e termini noti interi. Nel nostro esempio basta moltiplicare entrambi i vincoli per 2:
max x2
2x1≤ 1 2x2≤ 1
x1, x2≥ 0, x1, x2∈ I. e solo a questo punto aggiungere le due variabili y1e y2:
max x2
2x1+ y1= 1 2x2+ y2= 1
x1, x2, y1, y2≥ 0, x1, x2, y1, y2∈ I.
In questo modo le variabili aggiunte y1, y2 assumono sempre valori interi quando quelle originarie x1, x2hanno valori interi e quindi nella forma stan-dard possiamo imporre l’interezza anche delle variabili y1, y2. Si noti che il funzionamento dei successivi algoritmi di risoluzione `e garantito solo se si procede alla trasformazione in forma standard nel modo sopra indicato.
6.2 Algoritmi di taglio
Per introdurre gli algoritmi di taglio dobbiamo prima introdurre il concetto di taglio valido per un problema di PLI. Sia dato un problema di PLI con
il suo rilassamento lineare. Sia x∗ una soluzione ottima del rilassamento lineare, che si suppone abbia almeno una coordinata non intera (se tutte le sue coordinate fossero intere allora x∗∈ Zott).
Definizione 12 Una disequazione wx≤ v si definisce taglio valido per il problema di PLI se non ´e soddisfatta da x∗ ma ´e soddisfatta da tutti i punti nella regione ammissibile del problema di PLI, ovvero
wx∗> v, wx≤ v ∀ x ∈ Za
Il concetto di taglio valido conduce alla definizione degli algoritmi di taglio. In essi si comincia risolvendo il rilassamento lineare del problema di PLI. Se questo ha soluzione a coordinate tutte intere, essa ´e soluzione anche del problema di PLI. Altrimenti si genera (in modi che vedremo in seguito) un taglio valido, si aggiunge questo taglio ai vincoli del rilassamento lineare e si risolve il nuovo problema di PL ottenuto con questa aggiunta. Se la soluzione ottima ha coordinate tutte intere, essa ´e soluzione anche del problema di PLI. Altrimenti si genera un nuovo taglio valido che escluda la soluzione ottima del nuovo problema di PL, si aggiunge anche questo taglio ai vincoli del rilassamento lineare e si risolve il nuovo problema di PL ottenuto con questa ulteriore aggiunta. Si itera questa procedura fino a quando non si ottiene una soluzione intera (o si stabilisce che Za = ∅). Dato il problema di PLI
max cx
aix= bi i = 1, . . . , m xj ≥ 0, xj∈ I j = 1, . . . , n
formalmente, lo schema di un algoritmo di taglio ´e il seguente. Inizializzazione Si risolva il rilassamento lineare
max cx
aix= bi i = 1, . . . , m xj≥ 0 j = 1, . . . , n
del problema di PLI. Se Sa =∅, allora Za =∅. Tralasceremo il caso di obiettivo illimitato del rilassamento lineare e quindi l’unica altra possibilit´a ´e che esista una soluzione ottima, indicata con x∗1. Si ponga k = 1.
Passo 1 Se x∗k ha coordinate tutte intere, allora si restituisca x∗k
∈ Zott. Altrimenti si vada al Passo 2.
Passo 2 Si generi un taglio valido wkx ≤ vk che non sia soddisfatto da x∗k ma sia soddisfatto da tutti i punti in Za, ovvero
wkx∗k> vk, wkx≤ vk ∀ x ∈ Za.
Passo 3 Si aggiunga il nuovo taglio valido ai vincoli originari del problema e ai tagli validi generati in precedenza e si risolva il problema di PL
max cx
aix= bi i = 1, . . . , m (6.1)
wrx≤ vr r = 1, . . . , k xj≥ 0 j = 1, . . . , n
Se tale problema ha regione ammissibile vuota possiamo concludere che Za=∅. Altrimenti sia x∗(k+1) la sua soluzione ottima.
Passo 4 Si ponga k = k + 1 e si ritorni al Passo 1.
Si noti che il problema di PL (6.1) non ´e in forma standard. Tuttavia basta la semplice aggiunta di una variabile yr≥ 0 in ciascuno dei vincoli wrx≤ vr
per ricondursi al formato standard. Con tale aggiunta il problema di PL (6.1) viene trasformato in quello equivalente (in forma standard):
max cx
aix= bi i = 1, . . . , m
wrx+ yr= vr r = 1, . . . , k (6.2)
xj≥ 0 j = 1, . . . , n yr≥ 0 r = 1, . . . , k
Resta ancora da chiarire come si genera un taglio valido. Ci sono molti modi per generare tagli validi. Qui descriveremo un tipo di tagli detti tagli di Gomory.
6.2.1 Tagli di Gomory
Supponiamo di avere una base ottima B∗ ={xi1, . . . , xim} per il rilassa-mento lineare del problema di PLI. La riformulazione rispetto a tale base ´e la seguente:
max γ0+Pn−mj=1 γjxim+j
· · ·
xik = βk+Pn−mj=1 αkjxim+j
· · ·
xim= βm+Pn−mj=1 αmjxim+j
x1, . . . , xn≥ 0
Si suppone che almeno uno dei valori βr, r = 1, . . . , m, sia non intero (se fossero tutti interi la soluzione di base associata a B∗ sarebbe non solo ottima per il rilassamento lineare ma anche per il problema di PLI). Sia βk
un tale valore non intero. Scriviamo l’equazione relativa a xik:
xik = βk+ αk1xim+1+ αk2xim+2+· · · + αk,n−mxin. (6.3) Si consideri ora il seguente taglio, detto taglio di Gomory:
−fk+ fk1xim+1+ fk2xim+2+· · · + fk,n−mxin≥ 0 dove fkj, j = 1, . . . , n− m, ´e la mantissa di −αkj, cio´e
fkj=−αkj− ⌊−αkj⌋ ≥ 0
(⌊a⌋ rappresenta la parte intera di a ovvero il pi´u grande intero ≤ a), mentre fk ´e la mantissa di βk, cio´e
fk= βk− ⌊βk⌋ > 0,
dove fk> 0 ´e una conseguenza della non interezza di βk. Per mantenere il formato standard, possiamo aggiungere una nuova variabile y1 e riscrivere il taglio attraverso la seguente coppia di vincoli:
y1=−fk+ fk1xim+1+ fk2xim+2+· · · + fk,n−mxin (6.4) y1≥ 0.
Vogliamo dimostrare la seguente osservazione.
Osservazione 16 Il taglio di Gomory ´e un taglio valido.
Dimostrazione Per prima cosa dimostriamo che la soluzione ottima del rilassamento lineare non soddisfa questo vincolo. Notiamo che per tale so-luzione ottima si ha xim+1 =· · · = xin= 0 (tutte le variabili fuori base sono nulle) e quindi, in corrispondenza della soluzione ottima del rilassamento lineare si ha:
Quindi la soluzione ottima del rilassamento lineare non soddisfa, come de-siderato, il nostro taglio. Resta da far vedere che il taglio ´e soddisfatto da ogni punto in Za. Prendiamo un generico punto
(xi1, . . . , xin)
in Za. Sostituiamo le coordinate di tale punto in (6.3) e (6.4) ed otteniamo rispettivamente
xik = βk+ αk1xim+1+ αk2xim+2+· · · + αk,n−mxin. (6.5) y1=−fk+ fk1xim+1+ fk2xim+2+· · · + fk,n−mxin. (6.6) Ci´o che si vuole dimostrare ´e che il valore di y1´e≥ 0 e cio´e che la generica soluzione ammissibile in Za
xi1, . . . , xin (6.7)
soddisfa il taglio. Per prima cosa dimostriamo che in corrispondenza di ogni punto (6.7) in Za si ha che il valore di y1 ´e intero. Per dimostrare questo sommiamo (6.5) e (6.6). Ricordando la definizione delle fkj e di fk, la somma ha come risultato
y1=⌊βk⌋ − xik− ⌊−αk1⌋xim+1− ⌊−αk2⌋xim+2− · · · − ⌊−αk,n−m⌋xin
Questo mostra che in corrispondenza di ogni punto in Za il valore y1´e un valore intero (le parti intere sono tutti valori interi e le variabili xike xim+j, j = 1, . . . , n− m in Za assumono valori interi).
Da (6.6) abbiamo anche che y1+ fk= fk1 |{z} ≥0 xim+1 | {z } ≥0 + fk2 |{z} ≥0 xim+2 | {z } ≥0 +· · · + fk,n−m | {z } ≥0 xin |{z} ≥0 .
Questo ci dice che, in corrispondenza di ogni punto (6.7) di Za, si ha che y1+ fk ´e ≥ 0 ed inoltre sappiamo che 0 < fk < 1. Infine, in precedenza abbiamo dimostrato che y1 assume valori interi in corrispondenza di ogni punto di Za. Tutto questo ´e possibile soltanto se y1≥ 0 in corrispondenza di ogni punto di Za, come si voleva dimostrare.
La coppia di vincoli
y1=−fk+ fk1xim+1+ fk2xim+2+· · · + fk,n−mxin
che esprime il taglio viene aggiunta alla riformulazione rispetto alla base ottima B∗ e si ottiene quindi:
max γ0+Pn−mj=1 γjxim+j xi1 = β1+Pn−mj=1 α1jxim+j · · · xik = βk+Pn−mj=1 αkjxim+j (6.8) · · · xim= βm+Pn−mj=1 αmjxim+j y1=−fk+ fk1xim+1+ fk2xim+2+· · · + fk,n−mxin x1, . . . , xn, y1≥ 0
Si noti come (6.8) sia gi´a la riformulazione del nuovo problema di PL ri-spetto alla base B∗
∪ {y1}. La soluzione di base del primale associata a questa base ´e non ammissibile (la variabile y1 ha valore −fk < 0), come deve essere visto che il taglio deve rendere non ammissibile la soluzione del rilassamento lineare. Tuttavia la soluzione di base del duale associata a B∗
∪ {y1} ´e ammissibile (i valori γj continuano ad essere non positivi visto che non sono stati modoficati dall’introduzione del taglio). Questo ci consente di risolvere il nuovo problema di PL con il simplesso duale e con base iniziale B∗∪ {y1}. Si avr´a anche che la prima variabile ad uscire di base sar´a la y1. Perch´e?
Si noti anche come durante la dimostrazione dell’Osservazione 16 abbiamo anche dimostrato che la nuova variabile che viene introdotta (la y1) assu-me sempre valori interi in corrispondenza di ogni punto di Za. In pratica il risultato di interezza su y1 ci consente di dire che (6.8) con l’ulteriore imposizione
x1, . . . , xn, y1∈ I
`e una riformulazione equivalente del problema di PLI iniziale (dove per equivalente si intende che Za e Zott restano invariati). Pi´u in generale, iterando quanto visto, si ha che (6.2) con l’ulteriore imposizione
x1, . . . , xn, y1, . . . , yk ∈ I
`e sempre una riformulazione equivalente del problema di PLI iniziale. Que-sto consente di iterare la procedura, cio´e se dopo l’aggiunta del primo taglio e la risoluzione del nuovo problema di PL (6.8) non si ha ancora una solu-zione intera, possiamo generare un nuovo taglio utilizzando la stessa regola di generazione.
Ma vediamo ora di chiarire meglio il funzionamento di un algoritmo di ta-glio che utilizza tagli di Gomory applicandolo ad un problema di esempio.
Si consideri il seguente problema di PLI: max x1+ x2 2x1+ x3= 3 2x2+ x4= 3 x1, x2, x3, x4≥ 0 x1, x2, x3, x4∈ I.
Una base otttima per il rilassamento lineare di questo problema di PLI ´e la base B∗ ={x1, x2}. La riformulazione del rilassamento lineare rispetto a questa base ´e la seguente:
max 3− 1/2x3− 1/2x4
x1= 3/2− 1/2x3 (6.9)
x2= 3/2− 1/2x4
x1, x2, x3, x4≥ 0
Come si vede c’´e un termine noto non intero quindi la soluzione del rilas-samento lineare:
x∗1= x∗2= 3/2 x∗3 = x∗4= 0
non risolve il problema di PLI. A questo punto aggiungo un taglio di Gomory. Considero l’equazione
x1= 3/2− 1/2x3
e da questa, in base alle regole viste, si ricava il seguente taglio: −1/2 + 1/2x3≥ 0.
Aggiungendo una variabile y1il taglio viene espresso dalla seguente coppia di vincoli:
y1=−1/2 + 1/2x3, y1≥ 0.
Aggiungiamo ora questi alla riformulazione (6.9) rispetto alla base ottima B∗. max 3− 1/2x3− 1/2x4 x1= 3/2− 1/2x3 x2= 3/2− 1/2x4 y1=−1/2 + 1/2x3 x1, x2, x3, x4, y1≥ 0
Possiamo notare che questa ´e gi´a la riformulazione del nuovo problema ri-spetto alla base B∗∪ {y1} = {x1, x2, y1}. La soluzione di base del primale associata a questa base ´e non ammissibile (il valore di y1 ´e −1/2) ma la soluzione di base del duale associata alla stessa base ´e ammissibile (i coef-ficienti delle variabili fuori base nell’obiettivo non sono stati modificati e continuano ad essere negativi). Quindi possiamo applicare il simplesso dua-le con base iniziadua-le {x1, x2, y1}. Si verifica immediatamente che non sono soddisfatte n´e la condizione di ottimalit´a, n´e la condizione di illimitatezza dell’obiettivo duale. Chiaramente, la prima variabile che dovr´a entrare in base sar´a l’unica con un valore negativo e quindi dovr´a essere la y1. In base alle regole viste, l’unica variabile che potr´a entrare in base ´e la x3. Pas-seremo quindi alla base{x1, x2, x3} rispetto alla quale avremo la seguente riformulazione: max 5/2− y1− 1/2x4 x1= 1− y1 x2= 3/2− 1/2x4 (6.10) x3= 1 + 2y1 x1, x2, x3, x4, y1≥ 0
La base ´e ottima per il nuovo problema di PL ma purtroppo abbiamo ancora un termine noto non intero e quindi non abbiamo ancora una soluzione ottima del problema di PLI. Allora, dobbiamo aggiungere un ulteriore taglio di Gomory. La regola di generazione ´e la solita. Per prima cosa selezioniamo un’equazione con termine noto non intero. Qui la sola possibile ´e:
x2= 3/2− 1/2x4.
Da questa si genera, in base alle regole viste, il seguente taglio: −1/2 + 1/2x4≥ 0.
Aggiungendo una nuova variabile y2 il taglio viene espresso dalla seguente coppia di vincoli:
y2=−1/2 + 1/2x4, y2≥ 0.
Aggiungiamo ora questi alla riformulazione (6.10) rispetto alla base ottima {x1, x2, x3}.
max 5/2− y1− 1/2x4
x1= 1− y1
x3= 1 + 2y1
y2=−1/2 + 1/2x4
x1, x2, x3, x4, y1, y2≥ 0
Possiamo notare che questa ´e gi´a la riformulazione del nuovo problema ri-spetto alla base{x1, x2, x3, y2}. La soluzione di base del primale associata a questa base ´e non ammissibile (il valore di y2´e−1/2) ma la soluzione di base del duale associata alla stessa base ´e ammissibile (i coefficienti delle variabili fuori base nell’obiettivo non sono stati modificati e continuano ad essere negativi). Quindi possiamo applicare il simplesso duale con base ini-ziale{x1, x2, x3, y2}. Si verifica immediatamente che non sono soddisfatte n´e la condizione di ottimalit´a, n´e la condizione di illimitatezza dell’obietti-vo duale. Chiaramente, la prima variabile che dovr´a entrare in base sar´a l’unica con un valore negativo e quindi dovr´a essere la y2. In base alle regole viste, l’unica variabile che potr´a entrare in base ´e la x4. Passere-mo quindi alla base {x1, x2, x3, x4} rispetto alla quale avremo la seguente riformulazione: max 2− y1− y2 x1= 1− y1 x2= 1− y2 x3= 1 + 2y1 x4= 1 + 2y2 x1, x2, x3, x4, y1, y2≥ 0
La base ´e ottima per il nuovo problema di PL e tutte le variabili hanno valore intero. Abbiamo quindi la seguente soluzione ottima del problema di PLI:
x∗1= x∗2= x∗3= x∗4= 1.
Ci si pu´o chiedere se siamo stati solo fortunati oppure con i tagli di Gomory l’algoritmo di taglio termina sempre in un numero finito di iterazioni. Vale la seguente osservazione.
Osservazione 17 Se ad ogni iterazione il taglio di Gomory viene realizzato a partire dalla prima equazione con un termine noto βk non intero, allora l’algoritmo termina in un numero finito di iterazioni.
6.3 Approccio Branch-and-Bound per la Pro-grammazione Lineare Intera
Fino a questo momento abbiamo considerato la risoluzione dei problemi di PLI attraverso l’introduzione successiva di piani di taglio. Ora con-sidereremo un nuovo approccio di risoluzione basato sulla suddivisione del problema originale in sottoproblemi. L’approccio prende il nome di Branch-and-Bound. I concetti fondamentali di tale approccio verranno dapprima illustrati su un particolare problema di PLI ed in seguito generalizzati a tutti i problemi di PLI.
6.3.1 Branch-and-Bound: un esempio
Si consideri il seguente problema di PLI che verr´a indicato nel seguito come problema P0 P0 : max x1+ 3x2 (u1) x1≥ 12 (u2) x1+7 5x2≤132 (u3) −5x1+ 3x2≤ 5 x1, x2≥ 0 x1, x2∈ I
Vediamo di risolvere il rilassamento lineare di P0, indicato con P′
0, ovvero il problema ottenuto rimuovendo da P0 i vincoli di interezza sulle variabili x1e x2 P0′ : max x1+ 3x2 (u1) x1≥ 12 (u2) x1+7 5x2≤132 (u3) −5x1+ 3x2≤ 5 x1, x2≥ 0
Essendo il problema in due sole variabili, la risoluzione viene fatta gra-ficamente. Per problemi con pi´u di due variabili si ricorre all’algoritmo del simplesso. Dalla Figura 6.1 si vede che la regione ammissibile di P′
000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 000000000000000000000000000000 111111111111111111111111111111 111111111111111111111111111111 111111111111111111111111111111 111111111111111111111111111111 111111111111111111111111111111 111111111111111111111111111111 111111111111111111111111111111 111111111111111111111111111111 111111111111111111111111111111 111111111111111111111111111111 111111111111111111111111111111 111111111111111111111111111111 111111111111111111111111111111 111111111111111111111111111111 111111111111111111111111111111 111111111111111111111111111111 111111111111111111111111111111 111111111111111111111111111111 111111111111111111111111111111 111111111111111111111111111111 u1 u2 A B C D + -z u3 1 1 2 3 4 5 6 2 4 3
Figura 6.1: Il rilassamento lineare P′
0di P0, con regione ammissibile ABCD.
rappresentata dal politopo ABCD i cui vertici sono i punti A µ 5 4, 15 4 ¶ B µ 1 2, 5 2 ¶ C µ 1 2, 0 ¶ D µ 13 2 , 0 ¶ ´
E immediato verificare che l’unica soluzione ottima di P′
0 ´e il vertice A dove la funzione obiettivo ha valore pari a 50
4. Se il vertice A avesse coor-dinate intere sarebbe anche un punto di ottimo per il problema P0, ma nel nostro esempio ci´o non accade. Fino a questo punto non abbiamo so-stanziali differenze rispetto agli algoritmi di taglio visti in precedenza. A questo punto un algoritmo di taglio procederebbe introducendo un nuovo vincolo che non ´e soddifatto dal vertice ottimo di P′
soddisfatto da tutte le soluzioni ammissibili di P0. Qui per´o adottiamo un approccio diverso. Suddividiamo il problema P0in due sottoproblemi P1e P2 ottenuti aggiungendo in ciascuno un vincolo di forma semplice (ovvero una limitazione sui valori di una singola variabile) che esclude il vertice A. In P1 si aggiunge il vincolo che una delle variabili a valore frazionario in A sia non superiore alla parte intera di tale valore, mentre in P2si aggiunge il vincolo che la stessa variabile sia non inferiore alla parte intera dello stesso valore incrementata di uno. Nel nostro esempio in A sono frazionari i va-lori di entrambe le variabili. Come regola di scelta si adotta qui quella di prendere la variabile con indice minimo e quindi, nel nostro caso, x1(si noti che tale regola non ´e l’unica possibile ed altre pi´u sofisticate possono essere adottate, ad esempio scegliere quella con parte frazionaria pi´u elevata). In base a quanto detto in P1 si aggiunger´a il vincolo x1≤¥54
¦
= 1, mentre in P2verr´a aggiunto il vincolo x1≥¥5
4
¦
+ 1 = 2. I due sottoproblemi saranno quindi i seguenti: P1 : max x1+ 3x2 (u1) x1≥ 12 (u2) x1+7 5x2≤132 (u3) −5x1+ 3x2≤ 5 (u′ 4) x1≤¹ 5 4 º = 1 x1, x2≥ 0 x1, x2∈ I P2 : max x1+ 3x2 (u1) x1≥12 (u2) x1+7 5x2≤ 132 (u3) −5x1+ 3x2≤ 5 (u′′ 4) x1≥¹ 5 4 º + 1 = 2 x1, x2≥ 0 x1, x2∈ I In Figura 6.2 ´e rappresentato il rilassamento lineare P′
1 di P1, ottenuto rimuovendo i vincoli di interezza da P1. In Figura 6.3 ´e rappresentato il
rilassamento lineare P′
2 di P2. Le regioni ammissibili di P′
1 (il politopo CBEF ) e P′
2 (il politopo GHD) sono parti (disgiunte) della regione am-missibile di P′
0. La loro unione contiene tutte le soluzioni ammissibili di P0
ma non coincide con la regione ammissibile di P′
0in quanto manca la zona 1 < x1< 2 nella quale si trova il vertice ottimo A di P0′.
000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 111 u1 u2 u3 B C D + -z A E F 1 1 2 3 4 5 6 2 3 4 u′ 4
Figura 6.2: Il rilassamento lineare P′
1di P1, con regione ammissibile ABEF .
L’unica soluzione ottima di P′
1´e il vertice E ¡1,10 3
¢
con valore ottimo pari a 1 + 310
3 = 11. Si noti che E non ha coordinate intere e quindi non ´e una soluzione ammissibile per il problema originario P0. L’unica soluzio-ne ottima del problema P′