1.1 Il problema dello zaino

1 Programmazione Lineare Intera

Fino ad ora abbiamo affrontato problemi in cui le variabili potevano assumere valori reali. Ora invece ci concentreremo su problemi in cui le variabili posso- no assumere solo valori interi. Per prima cosa vedremo un paio di esempi di problemi reali in cui le variabili possono assumere solo valori interi.

1.1 Il problema dello zaino

Sono dati n tipi di oggetti. Agli oggetti di tipo i, i = 1, . . . , n, sono associati un peso p i e un valore v i . ´ E inoltre dato uno zaino con capacit´ a pari a b. Il problema dello zaino consiste nel decidere quanti oggetti di ciascun tipo inserire nello zaino, tenendo conto che non si pu´ o superare la capacit´ a dello zaino e che si vuole massimizzare il valore complessivo degli oggetti inseriti. Agli oggetti di tipo i associo una variabile x i che rappresenta il numero di oggetti di tipo i da inserire nello zaino. Si noti che tali variabili saranno necessariamente non negative e possono assumere solo valori interi. Abbiamo un unico vincolo nel problema, quello di non superare la capacit´ a b dello zaino. Tale vincolo ´ e espresso dalla seguente disequazione:

n

X

i=1

p i x i ≤ b.

L’obiettivo, da massimizzare, ´ e rappresentato dalla seguente formula:

n

X

i=1

v i x i .

Quindi il modello del problema ´ e il seguente

max P n

i=1 v _i x _i P n

i=1 p i x i ≤ b

x _i ≥ 0, x i ∈ I i = 1, . . . , n

dove I indica l’insieme degli interi. Esiste anche una variante del problema, detta problema dello zaino binario, in cui esiste un solo esemplare di ogni tipo di oggetto e quindi le variabili x i possono assumere i due soli valori 0 (se non si inserisce l’oggetto i) oppure 1 (se lo si inserisce). Variabili che possono assumere due soli valori vengono dette binarie. Il modello ´ e il seguente:

max P n

i=1 v i x i

P n

i=1 p _i x _i ≤ b

x i ≥ 0, x i ∈ {0, 1} i = 1, . . . , n

Esempio 1 Si supponga di avere tre tipi 1,2 e 3 di oggetti, con pesi p 1 = 5 p 2 = 7 p 3 = 9

e valori

v 1 = 11 v 2 = 14 v 3 = 18.

Si supponga inoltre di avere uno zaino con capacit´ a pari a 18. Il modello per il problema dello zaino ´ e il seguente:

max 11x 1 + 14x 2 + 18x 3

5x 1 + 7x 2 + 9x 3 ≤ 18 x ₁ , x ₂ , x ₃ ≥ 0, x 1 , x ₂ , x ₃ ∈ I

mentre per il problema dello zaino binario l’unica differenza ´ e rappresentata dal fatto che le variabili possono assumere i soli valori 0 e 1:

max 11x 1 + 14x 2 + 18x 3

5x 1 + 7x 2 + 9x 3 ≤ 18 x 1 , x 2 , x 3 ≥ 0, x 1 , x 2 , x 3 ∈ {0, 1}

1.2 Problemi di produzione e distribuzione di prodotti

Supponiamo di avere m negozi che hanno bisogno di un certo prodotto e n centri di produzione dove tale prodotto pu´ o essere realizzato. Avremo inoltre le seguenti indicazioni.

• Il negozio i richiede una quantit´a pari ad a i unit´ a di prodotto.

• Il centro di produzione j ha la possibilit´a di realizzare fino ad un massimo di M j unit´ a di prodotto.

• Trasportare un’unit´a di prodotto dal centro di produzione j al negozio i ha un costo pari a c ij .

• Attivare il centro di produzione j ha un costo fisso pari a k j . Tale costo interviene se si produce anche una sola unit´ a di prodotto nel centro di produzione j ed ´ e indipendente dalla quantit´ a prodotta (si pensi ai costi di attivazione dei macchinari che sono gli stessi sia che si produca una sola unit´ a di prodotto, sia che se ne producano migliaia).

Il problema consiste nel decidere, per ogni centro di produzione j e negozio i,

quante unit´ a di prodotto realizzare nel centro di produzione j perch´ e siano in-

viate al negozio i, tenuto conto che si devono soddisfare le richieste di tutti i

negozi, non si possono superare le capacit´ a produttive dei singoli centri e che si

