Fino a ora abbiamo affrontato problemi lineari in cui le variabili potevano as-sumere valori reali. Ora invece ci concentreremo su problemi in cui le variabili possono assumere solo valori interi. Questi problemi vengono chiamati problemi 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.
7.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 ∈ Zn
dove Z denota l’insieme degli interi. Si indicher`a con Za la regione ammissibile di questo problema, e quindi
Za={x ∈ Zn : Ax = b, x≥ 0}, e con Zottl’insieme delle sue soluzioni ottime:
Zott={x∗∈ Za : cx∗ ≥ cx ∀ x ∈ Za}.
Chiameremo rilassamento lineare del problema di PLI, il problema di PL ot-tenuto dal problema di PLI omettendo la richiesta che le variabili siano intere,
e quindi
z∗= max cx Ax = b
x≥ 0
Esempio 27 Si consideri il seguente problema di PLI: max x1+ x2
x1+ 2x2≤ 4 2x1+ x2≤ 4 x1, x2≥ 0, x1, x2∈ Z.
Si determinino per via grafica la soluzione del problema di PLI e del suo rilas-samento lineare.
Come al solito, indicheremo con Sae Sottrispettivamente la regione ammissibile 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 conseguono 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∗ Infatti: ¯ x∈ Zott ⇒ ¯x ∈ Za ⇒ ¯x ∈ Sa ⇒ ⇒ c¯x ≤ cx∗ per x∗∈ Sott.
4. Se Sott6= ∅ contiene un punto x∗a coordinate tutte intere, allora x∗ ∈ Zott
e w∗= z∗. Infatti
x∗∈ Sott ⇒ cx∗≥ cx ∀ x ∈ Sa ⇒ cx∗≥ cx ∀ x ∈ Za
x∗ a coordinate intere ⇒ x∗∈ Za
e quindi x∗∈ Zott. Una situazione del genere si ha nel seguente esempio max x2
x1+ 2x2≤ 4 2x1+ x2≤ 4 x1, x2≥ 0, x1, x2∈ Z.
Altri casi possibili nelle relazioni tra un problema di PLI e il suo rilassamento 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∈ Z.
2. Za = ∅ ma l’obiettivo del rilassamento lineare `e illimitato, come nel seguente esempio: max x2 x1≥1 4 x1≤34 x1, x2≥ 0, x1, x2∈ Z.
3. Se A, b e c contengono solo valori razionali, allora Zott6= ∅ implica Sott6= ∅. Se vi sono coefficienti irrazionali allora pu`o accadere che Zott6= ∅ ma il rilassamento lineare ha obiettivo illimitato, come nel seguente esempio:
max x2
x2=√ 2x1
x1, x2≥ 0, x1, x2∈ Z.
dove Za (e quindi Zott) contiene la sola origine, ma l’obiettivo del rilassa-mento 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 stesso.
Questa osservazione pu`o spingere a risolvere i problemi di PLI con la seguente procedura:
• 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).
1
Nella teoria della complessit`a, che tratteremo nel Capitolo 10, i problemi di PL sono classificati tra quelli risolvibili in tempo polinomiale, mentre quelli di PLI sono verosimilmente solo risolvibili in tempo esponenziale
In realt`a questa procedura rischia di restituire risultati molto inesatti. Ad es-empio, in precedenza abbiamo visto un caso dove il rilassamento lineare ha soluzione ottima mentre il problema di PLI ha regione ammissibile vuota. In tal caso, applicando la procedura vista sopra, restituiremmo una soluzione ot-tima 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 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 essendo 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 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 applica-bili in tutti i casi. Le vedremo nei capitoli successivi. Prima di esse, affrontiamo un ulteriore argomento teorico che ci permetter`a di individuare sottoclassi di problemi di PLI pi`u semplici rispetto ai generici problemi di PLI.
7.2 Chiusure convesse e sottoclassi speciali della
PLI
Come gi`a accennato in precedenza e come vedremo pi`u in dettaglio nel Capitolo 10, i problemi di PLI sono molto pi`u difficili da risolvere rispetto ai problemi di PL. In particolare il rilassamento lineare di un problema di PLI `e generalmente risolvibile in tempi molto pi`u rapidi rispetto al problema di PLI stesso. Questo fatto viene sfruttato algoritmicamente, visto che sia gli algoritmi di taglio che quelli branch-and-bound per la risoluzione di problemi di PLI si basano sulla risoluzione multipla di problemi di PLI (come vedremo nei Capitoli 8 e 9). In questo capitolo partendo dalla definizione di un problema di PL equivalente a un problema di PLI, basata sul concetto di chiusura convessa, arriveremo a identificare sottoclassi ‘facili’ dei problemi di PLI. In particolare, si tratter`a di problemi di PLI risolvibili come problemi di PL semplicemente rimuovendo i vincoli di interezza sulla variabili.
7.2.1 Problemi di PLI e chiusure convesse
Supponiamo di avere il nostro problema di PLI max
x∈Za
La relazione tra regione ammissibile Za del problema di PLI e regione ammissi-bile Sa del suo rilassamento lineare `e la seguente
Za = Sa∩ Zn
Diamo ora la definizione di chiusura convessa di un insieme.
Definizione 1 Dato un insieme T , la chiusura convessa di T , indicata con conv(T ), `e il pi`u piccolo insieme convesso (si veda la Definzione 1) contenente T .
In Figura 7.1 `e riportato un insieme T e la sua chiusura convessa. Si consideri
l l l l l l l l conv(T) T
Figura 7.1: Un insieme T e la sua chiusura convessa.
ora la chiusura convessa conv(Za) di Za. Si pu`o dimostrare che, se Za 6= ∅, conv(Za) `e un poliedro, cio`e esiste una matrice A′ ed un vettore b′ tale che
conv(Za) ={x ∈ Rn: A′x≤ b′, x≥ 0}. (7.2) Si consideri ora il seguente problema di PL
max
x∈conv(Za)cx (7.3)
Si pu`o dimostrare che:
• il problema (7.1) ammette soluzione se e solo se la ammette il problema (7.3);
• ogni soluzione ottima del problema (7.1) `e soluzione ottima del problema (7.3);
• esiste almeno una soluzione ottima (di base) del problema (7.3) che `e anche soluzione ottima del problema (7.1).
Questo vuol dire che se conoscessimo la matrice A′ed il vettore b′che definiscono conv(Za), potremmo risolvere il nostro problema di PLI risolvendo il problema di PL (7.3). Il problema `e che in molti casi conv(Za) non `e noto e determinarlo `e difficile almeno quanto risolvere il problema di PLI stesso. Citiamo anche il fatto che in alcuni casi conv(Za) `e noto ma `e formato da un numero esponenziale di vincoli, il che pu`o rendere inefficiente la risoluzione del problema (7.3).
Esempio 28 Si consideri il seguente problema di PLI, max x1+ x2 x1+1 2x2≤ 74 1 2x1+ x2≤ 74 x1, x2≥ 0 interi Si ha Sa={(x1, x2) : Ax≤ b, x1, x2≥ 0}, con A = 1 1 2 1 2 1 b = 7 4 7 4 . L’insieme Za = Sa∩ Z2`e formato dai quattro punti
(0, 0) (0, 1) (1, 0) (1, 1) Si ha che
conv(Za) ={(x1, x2) : x1≤ 1, x2≤ 1, x1, x2≥ 0}. (vedi Figura 7.2). In tal caso
A′ = 1 0 0 1 b′ = 1 1 .
Si noti che indipendentemente dalla funzione obiettivo i problemi (7.1) e (7.3) hanno sempre soluzione in questo caso. Con la funzione obiettivo x1+ x2 en-trambi i problemi hanno l’unica soluzione (1, 1). Se si considera invece l’obiettivo x1, si ha che il problema (7.1) ha soluzioni (1, 0) e (1, 1), mentre il problema (7.3) ha come soluzioni l’intero segmento avente come estremi (1, 0) e (1, 1). `E comunque sempre vero che esiste almeno una soluzione del problema (7.3) che `e anche soluzione del problema (7.1).
Dopo aver chiarito cosa sia la chiusura convessa di un insieme e l’importanza di tale chiusura per i problemi di PLI, ci concentreremo ora su speciali sottoclassi di problemi di PLI, quelli per cui la chiusura convessa di Za= Sa∩ Zncoincide con Sa, la regione ammissibile del rilassamento lineare, ovvero
conv(Za) = conv(Sa∩ Zn) = Sa. (7.4) Si noti che nell’esempio precedente ci`o non era vero. I problemi di PLI per cui si verifica questa condizione sono importanti perch`e sono molto pi`u semplici da risolvere rispetto agli altri problemi di PLI. Infatti, essendo conv(Za) = Sa e viste le strette relazioni tra le soluzioni dei problemi (7.1) e (7.3), possiamo risol-vere tali problemi semplicemente eliminando i vincoli di interezza sulle variabili, ovvero risolvendo il problema di PL
max
x∈Sa
HH HH HH HH HH HH HH HH HH HH HH HH HH HH A A A A A A A A A A A A A A A A A A A A A A A A A A A conv(S) P
Figura 7.2: La chiusura convessa di Za per l’esempio considerato.
Come detto e come chiariremo meglio nel Capitolo 10 i problemi di PL sono molto pi`u semplici da risolvere dei problemi di PLI e quindi le sottoclassi di problemi di PLI che soddisfano la condizione vista sono in generale molto pi`u semplici da risolvere dei generici problemi di PLI. Inoltre, in molti casi questi problemi hanno strutture particolari che consentono di risolverli attraverso al-goritmi specifici che sono per lo pi`u specializzazioni di metodi per risolvere problemi di PL (come il metodo del simplesso e le sue varianti), dove la partico-lare struttura dei problemi consente di implemementare in modo pi`u efficiente i passi di tali metodi.
Nel seguito mostreremo importanti sottoclassi per cui la condizione (7.4) `e soddisfatta.
7.2.2 Matrici totalmente unimodulari
Prima di approfondire ulteriormente il discorso sui problemi per cui conv(Za) = Sa, introduciamo il concetto di matrice totalmente unimodulare.
Definizione 2 Una matrice A si dice totalmente unimodulare (TU nel seguito) se ogni sua sottomatrice quadrata ha determinante pari a 0, +1 o -1.
Si noti che una matrice TU pu`o avere come elementi solo i valori 0, +1 e -1 visto che ogni suo elemento `e una particolare sottomatrice quadrata di ordine 1× 1. Si citano di seguito alcune propriet`a delle matrici TU.
Propriet´a 1 Se A `e una matrice TU si ha che 1. AT `e TU
2. [A I], dove I `e la matrice identica, `e TU
3. una matrice ottenuta duplicando righe e/o colonne di A `e ancora TU 4. una matrice ottenuta moltiplicando righe e/o colonne di A per -1 `e ancora
TU
5. una matrice ottenuta scambiando righe di A (oppure colonne di A) tra loro `e ancora TU
6. una matrice ottenuta da A mediante un’operazione di cardine `e ancora TU Ci chiediamo ora come sia possibile riconoscere una matrice TU senza dover cal-colare i determinanti di tutte le sottomatrici quadrate. Esistono alcune regole, tra cui la seguente.
Osservazione 19 Sia A una matrice i cui elementi sono tutti uguali a 0, +1 o -1 e lungo ogni colonna non vi sono pi`u di due elementi diversi da 0. Allora A `e TU se e solo se l’insieme delle righe di A pu`o essere suddiviso in due sottinsiemi Q1 e Q2 tali che se una colonna contiene due elementi diversi da 0 si ha che:
• se i due elementi hanno lo stesso segno allora una delle due righe in cui si trovano `e in Q1 e l’altra in Q2;
• se hanno segno opposto le righe corrispondenti sono entrambe contenute in Q1 od entrambe in Q2.
Esempio 29 Sia A la seguente matrice
A = 1 1 0 0 0 0 1 1 1 0 1 0 0 1 0 1
Prendendo Q1 = {1, 2} e Q2 = {3, 4} si verifica immediatamente che la con-dizione `e soddisfatta e quindi A `e TU.
Corollario 1 Sia A una matrice i cui elementi sono tutti uguali a 0, +1 o -1 e lungo ogni colonna non vi sono pi`u di due elementi diversi da 0. Se nelle colonne con due elementi diversi da 0 la somma di tali elementi `e uguale a 0 (ovvero un elemento `e uguale a +1 e l’altro a -1), allora A `e TU.
Dimostrazione `E sufficiente utilizzare l’Osservazione 19 ponendo Q1={tutte le righe di A} Q2=∅.
Il corollario ci dice che vale la seguente osservazione.
Osservazione 20 Tutte le matrici di incidenza nodo-arco di un grafo orientato e anche tutte le matrici ottenute da queste rimuovendone alcune righe sono matrici TU.
Esempio 30 Sia A la seguente matrice
A = 1 1 0 0 0 −1 1 1 −1 0 0 0 0 0 0 −1
In base al corollario tale matrice `e TU. Se si rimuove una qualsiasi delle righe la matrice ottenuta continua a essere TU.
Un’altra osseravzione `e la seguente:
Osservazione 21 La matrice di incidenza nodo-arco per un grafo bipartito non orientato G = (V1∪ V2, A), dove V1 e V2 sono le due classi di bipartizione, `e TU.
Dimostrazione Si ricordi che per grafi non orientati la matrice di incidenza nodo-arco `e una matrice con entrate pari a 0 o 1, con tante righe quanti sono i nodi del grafo e tante colonne quanti sono gli archi del grafo. Lungo la colonna relativa ad un arco (i, j) ∈ A la matrice ha un +1 all’altezza delle righe i e j e 0 in tutte le altre righe. Per dimostrare il corollario `e sufficiente utilizzare l’Osservazione 19 ponendo
Q1= V1 Q2= V2.
Ma perch´e sono importanti le matrici TU? La loro importanza `e legata a questo teorema (non dimostrato).
Teorema 6 Sia
e
Za(b1, b2, b3) = Sa(b1, b2, b3)∩ Zn,
con b1, b2, b3 vettori di interi. Si dimostra che A1, A2, A3 sono TU se e solo se per tutti i vettori di interi b1, b2, b3 per cui Sa(b1, b2, b3)6= ∅ si ha che
conv(Za(b1, b2, b3)) = Sa(b1, b2, b3).
La conseguenza principale di questo teorema `e che la soluzione di un problema di PLI con matrici dei vincoli TU e vettori dei termini noti interi pu`o essere ottenuta semplicemente eliminando i vincoli di interezza.
Esempio 31 Si consideri il seguente problema max x1+ x2+ x3+ x4 x1+ x2= 2 −x1+ x3= 4 −x2+ x4= 3 −x3− x4= 2 x1, x2, x3, x4≥ 0 interi
Il problema di PL ottenuto eliminando i vincoli di interezza ha regione ammis-sibile Sa(b3) ={x ∈ Rn: A3x = b3, x≥ 0} con A3= 1 1 0 0 −1 0 1 0 0 −1 0 1 0 0 −1 −1 e b3= 2 4 3 2
Si pu`o verificare attraverso il Corollario 1 che A3`e TU. Essendo b3un vettore di interi, il problema di PLI pu`o essere risolto eliminando semplicemente i vincoli di interezza.
Questi risultati coi consentono ora di dimostrare la seguente osservazione. Osservazione 22 I problemi di:
• flusso a costo minimo • flusso massimo • trasporto
• assegnamento
sono tutti risolvibili come problemi di PL rimuovendo i vincoli di interezza sulla variabili.
Dimostrazione Le Osservazioni 1-3 e le Osservazioni 20-21 mostrano che le matrici dei vincoli di questi problemi sono tutte TU, mentre per definizione dei problemi tutti i termini noti sono interi.