Ottimizzazione 2223
Ottimizzazione 2223
1 Introduzione 3
1.1 Modelli Matematici . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1.1 Il problema della dieta . . . . . . . . . . . . . . . . . . 5
1.1.2 Un problema di miscelazione . . . . . . . . . . . . . . . 8
1.1.3 Un problema di pianificazione della produzione . . . . 10
1.1.4 Il problema dello zaino . . . . . . . . . . . . . . . . . . 11
1.1.5 Un problema di pianificazione . . . . . . . . . . . . . . 12
1.1.6 Un problema di scheduling del personale . . . . . . . . 14
1.1.7 Un problema di pianificazione urbana . . . . . . . . . . 16
1.1.8 Un esempio sportivo . . . . . . . . . . . . . . . . . . . 18
1.1.9 Il problema del trasporto . . . . . . . . . . . . . . . . . 19
1.1.10 Un esempio di pianificazione edilizia . . . . . . . . . . 21
1.1.11 Un esempio di modello non lineare . . . . . . . . . . . 23
1.1.12 Un altro esempio di modello non lineare . . . . . . . . 26
1.2 Esercizi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3 Programmazione lineare 49
3.1 Introduzione . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
3.2 Il metodo grafico . . . . . . . . . . . . . . . . . . . . . . . . . 51
3.2.1 Alcune osservazioni sul metodo grafico . . . . . . . . . 54
3.3 La geometria dei problemi di programmazione lineare . . . . . 68
3.4 Il Metodo del Simplesso . . . . . . . . . . . . . . . . . . . . . 73
1
INDICE 2
Introduzione
3
CAPITOLO 1. INTRODUZIONE 4
Come detto la costruzione del modello matematico consiste nel tradurre una
serie di relazioni logiche tra le grandezze reali coinvolte in termini, appunto,
matematici. Per far questo è necessario applicare leggi fisiche, economiche,
di mercato tradotte in equazioni algebriche, disequazioni, funzioni e cosı̀ via.
Poichè il modello è definito per mezzo delle relazioni che lo costituiscono è
necessario che queste siano il più indipendenti possibile dai dati introdotti
poichè un modello deve essere usato in più situazioni e con valori differenti.
I risultati numerici devono essere considerati sempre in modo critico: la loro
affidabilità dipende da molti fattori (precisione dei dati, affidabilità del soft-
ware, efficacia e stabilità dell’algoritmo numerico e altri).
Nei successivi paragrafi saranno descritti alcuni classici Problemi di Ottimiz-
zazione in diversi ambiti applicativi.
Soggetto a:
Xn
aij xj ≥ bi , i = 1, . . . , m
j=1
xj ≥ 0, j = 1, . . . , n.
Sono disponibili tre tipi di materiale ferroso le cui caratteristiche sono ripor-
tate nella seguente tabella:
Materiale ferroso A B C
Silicio (%) 4.00 1.00 0.60
Manganese (%) 0.45 0.50 0.40
Costo (e/kg.) 0.025 0.030 0.018
Inoltre si può aggiungere direttamente manganese al costo di 10 Euro al kg. Il
problema che si vuole modellare è quello di determinare il piano di produzione
che minimizza il costo del materiale utilizzato. Si vogliono cioè individuare le
quantità di materiale per ciascuno dei tre tipi A, B, o C e di manganese puro
da acquistare per produrre i 1000 pezzi richiesti, spendendo il meno possibile.
Proviamo a costruire un modello analitico per il problema. A questo scopo
introduciamo le variabili x1 , x2 , x3 , x4 , aventi il seguente significato:
x1 (≥ 0): la quantità in kg di materiale ferroso A da utilizzare;
x2 (≥ 0): la quantità in kg di materiale ferroso B da utilizzare;
x3 (≥ 0): la quantità in kg di materiale ferroso C da utilizzare;
x4 (≥ 0): la quantità in kg di manganese da utilizzare.
Abbiamo imposto che le quantità di prodotto acquistate siano dei valori non
negativi (vincoli di nonnegatività). Il costo complessivo dei materiali risulta
essere:
0.025x1 + 0.030x2 + 0.018x3 + 10x4 .
CAPITOLO 1. INTRODUZIONE 9
xi ≥ 0, i = 1, 2, 3, 4.
Le variabili x1 , x2 , x3 e x4 corrispondono alle scelte operative che il problema
reale richiede di compiere, e ciascun vincolo del modello corrisponde ad una
condizione imposta dal problema reale. Determinare i valori delle variabili in
modo che i vincoli siano soddisfatti e la funzione obiettivo assuma il minimo
valore fornisce il miglior piano di produzione.
CAPITOLO 1. INTRODUZIONE 10
xi ≥ 0, i = 1, 2, 3, 4.
wi ≤ b, i = 1, . . . , n
in quanto nessun elemento di peso superiore alla capacità b può far parte di
una soluzione e quindi ogni elemento di peso superiore a b può essere eliminato
da E. Il problema può essere scritto come un problema di massimo. Possiamo
formulare il problema come uno di programmazione lineare introducendo, per
ogni oggetto i = 1, 2, . . . , n, una variabile xi ∈ {0, 1}, con il significato che
la variabile assume valore 1 se l’elemento i-esimo appartiene al sottoinsieme
selezionato, e 0 altrimenti (si decide cioè se inserire o meno l’oggetto). La
funzione obiettivo, da massimizzare, è
n
X
Z= ci xi
i=1
CAPITOLO 1. INTRODUZIONE 12
in cui sono sommati i valori dei soli oggetti selezionati. La condizione relativa
alla capacità dello zaino diviene
n
X
wi xi ≤ b
i=1
infatti, dato che ciascuna xi può assumere solo i valori 0 o 1, nella somma
vengono considerati i pesi dei soli oggetti selezionati. La formulazione finale
del problema è la seguente
n
X
max Z = ci xi
i=1
n
X
wi xi ≤ b
i=1
xi ∈ {0, 1}.
3(x1 + x4 + x7 ) − 2(x2 + x5 + x8 ) = 0
x2 + x5 + x8 − 2(x3 + x6 + x9 ) = 0
4(x3 + x6 + x9 ) − 3(x1 + x4 + x7 ) = 0,
Turno
Fascia oraria 1 2 3 4 5 Addetti
6.00-8.00 × 40
8.00-10.00 × × 70
10.00-12.00 × × 65
12.00-14.00 × × × 80
14.00-16.00 × × 65
16.00-18.00 × × 70
18.00-20.00 × × 80
20.00-22.00 × 40
22.00-24.00 × × 50
24.00-6.00 × 15
Costo per addetto 170e 160e 175e 180e 200e
x1 + x2 ≥ 70.
e inoltre
xj ≥ 0, xj ∈ N, j = 1, . . . , 5.
Possiamo osservare che alcuni vincoli non sono necessari. Infatti i vincoli di
nonnegatività per x1 , x4 e x5 sono ridondanti in virtù del primo, dell’ottavo
e del decimo vincolo, cosı̀ come anche il terzo vincolo, a causa della presenza
del secondo (se la somma tra x1 e x2 deve essere maggiore di 70 allora è
chiaro che supera anche 65) ma anche il sesto esattamente per un motivo
analogo.
per i, j = 1, . . . , 6. Ogni xij è una variabile binaria (può assumere solo due
valori). Per esempio se fosse x11 = 1 allora tutte le variabili x1j , con j 6= 1,
e xi1 , con i 6= 1, dovrebbero essere uguali a zero. Il valore assunto da tale
insieme di variabili potrebbe essere riassunto in una matrice, per esempio la
seguente
1 0 0 0 0 0
0 0 1 0 0 0
0 0 0 0 0 1
X = . (1.1)
0 0 0 1 0 0
0 1 0 0 0 0
0 0 0 0 1 0
Indicato con cij il costo richiesto per la realizzazione della i−esima opera
nella j−esima zona, il costo complessivo richiesto risulterebbe essere
6 X
X 6
Z= cij xij (1.2)
i=1 j=1
Se la scelta fosse stata quella schematizzata dalla matrice (1.1) allora il costo
complessivo sarebbe stato pari a
può essere tradotto richiedendo che la somma degli elementi di ogni riga e di
ogni colonna della matrice X sia uguale a 1 e che gli elementi possano essere
uguali a 0 o a 1.
Riassumendo il modello matematico è il seguente
6 X
X 6
min Z = cij xij
i=1 j=1
soggetto ai vincoli
6
X
xij = 1, i = 1, . . . , 6
j=1
X6
xij = 1, j = 1, . . . , 6
i=1
xij ∈ {0, 1}.
Il costo del trasporto dei container dai magazzini ai porti è proporzionale alla
distanza percorsa dal camion che lo trasporta. I costi (in e) di trasporto per
un singolo container sono riportati nella seguente tabella:
Genova Venezia Ancona Napoli Bari
Verona 290 115 355 715 810
Perugia 380 340 165 380 610
Roma 505 530 285 220 450
Pescara 655 450 155 240 315
Taranto 1010 840 550 305 95
Lamezia 1072 1097 747 372 333
Si vuole formulare il relativo problema di ottimizzazione avendo come obiet-
tivo la minimizzazione dei costi di trasporto.
Innanzitutto associamo ad ognuno dei sei magazzini un numero intero (1=Ve-
rona, 2=Perugia, 3=Roma, 4=Pescara, 5=Taranto, 6=Lamezia) e ad ognuno
dei porti un altro numero intero (1=Genova, 2=Venezia, 3=Ancona, 4=Na-
poli, 5=Bari). Per determinare il costo complessivo del trasporto si deve
conoscere il numero di container che sono trasportati da ciascun magazzino
ad ogni porto. Definiamo pertanto le seguenti variabili nonnegative
xij = il numero di container spediti dal magazzino i al porto j,
con i = 1, . . . , 6, e j = 1, . . . , 5.
Per semplicità indichiamo con cij il costo unitario per trasportare un contai-
ner dall’i−esimo magazzino al j−esimo porto.
La funzione obiettivo, da minimizzare, è pertanto
6 X
X 5
Z= cij xij .
i=1 j=1
Z = x1 + x2 + x3 + x4 + x5 .
max Z = x1 + x2 + x3 + x4 + x5
5050x1 +880x2 +510.4x3 +178.2x4 +792x5 ≤ 80000
x1 +0.4x2 +0.3x3 +0.5x4 +0.5x5 ≤ 4
x1 +x2 +x3 −2x4 −2x5 ≥ 0.
x1 , x2 , x3 , x4 , x5 ≥ 1, variabili intere.
y = 0.2 x1
x1
x2
x2 C
R B
x1
A
Un primo vincolo è che risulti x2 ≥ 0 (la raffineria deve trovarsi infatti a nord
del porto A). Inoltre deve distare da questo più di 100 km quindi deve essere
x2 ≥ 0.
1.2 Esercizi
Esercizio 1.2.1 Una multinazionale produce biocarburanti in uno stabili-
mento composto da tre reparti: Preparazione, Purificazione ed Estrazione.
Le tipologie di carburanti sono due: il biometano ed il biodiesel. I tempi
necessari per la lavorazione di una tonnellata di prodotto sono riportati nel-
la seguente tabella, insieme alla capacità produttiva giornaliera di ciascun
reparto.
Ore di lavorazione per tonnellata Capacità
Reparto Biometano Biodiesel giornaliera (ore)
Preparazione 0.50 0.75 18
Purificazione 1.10 1.35 18
Estrazione 1.85 1.95 15
Il management intende pianificare la produzione giornaliera dei due tipi di
carburante sapendo che il biometano produce un ricavo di 500 e per tonnel-
lata, il biodiesel 590 e per tonnellata con l’obiettivo di massimizzare il ricavo
giornaliero. Si scriva il relativo modello di ottimizzazione.
per ogni turno, è riportato il numero minimo di poliziotti che devono essere
presenti in quel turno:
Turno 1 2 3 4 5 6
Orario 0 − 4 4 − 8 8 − 12 12 − 16 16 − 20 20 − 24
Num. minimo 30 25 50 40 60 35
Per esempio, nel turno 4, cioè dalle ore 12 alle ore 16, devono essere in
servizio almeno 40 poliziotti. La retribuzione dei poliziotti è di 14 euro all’ora
per i turni diurni (3, 4, 5 e 6) e di 20 euro all’ora per i turni notturni (1 e
2). Formulare il problema come problema di ottimizzazione, con l’obiettivo
di minimizzare le spese giornaliere di retribuzione dei poliziotti.
produzione dei due concimi sapendo che la quantità di concime deve essere
pari a 40.000 kg per quello di tipo A e 50.000 kg per quello di tipo B con
l’obiettivo di minimzzare i costi di produzione.
Il vettore può essere anche rappresentato come una riga utilizzando l’opera-
zione di trasposizione, che viene indicata aggiungendo T come apice:
xT = x1 x2 . . . xn−1 xn .
33
CAPITOLO 2. ALGEBRA LINEARE E POLIEDRI 34
2. xT y = y T x per ogni x, y ∈ Rn ;
bij = aji , i = 1, . . . , n, j = 1, . . . , m.
Si noti che affinchè tale prodotto abbia senso è necessario che il numero delle
colonne di A coincida con il numero delle righe di B. Quando ciò accade
le matrici si dicono conformabili, altrimenti si dicono non conformabili. Ad
esempio nel nostro caso se m 6= n allora il prodotto BA non ha senso. Ha
sempre significato considerare i prodotti AB e BA se A e B sono matrici
quadrate dello stesso ordine (m = n).
È facile verificare che il prodotto tra matrici gode della proprietà associativa
ma in generale non di quella commutativa. Vale invece la seguente proprietà:
(AB)T = B T AT .
Esempio 2.1.1 Siano A e B le seguenti matrici:
3 1 0 2 1 −1
A = −1 2 1 ; B = 0 1 1 .
3 1 1 2 1 1
Calcoliamo la matrice C = AB. L’elemento cij è uguale alla somma dei
prodotti degli elementi della i−esima riga di A per la j−esima colonna di B.
c11 = 3·2+1·0+0·2= 6
c12 = 3·1+1·1+0·1= 4
c13 = 3 · (−1) + 1 · 1 + 0 · 1 = −2
c21 = −1 · 2 + 2 · 0 + 1 · 2 = 0
c22 = −1 · 1 + 2 · 1 + 1 · 1 = 2
c23 = −1 · (−1) + 2 · 1 + 1 · 1 = 4
c31 = 3·2+1·0+1·2= 8
c32 = 3·1+1·1+1·1= 5
c33 = 3 · (−1) + 1 · 1 + 1 · 1 = −1.
CAPITOLO 2. ALGEBRA LINEARE E POLIEDRI 37
In definitiva
6 4 −2
C = 0 2 4 .
8 5 −1
Calcolando il prodotto D = BA si trova invece:
2 3 0
D= 2 3 2
8 5 2
1 0 0 ... 0
0 1 0 ... 0
. .
. . .
In = .. . . . . . . .. .
. .. ..
..
. . 0
0 ... ... 0 1
dove A11 , B11 ∈ Rp×p , A12 , B12 ∈ Rp×(n−p) , A21 , B21 ∈ R(n−p)×p e infine
A22 , B22 ∈ R(n−p)×(n−p) , con p < n, rappresentano a loro volta matrici e non
semplici elementi. Si dice cioè che A e B sono state suddivise a blocchi.
Il prodotto AB può essere calcolato utilizzando tale decomposizione delle
matrici:
A11 B11 + A12 B21 A11 B12 + A12 B22
AB = .
A21 B11 + A22 B21 A21 B12 + A22 B22
Tale modo di effettuare il prodotto tra matrici viene detto prodotto a bloc-
chi ed è molto utile quando le matrici hanno una particolare struttura (per
CAPITOLO 2. ALGEBRA LINEARE E POLIEDRI 38
esempio se uno dei blocchi è identicamente nullo oppure è uguale alla matrice
identità). Data una matrice A ∈ Rm×n , una matrice B ∈ Rh×k , 0 < h ≤ m,
0 < k ≤ n, è detta sottomatrice di A se è ottenuta da A eliminando m − h
righe ed n − k colonne. Data una matrice A ∈ Rm×n , una sottomatrice qua-
drata B di ordine k ≤ n di A è detta principale se gli elementi principali
di B sono anche gli elementi principali di A. Una sottomatrice B principale
di ordine k di A è detta principale di testa se è formata dagli elementi aij ,
i, j = 1, . . . , k.
Esiste un secondo prodotto tra vettori, il cosiddetto prodotto esterno: se
x ∈ Rn e y ∈ Rm allora viene definito nel seguente modo:
A = xy T
aij = xi yj , i = 1, . . . , n, j = 1, . . . , m.
xT y = 1 · (−1) + 2 · (−2) + 3 · 4 = 7.
allora
det A = a11 a22 − a21 a12 .
Assegnata la matrice A di ordine 3
a11 a12 a13
A = a21 a22 a23
a31 a32 a33
e prendendo i = 1 risulta
a22 a23 a21 a23 a21 a22
det A = a11 det − a12 det + a13 det .
a32 a33 a31 a33 a31 a32
2. det I = 1;
3. det AT = det A;
4. det AB = det A det B (Regola di Binet);
5. se α ∈ R allora det αA = αn det A;
6. det A = 0 se una riga (o una colonna) è nulla, oppure una riga (o una
colonna) è proporzionale ad un’altra riga (o colonna) oppure è combinazione
lineare di due (o più) righe (o colonne) di A.
CAPITOLO 2. ALGEBRA LINEARE E POLIEDRI 41
1 0 0 −3 0 2
0 1 1 0 1/2 0 +
0 0 −1 5 −1 −3 =
0 1 0 5 −1/2 −3
Otteniamo la matrice
1 0 0 −3 0 2
0 1 0 5 −1/2 −3 .
0 0 1 −5 1 3
Avendo ottenuto una matrice le cui prime tre colonne coincidono con quelle
della matrice identità abbiamo terminato il calcolo della matrice inversa di
CAPITOLO 2. ALGEBRA LINEARE E POLIEDRI 45
Se risulta
rk(A) = min {m, n}
allora si dice che la matrice ha rango pieno.
Se A è rettangolare con m ≤ n, allora un insieme di k ≤ m colonne di A
forma una sottomatrice corrispondente ad una matrice di base se:
1. le k colonne sono linearmente indipendenti;
si dice:
• combinazione affine di x(1) , . . . , x(k) se
k
X
αj = 1;
j=1
CAPITOLO 2. ALGEBRA LINEARE E POLIEDRI 46
I = x ∈ R n | aT x = b .
S1 ∩ S2 = I.
S = {x ∈ Rn | Ax = b}
C = {x ∈ Rn | Ax ≤ 0} .
P = {x ∈ Rn | Ax ≤ b} .
kxk ≤ M.
Programmazione lineare
3.1 Introduzione
I problemi di ottimizzazione, alcuni dei quali sono stati descritti nel prece-
dente capitolo, hanno la seguente forma
max Z = f (x)
(3.1)
x∈S
dove f è una funzione
f : Rn −→ R
mentre S ⊆ Rn . Una possibile variazione del problema (3.1) è che il problema
sia quello di minimizzare f (x). La funzione
Z = f (x1 , x2 , . . . , xn )
49
CAPITOLO 3. PROGRAMMAZIONE LINEARE 50
Z = c1 x1 + c2 x2 + · · · + cn xn
x2 = 3.
I punti sono quelli che si trovano al di sotto di questa, come evidenziato nella
figura.
CAPITOLO 3. PROGRAMMAZIONE LINEARE 52
x2
x2 ≤ 3
x1
x1 + x2 = 5.
x2
x1 + x2 ≤ 5
(2, 3)
(5, 0) x1
CAPITOLO 3. PROGRAMMAZIONE LINEARE 53
x2 −x1 + x2 ≤ 2
(1, 3) (2, 3)
(0, 2)
(5, 0) x1
x2
Z = 21
Z = 18
Z = 15 x1
Z = 10
CAPITOLO 3. PROGRAMMAZIONE LINEARE 54
max Z = x1 + x2
x2
•
x1
−x1 +x2 ≤ 1
2x1 −3x2 ≤ 4
x1 ≥ 0, x2 ≥ 0.
x2
(0, 1)
(2, 0) x1
−x1 +x2 ≥ 1
2x1 −3x2 ≥ 4
x1 ≥ 0, x2 ≥ 0.
allora la regione ammissibile sarebbe stata l’intersezione tra gli insiemi evi-
denziati nel seguente grafico, ovvero sarebbe stata vuota ed il problema non
avrebbe ammesso soluzione.
CAPITOLO 3. PROGRAMMAZIONE LINEARE 57
x2
(0, 1)
(2, 0) x1
x2
x1
L’insieme dei punti che soddisfa il primo vincolo è quello che non contiene
l’origine pertanto coincide con quello evidenziato in ciano. La retta x2 =
10 è parallela all’asse x1 cosicchè il secondo vincolo identifica i punti che
appartengono alla striscia delimitata dalle due rette e, intersecandola con
l’insieme già ottenuto si ottiene il seguente
x2
x1
CAPITOLO 3. PROGRAMMAZIONE LINEARE 59
x2
x1
x2
x1
x2
x1
CAPITOLO 3. PROGRAMMAZIONE LINEARE 61
max Z = x1 − x2
x1 +x2 ≥ 2
x1 +x2 ≤ 8
x1 −2x2 ≤ 0
x1 ≥ 0, x2 ≥ 0.
x2
x1
L’insieme dei punti che soddisfa il primo vincolo è quello che non contiene
l’origine pertanto coincide con quello evidenziato in ciano. La retta x1 + x2 =
8 è parallela alla retta giá tracciata e, poichè l’origine soddisfa il vincolo stesso
la regione ammissibile identificata dal secondo vincolo identifica i punti che
appartengono alla striscia delimitata dalle due rette:
CAPITOLO 3. PROGRAMMAZIONE LINEARE 62
x2
x1
x1
che rappresenta l’equazione del fascio di rette parallele alla bisettrice del
primo e terzo quadrante. Una generica retta appartente a tale fascio interseca
l’asse x2 nel punto di coordinate (0, −Z). Poichè il valore della funzione
obiettivo (cioè Z) deve essere massimizzato, la direzione di crescita è quella
verso il basso (nella direzione in cui il valore −Z diminuisce e quindi Z
aumenta) Tracciando la retta del fascio passante per l’origine (con Z = 0
quindi)
x2
x1
CAPITOLO 3. PROGRAMMAZIONE LINEARE 64
x2
Z = 8/3
x1
max Z = x1 − 2x2
x1 +x2 ≥ 4
x1 −x2 ≤ 1
x1 ≥ 1
x1 ≥ 0, x2 ≥ 0.
x2
x1
L’insieme dei punti che soddisfa il primo vincolo è quello che non contiene
l’origine pertanto coincide con quello evidenziato in ciano. La retta x1 −x2 =
1 è parallela alla bisettrice del primo e terzo quadrante e passa per il punto
di coordinate (1, 0), poichè l’origine soddisfa il vincolo la regione ammissibile
identificata dal secondo vincolo identifica i punti che si trovanp al di sopra
della retta:
x2
x1
CAPITOLO 3. PROGRAMMAZIONE LINEARE 66
x2
x1
x2
Z=0
x1
x2
Z = −1/2
x1
−3x1 + 5x2 − x3 ≤ −2
max Z = c1 x1 + c2 x2 + · · · + cn xn
ed inoltre bi ≥ 0, i = 1, . . . , m.
Le variabili xi che definiscono le incognite del problema sono dette, come
abbiamo visto, variabili decisionali. Talvolta questi problemi possono essere
CAPITOLO 3. PROGRAMMAZIONE LINEARE 69
Ax ≤ b.
max Z = cT x
Ax ≤ b
x ≥ 0.
x2
C G
A
O E F x1
Figura 3.1:
Z1 = cT x, Z2 = cT y,
Ovviamente risulta
B
•
D
• A
•
•
C
Due vertici adiacenti sono collegati attraverso un segmento che giace sulla
frontiera comune e che viene detto spigolo della regione ammissibile. Una
delle idee alla base del metodo del simplesso è la proprietà che la soluzione
ottima è sempre uno dei vertici della regione ammissibile, e inoltre se si con-
sidera un qualsiasi problema di programmazione lineare che possiede almeno
una soluzione ottima allora se un vertice non ha vertici adiacenti migliori
(valutati attraverso la funzione obiettivo), allora deve essere necessariamente
la soluzione ottima. Consideriamo infatti la seguente figura in R2 .
x2
C
A D
x1
CAPITOLO 3. PROGRAMMAZIONE LINEARE 73
x2 (0, 9)
(4, 3)
x1 ≤ 4 ⇒ 4 − x1 ≥ 0
e ponendo
x3 = 4 − x1
risulta
x3 ≥ 0
cosicchè le variabili x1 e x3 soddisfano l’equazione
x1 + x3 = 4.
diventa il seguente
x2
x4 = 0 (2, 6)
(0, 6)
x5 = 0
(4, 3)
x1 = 0
x3 = 0
(0, 0) x2 = 0 (4, 0) x1
i valori delle variabili sono desunte dalle equazioni dei vincoli scritte in forma
aumentata (3.2). Per esempio posto x1 = x2 = 0, dall’equazione del primo
vincolo si deduce x3 = 4, dal secondo x4 = 12 e dal terzo x5 = 18. Ancora,
posto x1 = 0 e x2 = 6 sempre dall’equazione del primo vincolo si ricava
x3 = 4, x4 = 0 perchè appartiene al segmento in cui x4 è nulla, mentre x5 si
CAPITOLO 3. PROGRAMMAZIONE LINEARE 77
x5 = 18 − 2x2 = 6.
Si parte da una soluzione base e si usa l’equazione (0) per calcolare il valore
della funzione obiettivo. Anche Z viene considerata come variabile sempre
in base.
Scegliere l’origine come vertice ammissibile significa porre x1 = x2 = 0 cioè
si considera come soluzione basica ammissibile (0, 0, 4, 12, 18). Appare chiaro
che inizialmente le variabili in base sono le variabili slack, i cui valori vengono
CAPITOLO 3. PROGRAMMAZIONE LINEARE 78
scelta della variabile non di base viene fatta osservando l’espressione della
funzione obiettivo:
Z = 3x1 + 5x2 .
Aumentare x1 significa che il tasso di miglioramento della funzione obiettivo
è 3, mentre per x2 è 5. Appare chiaro che conviene scegliere x2 come variabile
entrante in base.
Passo 2 della singola iterazione: Criterio di arresto.
Bisogna determinare il valore da assegnare alla variabile entrante senza che
la nuova soluzione basica esca dalla regione di ammissibilità. Il valore della
variabile non di base x1 resta zero.
(1) x1 +x3 = 4 x3 = 4
(2) 2x2 +x4 = 12 x4 = 12 − 2x2
(3) 3x1 +2x2 +x5 = 18 x5 = 18 − 2x2 .
x4 = 12 − 2x2 ≥ 0 x2 ≤ 12/2 = 6
x5 = 18 − 2x2 ≥ 0 x2 ≤ 18/2 = 9.
Quindi il valore di x2 può essere incrementato fino a 6, valore che rende la
variabile attualmente in base x4 = 0. Oltre tale valore x4 assume valore ne-
gativo violando l’ammissibilità della soluzione. Questi calcoli costituiscono
quello che è noto come test del minimo rapporto. Obiettivo di tale test è
determinare quale variabile di base assume per prima il valore zero all’au-
mentare del valore della variabile entrante. Si possono escludere da tale test
tutte quelle variabili associate ad equazioni in cui il coefficiente della varia-
bile entrante è zero oppure negativo. Quindi per ogni equazione in cui il
coefficiente della variabile entrante è strettamente positivo, il test calcola il
rapporto tra il termine noto ed il coefficiente della variabile entrante. La va-
riabile di base nell’equazione con il minimo rapporto è quella che raggiunge
per prima il valore 0 e quindi rappresenta, di fatto, la variabile uscente dalla
base. Nell’esempio fatto entra x2 ed esce x4 .
Passo 3 della singola iterazione: Ottenere la nuova BFS.
La situazione determinata dal passo 2 del metodo del simplesso è schematiz-
zata nella seguente tabella:
CAPITOLO 3. PROGRAMMAZIONE LINEARE 80
Il sistema
(0) Z −3x1 −5x2 =0
(1) x1 +x3 =4
(2) 2x2 +x4 = 12
(3) 3x1 +2x2 +x5 = 18
deve essere scritto ora in forma canonica, cioè ogni variabile in base deve
comparire solo in un’equazione e con coefficiente uguale a 1 e nell’equazione
(0) i coefficienti delle variabili in base devono essere uguali a zero. La trasfor-
mazione può avvenire effettuando delle opportune combinazioni lineari tra le
equazioni del problema attraverso il cosiddetto metodo di Gauss-Jordan.
Innanzitutto dividiamo l’equazione (2) per 2 ottenendo la nuova seconda
equazione:
1
(2′ ) x2 + x4 = 6.
2
Per eliminare il coefficiente di x2 dall’equazione (3) sommiamo all’equazione
(3) l’equazione (2′ ) moltiplicata per -2:
5
5 × (2′ ) 5x2 + x4 = 30
2
5
(0′ ) Z −3x1 + x4 = 30.
2
CAPITOLO 3. PROGRAMMAZIONE LINEARE 81
1
(2) x2 + x4 = 6 Variabile di base x2
2
(1) x3 = 4 − x1 ≥ 0 x1 ≤ 4
Il sistema
5
(0) Z −3x1 + x4 = 30
2
(1) x1 +x3 = 4
1
(2) x2 + x4 = 6
2
deve essere trasformato in modo tale che i coefficienti della colonna relativa
alla variabile entrante x1 siano uguali a quelli della colonna relativa alla va-
riabile uscente x5 , quindi bisogna rendere 1 il coefficiente di x1 nell’equazione
(3) ed eliminare quelli di x1 dalle equazioni (0) e (1). L’equazione (3) viene
divisa per 3 diventando:
1 1
(3) x1 − x4 + x5 = 2.
3 3
Il sistema è diventato
5
(0) Z −3x1 + x4 = 30
2
(1) x1 +x3 = 4
1
(2) x2 + x4 = 6
2
1 1
(3) x1 − x4 + x5 = 2.
3 3
Sommiamo all’equazione (3) la (1) moltiplicata per −1:
(1) x1 +x3 = 4 +
1 1
−1 × (3) x1 x4 − x5 = −2
3 3
1 1
(1′ ) x3 + x4 − x5 = 2
3 3
CAPITOLO 3. PROGRAMMAZIONE LINEARE 83
3
(0′ ) Z + x4 +x5 = 36.
2
Il sistema è diventato
3
(0) Z + x4 +x5 = 36 Variabile di base Z
2
1 1
(1) x3 + x4 − x5 = 2 Variabile di base x3
3 3
1
(2) x2 + x4 = 6 Variabile di base x2
2
1 1
(3) x1 − x4 + x5 = 2 Variabile di base x1 .
3 3
Dalla (1) segue che x3 = 2 quindi la nuova BFS è (2, 6, 2, 0, 0) da cui si
ottiene il valore della funzione obiettivo Z = 36 che è ottimo perchè tutti i
coefficienti dell’equazione (0)
3
Z = − x4 − x5 + 36
2
sono negativi quindi non è possibile trovare nessuna direzione di ulteriore
crescita.
x1 ≤ 3
x1 +x2 ≤ 6
−x1 +x2 ≤ 2
x1 , x2 ≥ 0.
CAPITOLO 3. PROGRAMMAZIONE LINEARE 84
Tableau iniziale
Var. x1 x2 x3 x4 x5
base Eq. Z bi
Z (0) 1 −1 −2 −1 0 0 0
x4 (1) 0 1 1 3 1 0 6
x5 (2) 0 2 3 1 0 1 15
Tableau iniziale
Var. x1 x2 x3 x4 x5
base Eq. Z bi
Z (0) 1 −1 −2 −1 0 0 0
x4 (1) 0 1 1 3 1 0 6
x5 (2) 0 2 3 1 0 1 15
Tableau iniziale
Var. x1 x2 x3 x4 x5
base Eq. Z bi
Z (0) 1 −1 −2 −1 0 0 0
x4 (1) 0 1 1 3 1 0 6 → 6/1 = 6
x5 (2) 0 2 3 1 0 1 15 → 15/3 = 5
Il criterio del minimo rapporto stabilisce che dalla base deve uscire la variabile
x5 . Evidenziamo tutti i coefficienti dell’equazione relativa alla riga di x5 :
Tableau iniziale
Var. x1 x2 x3 x4 x5
base Eq. Z bi
Z (0) 1 −1 −2 −1 0 0 0
x4 (1) 0 1 1 3 1 0 6
x5 (2) 0 2 3 1 0 1 15
CAPITOLO 3. PROGRAMMAZIONE LINEARE 86
2 1 1
(2) 3
1 3
0 3
5
Nelle operazioni sul tableau non vengono considerati i coefficienti della co-
lonna relativa a Z perchè rimangono inalterati in tutte le iterazioni.
Adesso si devono azzerare, con opportune combinazioni lineari tra le equa-
zioni, i coefficienti di x2 nelle equazioni (0) e (1).
Per quello che riguarda il coefficiente 1 nell’equazione (1) si può sottrarre
da questa l’equazione (2) che adesso presenta lo stesso coefficiente, ovvero
sommare alla stessa l’equazione (2) moltiplicata per −1:
x1 x2 x3 x4 x5 bi
(1) 1 1 3 1 0 6 +
−1 × (2) − 23 −1 − 13 0 − 13 −5 =
1 8
(1′ ) 3
0 3
1 − 13 1
x1 x2 x3 x4 x5 bi
(0) −1 −2 −1 0 0 0 +
4 2 2
2 × (2) 3
2 3
0 3
10 =
1
(0′ ) 3
0 − 13 0 2
3
10
CAPITOLO 3. PROGRAMMAZIONE LINEARE 87
Adesso i valori possono essere riportati nel tableau relativo alla prima iterata
del metodo del simplesso.
Iterazione 1
Var. x1 x2 x3 x4 x5
base Eq. Z bi
1
Z (0) 1 3 0 − 13 0 2
3 10
1 8
x4 (1) 0 3 0 3 1 − 13 1
x2 2 1 1
(2) 0 3 1 3 0 3 5
Iterazione 1
Var. x1 x2 x3 x4 x5
base Eq. Z bi
1
Z (0) 1 3 0 − 13 0 2
3 10
1 8
x4 (1) 0 3 0 3 1 − 13 1
x2 2 1 1
(2) 0 3 1 3 0 3 5
x1 x2 x3 x4 x5 bi
1 3
(1) 8
0 1 8
− 18 3
8
CAPITOLO 3. PROGRAMMAZIONE LINEARE 88
x1 x2 x3 x4 x5 bi
2 1 1
(2) 3
1 3
0 3
5 +
1
−1/3 × (1) − 24 0 − 31 − 18 1
24
− 18 =
5
(2′ ) 8
1 0 − 81 3
8
39
8
x1 x2 x3 x4 x5 bi
1
(0) 3
0 − 13 0 2
3
10 +
1 1 1 1 1
1/3 × (1) 24
0 3 8
− 24 8
=
3 1 5 81
(0′ ) 8
0 0 8 8 8
Iterazione 2
Var. x1 x2 x3 x4 x5
base Eq. Z bi
3 1 5 81
Z (0) 1 8 0 0 8 8 8
1 3
x3 (1) 0 8 0 1 8
− 18 3
8
5
x2 (2) 0 8 1 0 − 18 3
8
39
8
Siamo arrivati alla soluzione ottima (0, 39/8, 3/8, 0, 0) in cui la funzione obiet-
tivo vale Z = 81/8.
Terminiamo questo paragrafo analizzando alcune situazioni che si possono
verificare applicando il metodo del simplesso ad un problema di programma-
zione lineare.
CAPITOLO 3. PROGRAMMAZIONE LINEARE 89
Iterazione 0
Var. x1 x2 x3 x4 x5 x6
base Eq. Z bi
Z (0) 1 −5 −6 −4 0 0 0 0
x4 (1) 0 −1 3 4 1 0 0 18
x5 (2) 0 2 2 1 0 1 0 4
x6 (3) 0 3 0 2 0 0 1 8
CAPITOLO 3. PROGRAMMAZIONE LINEARE 91
Iterazione 1
Var. x1 x2 x3 x4 x5 x6
base Eq. Z bi
Z (0) 1 1 0 −1 0 3 0 12
5
x4 (1) 0 −4 0 2 1 − 32 0 12
x2 1 1
(2) 0 1 1 2 0 2 0 2
x6 (3) 0 3 0 2 0 0 1 8
Iterazione 2
Var. x1 x2 x3 x4 x5 x6
base Eq. Z bi
Z (0) 1 3 2 0 0 4 0 16
x4 (1) 0 −9 −5 0 1 −4 0 2
x3 (2) 0 2 2 1 0 1 0 4
x6 (3) 0 −1 −4 0 0 −2 1 0
Iterazione 0
Var. x1 x2 x3 x4 x5 x6
base Eq. Z bi
Z (0) 1 −6 −4 −1 −1 0 0 0
x5 (1) 0 2 1 −3 4 1 0 10
x6 (2) 0 3 1 0 5 0 1 6
Iterazione 1
Var. x1 x2 x3 x4 x5 x6
base Eq. Z bi
Z (0) 1 0 −2 −1 9 0 2 12
1 2
x5 (1) 0 0 3 −3 3 1 − 32 6
x1 1 5 1
(2) 0 1 3 0 3 0 3 2
CAPITOLO 3. PROGRAMMAZIONE LINEARE 93
Iterazione 2
Var. x1 x2 x3 x4 x5 x6
base Eq. Z bi
Z (0) 1 6 0 −1 19 0 4 24
x5 (1) 0 −1 0 −3 −1 1 −1 4
x2 (2) 0 3 1 0 5 0 1 6
x1 , x2 , x3 , x4 ≥ 0.
CAPITOLO 3. PROGRAMMAZIONE LINEARE 94
x1 , x2 , x3 , x4 , x5 , x6 , x7 ≥ 0.
Iterazione 0
Var. x1 x2 x3 x4 x5 x6 x7
base Eq. Z bi
Z (0) 1 −4 −5 −3 −5 0 0 0 0
x5 (1) 0 1 1 1 2 1 0 0 12
x6 (2) 0 3 2 −1 2 0 1 0 6
x7 (3) 0 1 0 2 0 0 0 1 10
Iterazione 1
Var. x1 x2 x3 x4 x5 x6 x7
base Eq. Z bi
7
Z (0) 1 2 0 − 11
2 0 0 5
2 0 15
x5 (1) 0 − 12 0 3
2 1 1 − 12 0 9
3
x2 (2) 0 2 1 − 12 1 0 1
2 0 3
x7 (3) 0 1 0 2 0 0 0 1 10
CAPITOLO 3. PROGRAMMAZIONE LINEARE 95
Iterazione 2
Var. x1 x2 x3 x4 x5 x6 x7
base Eq. Z bi
25 5 11 85
Z (0) 1 4 0 0 0 0 2 4 2
x5 (1) 0 − 54 0 0 1 1 − 12 − 34 3
2
x2 7 1 1 11
(2) 0 4 1 0 1 0 2 4 2
x3 1 1
(3) 0 2 0 1 0 0 0 2 5
Iterazione 2
Var. x1 x2 x3 x4 x5 x6 x7
base Eq. Z bi
25 5 11 85
Z (0) 1 4 0 0 0 0 2 4 2
x5 (1) 0 − 54 0 0 1 1 − 12 − 34 3
2
x2 7 1 1 11
(2) 0 4 1 0 1 0 2 4 2
x3 1 1
(3) 0 2 0 1 0 0 0 2 5
CAPITOLO 3. PROGRAMMAZIONE LINEARE 96
Iterazione 3
Var. x1 x2 x3 x4 x5 x6 x7
base Eq. Z bi
25 5 11 85
Z (0) 1 4 0 0 0 0 2 4 2
x4 (1) 0 − 54 0 0 1 1 − 12 − 34 3
2
x2 (2) 0 3 1 0 0 −1 1 1 4
x3 1 1
(3) 0 2 0 1 0 0 0 2 5
Anche la BFS
3
x1 = 0, x2 = 4, x3 = 5, x4 =
2
in cui la funzione obiettivo assume valore Z = 85/2, soddisfa il test di otti-
malità, pertanto estistendo due vertici ottimi significa che tutti i punti che
appartengono allo spigolo che li congiunge sono soluzione ottima.
•
−Z = −f (x)
Z = f (x) •
Ogni BFS per la nuova forma del modello ha la proprietà che x+ j = 0 oppure
x−j = 0 (oppure possono essere entrambe nulle). Nella soluzione ottenuta con
il metodo del simplesso si ha:
xj se xj ≥ 0; |xj | se xj ≤ 0;
+ −
xj = xj =
0 altrimenti, 0 altrimenti.
CAPITOLO 3. PROGRAMMAZIONE LINEARE 99
Iterazione 0
Var.
base Eq. Z x1 x2 x+
3 x−
3
x4 x5 bi
Z (0) 1 −3 −1 4 −4 0 0 0
x4 (1) 0 2 1 −1 1 1 0 4
x5 (2) 0 2 2 3 −3 0 1 9
Iterazione 1
Var.
base Eq. Z x1 x2 x+
3 x−
3
x4 x5 bi
Z (0) 1 5 3 0 0 4 0 16
x−
3 (1) 0 2 1 −1 1 1 0 4
x5 (2) 0 8 5 0 0 3 1 21
CAPITOLO 3. PROGRAMMAZIONE LINEARE 100
La soluzione è x1 = x2 = x+ −
3 = 0, x3 = 4 da cui segue
x3 = −4
e quindi la BFS è (0, 0, −4) con valore della funzione obiettivo Z = 16.
Questa tecnica ha lo svantaggio di incrementare il numero di variabili decisio-
nali rispetto al problema originale. Infatti se nessuna variabile avesse limite
inferiore il loro numero raddoppierebbe. Questo approccio può essere modi-
ficato in modo tale da aggiungere solo una variabile decisionale al modello.
Infatti ad ogni variabile non limitata inferiormente si può sostituire
lj ≤ xj ≤ Lj , lj < Lj .
0 ≤ xj − lj ≤ Lj − lj .
x′j = xj − lj ,
il vincolo
x′j ≤ Lj − lj
viene considerato come un vincolo funzionale mentre il limite inferiore
x′j = xj − lj ≥ 0,
Definiamo le variabili
cosicchè
x1 = x′1 − 10, x2 = x′2 + 1
ed il problema diventa
x′1 , x′2 ≥ 0
e quindi
max Z = 3x′1 + 5x′2 − 25
x′1 ≤ 14
2x′2 ≤ 10
3x′1 + 2x′2 ≤ 46
x′1 , x′2 ≥ 0.
1. l’origine non è (nella gran parte dei casi) un vertice ammissibile quindi il
metodo del simplesso non è applicabile in quanto manca la BFS iniziale
da cui iniziare l’esplorazione dei vertici ammissibili;
CAPITOLO 3. PROGRAMMAZIONE LINEARE 102
I Fase
max Z = −x5
x1 +5x2 −x3 +x4 = 4
x1 +2x2 +3x3 +x5 = 6
x1 , x2 , x3 , x4 , x5 ≥ 0.
CAPITOLO 3. PROGRAMMAZIONE LINEARE 103
Iterazione 1
Var. x1 x2 x3 x4
base Eq. Z x5 bi
Z (0) 1 0 0 0 0 1 0
x4 4 17 1
(1) 0 3 3 0 1 3 6
x3 1 2 1
(2) 0 3 3 1 0 3 2
Abbiamo ottenuto la soluzione ottima della I fase in cui il valore della funzio-
ne obiettivo è 0 (come era atteso), la BFS (0, 0, 2) è quella iniziale per la II
fase. Terminata la prima fase del metodo del simplesso, prima di procedere
alla successiva, si devono effettuare alcune operazioni sul tableau che è stato
ottenuto. Innanzitutto devono essere eliminate le colonne relative alle varia-
bili artificiali, inoltre deve essere sostituita la funzione obiettivo ed infine il
problema deve essere posto in forma canonica (cioè devono essere azzerati
i coefficienti della funzione obiettivo relativi alle variabili in base), quindi
eliminiamo la colonna relativa alla variabile x5 e sostituiamo l’equazione (0):
(0) Z −5x1 −x2 −6x3 = 0
Iterazione 0
Var. x1 x2 x3 x4
base Eq. Z bi
Z (0) 1 −3 3 0 0 12
x4 4 17
(1) 0 3 3 0 1 6
x3 1 2
(2) 0 3 3 1 0 2
CAPITOLO 3. PROGRAMMAZIONE LINEARE 105
Iterazione 1
Var. x1 x2 x3 x4
base Eq. Z bi
63 9 51
Z (0) 1 0 4 0 4 2
x1 17 3 9
(1) 0 1 4 0 4 2
x3 (2) 0 0 − 34 1 − 14 1
2
II Fase
max Z = 4x1 + 2x2 + x3
2x1 +x2 = 4
x1 +3x2 +3x3 = 8
x1 , x2 , x3 ≥ 0.
CAPITOLO 3. PROGRAMMAZIONE LINEARE 106
Scriviamo il tableau della iterazioni del metodo del simplesso applicato alla
I fase:
Iterazione 0
Var. x1 x2 x3
base Eq. Z x4 x5 bi
Z (0) 1 −3 −4 −3 0 0 −12
x4 (1) 0 2 1 0 1 0 4
x5 (2) 0 1 3 3 0 1 8
Iterazione 1
Var. x1 x2 x3
base Eq. Z x4 x5 bi
Z (0) 1 − 35 0 1 0 4
3
− 43
5
x4 (1) 0 3 0 −1 1 − 13 4
3
x2 1 1 8
(2) 0 3 1 1 0 3 3
CAPITOLO 3. PROGRAMMAZIONE LINEARE 107
Iterazione 2
Var. x1 x2 x3
base Eq. Z x4 x5 bi
Z (0) 1 0 0 0 1 1 0
x1 (1) 0 1 0 − 35 3
5
− 15 4
5
6
x2 (2) 0 0 1 5
− 15 2
5
12
5
Abbiamo ottenuto la soluzione ottima della I fase in cui il valore della funzione
obiettivo è 0 (come era atteso), la BFS (4/5, 12/5, 0) è quella iniziale per la
II fase. Per risolvere la seconda eliminiamo dal tableau le colonne relative
alle variabili artificiali e sostituiamo la funzione obiettivo scrivendo la nuova
l’equazione (0):
x2 6 12
(2) 0 0 1 5 5
Iterazione 0
Var. x1 x2 x3
base Eq. Z bi
Z (0) 1 0 0 −1 8
x1 (1) 0 1 0 − 35 4
5
x2 6 12
(2) 0 0 1 5 5
CAPITOLO 3. PROGRAMMAZIONE LINEARE 108
Iterazione 1
Var. x1 x2 x3
base Eq. Z bi
5
Z (0) 1 0 6 0 10
x1 1
(1) 0 1 2 0 2
x3 5
(2) 0 0 6 1 2
x4 = x1 + 3x2 − 6x3 − 6, x4 ≥ 0.
x1 + 3x2 − 6x3 − x4 = 6
Massimizzare Z = −x5
con x5 = 0. La soluzione ottima della prima fase viene utilizzata come BFS
iniziale per la seconda.
Riscriviamo ora i problemi che devono essere risolti nelle due fasi.
I Fase:
max Z = −x5
x1 +3x2 −6x3 −x4 +x5 = 6
2x1 −x2 +5x3 +x6 = 10
x1 , x2 , x3 , x4 , x5 , x6 ≥ 0,
II Fase
max Z = x1 + 4x2 + 3x3
x1 +3x2 −6x3 −x4 = 6
2x1 −x2 +5x3 +x6 = 10
x1 , x2 , x3 , x4 , x6 ≥ 0.
(0) Z +x5 = 0
(1) x1 +3x2 −6x3 −x4 +x5 = 6
(2) 2x1 −x2 +5x3 +x6 = 10
Iterazione 0
Var. x1 x2 x3 x4 x6
base Eq. Z x5 bi
Z (0) 1 −1 −3 6 1 0 0 −6
x5 (1) 0 1 3 −6 −1 1 0 6
x6 (2) 0 2 −1 5 0 0 1 10
Iterazione 1
Var. x1 x2 x3 x4 x6
base Eq. Z x5 bi
Z (0) 1 0 0 0 0 1 0 0
1
x2 (1) 0 3 1 −2 − 31 1
3 0 2
7
x6 (2) 0 3 0 3 − 13 1
3 1 12
Iterazione 0
Var. x1 x2 x3 x4 x6
base Eq. Z bi
1
Z (0) 1 3 0 −11 − 34 0 8
1
x2 (1) 0 3 1 −2 − 13 0 2
7
x6 (2) 0 3 0 3 − 13 1 12
Iterazione 1
Var. x1 x2 x3 x4 x6
base Eq. Z bi
80
Z (0) 1 9 0 0 − 23
9
11
3 52
17
x2 (1) 0 9 1 0 − 59 2
3 10
7
x3 (2) 0 9 0 1 − 19 1
3 4
Il problema che definisce la prima fase del metodo a due fasi deve essere tale
che la sua soluzione abbia tutte le variabili artificiali (in questo caso x4 e x6 )
uguali a zero, quindi:
I Fase
min Z = x4 + x6
x1 +3x3 +x4 = 6
x1 +x2 +x3 −x5 + x6 = 4
x1 , x2 , x3 , x4 , x5 , x6 ≥ 0.
In generale se il problema è di minimo si sceglie come funzione obiettivo
P
Z= variabili artificiali
ovvero tale che Z ≥ 0 ed assuma valore minimo (nullo) proprio quando le
variabili artificiali introdotte sono tutte uguali a zero.
Nella seconda fase si può applicare il metodo del simplesso alla funzione
obiettivo del problema di partenza:
II Fase
min Z = x1 + 5x2 + 4x3
x1 +3x3 = 6
x1 +x2 +x3 −x5 = 4
x1 , x2 , x3 , x5 ≥ 0.
Poichè il problema è di minimo dobbiamo trasformarlo in un problema di
massimo cambiando il segno ai due membri della funzione obiettivo in en-
trambi i problemi:
I Fase
max −Z = −x4 − x6
x1 +3x3 +x4 = 6
x1 +x2 +x3 −x5 + x6 = 4
x1 , x2 , x3 , x4 , x5 , x6 ≥ 0.
II Fase
max −Z = −x1 − 5x2 − 4x3
x1 +3x3 = 6
x1 +x2 +x3 −x5 = 4
x1 , x2 , x3 , x5 ≥ 0.
CAPITOLO 3. PROGRAMMAZIONE LINEARE 113
Iterazione 0
Var. x1 x2 x3 x5
base Eq. Z x4 x6 bi
Z (0) −1 −2 −1 −4 0 1 0 −10
x4 (1) 0 1 0 3 1 0 0 6
x6 (2) 0 1 1 1 0 −1 1 4
Iterazione 1
Var. x1 x2 x3 x5
base Eq. Z x4 x6 bi
Z (0) −1 − 32 −1 0 4
3 1 0 −2
x3 1 1
(1) 0 3 0 1 3 0 0 2
2
x6 (2) 0 3 1 0 − 13 −1 1 2
CAPITOLO 3. PROGRAMMAZIONE LINEARE 114
Iterazione 2
Var. x1 x2 x3 x5
base Eq. Z x4 x6 bi
Z (0) −1 0 0 0 1 0 1 0
x3 1 1
(1) 0 3 0 1 3 0 0 2
2
x2 (2) 0 3 1 0 − 13 −1 1 2
Ora eliminiamo dal tableau finale della I fase le colonne relative alle variabili
artificiali e sostituiamo i coefficienti dell’equazione obiettivo della II fase:
Tableau II Fase
Var. x1 x2 x3 x5
base Eq. Z bi
Z (0) −1 1 5 4 0 0
x3 1
(1) 0 3 0 1 0 2
x2 2
(2) 0 3 1 0 −1 2
Iterazione 0
Var. x1 x2 x3 x5
base Eq. Z bi
Z (0) −1 − 11
3 0 0 5 −18
x3 1
(1) 0 3 0 1 0 2
x2 2
(2) 0 3 1 0 −1 2
CAPITOLO 3. PROGRAMMAZIONE LINEARE 115
Iterazione 1
Var. x1 x2 x3 x5
base Eq. Z bi
11
Z (0) −1 0 2 0 − 12 −7
x3 (1) 0 0 − 12 1 1
2 1
3
x1 (2) 0 1 2 0 − 32 3
Iterazione 2
Var. x1 x2 x3 x5
base Eq. Z bi
Z (0) −1 0 5 1 0 −6
x5 (1) 0 0 −1 2 1 2
x1 (2) 0 1 0 3 0 6
La BFS ottima è (6, 0, 0) mentre il valore minimo della funzione obiettivo è:
Z = 6.
di zero.
Consideriamo per esempio il seguente problema di programmazione lineare:
max Z = 6x1 + x2
x1 +x2 ≥ 5
2x1 +x2 = 2
x1 ≥ 0, x2 ≥ 0
e scriviamo direttamente il problema artificiale
max Z = 6x1 + x2
x1 +x2 −x3 +x4 = 5
2x1 +x2 +x5 = 2
x1 , x2 , x3 , x4 , x5 ≥ 0.
L’applicazione del metodo del simplesso a due fasi implica la risoluzione dei
seguenti problemi:
I Fase
max Z = −x4 − x5
x1 +x2 −x3 +x4 = 5
2x1 +x2 +x5 = 2
x1 , x2 , x3 , x4 , x5 ≥ 0;
II Fase
max Z = 6x1 + x2
x1 +x2 −x3 = 5
2x1 +x2 = 2
x1 , x2 , x3 ≥ 0.
Le equazioni della prima fase sono:
(0) Z +x4 +x5 = 0
(1) x1 +x2 −x3 +x4 = 5
(2) 2x1 +x2 +x5 = 2
Trasformiamo il problema della prima fase in forma canonica eliminando
dalla funzione obiettivo i coefficienti delle variabili di base x4 e x5 . Prima
sottraiamo dall’equazione (0) l’equazione (1)
Z +x4 +x5 = 0
−x1 −x2 +x3 −x4 = −5
Z −x1 −x2 +x3 +x5 = −5.
CAPITOLO 3. PROGRAMMAZIONE LINEARE 117
Iterazione 0
Var. x1 x2 x3
base Eq. Z x4 x5 bi
Z (0) 1 −3 −2 1 0 0 −7
x4 (1) 0 1 1 −1 1 0 5
x5 (2) 0 2 1 0 0 1 2
Iterazione 1
Var. x1 x2 x3
base Eq. Z x4 x5 bi
Z (0) 1 0 − 12 1 0 3
2 −4
1
x4 (1) 0 0 2 −1 1 − 12 4
x1 1 1
(2) 0 1 2 0 0 2 1
Iterazione 2
Var. x1 x2 x3
base Eq. Z x4 x5 bi
Z (0) 1 1 0 1 0 2 −3
x4 (1) 0 −1 0 −1 1 −1 3
x2 (2) 0 2 1 0 0 1 2
CAPITOLO 3. PROGRAMMAZIONE LINEARE 118
Esempio 3.6.2 Applicare il metodo del simplesso a due fasi per risolvere il
seguente problema di programmazione lineare in forma non standard:
I Fase
max Z = −x4 − x5
x1 +2x2 +3x3 +x4 = 4
2x1 +x2 −x3 +x5 = 8
x1 , x2 , x3 , x4 , x5 ≥ 0.
II Fase
max Z = 4x1 + 2x2 + 3x3
x1 +2x2 +3x3 = 4
x1 +x2 −x3 = 8
x1 , x2 , x3 ≥ 0.
Applichiamo ora il metodo del simplesso al problema definito nella I fase,
considerando che le variabili di base sono x4 e x5 , e che la BFS iniziale è
(0, 0, 0, 4, 8). Le equazioni della I fase sono
Iterazione 0
Var. x1 x2 x3
base Eq. Z x4 x5 bi
Z (0) 1 −3 −3 −2 0 0 −12
x4 (1) 0 1 2 3 1 0 4
x5 (2) 0 2 1 −1 0 1 8
Iterazione 1
Var. x1 x2 x3
base Eq. Z x4 x5 bi
Z (0) 1 0 3 7 3 0 0
x1 (1) 0 1 2 3 1 0 4
x5 (2) 0 0 −3 −7 −2 1 0
Iterazione 2
Var. x1 x2 x3
base Eq. Z x4 x5 bi
Z (0) 1 0 0 0 1 1 0
x1 (1) 0 1 0 − 53 − 31 2
3 4
7 2
x2 (2) 0 0 1 3 3
− 13 0
CAPITOLO 3. PROGRAMMAZIONE LINEARE 121
Iterazione 0
Var. x1 x2 x3
base Eq. Z bi
Z (0) 1 0 0 −5 16
x1 (1) 0 1 0 − 53 4
x2 7
(2) 0 0 1 3 0
Iterazione 1
Var. x1 x2 x3
base Eq. Z bi
15
Z (0) 1 0 7 0 16
x1 5
(1) 0 1 7 0 4
x3 3
(2) 0 0 7 1 0
Esempio 3.6.3 Applicare il metodo del simplesso a due fasi per risolvere il
seguente problema di programmazione lineare:
max Z = 2x1 + 4x2 + 6x3
3x1 +2x2 +4x3 = 4
3x1 +x2 +4x3 = 5
x1 +3x2 +x3 = 6
x1 , x2 , x3 ≥ 0.
Scriviamo quindi il problema nella forma aumentata introducendo una va-
riabile artificiale in ogni vincolo di uguaglianza:
max Z = 2x1 + 4x2 + 6x3
3x1 +2x2 +4x3 +x4 = 4
3x1 +x2 +4x3 +x5 = 5
x1 +3x2 +x3 +x6 = 6
x1 , x2 , x3 , x4 , x5 , x6 ≥ 0.
Scriviamo ora i problemi da risolvere nelle due fasi:
I Fase
max Z = −x4 − x5 − x6
3x1 +2x2 +4x3 +x4 = 4
3x1 +x2 +4x3 +x5 = 5
x1 +3x2 +x3 +x6 = 6
x1 , x2 , x3 , x4 , x5 , x6 ≥ 0.
II Fase
max Z = 2x1 + 4x2 + 6x3
3x1 +2x2 +4x3 = 4
3x1 +x2 +4x3 = 5
x1 +3x2 +x3 = 6
x1 , x2 , x3 ≥ 0.
Applichiamo ora il metodo del simplesso al problema definito nella I fase,
considerando che le variabili di base sono quelle artificiali e che la BFS iniziale
è (0, 0, 0, 4, 8). Le equazioni della I fase sono
(0) Z +x4 +x5 +x6 = 0
(1) 3x1 +2x2 +4x3 +x4 = 4
(2) 3x1 +x2 +4x3 +x5 = 5
(3) x1 +3x2 +x3 +x6 = 6.
CAPITOLO 3. PROGRAMMAZIONE LINEARE 123
Scriviamo il tableau della iterazioni del metodo del simplesso applicato alla
I fase:
Iterazione 0
Var. x1 x2 x3
base Eq. Z x4 x5 x6 bi
Z (0) 1 −7 −6 −9 0 0 0 −15
x4 (1) 0 3 2 4 1 0 0 4
x5 (2) 0 3 1 4 0 1 0 5
x6 (3) 0 1 3 1 0 0 1 6
Iterazione 1
Var. x1 x2 x3
base Eq. Z x4 x5 x6 bi
Z (0) 1 − 41 − 32 0 9
4 0 0 −6
x3 3 1 1
(1) 0 4 2 1 4 0 0 1
x5 (2) 0 0 −1 0 −1 1 0 1
1 5
x6 (3) 0 4 2 0 − 41 0 1 5
CAPITOLO 3. PROGRAMMAZIONE LINEARE 124
Iterazione 2
Var. x1 x2 x3
base Eq. Z x4 x5 x6 bi
Z (0) 1 2 0 3 3 0 0 −3
x2 3 1
(1) 0 2 1 2 2 0 0 2
3
x5 (2) 0 2 0 2 − 21 1 0 3
x6 (3) 0 − 72 0 −5 − 32 0 1 0
1. Tutte le variabili artificiali sono fuori dalla base, quindi si procede alla
risoluzione della seconda fase;
3. Una variabile artificiale resta in base con valore nullo, in questo caso si
procede ad un’ulteriore iterazione facendo entrare in base un’altra va-
riabile purchè abbia coefficiente diverso da zero nell’equazione associata
alla variabile artificiale in base. Subito dopo si passa alla risoluzione
della seconda fase.
max Z = cT x
Ax ≤ b
x≥0
sono poste uguali a zero. Eliminando tali variabili, ovvero ponendo il loro
valore uguale a zero, rimane un sistema di m equazioni in m incognite
BxB = b (3.7)
dove il vettore
xB1
xB2
xB = ..
.
xBm
è ottenuto da [x xS ] eliminando le variabili non di base mentre la matrice
B11 B12 . . . B1m
B21 B22 . . . B2m
B = .. .. ..
. . .
Bm1 Bm2 . . . Bmm
poichè
0
cB = 0
0
si ha
4
Z = cTB xB =
0 0 0 12 = 0.
18
Iterazione 1:
x3
xB = x2
x5
1 0 0 1 0 0
B = 0 2 0 , B −1 = 0 1/2 0
0 2 1 0 −1 1
e pertanto
x3 1 0 0 4 4
xB = x2
= 0 1/2 0 12 = 6 ,
x5 0 −1 1 18 6
poichè
0
cB = 5
0
si ha
4
Z = cTB xB =
0 5 0 6 = 30.
6
Iterazione 2:
x3
xB = x2
x1
1 0 1 1 1/3 −1/3
B = 0 2 0 , B −1 = 0 1/2 0
0 2 3 0 −1/3 1/3
CAPITOLO 3. PROGRAMMAZIONE LINEARE 129
e pertanto
x3 1 1/3 −1/3 4 2
−1
xB = x2 = B b = 0 1/2
0 12 = 6 ,
x1 0 −1/3 1/3 18 2
poichè
0
cB = 5
3
si ha
2
Z = cTB xB =
0 5 3 6 = 36.
2
Le forme del simplesso viste (forma algebrica, forma tabellare e forma ma-
triciale) prendono esattamente sempre le stesse decisioni (variabile entrante,
variabile uscente), l’unica differenza è il modo usato per effettuare i calcoli
per poi prendere tali decisioni. La forma matriciale fornisce sicuramente un
modo compatto che non richiede la scrittura di una sequenza di equazioni
algebriche o di tabelle.
In questo caso
B = {1, 3, 4}, N = {2, 5, 6}
Le colonne della matrice [A, I] relative alle variabili di base e non di base
sono
1 3 1 2 0 0
AB = 2 −5 0 , AN = −1 1 0 ,
1 −1 0 2 0 1
I vettori dei costi
cB = 1 1 1 , cN = 2 1 1 .
Calcoliamo A−1
B :
0 −1 5
1
A−1
B = 0 −1 2
3
3 4 −11
CAPITOLO 3. PROGRAMMAZIONE LINEARE 131
x1 +x2 +x3 = 2
x1 +x4 = 2
x2 +x5 = 1
B = {1, 2, 3}
CAPITOLO 3. PROGRAMMAZIONE LINEARE 133
1 1 1
AB = 1 0 0
0 1 0
0 1 0 2 2
xB = A−1
B b =
0 0 1 2 = 1
1 −1 −1 1 −1
In questo caso non abbiamo una BFS.
In alternativa al calcolo dell’inversa della matrice AB si può risolvere il siste-
ma lineare che si ottiene ponendo le variabili fuori base uguali a zero (cioè
x4 = x5 = 0):
x1 +x2 +x3 = 2
x1 = 2
x2 = 1
x1 = 2 x2 = 1 x3 = −1.
da cui risulta che gli indici assegnati non individuano una BFS.
B = {1, 2, 4}
1 1 0
AB = 1 0 1
0 1 0
1 0 −1 2 1
−1
xB = AB b = 0 0 1 2 = 1
−1 1 1 1 1
In questo caso gli indici individuano una BFS.
B = {1, 2, 5}
1 1 0
AB = 1 0 0
0 1 1
0 1 0 2 2
−1
xB = AB b = 1 −1 0 2 = 0
−1 1 1 1 1
In questo caso gli indici individuano una BFS seppur degenere.
CAPITOLO 3. PROGRAMMAZIONE LINEARE 134
3.8 Esercizi
Esercizio 3.8.1 Applicare il metodo grafico per risolvere il seguente proble-
ma di programmazione lineare
max Z = 5x1 + 2x2
x1 −x2 ≤ 0
−x1 +x2 ≤ 4
5x1 +2x2 ≤ 10
x1 , x2 ≥ 0.
(Soluzione ottima Z = 10).
Esercizio 3.8.2 Applicare il metodo grafico per risolvere il seguente proble-
ma di programmazione lineare
max Z = x1 − x2
x1 +x2 ≤ 6
x1 +x2 ≥ 2
x1 −x2 ≤ 4
x1 , x2 ≥ 0.
(Soluzione ottima Z = 4).
Esercizio 3.8.3 Applicare il metodo grafico per risolvere il seguente proble-
ma di programmazione lineare
max Z = x1 − x2
x1 +x2 ≤ 8
x1 +x2 ≥ 3
x1 −x2 ≤ 5
x1 ≥ 1, x2 ≥ 0.
CAPITOLO 3. PROGRAMMAZIONE LINEARE 135
(Problema illimitato).
Esercizio 3.8.8 Risolvere il seguente problema di programmazione lineare
max Z = 4x1 + 3x2 − x3
3x1 +4x2 −2x3 ≤ 5
3x2 +3x3 ≤ 6
x1 , x2 , x3 ≥ 0.
(Soluzione ottima Z = 10).
Esercizio 3.8.9 Risolvere il seguente problema di programmazione lineare
max Z = 4x1 + 4x2 + x3
4x1 +3x2 +5x3 ≤ 8
2x1 −x2 +4x3 ≤ 6
x1 , x2 , x3 ≥ 0.
(Soluzione ottima Z = 32/3).
Esercizio 3.8.10 Risolvere il seguente problema di programmazione lineare
max Z = 4x1 − 2x2 + 3x3
4x1 +3x2 +2x3 ≤ 4
3x1 +x2 +x3 ≤ 3
x1 , x2 , x3 ≥ 0.
(Soluzione ottima Z = 6).
Esercizio 3.8.11 Risolvere il seguente problema di programmazione lineare
max Z = 4x1 + x2 + x3
−x1 +2x2 +3x3 ≤ 3
2x1 +x2 ≤ 4
x1 , x2 , x3 ≥ 0.
(Soluzione ottima Z = 29/3).
Esercizio 3.8.12 Risolvere il seguente problema di programmazione lineare
max Z = 3x1 − x2 + 5x3
3x1 +3x3 ≤ 4
2x1 −2x2 +3x3 ≤ 3
x1 , x2 , x3 ≥ 0.
(Soluzione ottima Z = 37/6).
CAPITOLO 3. PROGRAMMAZIONE LINEARE 137
4.1 Introduzione
Un problema di programmazione lineare intera (in breve PLI) si presenta
nella forma n
X
max Z = cj xj
j=1
n
X (4.1)
aij xj ≤ bi , i = 1, 2, . . . , m,
j=1
xj variabile intera, per j = 1, . . . , n.
In questo capitolo affronteremo la risoluzione di problemi di PLI in forma
standard considerando che i metodi che saranno descritti possono essere
adattati anche a problemi in forma non standard. Nella programmazione
intera il maggiore problema che si presenta è che la regione ammissibile è
composta da un numero discreto (ovvero finito o infinitamente numerabile)
di punti e non forma un insieme compatto. Nella seguente figura viene ri-
portato un esempio di regione ammissibile definita dai vincoli del generico
problema (4.1) considerando le variabili decisionali come se fossero reali e
all’interno della quale sono evidenziati i punti che rappresentano invece la
regione ammissibile (discreta) del problema di programmazione intera.
141
CAPITOLO 4. PROGRAMMAZIONE LINEARE INTERA 142
• • • •
• • • • • •
• • • • • • • •
• • • • • • • • • •
• • • • • • • • •
• • • • • • • •
È evidente dalla figura che il problema non può essere risolto con i classici
metodi per la programmazione lineare a variabili reali (ad esempio, il metodo
del simplesso) in quanto in generale non tutti i vertici hanno coordinate intere
e quindi anche il vertice ottimale non è detto che abbia coordinate intere
(dipende dalla regione ammissibile e dalla funzione obiettivo).
Poichè i problemi di PLI sono, in generale, più difficili da risolvere rispetto
a quelli di programmazione lineare, si potrebbe essere tentati dall’uso di una
tecnica di approsimazione che consiste nell’applicare il metodo del simplesso
al problema ignorando il vincolo di interezza delle variabili, e approssimando
la soluzione, di solito reale, al valore intero più vicino. Un primo problema
legato a tale approccio sta nel fatto che tale approssimazione non garantisce
che questa sia ancora ammissibile. Consideriamo il seguente esempio.
Esempio 4.1.1
max Z = x2
1
−x1 +x2 ≤
2
7
x1 +x2 ≤
2
x1 , x2 ∈ N.
Risolviamo il problema in modo grafico ignorando il vincolo di interezza delle
variabili, ottenendo quello che si chiama problema rilassato.
CAPITOLO 4. PROGRAMMAZIONE LINEARE INTERA 143
Soluzioni arrotondate
• • • • • •
• • • • •
• •
esplorare;
2. Bounding, ovvero il calcolo di un opportuno limite per la soluzione otti-
ma;
3. Fathoming, ovvero la cancellazione di sottoinsiemi di soluzioni all’interno
ai quali la soluzione ottima non può appartenere.
Branching
Quando si opera con variabili binarie il modo più semplice di procedere è
quello di suddividere l’insieme delle soluzioni ammissibili in sottoinsiemi, fis-
sando ad ogni passo il valore di una variabile detta variabile di branching (i
cui valori possibili sono chiaramente solo 0 e 1). Esistono tecniche piuttosto
sofisticate per la scelta della variabile di branching, in alternativa si può se-
guire l’ordine naturale, per esempio al primo passo si sceglie x1 , quindi x2
e cosı̀ via. I due valori della variabile di branching definiscono due sotto-
problemi che vengono risolti in modo approssimato, come sarà descritto nel
paragrafo successivo. In questo modo si definisce un vero e proprio albero,
detto albero delle soluzioni, che si ramifica iterazione dopo iterazione, quan-
do vengono definiti (e risolti) i sottoproblemi definiti attribuendo i valori alle
diverse variabili di branching. Nel corso dell’algoritmo alcuni di questi pro-
blemi potranno essere tagliati (fathomed) mentre altri saranno ulteriormente
suddivisi in sottoproblemi.
Bounding
Per ogni sottoproblema si deve ottenere un limite (bound) sulla soluzione
ammissibile. Un modo classico per ottenere questa informazione è quello di
risolvere il problema rilassato (anche detto rilassamento lineare), che viene
ottenuto cancellando (o sostituendo) i vincoli che lo rendono difficile da ri-
solvere.
Per un problema di programmazione binaria si taglia proprio il vincolo xj ∈
{0, 1} che viene sostituito dai vincoli
xj ≤ 1, xj ≥ 0
per ogni j. Per risolvere il problema rilassato si può applicare, per esempio,
il metodo del simplesso (oppure anche il metodo grafico qualora il numero di
variabili decisionali sia uguale a due).
CAPITOLO 4. PROGRAMMAZIONE LINEARE INTERA 146
Fathoming
Una volta risolto un problema rilassato un’eventualità è che l’insieme delle
sue soluzioni non possa contenere con certezza la soluzione ottima. In que-
sto caso può essere tagliato, cioè non si considerano più i sottoproblemi che
esso potrebbe generare in quanto si è certi che essi non porteranno ad una
soluzione migliore. Esistono tre criteri per tagliare un sottoproblema.
Un criterio è quello di avere ottenuto una soluzione binaria del rilassamento
lineare. Infatti se la soluzione ottima del rilassamento lineare è una solu-
zione binaria, questa deve essere soluzione ottima anche del problema di
programmazione binaria. Se questa soluzione binaria è la migliore soluzione
trovata fino all’iterazione attuale allora viene memorizzata come soluzione
incombente (cioè la migliore soluzione ammissibile trovata finora). Si pone
Iterazione 0
Var. x1 x2 x3 x4 x5 x6 x7 x8
base Eq. Z bi
Z (0) 1 −9 −5 −6 0 0 0 0 0 0
x4 (1) 0 6 3 5 1 0 0 0 0 10
x5 (2) 0 −1 −1 1 0 1 0 0 0 0
x6 (3) 0 1 0 0 0 0 1 0 0 1
x7 (4) 0 0 1 0 0 0 0 1 0 1
x8 (5) 0 0 0 1 0 0 0 0 1 1
CAPITOLO 4. PROGRAMMAZIONE LINEARE INTERA 149
Iterazione 1
Var. x1 x2 x3 x4 x5 x6 x7 x8
base Eq. Z bi
Z (0) 1 0 −5 −6 0 0 9 0 0 9
x4 (1) 0 0 3 5 1 0 −6 0 0 4
x5 (2) 0 0 −1 1 0 1 1 0 0 1
x1 (3) 0 1 0 0 0 0 1 0 0 1
x7 (4) 0 0 1 0 0 0 0 1 0 1
x8 (5) 0 0 0 1 0 0 0 0 1 1
Iterazione 2
Var. x1 x2 x3 x4 x5 x6 x7 x8
base Eq. Z bi
Z (0) 1 0 − 75 0 6
5 0 9
5 0 0 69
5
3 1
x3 (1) 0 0 5 1 5 0 − 56 0 0 4
5
x5 (2) 0 0 − 85 0 − 15 1 11
5 0 0 1
5
x1 (3) 0 1 0 0 0 0 1 0 0 1
x7 (4) 0 0 1 0 0 0 0 1 0 1
x8 (5) 0 0 − 35 0 − 15 0 6
5 0 1 1
5
CAPITOLO 4. PROGRAMMAZIONE LINEARE INTERA 150
Iterazione 3
Var. x1 x2 x3 x4 x5 x6 x7 x8
base Eq. Z bi
6 9 7 76
Z (0) 1 0 0 0 5 0 5 5 0 5
1
x3 (1) 0 0 0 1 5 0 − 56 − 35 0 1
5
x5 (2) 0 0 0 0 − 15 1 11
5
8
5 0 9
5
x1 (3) 0 1 0 0 0 0 1 0 0 1
x2 (4) 0 0 1 0 0 0 0 1 0 1
x8 (5) 0 0 0 0 − 15 0 6
5
3
5 1 4
5
Soluzione del problema rilassato è (1, 1, 1/5) mentre il valore della funzione
obiettivo è 76/5 = 15 + 1/5 che viene approssimato al valore intero
Z = 15.
Sottoproblema 1
Fissato x1 = 0
Sottoproblema 2
Fissato x1 = 1
ovvero
Sottoproblema 2
Iterazione 0
Var. x2 x3 x4 x5 x6 x7
base Eq. Z bi
Z (0) 1 −5 −6 0 0 0 0 0
x4 (1) 0 3 5 1 0 0 0 10
x5 (2) 0 −1 1 0 1 0 0 0
x6 (3) 0 1 0 0 0 1 0 1
x7 (4) 0 0 1 0 0 0 1 1
CAPITOLO 4. PROGRAMMAZIONE LINEARE INTERA 152
Iterazione 1
Var. x2 x3 x4 x5 x6 x7
base Eq. Z bi
Z (0) 1 −11 0 0 6 0 0 0
x4 (1) 0 8 0 1 −5 0 0 10
x3 (2) 0 −1 1 0 1 0 0 0
x6 (3) 0 1 0 0 0 1 0 1
x7 (4) 0 1 1 0 −1 0 1 1
Iterazione 2
Var. x2 x3 x4 x5 x6 x7
base Eq. Z bi
Z (0) 1 0 0 0 6 11 0 11
x4 (1) 0 0 0 1 −5 −8 0 2
x3 (2) 0 0 1 0 1 1 0 1
x2 (3) 0 1 0 0 0 1 0 1
x7 (4) 0 0 0 0 −1 −1 1 0
Iterazione 0
Var. x2 x3 x4 x5 x6 x7
base Eq. Z bi
Z (0) 1 −5 −6 0 0 0 0 9
x4 (1) 0 3 5 1 0 0 0 4
x5 (2) 0 −1 1 0 1 0 0 1
x6 (3) 0 1 0 0 0 1 0 1
x7 (4) 0 0 1 0 0 0 1 1
Iterazione 1
Var. x2 x3 x4 x5 x6 x7
base Eq. Z bi
Z (0) 1 − 75 0 6
5 0 0 0 69
5
x3 3 1 4
(1) 0 5 1 5 0 0 0 5
x5 (2) 0 − 85 0 − 15 1 0 0 1
5
x6 (3) 0 1 0 0 0 1 0 1
x7 (4) 0 − 35 0 − 15 0 0 1 1
5
Iterazione 2
Var. x2 x3 x4 x5 x6 x7
base Eq. Z bi
6 7 76
Z (0) 1 0 0 5 0 5 0 5
1
x3 (1) 0 0 1 5 0 − 35 0 1
5
x5 (2) 0 0 0 − 15 1 8
5 0 9
5
x2 (3) 0 1 0 0 0 1 0 1
x7 (4) 0 0 0 − 15 0 3
5 1 4
5
CAPITOLO 4. PROGRAMMAZIONE LINEARE INTERA 154
Z = 15.
Completo Z = 15
(1, 1, 1/5)
x1 1 Z = 15
0 Z ∗ = 11
(1, 1, 1/5) (0, 1, 1)
F(3)
Passiamo ora alla seconda iterazione e scriviamo i sottoproblemi ponendo
x2 = 1 e x2 = 0:
Sottoproblema 3
Fissato x2 = 0
max Z = 9 + 6x3
(1) 5x3 ≤ 4
(2) x3 ≤ 1
(3) x3 variabile binaria,
Sottoproblema 4
Fissato x2 = 1
max Z = 14 + 6x3
(1) 3 + 5x3 ≤ 4
(2) − 1 + x3 ≤ 1
(3) x3 variabile binaria,
CAPITOLO 4. PROGRAMMAZIONE LINEARE INTERA 155
ovvero
Sottoproblema 4
max Z = 14 + 6x3
(1) 5x3 ≤ 1
(2) x3 ≤ 2
(3) x3 variabile binaria.
In questo caso è superfluo risolvere il rilassamento lineare dei problemi binari
perchè le soluzioni sono molto semplici. Infatti x3 = 0 è soluzione del sotto-
problema 3, e Z = 9 è il relativo valore della funzione obiettivo. Poichè tale
valore è inferiore rispetto alla soluzione incombente il sottoproblema viene
tagliato applicando il primo criterio di fathoming. La soluzione del sottopro-
blema 4 è x3 = 0, in cui la funzione obiettivo ammette valore Z = 14, che
diviene la nuova soluzione incombente
Z ∗ = 14,
Completo Z = 15
(1, 1, 1/5)
x1 1 Z = 15
0 Z ∗ = 11
(1, 1, 1/5) (0, 1, 1)
F(3)
x2 1 Z ∗ = 14
0 Z=9
(1, 1, 0) (1, 0, 0)
F(3) F(1)
CAPITOLO 4. PROGRAMMAZIONE LINEARE INTERA 156
xi ≤ ⌊x∗i ⌋
nel primo e
xi ≥ ⌊x∗i ⌋ + 1
in cui ⌊x∗i ⌋ indica la parte intera del numero reale x∗i :
xj ≤ ⌊x∗j ⌋ e xj ≥ ⌊x∗j ⌋ + 1.
Iterazione 0
Var. x1 x2 x3 x4 x5
base Eq. Z bi
Z (0) 1 −2 −3 −2 0 0 0
x4 (1) 0 1 0 2 1 0 3
x5 (2) 0 2 1 0 0 1 5
Iterazione 1
Var. x1 x2 x3 x4 x5
base Eq. Z bi
Z (0) 1 4 0 −2 0 3 15
x4 (1) 0 1 0 2 1 0 3
x2 (2) 0 2 1 0 0 1 5
CAPITOLO 4. PROGRAMMAZIONE LINEARE INTERA 159
Iterazione 2
Var. x1 x2 x3 x4 x5
base Eq. Z bi
Z (0) 1 5 0 0 1 3 18
x3 1 1 3
(1) 0 2 0 1 2 0 2
x2 (2) 0 2 1 0 0 1 5
La soluzione ottenuta (0, 5, 3/2) non è intera, quindi non può essere applicato
il terzo criterio di fathoming ed il problema non viene tagliato, inoltre
Z = 18
Sottoproblema 1
e
Sottoproblema 2
Iterazione 0
Var. x1 x2 x3 x4 x5 x6
base Eq. Z bi
Z (0) 1 −2 −3 −2 0 0 0 0
x4 (1) 0 1 0 2 1 0 0 3
x5 (2) 0 2 1 0 0 1 0 5
x6 (3) 0 0 0 1 0 0 1 1
Iterazione 1
Var. x1 x2 x3 x4 x5 x6
base Eq. Z bi
Z (0) 1 4 0 −2 0 3 0 15
x4 (1) 0 1 0 2 1 0 0 3
x2 (2) 0 2 1 0 0 1 0 5
x6 (3) 0 0 0 1 0 0 1 1
CAPITOLO 4. PROGRAMMAZIONE LINEARE INTERA 161
Iterazione 2
Var. x1 x2 x3 x4 x5 x6
base Eq. Z bi
Z (0) 1 4 0 0 0 3 2 17
x4 (1) 0 1 0 0 1 0 −2 1
x2 (2) 0 2 1 0 0 1 0 5
x3 (3) 0 0 0 1 0 0 1 1
Z ∗ = 17.
Completo Z = 18
(0, 5, 3/2)
∗ Soluzione
x3 ≤ 1 Z = 17 x3 ≥ 2
(0, 5, 1) Non Ammissibile
F(3) F(2)
• • •
5 + 4 + 7 + 0 ≥ 13.
x1 + x3 ≤ 1. (4.4)
I due vincoli (4.3) e (4.4) sono più stringenti rispetto a (4.2) poichè i ver-
tici ammissibili appartengono alla frontiera di almeno uno dei due, mentre
nessuno appartiene alla frontiera del vincolo originario (fa eccezione l’origine
che appartiene comunque alla frontiera di tutti i vincoli di nonnegatività),
come si evince dalla presente tabella:
CAPITOLO 4. PROGRAMMAZIONE LINEARE INTERA 166
Iterazione 0
Var. x1 x2 x3 x4 x5 x6 x7 x8
base Eq. Z bi
Z (0) 1 −6 −5 −4 0 0 0 0 0 0
x4 (1) 0 2 3 4 1 0 0 0 0 6
x5 (2) 0 3 1 6 0 1 0 0 0 9
x6 (3) 0 1 0 0 0 0 1 0 0 1
x7 (4) 0 0 1 0 0 0 0 1 0 1
x8 (5) 0 0 0 1 0 0 0 0 1 1
CAPITOLO 4. PROGRAMMAZIONE LINEARE INTERA 167
Iterazione 1
Var. x1 x2 x3 x4 x5 x6 x7 x8
base Eq. Z bi
Z (0) 1 0 −5 −4 0 0 6 0 0 6
x4 (1) 0 0 3 4 1 0 −2 0 0 4
x5 (2) 0 0 1 6 0 1 −3 0 0 6
x1 (3) 0 1 0 0 0 0 1 0 0 1
x7 (4) 0 0 1 0 0 0 0 1 0 1
x8 (5) 0 0 0 1 0 0 0 0 1 1
Iterazione 2
Var. x1 x2 x3 x4 x5 x6 x7 x8
base Eq. Z bi
Z (0) 1 0 0 −4 0 0 6 5 0 11
x4 (1) 0 0 0 4 1 0 −2 −3 0 1
x5 (2) 0 0 0 6 0 1 −3 −1 0 5
x1 (3) 0 1 0 0 0 0 1 0 0 1
x2 (4) 0 0 1 0 0 0 0 1 0 1
x8 (5) 0 0 0 1 0 0 0 0 1 1
CAPITOLO 4. PROGRAMMAZIONE LINEARE INTERA 168
Iterazione 3
Var. x1 x2 x3 x4 x5 x6 x7 x8
base Eq. Z bi
Z (0) 1 0 0 0 1 0 4 2 0 12
1
x3 (1) 0 0 0 1 4 0 − 21 − 43 0 1
4
x5 (2) 0 0 0 0 − 32 1 0 7
2 0 7
2
x1 (3) 0 1 0 0 0 0 1 0 0 1
x2 (4) 0 0 1 0 0 0 0 1 0 1
x8 (5) 3
0 0 0 0 0 0 0 0 1 4
Soluzione del problema rilassato è dunque il vettore (1, 1, 1/4), con valore
della funzione obiettivo Z = 12. È ovvio che non potendo tagliare il proble-
ma completo poichè tale soluzione non soddisfa alcun criterio di fathoming,
è necessario scegliere la variabile di branching (x1 seguendo l’ordine naturale
oppure x3 in modo più oculato), definire due sottoproblemi e risolverli. Con-
sideriamo invece la possibilità di risolvere il problema completo sostituendo
ai due vincoli quelli definiti dalle rispettive coperture minime. È facile os-
servare che il primo vincolo ammette come unica copertura minima l’insieme
{x2 , x3 }, che definisce il vincolo
x2 + x3 ≤ 1
x1 + x2 + x3 ≤ 2.
Iterazione 0
Var. x1 x2 x3 x4 x5 x6 x7 x8
base Eq. Z bi
Z (0) 1 −6 −5 −4 0 0 0 0 0 0
x4 (1) 0 0 1 1 1 0 0 0 0 1
x5 (2) 0 1 1 1 0 1 0 0 0 2
x6 (3) 0 1 0 0 0 0 1 0 0 1
x7 (4) 0 0 1 0 0 0 0 1 0 1
x8 (5) 0 0 0 1 0 0 0 0 1 1
CAPITOLO 4. PROGRAMMAZIONE LINEARE INTERA 170
Iterazione 1
Var. x1 x2 x3 x4 x5 x6 x7 x8
base Eq. Z bi
Z (0) 1 0 −5 −4 0 0 6 0 0 6
x4 (1) 0 0 1 1 1 0 0 0 0 1
x5 (2) 0 0 1 1 0 1 −1 0 0 1
x1 (3) 0 1 0 0 0 0 1 0 0 1
x7 (4) 0 0 1 0 0 0 0 1 0 1
x8 (5) 0 0 0 1 0 0 0 0 1 1
Iterazione 2
Var. x1 x2 x3 x4 x5 x6 x7 x8
base Eq. Z bi
Z (0) 1 0 0 1 5 0 6 0 0 11
x2 (1) 0 0 1 1 1 0 0 0 0 1
x5 (2) 0 0 0 0 −1 1 −1 0 0 0
x1 (3) 0 1 0 0 0 0 1 0 0 1
x7 (4) 0 0 0 −1 −1 0 0 1 0 0
x8 (5) 0 0 0 1 0 0 0 0 1 1
Soluzione ottima del problema rilassato è dunque (1, 1, 0), con Z = 11, che
risulta essere soluzione ottima anche del problema binario iniziale. L’uso dei
vincoli definiti dalle coperture minime consente di ridurre la regione ammissi-
bile eliminando quei vertici che sono ammissibili per il problema rilassato ma
non per quello binario. In tal modo aumenta la probabilità che la soluzione
del rilassamento lineare coincida con quella del problema binario.
CAPITOLO 4. PROGRAMMAZIONE LINEARE INTERA 171
4.5 Esercizi
Esercizio 4.5.1 Applicare il metodo del simplesso per risolvere il rilassa-
mento lineare del seguente problema di programmazione lineare binaria de-
terminando un limite per Z:
max Z = 3x1 + 2x2
2x1 +3x2 ≤ 5
2x1 +x2 ≤ 2
x1 , x2 ∈ {0, 1}.
(Soluzione Z = 3).
Esercizio 4.5.2 Applicare il metodo del simplesso per risolvere il rilassa-
mento lineare del seguente problema di programmazione lineare binaria de-
terminando un limite per Z:
max Z = 4x1 + 2x2
3x1 −x2 ≤ 6
2x1 +x2 ≤ 2
x1 , x2 ∈ {0, 1}.
(Soluzione Z = 4).
Esercizio 4.5.3 Applicare il metodo del simplesso per risolvere il rilassa-
mento lineare del seguente problema di programmazione lineare binaria de-
terminando un limite per Z:
max Z = 5x1 + 3x2
−x1 +4x2 ≤ 5
3x1 +6x2 ≤ 5
x1 , x2 ∈ {0, 1}.
(Soluzione Z = 6).
Esercizio 4.5.4 Applicare il metodo del simplesso per risolvere il rilassa-
mento lineare del seguente problema di programmazione lineare binaria de-
terminando un limite per Z:
max Z = 6x1 + 3x2
4x1 +5x2 ≤ 5
2x1 +3x2 ≤ 4
x1 , x2 ∈ {0, 1}.
(Soluzione Z = 6).
CAPITOLO 4. PROGRAMMAZIONE LINEARE INTERA 172
5.1 Introduzione
La teoria della dualità consente di stabilire un legame tra un problema as-
segnato, che prende il nome di primale ed un altro, detto appunto duale. Il
vantaggio di tale aspetto risiede innanzitutto nella possibilità di approfondire
gli aspetti legati all’interpretazione economica della soluzione di un proble-
ma di programmazione lineare e, in subordine, può risultare vantaggioso,
dal punto di vista algoritmico, risolvere il problema duale al posto di quello
primale, ottenendo comunque la soluzione ottima del problema assegnato.
Vediamo innanzitutto un esempio di problema duale.
174
CAPITOLO 5. TEORIA DELLA DUALITÀ 175
2y1 + 4y2 + y3 ≤ 10
AT y ≥ c,
cT x ≤ bT y.
Ne segue che
Z ∗ ≤ bT y,
dunque il valore bT y è una maggiorazione per il valore ottimo Z ∗ . Se sia-
mo alla ricerca della migliore maggiorazione (cioè quella minima) che può
essere ricavata in questo modo, bisogna determinare il valore ottimo W ∗ del
seguente problema di programmazione lineare
min W = bT y
(D)
AT y ≥ c.
Teorema 5.2.1 (Teorema della dualità debole) Per ogni x soluzione am-
missibile di (P) e per ogni y soluzione ammissibile di (D) risulta
cT x ≤ bT y.
cT x ≤ y T Ax ≤ y T b = bT y. ✷
cT x∗ = bT y ∗ ,
cT x ≤ bT y ∗ = cT x∗
bT y ≥ cT x∗ = bT y ∗ ,
Corollario 5.2.2 Se uno dei due problemi (P) e (D) è illimitato allora l’altro
è inammissibile.
Dimostrazione. Supponiamo che (P) sia illimitato. Se, per assurdo, (D)
ammettesse una soluzione ammissibile y allora per il Teorema della dualità
debole
cT x ≤ bT y
per ogni x soluzione ammissibile per (P), e quindi (P) non sarebbe illimitato.
✷
cT x∗ = bT y ∗ .
Definiamo
y = A−T
B cB ,
dove A−T
B è
−1 T T −1
A−T
B = (AB ) = (AB ) .
Notiamo che
T
cT x = cTB xB = cTB A−1 −T
B b = AB cB b = y T b = bT y.
cioè se e solo se
cN − ATN A−1
B cB ≤ 0.
cioè se y è ammissibile per il problema duale (D). Quanto visto sopra mostra
che se B è una base ammissibile sia nel primale che nel duale, allora i cor-
rispondenti vettori x e y sono soluzioni ottime dei rispettivi problemi. Per
questo motivo, B è detta una base ottima se è ammissibile sia nel primale
che nel duale.
Dunque, se (P) ha soluzione ottima, allora il metodo del simplesso mantiene
una base ammissibile nel primale ad ogni iterazione e termina quando rag-
giunge una base ammissibile anche nel duale, cioè quando arriva ad una base
ottima.
CAPITOLO 5. TEORIA DELLA DUALITÀ 181
max W = y1 + y2
−y2 ≤ −1
y1 −y2 ≤ 1
−2y1 +y2 ≤ 2
y1 , y2 ≥ 0.
(0) ±1 c1 c2 . . . . . . cn 0 0 ... 0 Z
(1) 0 b1
.. .. ..
. . .
.. ..
. . Matrice A Matrice I bi
.. .. ..
. . .
(m) 0 bm
il problema
max Z = cT x
Ax = b
x ≥ 0.
il cui duale è
min W = bT y
AT y ≥ c.
Sia B = {k1 , k2 , . . . , km } una base ammissibile nel duale. Il problema in
forma tableau rispetto a tale base è il seguente:
Z −cN xN = Z
xB +AN xN = b
x ≥ 0.
y = A−T
B cB
W = cTB A−1
B b.
x ki = bi , i = 1, . . . , m
xN = 0.
B ′ = B ∪ {k} \ {ih }
x1 ≥ 2
−x1 +2x2 ≥ 3
x1 , x2 ≥ 0.
CAPITOLO 5. TEORIA DELLA DUALITÀ 189
max −Z = −x1 − x2
x1 −x3 = 2
−x1 +2x2 −x4 = 3
x1 , x2 , x3 , x4 ≥ 0.
Iterazione 0
Var. x1 x2 x3 x4
base Eq. Z bi
Z (0) −1 1 1 0 0 0
x3 (1) 0 −1 0 1 0 −2
x4 (2) 0 1 −2 0 1 −3
È uscita dalla base x4 che aveva il valore negativo più piccolo, mentre è
entrata in base x2 che presentava l’unico coefficiente negativo nell’equazione
(2). Si esegue un’operazione di pivoting sull’elemento −2 e si procede in
modo analogo con la successiva iterazione.
Iterazione 1
Var. x1 x2 x3 x4
base Eq. Z bi
3 1
Z (0) −1 2 0 0 2
− 32
x3 (1) 0 −1 0 1 0 −2
x2 (2) 0 − 21 1 0 − 12 3
2
CAPITOLO 5. TEORIA DELLA DUALITÀ 190
Iterazione 2
Var. x1 x2 x3 x4
base Eq. Z bi
3 1
Z (0) −1 0 0 2 2
− 92
x1 (1) 0 1 0 −1 0 2
x2 (2) 0 0 1 − 12 − 12 5
2
Non ci sono coefficienti negativi nella colonna dei termini noti quindi abbiamo
trovato la soluzione ottima (2, 5/2, 0, 0) in cui
Z = 9/2.
x2
x1
Esempio 5.4.5 Applicare il metodo del simplesso duale per risolvere il se-
guente problema di programmazione lineare in forma non standard:
max Z = −3x1 − 4x2 − 6x3
Iterazione 0
Var. x1 x2 x3 x4 x5
base Eq. Z bi
Z (0) 1 3 4 6 0 0 0
x4 (1) 0 −2 −4 1 1 0 −2
x5 (2) 0 −1 −5 −4 0 1 −3
È uscita dalla base x5 che aveva il valore negativo più piccolo, mentre per
determinare la variabile entrante si è calcolato il
3 4 6 4
max , , =−
−1 −5 −4 5
quindi è entrata la variabile x2 .
CAPITOLO 5. TEORIA DELLA DUALITÀ 192
Iterazione 1
Var. x1 x2 x3 x4 x5
base Eq. Z bi
11 14 4
Z (0) 1 5 0 5 0 5
− 12
5
x4 (1) 0 − 65 0 21
5 1 − 45 2
5
x2 (2) 0 − 15 1 4
5 0 − 15 3
5
Non ci sono coefficienti negativi nella colonna dei termini noti quindi abbiamo
trovato la soluzione ottima (0, 3/5, 0, 2/5, 0) in cui
12
Z=− .
5
Esempio 5.4.6 Applicare il metodo del simplesso duale per risolvere il se-
guente problema di programmazione lineare in forma non standard:
min Z = x1 + x2
−x1 +x2 ≤ −2
2x1 −x2 ≤ 1
x1 , x2 ≥ 0.
Il sistema da risolvere è
(0) −Z +x1 +x2 = 0
(1) −x1 +x2 +x3 = −2
(2) 2x1 −x2 +x4 = 1
Iterazione 0
Var. x1 x2 x3 x4
base Eq. Z bi
Z (0) −1 1 1 0 0 0
x3 (1) 0 −1 1 1 0 −2
x4 (2) 0 2 −1 0 1 1
Iterazione 1
Var. x1 x2 x3 x4
base Eq. Z bi
Z (0) −1 0 2 1 0 −2
x1 (1) 0 1 −1 −1 0 2
x4 (2) 0 0 1 2 1 −3
x1 −x2 ≥ 2
x1 +x2 ≥ 2
x2 ≤ 2
x1 , x2 ≥ 0.
Innanzitutto riscriviamo la funzione obiettivo come problema di massimo e
introduciamo due variabili surplus ed una slack:
1
max −Z = − x1 − x2
2
x1 −x2 −x3 = 2
x1 +x2 −x4 = 2
x2 +x5 = 2
x1 , x2 , x3 , x4 , x5 ≥ 0.
CAPITOLO 5. TEORIA DELLA DUALITÀ 194
Tableau iniziale
Var. x1 x2 x3 x4 x5
base Eq. Z bi
1
Z (0) −1 2 1 0 0 0 0
x3 (1) 0 −1 1 1 0 0 −2
x4 (2) 0 −1 −1 0 1 0 −2
x5 (3) 0 0 1 0 0 1 2
Iterazione 1
Var. x1 x2 x3 x4 x5
base Eq. Z bi
3 1
Z (0) −1 0 2 2 0 0 −1
x1 (1) 0 1 −1 −1 0 0 2
x4 (2) 0 0 −2 −1 1 0 0
x5 (3) 0 0 1 0 0 1 2
Non ci sono coefficienti negativi nella colonna dei termini noti quindi abbiamo
trovato la soluzione ottima (2, 0, 0, 0, 2) in cui
Z = 1.
CAPITOLO 5. TEORIA DELLA DUALITÀ 195
Esempio 5.4.8 Applicare il metodo del simplesso duale per risolvere il se-
guente problema di programmazione lineare in forma non standard:
min Z = 3x1 + 4x2 + 5x3
Iterazione 1
Var. x1 x2 x3 x4 x5
base Eq. Z bi
7 3
Z (0) −1 0 1 2 2 0 −9
1
x1 (1) 0 1 1 2
− 12 0 3
x5 (2) 0 0 −1 − 52 − 12 1 −2
CAPITOLO 5. TEORIA DELLA DUALITÀ 196
Iterazione 2
Var. x1 x2 x3 x4 x5
base Eq. Z bi
Z (0) −1 0 0 1 1 1 −11
x1 (1) 0 1 0 −2 −1 1 1
x2 5 1
(2) 0 0 1 2 2 −1 2
Esempio 5.4.9 Applicare il metodo del simplesso duale per risolvere il se-
guente problema di programmazione lineare in forma non standard:
max Z = −x1 − x2
x1 +3x2 = 5
3x1 +2x2 ≥ 1
x1 , x2 ≥ 0.
CAPITOLO 5. TEORIA DELLA DUALITÀ 197
x1 +3x2 ≥ 5
x1 +3x2 ≤ 5
3x1 +2x2 ≥ 1
x1 , x2 ≥ 0.
Scriviamo il problema in forma aumentata inserendo due variabili surplus
(nel primo e terzo vincolo) ed una variabile slack nel secondo:
max Z = −x1 − x2
x1 +3x2 −x3 = 5
x1 +3x2 +x4 = 5
3x1 +2x2 −x5 = 1
x1 , x2 , x3 , x4 , x5 ≥ 0.
Iterazione 0
Var. x1 x2 x3 x4 x5
base Eq. Z bi
Z (0) 1 1 1 0 0 0 0
x3 (1) 0 −1 −3 1 0 0 −5
x4 (2) 0 1 3 0 1 0 5
x5 (3) 0 −3 −2 0 0 1 −1
CAPITOLO 5. TEORIA DELLA DUALITÀ 198
Iterazione 1
Var. x1 x2 x3 x4 x5
base Eq. Z bi
2 1
Z (0) 1 3 0 3 0 0 − 35
1
x2 (1) 0 3 1 − 13 0 0 5
3
x4 (2) 0 0 0 1 1 0 0
x5 (3) 0 − 37 0 − 13 0 1 7
3
max Z = x1 + 2x2
20x1 +3x2 +x3 = 50
10x1 +3x2 +x4 = 30
x2 +x5 = 4
xi ≥ 0, i = 1, 2, 3, 4, 5.
Iterazione 0
Var. x1 x2 x3 x4 x5
base Eq. Z bi
Z (0) 1 −1 −2 0 0 0 0
x3 (1) 0 20 3 1 0 0 50
x4 (2) 0 10 3 0 1 0 30
x5 (3) 0 0 1 0 0 1 4
Iterazione 1
Var. x1 x2 x3 x4 x5
base Eq. Z bi
Z (0) 1 −1 0 0 0 2 8
x3 (1) 0 20 0 1 0 −3 38
x4 (2) 0 10 0 0 1 −3 18
x2 (3) 0 0 1 0 0 1 4
CAPITOLO 5. TEORIA DELLA DUALITÀ 202
Iterazione 2
Var. x1 x2 x3 x4 x5
base Eq. Z bi
1 17 49
Z (0) 1 0 0 0 10 10 5
x3 (1) 0 0 0 1 −2 3 2
x1 1 3 9
(2) 0 1 0 0 10
− 10 5
x2 (3) 0 0 1 0 0 1 4
Iterazione 0
Var. x1 x2 x3 x4 x5
base Eq. Z bi
Z (0) 1 −1 −2 0 0 0 0
x3 (1) 0 20 3 1 0 0 50
x4 (2) 0 10 3 0 1 0 30
x5 (3) 0 0 1 0 0 1 5
Iterazione 1
Var. x1 x2 x3 x4 x5
base Eq. Z bi
Z (0) 1 −1 0 0 0 2 10
x3 (1) 0 20 0 1 0 −3 35
x4 (2) 0 10 0 0 1 −3 15
x2 (3) 0 0 1 0 0 1 5
Iterazione 2
Var. x1 x2 x3 x4 x5
base Eq. Z bi
1 17 23
Z (0) 1 0 0 0 10 10 2
x3 (1) 0 0 0 1 −2 3 5
x1 1 3 3
(2) 0 1 0 0 10
− 10 2
x2 (3) 0 0 1 0 0 1 5
Il valore yi∗ definito in precedenza viene detto prezzo ombra per la risorsa
i e misura il valore marginale della risorsa, cioè il tasso di incremento di
Z ottenuto aumentando la disponibilità della i−esima risorsa. Il metodo
del simplesso identifica il prezzo ombra come il valore del coefficiente della
i−esima variabile slack nell’equazione (0) del tableau finale.
L’analisi dei prezzi ombra può essere fatta anche graficamente quando il
problema ha solo due variabili decisionali. Dall’analisi del prezzo ombra y1∗ =
0 si deduce che un incremento della prima risorsa non cambia la soluzione
ottima (infatti questa non soddisfa il primo vincolo in forma di uguaglianza).
5.6 Esercizi
Esercizio 5.6.1 Scrivere il problema duale dei seguenti problemi di program-
mazione lineare:
max Z = 3x1 + 2x2 − 5x3
4x1 −2x2 +2x3 ≤ 4
2x1 +x2 +x3 ≤ 1
x1 , x2 , x3 ≥ 0
min Z = 3x1 + x2 − 2x3 − x4
2x1 +x2 −x3 +3x4 ≤ 8
−x1 +2x2 −2x3 +2x4 ≤ 4
x1 +x2 ≤ 10
x1 , x2 , x3 , x4 ≥ 0
max Z = 4x1 + x2 + 5x3
−x1 +x2 ≤ 1
2x2 −x3 ≤ 2
x1 +x3 ≤ 1
x1 , x2 , x3 ≥ 0
Esercizio 5.6.2 Applicare il metodo del simplesso duale per risolvere il se-
guente problema
min Z = 3x1 + x2 + 3x3
x1 +x2 ≥ 4
x1 +x2 −x3 ≥ 8
x1 , x2 , x3 ≥ 0
(Soluzione: Z = 8).
CAPITOLO 5. TEORIA DELLA DUALITÀ 205
Esercizio 5.6.3 Applicare il metodo del simplesso duale per risolvere il se-
guente problema
min Z = 2x1 + 3x2 + x3
x1 +x2 −x3 ≥ 6
2x1 +x3 ≥ 4
x1 +x2 −2x3 ≤ 2
x1 , x2 , x3 ≥ 0
(Soluzione: Z = 24).
Esercizio 5.6.4 Considerato il seguente problema di programmazione linea-
re:
max Z = 8x1 + 7x2
2x1 +x2 ≤ 2
3x1 +x2 ≤ 4
−x1 +2x2 ≤ 2
x1 , x2 ≥ 0
determinare di quale delle risorse associate a ciascun vincolo conviene incre-
mentare la disponibilità per aumentare maggiormente il valore della funzione
obiettivo nella soluzione ottima.
(Soluzione: la prima risorsa).
Esercizio 5.6.5 Considerato il seguente problema di programmazione linea-
re:
max Z = 4x1 + x2
3x1 −x2 ≤ 4
2x1 +2x2 ≤ 3
−x1 +2x2 ≤ 4
x1 , x2 ≥ 0
determinare di quale delle risorse associate a ciascun vincolo conviene incre-
mentare la disponibilità per aumentare maggiormente il valore della funzione
obiettivo nella soluzione ottima.
(Soluzione: la seconda risorsa).
Esercizio 5.6.6 Considerato il seguente problema di programmazione linea-
re:
max Z = 3x1 + 4x2
2x1 −x2 ≤ 4
4x1 +3x2 ≤ 3
x1 +2x2 ≤ 1
x1 , x2 ≥ 0
CAPITOLO 5. TEORIA DELLA DUALITÀ 206