vuole realizzare il tutto minimizzando i costi.

Per prima cosa identifichiamo le variabili del problema. Per ogni coppia ne- gozio i, i = 1, . . . , m, e centro di produzione j, j = 1, . . . , n, definiremo una variabile x ij che rappresenta le unit´ a di prodotto realizzate nel centro di pro- duzione j per essere inviate al negozio i. Tali variabili sono ovviamente non negative e possono assumere solo valori interi. Oltre a tali variabili, introducia- mo anche delle variabili binarie y j da associare a ciascun centro di produzione.

La variabile y j assumer´ a valore 0 se il centro di produzione j non viene attivato, ovvero non viene realizzato alcun prodotto in esso, mentre assume il valore 1 se il centro viene attivato.

Per esprimere il vincolo che deve essere soddisfatta la richiesta a i di prodotti del negozio i, richiederemo che la somma dei prodotti realizzati nei vari centri di produzione j per il negozio i sia pari ad a _i , il che corrisponde alla seguente equazione:

n

X

j=1

x _ij = a _i .

Nel centro di produzione j la quantit´ a massima di prodotto realizzabile ´ e pari a 0 se il centro non viene attivato (ovvero se y _j = 0) ed ´ e pari a M _j se il centro viene attivato (ovvero se y _j = 1). Il vincolo sul massimo numero di prodotti realizzabili nel centro j ´ e quindi rappresentato dalla seguente disequazione:

m

X

i=1

x _ij ≤ M j y _j .

Per quanto riguarda i costi, avremo dei costi di trasporto dai centri di produzione j ai negozi i rappresentati dalla seguente espressione:

m

X

i=1 n

X

j=1

c ij x ij .

A questi dovremo aggiungere i costi fissi k j per i soli centri di produzione j attivati (per i quali cio´ e si ha y j = 1). Tali costi sono rappresentati dalla seguente espressione

n

X

j=1

k j y j .

(Si noti che i centri di produzione non attivati, cio´ e con y j = 0, non portano alcun contributo a tali costi). I costi complessivi sarano dati dalla somma di costi di trasporto e costi fissi:

m

X

i=1 n

X

j=1

c ij x ij +

n

X

j=1

k j y j .

Tabella 1:

N 1 N 2 N 3

C1 2 1 5

C2 1 5 3

C3 4 3 1

C4 2 3 3

Quindi il modello del problema ´ e il seguente:

min P m i=1

P n

j=1 c ij x ij + P n j=1 k j y j

P n

j=1 x _ij = a _i i = 1, . . . , m P m

i=1 x ij ≤ M j y j j = 1, . . . , n

x _ij ≥ 0, x ij ∈ I i = 1, . . . , m, j = 1, . . . , n y j ∈ {0, 1} j = 1, . . . , n

Esempio 2 Si considerino 3 negozi N 1, N 2, N 3 di elettrodomestici con ri- chieste di lavatrici pari rispettivamente a 500, 700 e 800. Si considerino inoltre 4 centri di produzione C1, C2, C3, C4 con capacit´ a di produzione massima pari rispettivamente a 1500, 2000, 2500 e 2500. I costi per trasportare una sin- gola lavatrice da un centro di produzione Cj ad un negozio N i sono riportati in Tabella 1, mentre i costi fissi per i centri di produzione sono rispettivamente pari a 100, 150, 150 e 200. Il modello risultante ´ e il seguente:

min 2x 11 + x 12 + 4x 13 + 2x 14 + x 21 + 5x 22

3x 23 + 3x 24 + 5x 31 + 3x 32 + 1x 33 + 3x 34

100y 1 + 150y 2 + 150y 3 + 200y 4

tenuto conto che

x 11 + x 12 + x 13 + x 14 = 500 x ₂₁ + x ₂₂ + x ₂₃ + x ₂₄ = 700 x 31 + x 32 + x 33 + x 34 = 800 x 11 + x 21 + x 31 ≤ 1500y 1

x ₁₂ + x ₂₂ + x ₃₂ ≤ 2000y 2

x 13 + x 23 + x 33 ≤ 2500y 3

x ₁₄ + x ₂₄ + x ₃₄ ≤ 2500y 4

x ij ≥ 0, x ij ∈ I i = 1, 2, 3 j = 1, 2, 3, 4

y 1 , y 2 , y 3 , y 4 ∈ {0, 1}

1.3 Uso delle variabili binarie per modellare vincoli logici

Le variabili binarie vengono utilizzate per modellare decisioni del tipo ”fare o non fare una cosa”, ”svolgere o non svolgere un’attivit´ a”. Data la variabile binaria x, ad essa si associa il valore 0 se si decide di non fare una cosa e il valore 1 se si decide di farla. Tali variabili vengono spesso utilizzate per modellare vincoli di tipo logico attraverso equazioni o disequazioni. Nel seguito verranno dati alcuni esempi di questo. Il vincolo logico ”se non svolgo l’attivit´ a 1 allora non svolgo neppure l’attivit´ a 2” pu´ o essere espresso tramite il vincolo

x ₂ ≤ x 1

dove x 1 e x 2 sono ovviamente le variabili binarie associate rispettivamente alle attivit´ a 1 e 2. Il vincolo logico ”se svolgo l’attivit´ a 3 allora svolgo almeno una tra le attivit´ a 4 e 5” pu´ o essere espresso tramite il vincolo

x 3 ≤ x 4 + x 5

Il vincolo logico ”se svolgo l’attivit´ a 6 allora devo svolgere sia l’attivit´ a 7 che l’attivit´ a 8 ” pu´ o essere espresso tramite il vincolo

2x 6 ≤ x 7 + x 8

oppure attraverso la coppia di vincoli

x ₆ ≤ x 7 x ₆ ≤ x 8 .

1.4 Relazione tra un problema lineare intero e il suo ri- lassamento lineare

Si consideri un problema di Programmazione Lineare Intera (abbreviato con PLI nel seguito) in forma canonica:

w ^∗ = max c ^T x A ^T x ≤ b x ≥ 0, x ∈ I ⁿ

dove ricordiamo che I denota l’insieme degli interi. Si indicher´ a con Z _a la regione ammissibile di questo problema, e quindi

Z a = {x ∈ I ⁿ : A ^T x ≤ b, x ≥ 0}, e con Z ott l’insieme delle sue soluzioni ottime:

Z ott = {x ^∗ ∈ Z a : c ^T x ^∗ ≥ c ^T x ∀ x ∈ Z a }.

Chiameremo rilassamento lineare del problema di PLI, il problema di Pro- grammzaione Lineare Ordinaria (abbreviato con PLO nel seguito) ottenuto dal problema di PLI omettendo la richiesta che le variabili siano intere, e quindi

z ^∗ = max c ^T x A ^T x ≤ b

x ≥ 0 Esempio 3 Si consideri il seguente problema di PLI:

max x 1 + x 2

x 1 + 2x 2 ≤ 4 2x ₁ + x ₂ ≤ 4 x 1 , x 2 ≥ 0, x 1 , x 2 ∈ I.

Si determinino per via grafica la soluzione del problema di PLI e del suo rilas- samento lineare.

Come al solito, indicheremo con S _a e S _ott rispettivamente la regione ammissibile e l’insieme delle soluzioni ottime del problema di PLO. Possiamo notare che

Z _a ⊆ S a

e che i due problemi hanno la stessa funzione obiettivo c ^T x. Da ci´ o conseguono le seguenti relazioni tra il problema di PLI e il problema di PLO suo rilassamento lineare.

1. Se S a = ∅, allora Z a = ∅.

2. Se l’obiettivo del problema di PLI ´ e illimitato, allora lo ´ e anche quello del suo rilassamento lineare.

3. Se S ott 6= ∅ e Z ott 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 S _ott 6= ∅ contiene un punto x ^∗ a coordinate tutte intere, allora x ^∗ ∈ Z ott

e w ^∗ = z ^∗ , come accade nel seguente esempio

max x 2

x 1 + 2x 2 ≤ 4

2x 1 + x 2 ≤ 4

x ₁ , x ₂ ≥ 0, x ₁ , x ₂ ∈ I.

Altri casi possibili nelle relazioni tra un problema di PLI e il suo rilassamento lineare sono le seguenti.

1. Z a = ∅ ma S ott 6= ∅, come nel seguente esempio:

max x 2

x ₁ ≥ ¹ ₄ x 1 ≤ ³ ₄ x ₂ ≤ 2

x 1 , x 2 ≥ 0, x 1 , x 2 ∈ I.

2. Z _a = ∅ ma l’obiettivo del rilassamento lineare ´e illimitato, come nel seguente esempio:

max x ₂

x 1 ≥ ¹ ₄ x 1 ≤ ³ ₄

x ₁ , x ₂ ≥ 0, x ₁ , x ₂ ∈ I.

3. Se A, b e c contengono solo valori razionali, allora Z _ott 6= ∅ implica S ott 6= ∅.

Se vi sono coefficienti irrazionali allora pu´ o accadere che Z _ott 6= ∅ ma il rilassamento lineare ha obiettivo illimitato, come nel seguente esempio:

max x 2

x ₂ = √ 2x ₁ x 1 , x 2 ≥ 0, x 1 , x 2 ∈ I.

dove Z a (e quindi Z ott ) contiene la sola origine, ma l’obiettivo del rilassa- mento lineare ´ e illimitato.

Un’importante osservazione ´ e la seguente.

I problemi di PLO sono in generale molto pi´ u semplici da risolvere dei pro- blemi di PLI ¹ . In particolare il rilassamento lineare di un problema di PLI ´ e tipicamente molto pi´ u facile da risolvere del problema di PLI stesso.

Questa osservazione pu´ o spingere a risolvere i problemi di PLI con la seguente procedura:

• risolvo il rilassamento lineare del problema di PLI;

1

Nella teoria della complessit´ a i problemi di PLO sono classificati tra quelli risolvibili

in tempo polinomiale, mentre quelli di PLI sono verosimilmente solo risolvibili in tempo

esponenziale

• 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 esem- pio, in precedenza abbiamo visto un caso dove il rilassamento lineare ha soluzio- ne ottima mentre il problema di PLI ha regione ammissibile vuota. In tal caso, applicando la procedura vista sopra, restituiremmo una soluzione ottima per un problema che non ha neppure una soluzione ammissibile. Va detto comunque che una procedura di questo tipo ´ e accettabile quando si ha a che fare con varia- bili 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 essendo la parte decimale (0.4) quasi irrilevante rispet- to 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’ar- rotondamento a 1 del valore di tale variabile pu´ o causare errori non trascurabili, come conseguenza 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 appli- cabili in tutti i casi. Una di queste verr´ a vista nel seguito.

1.5 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 ^∗ ∈ Z ott ).

Definizione 1 Una disequazione w ^T x ≤ v si definisce taglio valido per il pro- blema di PLI se non ´ e soddisfatta da x ^∗ ma ´ e soddisfatta da tutti i punti nella regione ammissibile del problema di PLI, ovvero

w ^T x ^∗ > v w ^T x ≤ v ∀ x ∈ Z a

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 problema

di PLO 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, si aggiunge anche questo taglio ai vincoli del rilassamento

lineare e si risolve il problema di PLO ottenuto con questa ulteriore aggiunta. Si itera questa procedura fino a quando non si ottiene una soluzione intera. Dato il problema di PLI

max c ^T x

a ^T _i x ≤ b i i = 1, . . . , m x j ≥ 0, x j ∈ I j = 1, . . . , n formalmente, lo schema di un algoritmo di taglio ´ e il seguente.

Inizializzazione Si risolva il rilassamento lineare max c ^T x

a ^T _i x ≤ b i i = 1, . . . , m x j ≥ 0 j = 1, . . . , n

del problema di PLI. Se S _a = ∅, allora Z a = ∅. Tralasceremo il ca- so di obiettivo illimitato del rilassamento lineare e quindi l’unica altra possibilit´ a ´ e che esista una soluzione ottima, indicata con x ^∗ ₁ . Si ponga k = 1.

Passo 1 Se x ^∗ _k ha coordinate tutte intere, allora si restituisca x ^∗ _k ∈ Z ott . Altri- menti si vada al Passo 2.

Passo 2 Si generi un taglio valido w _k ^T x ≤ v k che non sia soddisfatto da x ^∗ _k ma sia soddisfatto da tutti i punti in Z a , ovvero

w ^T _k x ^∗ _k > v k w ^T _k x ≤ v k ∀ x ∈ Z a .

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 PLO

max c ^T x

a ^T _i x ≤ b i i = 1, . . . , m w _r ^T x ≤ v r r = 1, . . . , k

x _j ≥ 0 j = 1, . . . , n

Se tale problema ha regione ammissibile vuota possiamo concludere che Z a = ∅. Altrimenti sia x ^∗ k+1 la sua soluzione ottima.

Passo 4 Si ponga k = k + 1 e si ritorni al Passo 1.

Resta ancora da chiarire come si genera un taglio valido. Ci sono molti modi

per generare tagli validi. Qui ne descriveremo un paio con alcune considerazioni

sull’efficienza. In entrambi i casi si richiede di compiere la seguente operazione,

fondamentale per il funzionamento della procedura, prima di iniziare a risolvere il problema:

tutti i coefficienti e termini noti dei vincoli devono essere resi interi.

Ad esempio, nel problema di PLI

max x 1 + x 2

x ₁ ≤ ³ ₂ x 2 ≤ ³ ₂

x 1 , x 2 ≥ 0, x 1 , x 2 ∈ I.

dovremo moltiplicare entrambi i vincoli per 2 in modo da rendere tutti i coeffi- cienti e i termini noti interi, ottenendo quindi il problema:

max x 1 + x 2

2x 1 ≤ 3 2x 2 ≤ 3

x 1 , x 2 ≥ 0, x 1 , x 2 ∈ I.

Questa trasformazione garantisce che le variabili u i che verranno associate a ciascun vincolo saranno anch’esse vincolate ad assumere valori interi quando le x j assumono valori interi, la qual cosa non si pu´ o garantire senza la trasfor- mazione. Nell’esempio verranno aggiunte ai due vincoli le variabili u 1 e u 2 nel modo seguente

max x ₁ + x ₂

u 1 = 3 − 2x 1

u ₂ = 3 − 2x 2

x 1 , x 2 , u 1 , u 2 ≥ 0, x 1 , x 2 , u 1 , u 2 ∈ I.

dove u 1 , u 2 ∈ I non avrebbe potuto essere garantito senza la trasformazione.

1.6 Tagli di Dantzig

Supponiamo di aver risolto il rilassamento lineare e di aver ottenuto con la base ottima {y 1 , . . . , y n } la soluzione di base

y j = 0 j = 1, . . . , n y n+i = β i i = 1, . . . , m

a coordinate non tutte intere (ovvero almeno uno dei β i non ´ e intero). Questo

ci dice che fissando tutte le variabili in base a 0 non otteniamo una soluzione a

coordinate intere. Quindi per entrare in Z a almeno una delle variabili in base

Tabella 2:

u 1 u 2

x ₁ -1/2 0 3/2

x 2 0 -1/2 3/2

z -1/2 -1/2 3

deve avere valore positivo. Essendo tali variabili vincolate ad assumere valori interi, questo equivale a dire che almeno una delle variabili deve assumere valore

≥ 1, o, equivalentemente, che la somma delle variabili in base deve essere ≥ 1.

Da ci´ o possiamo scrivere il seguente taglio valido detto taglio di Dantzig.

y 1 + · · · + y n ≥ 1.

Vediamo di ricavare il taglio di Dantzig per il nostro esempio. Applicando l’algoritmo del simplesso si arriva alla Tabella 2 che ´ e la tabella ottima. La soluzione ottima x ^∗ ₁ = 3/2, x ^∗ ₂ = 3/2 del rilassamento lineare ha coordinate non intere. Quindi posso introdurre un taglio. In base a quanto visto il taglio di Dantzig si ottiene ponendo ≥ 1 le variabili in base, cio´e

u 1 + u 2 ≥ 1.

Possiamo anche esprimere questo vincolo nelle variabili originarie x 1 e x 2 . Ri- cordando che u 1 = 3 − 2x 1 e u 2 = 3 − 2x 2 si ha che il vincolo equivale a:

2x 1 + 2x 2 ≤ 5.

Come controllo si verifichi che il taglio non ´ e soddisfatto dalla soluzione ottima x ^∗ ₁ = 3/2, x ^∗ ₂ = 3/2 del rilassamento lineare ma ´ e soddisfatto da tutti i punti in Z _a . A questo punto l’algoritmo di taglio prescrive di aggiungere il taglio ai vincoli precedenti e risolvere il problema ottenuto in questo modo. Per fare ci´ o aggiungiamo una nuova variabile u ₃ da associare al taglio, ponendo

u ₃ = u ₁ + u ₂ − 1.

A questo punto abbiamo gi´ a pronta la tabella relativa alla base {u 1 , u 2 } del nuo- vo problema. Infatti sar´ a sufficiente aggiungere alla Tabella 2 una riga relativa alla variabile u 3 come mostrato in Tabella 3. Si nota immediatamente che la base {u 1 , u 2 } non ´e ammissibile (come deve essere perch´e sia tagliata la solu- zione ottima del rilassamento lineare), ma l’ultima riga continua ad avere valori negativi e quindi la base corrispondente del duale {x 1 , x 2 , u 3 } ´e ammissibile.

Questo ci consente di utilizzare l’algoritmo del simplesso duale. Applicando ta-

le algoritmo si giunge alla Tabella 4 che ´ e ottima. La soluzione ottima x ^∗ ₁ = 1,

x ^∗ ₂ = 3/2 del nuovo problema ha una coordinata non intera. Quindi devo intro-

durre un nuovo taglio di Dantzig. In base a quanto visto il taglio di Dantzig si

Tabella 3:

u 1 u 2

x ₁ -1/2 0 3/2

x 2 0 -1/2 3/2

u 3 1 1 -1

z -1/2 -1/2 3

Tabella 4:

u ₃ u ₂ x 1 -1/2 1/2 1

x 2 0 -1/2 3/2

u 1 1 -1 1

z -1/2 0 5/2

ottiene ponendo ≥ 1 le variabili in base, cio´e u ₃ + u ₂ ≥ 1.

Possiamo anche esprimere questo vincolo nelle variabili originarie x 1 e x 2 . Ri- cordando che u 3 = u 1 + u 2 − 1, u 1 = 3 − 2x 1 e u 2 = 3 − 2x 2 si ha che il vincolo equivale a:

2x 1 + 4x 2 ≤ 7.

Come controllo si verifichi che il taglio non ´ e soddisfatto dalla soluzione ottima x ^∗ ₁ = 1, x ^∗ ₂ = 3/2 del nuovo problema ma ´ e soddisfatto da tutti i punti in Z a . A questo punto l’algoritmo di taglio prescrive di aggiungere il taglio ai vincoli precedenti e risolvere il problema ottenuto in questo modo. Per fare ci´ o aggiungiamo una nuova variabile u 4 da associare al taglio, ponendo

u ₄ = u ₂ + u ₃ − 1.

A questo punto abbiamo gi´ a pronta la tabella relativa alla base {u 2 , u ₃ } del nuo- vo problema. Infatti sar´ a sufficiente aggiungere alla Tabella 4 una riga relativa alla variabile u ₄ come mostrato in Tabella 5. Si nota immediatamente che la

Tabella 5:

u 3 u 2

x ₁ -1/2 1/2 1

x 2 0 -1/2 3/2

u 1 1 -1 1

u 4 1 1 -1

z -1/2 0 5/2

base {u 2 , u ₃ } non ´e ammissibile (come deve essere perch´e sia tagliata la solu- zione ottima del problema), ma l’ultima riga continua ad avere valori negativi e quindi la base corrispondente del duale {x 1 , x 2 , u 1 , u 4 } ´e ammissibile. Questo ci consente di utilizzare l’algoritmo del simplesso duale.

La procedura viene ripetuta fino a quando si ottiene una soluzione a coordinate tutte intere.

Ci si pu´ o chiedere se possiamo garantire che l’algoritmo di taglio che usa i tagli di Dantzig termina in un numero finito di iterazioni. La risposta ´ e negativa.

Si possono costruire esempi in cui anche aggiungendo infiniti tagli l’algoritmo non restitusice mai una soluzione ottima del problema di PLI. Questo mostra come i tagli di Dantzig possano essere molto inefficienti. Ci si chiede allora se esistono tagli pi´ u efficienti, per i quali ´ e possibile garantire la restituzione di una soluzione ottima in un numero finito di iterazioni. Tagli di questo tipo sono i tagli di Gomory, che ci apprestiamo a descrivere.

1.7 Tagli di Gomory

Supponiamo di essere giunti alla tabella ottima del rilassamento lineare relativa alla base {y 1 , . . . , y n } e di avere che la soluzione di base corrispondente ha almeno una variabile fuori base con valore non intero. Sia y n+k una tale variabile e sia la seguente la riga relativa a y _n+k nella tabella ottima:

y _n+k | α k1 α _k2 · · · α kn | β k

con β k ≥ 0 e non intero. Si ricordi che il significato di tale riga ´e il seguente y n+k = α k1 y 1 + α k2 y 2 + · · · + α kn y n + β k . (1) Si consideri ora il seguente taglio, detto taglio di Gomory

f k1 y 1 + f k2 y 2 + · · · + f kn y n − f k ≥ 0 dove f _kj , j = 1, . . . , n, ´ e la mantissa di −α kj , cio´ e

f _kj = −α kj − b−α kj c ≥ 0

( bac rappresenta la parte intera di a ovvero il pi´u grande intero ≤ a), mentre f k ´ e la mantissa di β k , cio´ e

f k = β k − bβ k c > 0,

dove f k > 0 ´ e una conseguenza della non interezza di β k . Possiamo associare

come di consueto a questo taglio una nuova variabile y n+m+1 nel modo seguente

y _n+m+1 = f _k1 y ₁ + f _k2 y ₂ + · · · + f kn y _n − f k (2)

ed il nostro taglio equivale a richiedere che si abbia y _n+m+1 ≥ 0.

Vogliamo dimostrare la seguente osservazione.

Osservazione 1 Il taglio di Gomory ´ e un taglio valido.

Dimostrazione Per prima cosa dimostriamo che la soluzione ottima del rilas- semento lineare non soddisfa questo vincolo. Notiamo che per tale soluzione ottima si ha y 1 = · · · = y n = 0 e quindi

y n+m+1 = −f k < 0.

Quindi la soluzione ottima del rilassamento lineare non soddisfa, come desidera- to, il nostro taglio. Resta da far vedere che il taglio ´ e soddisfatto da ogni punto in Z a . Prendiamo un generico punto

y ₁ , . . . , y _n , y _n+1 , . . . , y _n+m

in Z _a . Sostiuiamo le coordinate di tale punto in (1) e (2) ed otteniamo rispet- tivamente

y _n+k = α _k1 y ₁ + α _k2 y ₂ + · · · + α kn y _n + β _k . (3) y _n+m+1 = f k1 y ₁ + f k2 y ₂ + · · · + f kn y _n − f k . (4) Ci´ o che si vuole dimostrare ´ e che il valore di y _n+m+1 ´ e ≥ 0 e cio´e che la generica soluzione ammissibile in Z a

y ₁ , . . . , y _n , y _n+1 , . . . , y _n+m (5) soddisfa il taglio. Per prima cosa dimostraimo che in corrispondenza di ogni punto (5) in Z a si ha che il valore di y _n+m+1 ´ e intero. Per dimostrare questo sommiamo (3) e (4). Ricordando la definizione delle f kj e di f k , la somma ha come risultato

y _n+m+1 = −y n+k − b−α k1 cy 1 − b−α k2 cy 2 − · · · − b−α kn cy n + bβ k c Questo mostra che in corrispondenza di ogni punto in Z _a il valore y _n+m+1 ´ e un valore intero (le parti intere sono tutti valori interi e le variabili y _j , j = 1, . . . , n;

in Z _a assumono valori interi).

Da (4) abbiamo anche che y _n+m+1 + f _k = f _k1

|{z}

≥0

y ₁

|{z}

≥0

+ f _k2

|{z}

≥0

y ₂

|{z}

≥0

+ · · · + f kn

|{z}

≥0

y _n

|{z}

≥0

.

Questo ci dice che, in corrispondenza di ogni punto (5) di Z _a , si ha che y _n+m+1 +

f _k ´ e ≥ 0 ed inoltre sappiamo che 0 < f k < 1 e in precedenza abbiamo dimostra-

to che y _n+m+1 assume valori interi in corrispondenza di ogni punto di Z _a . Ci´ o

Tabella 6:

u 1 u 2

x ₁ -1/2 0 3/2

x 2 0 -1/2 3/2

u 5 1/2 0 -1/2

z -1/2 -1/2 3

´

e possibile soltanto se y _n+m+1 ≥ 0 in corrispondenza di ogni punto di Z a , come si voleva dimostrare.

Vediamo ora di applicare l’algoritmo di taglio con i tagli di Gomory nell’esempio visto in precedenza. Fino alla risoluzione del rilassamento lineare non ci sono differenze rispetto a quanto visto con i tagli di Dantzig. Quindi riprendiamo con la Tabella 2 ottima per il rilassamento lineare. Si nota che la soluzione ottima non ha coordinate tutte intere. Per generare un taglio di Gomory dobbiamo considerare una riga con un β k non intero. Per convenzione prendiamo la prima dall’alto e quindi la riga relativa alla variabile x 1 . Il taglio ´ e definito come segue:

 1 2 −  1

2



u ₁ + (0 − b0c)u 2 −  3 2 −  3

2



≥ 0, cio´ e

1 2 u 1 − 1

2 ≥ 0.

Ricordando la definizione di u ₁ possiamo definire questo taglio in funzione delle variabili originarie, ottenendo

x ₁ ≤ 1.

Si pu´ o verificare che il taglio non ´ e soddisfatto dalla soluzione ottima x ^∗ ₁ = 3/2, x ^∗ ₂ = 3/2 del rilassamento lineare, ma ´ e soddisfatto da tutti i punti di Z a . A questo punto l’algoritmo di taglio prescrive di aggiungere il taglio ai vincoli precedenti e risolvere il problema ottenuto in questo modo. Per fare ci´ o aggiungiamo una nuova variabile u 5 da associare al taglio, ponendo

u ₅ = 1 2 u ₁ − 1

2

A questo punto abbiamo gi´ a pronta la tabella relativa alla base {u 1 , u 2 } del nuo-

vo problema. Infatti sar´ a sufficiente aggiungere alla Tabella 2 una riga relativa

alla variabile u 5 come mostrato in Tabella 6. Si nota immediatamente che la ba-

se {u 1 , u 2 } non ´e ammissibile (come deve essere perch´e sia tagliata la soluzione

ottima del rilassamento lineare), ma l’ultima riga ha valori negativi e quindi la

base corrispondente del duale {x 1 , x ₂ , u ₅ } ´e ammissibile. Questo ci consente di

utilizzare l’algoritmo del simplesso duale. Applicando tale algoritmo si ottiene

la Tabella 7 che ´ e ottima. Si nota che la soluzione ottima non ha coordinate

Tabella 7:

u 5 u 2

x ₁ -1 0 1

x 2 0 -1/2 3/2

u 1 2 0 1

z -1 -1/2 5/2

Tabella 8:

u ₅ u ₂

x 1 -1 0 1

x 2 0 -1/2 3/2

u 1 2 0 1

u ₆ 0 1/2 -1/2 z -1 -1/2 5/2

tutte intere (x ^∗ ₂ = 3/2). Per generare un taglio di Gomory prendiamo la prima riga dall’alto con un β k non intero e quindi la riga relativa alla variabile x 2 . Il taglio ´ e definito come segue:

(0 − b0c)u 5 +  1 2 −  1

2



u 2 −  3 2 −  3

2



≥ 0, cio´ e

1 2 u 2 − 1

2 ≥ 0.

Ricordando la definizione di u 2 possiamo definire questo taglio in funzione delle variabili originarie, ottenendo

x 2 ≤ 1.

Si pu´ o verificare che il taglio non ´ e soddisfatto dalla soluzione ottima x ^∗ ₁ = 1, x ^∗ ₂ = 3/2 del problema appena risolto, ma ´ e soddisfatto da tutti i punti di Z _a . A questo punto l’algoritmo di taglio prescrive di aggiungere il taglio ai vincoli precedenti e risolvere il problema ottenuto in questo modo. Per fare ci´ o aggiungiamo una nuova variabile u 6 da associare al taglio, ponendo

u 6 = 1 2 u 2 − 1

2

A questo punto abbiamo gi´ a pronta la tabella relativa alla base {u 2 , u 5 } del

nuovo problema. Infatti sar´ a sufficiente aggiungere alla Tabella 7 una riga re-

lativa alla variabile u 6 come mostrato in Tabella 8. Si nota immediatamente

che la base {u 2 , u ₅ } non ´e ammissibile (come deve essere perch´e sia tagliata la

soluzione ottima del problema precedente), ma l’ultima riga ha valori negativi e

quindi la base corrispondente del duale {x 1 , x ₂ , u ₁ , u ₆ } ´e ammissibile. Questo ci

Tabella 9:

u 5 u 6

x ₁ -1 0 1

x 2 0 -1 1

u 1 2 0 1

u 2 0 2 1

z -1 -1 2

consente di utilizzare l’algoritmo del simplesso duale. Applicando tale algoritmo si ottiene la Tabella 9 che ´ e ottima. La soluzione ha coordinate tutte intere e quindi l’algoritmo si arresta restituendo come soluzione ottima x ^∗ ₁ = 1 e x ^∗ ₂ = 1 con valore ottimo pari a 1. Ci si pu´ o chiedere se siamo stati solo fortunati op- pure con i tagli di Gomory l’algoritmo di taglio termina sempre in un numero finito di iterazioni. Vale la seguente osservazione.

Osservazione 2 Se ad ogni iterazione il taglio di Gomory viene realizzato a

partire dalla prima riga dall’alto con un β _k non intero, allora l’algoritmo ter-

mina in un numero finito di iterazioni.