Lezioni di Ricerca Operativa

Lezioni di Ricerca Operativa
Massimo Paolucci
Dipartimento di Informatica, Sistemistica e Telematica
(DIST)
Università di Genova
[email protected]
http://www.dattero.dist.unige.it
Estratto per la parte di programmazione lineare
del corso di Ricerca Operativa per
Ingegneria Gestionale
A.A. 2011/2012
1
La Ricerca Operativa
(Operation Research)
?
Metodi matematici rivolti alla soluzione di problemi decisionali
?
Nata durante la seconda guerra mondiale (gestione di risorse
limitate e problemi logistici)
?
Si è sviluppata grazie alla disponibilità di strumenti automatici
di calcolo (computer)
?
Scopo: determinare la decisione ottima dato un problema in
presenza di risorse limitate
?
I problemi reali vengono affrontati definendone una
rappresentazione quantitativa (modello matematico)
?
La soluzione dei problemi è cercata per mezzo di tecniche
(algoritmi) di ottimizzazione
?
Applicazioni:
?
Problemi logistici della produzione
?
Problemi decisionali di tipo economico
?
Problemi di gestione operativa
?
...
2
Esempi di applicazioni:
?
Problemi logistici della produzione
? Pianificazione della produzione
? Controllo delle scorte
? Scheduling
? Trasporto
?
Problemi decisionali di tipo economico
? Allocazione di capitali
? Acquisto/Produzione di beni
?
Problemi di gestione operativa
? Definizione dei turni di lavoro
? Definizione delle rotte di mezzi di trasporto
? Facility location
? Gestione ottima di risorse idriche
? Ottimizzazione di politiche di controllo
? Gestione ottima di aree di carico/scarico
? Problemi in reti di comunicazione e distribuzione
3
Formulazione dei problemi decisionali
?
Decisione: processo di selezione tra più alternative
?
Alternative finite o infinite
?
Alternative definite esplicitamente o implicitamente
?
Scelta sulla base di uno o più criteri (obiettivi)
?
Condizioni di certezza, incertezza o rischio
Problema
Reale
Formulazione
Modello
Modello
Matematico
Matematico
Problema fondamentale della Ricerca Operativa:
identificare un modello matematico con cui studiare
in modo sistematico il problema decisionale
4
Struttura del problema di decisione
Modello
ModelloMatematico
Matematico
Obiettivi
Obiettivi
Variabili
Variabilidecisionali
decisionali
Vincoli
Vincoli
Caratteristiche dei problemi che saranno considerati:
? Condizioni di certezza (problemi deterministici)
? Presenza di un solo criterio (singolo obiettivo)
?
Per risolvere i problemi decisionali sono usati algoritmi
?
Un algoritmo è una procedura iterativa costituita da un numero
finito di passi
?
Esistono problemi facili (pochi) e difficili
?
La facilità di un problema è legata all’esistenza di un algoritmo di
soluzione efficiente
5
Un esempio: Assegnare 70 lavori a 70 persone.
?
Si indichino con i=1,...,70 i lavori e con j=1,...,70 le persone.
?
Se la i-esima persona esegue il j-esimo lavoro si paga un costo cij.
?
Una persona può eseguire solo un lavoro (vincolo)
?
?
Ogni lavoro deve essere eseguito (vincolo)
Lo scopo (decisione) è stabilire chi fa che cosa in modo che il
costo pagato sia minimo (obiettivo).
Un possibile algoritmo di soluzione (Brute Force):
1) costruire tutte le possibili assegnazioni persone-lavori e
calcolarne il costo
2) scegliere l’assegnazione con il costo più piccolo
Le assegnazioni alternative sono 70! (le permutazioni di 70 numeri)
Persone 1 2
Lavori 1 2
70 Persone 1 2
70 Lavori 2 1
Il numero delle assegnazioni alternative è molto grande
70! ? 10100
6
70
70
Si supponga di disporre di un calcolatore che è in grado di calcolare
106 assegnazioni alternative (soluzioni) al secondo.
Quanto impiega l’algoritmo a risolvere il problema?
Supponendo di dover “esplorare” 10100 assegnazioni sono necessari
1094 secondi.
In un anno ci sono:
365(gg)x24(h)x60(min)x60(sec)? 31?106 ? 107 sec
Per risolvere il problema sono necessari 1087 anni !
Il Big Bang (data di inizio dell’Universo)
è avvenuto circa 15?109 anni fa!
...ma se si disponesse di un calcolatore 1000 volte più veloce?
...si impiegherebbero 1084 anni.
...e se si usassero 109 calcolatori in parallelo?
...si impiegherebbero 1075 anni.
7
Conclusioni:
?
L’algoritmo Brute Force non è efficiente!
?
Se questo fosse l’unico algoritmo utilizzabile per il problema
dell’assegnazione persone-lavori, il problema sarebbe difficile
?
La soluzione ottima dei problemi difficili può essere trovata solo
per casi di ridotte dimensioni
? I problemi in cui la scelta è tra un numero finito di alternative (le
variabili decisionali possono assumere sono un numero discreto
di valori) si dicono combinatorici.
? La teoria della complessità una parte della Ricerca Operativa che
studia la difficoltà della soluzione dei problemi.
? Conoscere che un problema è difficile permette la scelta di un
appropriato algoritmo:
?
?
?
?
Algoritmi esatti basati sull’enumerazione esplicita delle
soluzioni
Algoritmi esatti basati sull’enumerazione implicita delle
soluzioni
Algoritmi approssimati
Algoritmi euristici
8
Programmazione Matematica Lineare
Problema di Programmazione Matematica
ottimizzazione)
(PM) ( problema di
max f(x)
s.t.
x ∈X ⊆ Rn
vettore delle variabili
decisionali
insieme delle soluzioni
ammissibili
funzione obiettivo
scalare
Un problema di PM è lineare quando:
f ( x) = cT x
la funzione obiettivo è lineare
l’insieme X è espresso in termini di relazioni (uguaglianze e
disuguaglianze) lineari
{
}
variabili x continue
Programmazione Lineare Continua
(PL)
{
}
variabili x intere
Programmazione Lineare Intera
(PLI)
x ∈ R n : Ax ≤ b
X
x ∈ Z n : Ax ≤ b
9
Esempio grafico in 2 dimensioni
{
}
X = x ∈ R n : Ax ≤ b
poliedro composto da ∞ punti
x2
X
{
}
X = x ∈ Z n : Ax ≤ b
x1
poliedro composto da un numero finito di
punti
x2
X
x1
10
Esempio: pianificare la produzione di una
piccola azienda che produce vernici
L’azienda produce due tipi di vernici, una vernice per interni (I) ed
una per esterni (E), usando due materie prime indicate con A e B.
La disponibilità al giorno di materia prima A è pari a 6 ton, mentre
quella di materia prima B è di 8 ton.
La quantità di A e B consumata per produrre una ton di vernice E
ed I è riportata nella seguente tabella.
materie prime
A
B
vernici
E
I
1
2
2
1
Si ipotizza che tutta la vernice prodotta venga venduta.
Il prezzo di vendita per tonnellata è 3K$ per E e 2K$ per I.
L’azienda ha effettuato un’indagine di mercato con i seguenti esisti:
• la domanda giornaliera di vernice I non supera mai di più di 1 ton
quella di vernice E
• la domanda massima giornaliera di vernice I è di 2 ton
Problema: determinare le quantità delle due vernici che debbono
essere prodotte giornalmente in modo da rendere
massimo il guadagno.
11
Esempio: formulare il modello matematico
Definizione
delle variabili
Definizione
dell’obiettivo
Formulazione
Matematica
Definizione
dei vincoli
Definizione delle variabili
Si introducono due variabili che rappresentano le quantità
prodotte (e vendute) al giorno per le due vernici (ton):
x E produzione di vernice per esterni
xI produzione di vernice per interni
Le due variabili sono continue.
12
Definizione dell’obiettivo
Il guadagno giornaliero (K$) è dato da
Z = 3x E + 2 x I
L’obiettivo è rappresentato da un’equazione lineare.
Definizione dei vincoli
• Vincoli ( tecnologici) sull’uso delle materie prime ( l’uso
giornaliero delle materie prime non può eccedere la
disponibilità):
(A) x E + 2 xI ≤ 6
(B) 2 x E + x I ≤ 8
• Vincoli conseguenti le indagini di mercato
xI − x E ≤ 1
xI ≤ 2
• Non negatività delle variabili
xE ≥ 0
xI ≥ 0
13
La formulazione definisce un Problema di Programmazione Lineare
a variabili continue
max Z = 3x E + 2 x I
x E + 2 xI ≤ 6
2 x E + xI ≤ 8
− x E + xI ≤ 1
xI ≤ 2
xE ≥ 0
xI ≥ 0
xI
(1)
( 2)
( 3)
( 4)
(5)
( 6)
}
Funzione obiettivo
vincoli che definiscono quali valori
sono ammessi per le due variabili
(Insieme delle soluzioni ammissibili)
(5)
8
7
(2)
(3)
6
5
4
3
(4)
2
1
−2
−1
(1)
X
1
2
3
4
14
5
(6)
6
xE
xI
(5)
4
(2)
(3)
3
2
1
E
(4)
D
C
F
A
-2
-1
(6)
B
1
2
3
4
z=6
l’obiettivo per
z=0
A=(0,0) B=(4,0)
Ottimo
C=(10/3,4/3)
D=(2,2)
5
6
xE
(1)
z=38/3
E=(1,2) F=(0,1)
Proprietà:
• le soluzioni si trovano sulla frontiera del poliedro
X, quindi
corrispondono ai vertici di X;
• deve essere considerato solo un numero finito di soluzioni.
15
Se la funzione obiettivo fosse parallela ad un vincolo ...
xI
I punti del segmento DC
sono tutti ottimi
2
1
E
D
un diverso obiettivo
parallelo a (1)
C
F
X
A
B
1
2
3
4
xE
... esisterebbero infiniti punti di ottimo tutti equivalenti (nell’esempio,
quelli del segmento DC).
In questo caso si potrebbe scegliere alternativamente tra
estremi C e D.
i punti
La ricerca dell’ottimo resta pertanto una esplorazione tra un numero
finito di soluzioni alternative corrispondenti ad i vertici del poliedro
X.
16
Formulazione di Problemi Decisionali come
Problemi di Programmazione Lineare
Consideriamo i seguenti problemi decisionali ed esaminiamo come
possono essere formulati come problemi di PL:
•
Il problema del trasporto
•
Il problema del “product-mix”
•
Il problema della pianificazione della produzione (production
planning)
17
Il Problema del Trasporto
•
m fonitori producono s1,..., sm quantità di un certo prodotto (ad
esempio, gas o petrolio)
•
n destinatari richiedono r1,..., rn quantità di prodotto
•
il prodotto può essere trasportato da ogni fornitore ad ogni
destinatario (ad esempio attraverso un gasdotto o oleodotto)
•
per ogni unità di prodotto trasportata dal fornitore i al cliente j
viene pagato un costo cij
Il problema: determinare quali quantità di prodotto trasportare tra
ogni coppia (i,j) di fornitori-destinatari in modo da
minimizzare il costo complessivo del trasporto.
s1
si
r1
M
M
rj
cij
M
M
sm
rn
18
Ipotesi di ammissibilità
Perché il problema possa ammettere una soluzione deve essere
verificata la seguente condizione sui dati
m
n
i =1
j=1
∑ si ≥ ∑ rj
che stabilisce che la quantità totale di prodotto disponibile non
può essere inferiore alla richiesta totale del prodotto stesso.
Formulazione del problema.
Le variabili:
la quantità di prodotto trasportata su ciascun arco
x ij ∈ R
i = 1,..., m; j = 1,..., n
sono variabili continue
La funzione obiettivo:
il costo del trasporto complessivo
m
n
∑ ∑ c ijx ij
i = 1 j= 1
19
I vincoli:
•
la quantità totale di prodotto fornita da ciascun fornitore
può superare la disponibilità del fornitore stesso
non
n
∑ x ij ≤ si i = 1,..., m (1)
j= 1
•
la quantità totale di prodotto ricevuta da ciascun destinatario
deve essere uguale a quella richiesta
m
∑ x ij = r j j = 1,..., n
i =1
•
(2 )
le quantità di prodotto trasportate sugli archi sono sempre non
negative
x ij ≥ 0 i = 1,.., m; j = 1,..., n
20
( 3)
Il problema del
trasporto
m
n
min ∑ ∑ c ijx ij
i = 1 j= 1
n
∑ x ij ≤ si i = 1,..., m
j= 1
m
∑ x ij = r j j = 1,..., n
i =1
(1)
(2)
x ij ≥ 0 i = 1,..., m; j = 1,..., n ( 3)
x ij ∈ R i = 1,..., m; j = 1,..., n
• E’ un problema di PL con variabili continue.
• Può essere risolto con l’algoritmo del simplesso.
• Possibili variazioni:
• introduzione della massima capacità per gli archi;
• non tutti i fornitori sono connessi a tutti i destinatari;
• il trasporto non avviene direttamente tra fornitore
e
destinatario ma attraverso dei centri
di raccolta e
distribuzione intermedi
21
Il Problema del Product-Mix
•
si dispone di m risorse produttive in quantità limitata , in
particolare, la loro massima disponibilità
èb
1,...,
b
m
(ad
esempio, materie prime)
•
possono essere eseguite n attività che necessitano delle risorse
precedenti (ad esempio, la produzione di n diversi prodotti)
•
alle n attività sono associati i seguenti profitti unitari c 1,..., c n
(ad esempio, il profitto per unità di prodotto)
•
sono noti i consumi di risorse per unità di attività eseguita ; in
particolare, per eseguire una unità della attività
i- esima si
utilizzano aij unità della risorsa j-esima
Il problema: determinare quali attività eseguire ed a quale livello
(ad esempio, quali e quanti prodotti produrre) in
modo da massimizzare il profitto conseguente.
(Nota: a questa classe di problemi appartiene il problema
dell’azienda che produce vernici.)
22
Formulazione del problema.
Le variabili:
i livelli a cui devono essere eseguite le attività (variabili
continue)
xi ∈R
i = 1,..., n
La funzione obiettivo:
il profitto risultante dall’esecuzione delle attività
n
∑ ci xi
i =1
I vincoli:
• per ciascuna risorsa , la quantità totale di risorsa utilizzata per
eseguire le attività non può superare la disponibilità massima
della risorsa stessa
n
∑ a ijx i ≤ b j j = 1,..., m (1)
i =1
•
i livelli delle attività sono sempre non negativi
x i ≥ 0 i = 1,.., n
23
( 2)
Il problema del product-mix
n
max ∑ c i x i
i =1
n
∑ a ijx i ≤ b j j = 1,..., m
(1)
x i ≥ 0 i = 1,..., n
x i ∈ R i = 1,..., n
(2)
i =1
24
Il Problema della pianificazione della produzione
(Production Planning)
Caso considerato: pianificare la produzione di un singolo prodotto per
i prossimi N mesi.
•
per ciascuno degli
N mesi è nota la capacità produttiva
massima del prodotto, m1,...,mN
•
sono noti c1,...,cN, i costi di produzione per unità di prodotto nei
diversi mesi
•
sono noti r 1,...,rN, i costi di immagazzinamento per unità di
prodotto nei diversi mesi
•
è nota la domanda di prodotto per i diversi mesi, d1,...,dN
•
è nota la disponibilità iniziale di prodotto in magazzino M0
Il problema: determinare la quantità di prodotto da produrre nei
diversi mesi minimizzando il costo complessivo di
produzione e di immagazzinamento.
25
Formulazione del problema.
Le variabili:
•
la quantità di prodotto pianificata per ciascun mese (variabili
continue)
x i ∈ R i = 1,..., N
•
la quantità di prodotto che deve essere immagazzinata per
ciascun mese (variabili continue)
si ∈ R
i = 1,..., N
La funzione obiettivo:
il costo totale pagato per la produzione più quello pagato
per l’immagazzinamento durante l’arco degli N mesi
N
∑ ( c i x i + ri si )
i =1
I vincoli:
• per ciascun mese , la quantità il prodotto disponibile ( prodotto
nel mese o presente perchè immagazzinato il mese precedente )
soddisfa la domanda corrente ; l’eventuale rimanenza viene
immagazzinata e resa disponibile per il mese successivo ( legge
di conservazione del prodotto)
x i + si −1 = d i + si i = 1,..., N (1)
26
•
la produzione mensile non può superare la relativa capacità
produttiva
x i ≤ m i i = 1,..., N ( 2 )
•
il livello iniziale del magazzino è quello dato
s0 = M 0
•
(3)
il livello di produzione e la quantità di prodotto in magazzino nei
vari mesi non può essere negativa
x i ≥ 0 si ≥ 0 i = 1,.., N
(4)
Il problema del production planning (singolo prodotto)
N
min ∑ (ci x i + risi )
i =1
x i + si −1 − si = d i i = 1,..., N (1)
x i ≤ m i i = 1,..., N
( 2)
s0 = M 0
(3)
x i ≥ 0si ≥ 0i = 1,..., N
( 4)
x i ∈ R si ∈ R i = 1,..., N
Una possibile variante consiste nel considerare
diversi prodotti.
27
la produzione di n
Soluzione dei Problemi di
Programmazione Lineare
Consideriamo un problema di Programmazione Lineare (PL) con m
vincoli ed n variabili in Forma Standard
max x0 = cT x
Ax = b
x≥0
(1)
(2)
x ∈Rn
dove:
• x è il vettore nx1 delle variabili decisionali
• c è il vettore nx1 dei coefficienti della funzione obiettivo
• b è il vettore mx1 dei termini noti dei vincoli
• A è la matrice mxn dei coefficienti dei vincoli; A=[aij], i=1,...,n,
j=1,...,m
Inoltre, si assumono soddisfatte le seguenti ipotesi:
b ≥ 0 ⇒ b j ≥ 0 ∀j = 1,K , m
• m<n
• m=rango(A)
Qualunque problema di PL può essere trasformato in un problema
equivalente in forma standard.
28
I valori di x che soddisfano i vincoli (1) sono detti soluzioni del
problema di PL.
Inoltre, i valori di x che soddisfano anche i vincoli (2) sono detti
soluzioni ammissibili del problema di PL.
L’ipotesi m<n ( più variabili che vincoli ) non rappresenta una
perdita di generalità . E’ noto infatti che il sistema di equazioni
lineari (1):
• può ammettere una soluzione unica se m=n
• può ammettere soluzione se m>n ed almeno m-n equazioni sono
ridondanti (quindi possono essere eliminate)
n−m
• può ammettere ∞
soluzioni se m<n
Solo l’ultimo caso è significativo dal punto di vista dei problemi di
ottimizzazione.
Un problema di PL può essere:
a) Ammissibile con soluzioni ottime finite
b) Ammissibile senza soluzione ottime finite ( detto anche
illimitato, o con ottimo all’infinito)
c) Non Ammissibile (senza soluzioni ammissibili)
29
Da un punto di vista grafico i tre casi corrispondono a:
a) una regione di ammissibilità
associata ad un poliedro chiuso non
vuoto (Politopo)
{
X
}
X = x ∈ R n : Ax ≤ b ≠ ∅
b) una regione di ammissibilità
associata ad un poliedro aperto
non vuoto
X
(n.b., una soluzione ottima
all’infinito implica un poliedro X
aperto, ma non è vero il viceversa)
X ≠ ∅ (X aperto)
c) una regione di ammissibilità
associata ad un poliedro vuoto
X2
X1
X = ∅ ⇒ ∃x ∈ R n tale chex ∈ X
X = X1 ∩ X 2 = ∅
30
• Un poliedro è dato dall’intersezione di semispazi.
• Un semispazio in n dimensioni è individuato da una disuguaglianza
n
T
lineare a x ≤ b x ∈R
• Un poliedro X è un insieme convesso
Definizione
Un insieme X è convesso se e solo se dati due punti x a , x b ∈ X
ogni punto y generato come y = λ x a + (1 − λ ) x b
0≤ λ ≤1
(combinazione convessa di x a , x b ) è tale che y ∈ X
Vertici del Poliedro X
xa
X
y
I vertici di un poliedro si dicono
Punti Estremi
xb
Definizione
Un punto di un poliedro X è un punto estremo se e solo se non può
essere espresso come combinazione convessa di altri punti di X.
31
1. Teorema (Proprietà dei punti estremi di un poliedro)
Dato X poliedro chiuso non vuoto con punti estremi x e i , i = 1,..., E
ogni punto x ∈X può essere espresso come combinazione
convessa dei punti estremi di X:
E
E
i =1
i =1
x = ∑ λ i x e i con ∑ λ i = 1 λ i ≥ 0 ∀i
x e1
Ad es., la combinazione convessa
di x e1 x e 2 x e 3
permette di esprimere tutti i punti
di X'⊂ X
x e2
X’
X
x e3
Se X è un poliedro aperto non vuoto per esprimere tutti i suoi punti
oltre ad i punti estremi si devono utilizzare anche le
sue direzioni
estreme.
Definizione
Dato un poliedro X, d è una direzione di X se e solo se
∀x ∈X ⇒ x + µd ∈ X
µ ≥ 0.
32
Ad esempio:
x
X
x + µ d ( µ ≥ 0)
d
Definizione
Una direzione d di un poliedro X, è una direzione estrema di X se
e solo se non è
esprimibile come combinazione lineare di altre
direzioni di X.
Ad esempio:
X
x
d = µ1 d e1 + µ 2 d e 2
µ1 , µ 2 ≥ 0
d e2
d e1
33
2. Teorema (Proprietà dei punti estremi e delle direzioni
estreme di un poliedro)
Dato X poliedro non vuoto con punti estremi x e i , i = 1,..., E
e direzioni estreme d e j , j = 1,..., D
Ogni punto x ∈X può essere espresso come combinazione
convessa dei punti estremi di X e combinazione lineare delle sue
direzioni estreme:
E
D
i =1
j=1
x = ∑ λ i x ei + ∑ µ j d e j
E
con ∑ λ i = 1 λ i ≥ 0 ∀i , µ j ≥ 0 ∀j
i =1
Se d è una direzione del poliedro X = {A x = b , x ≥ 0}
allora si ha che
x + λ d ∈ X x ∈ X, λ ≥ 0 ⇒ A( x + λ d ) = b ⇒ A d = 0
34
Soluzione Algebrica dei problemi di PL
Consideriamo il problema (PL) in Forma Standard
(PL)
max x0 = cT x
Ax = b
x≥0
(1)
( 2)
x ∈Rn
Poiché m=rango(A) ed m<n, si può partizionare A come
A = [B N]
dove:
• B è matrice non singolare mxm (det( B) ≠ 0)
• N è matrice mx(n-m)
La matrice B è composta da m colonne linearmente indipendenti di
A. Tali colonne sono quindi una base nello spazio vettoriale ad m
dimensioni delle colonne di A.
La matrice B è detta Matrice di Base (Base).
In corrispondenza di una scelta di B ed N si può partizionare anche il
vettore delle x:
 x  m componenti
x =  B
x N  n − m componenti
x B è detto Vettore delle Variabili in Base (Vettore di Base)
x N è detto Vettore delle Variabili fuori Base
35
Il sistema di equazioni lineari A x = b si può riscrivere come
x 
[ B N]x B  = b ⇒ Bx B + Nx N = b
 N
⇒
x B = B−1 b − B−1Nx N
Una soluzione del sistema di equazioni (1) corrisponde a determinare
il valore per m variabili ( x B ) avendo fissato arbitrariamente il valore
per le restanti n-m variabili (xN)
Una scelta particolarmente importante è porre xN = 0 da cui si ottiene
 x B   B−1 b 
x= =

x
0
 N  

Soluzione di Base
Se x B = B−1 b ≥ 0 si ottiene una Soluzione di Base Ammissibile.
36
Le soluzioni di base sono importanti poichè vale il seguente teorema
3. Teorema
Dato X = {Ax = b, x ≥ 0}
insieme convesso, dove A è una
matrice mxn di rango m con m<n, xe è un punto estremo di X
se e solo se xe è una soluzione di base ammissibile.
• La ricerca delle soluzioni di un problema di PL si può effettuare
esaminando solamente un numero finito di soluzioni corrispondenti
alle soluzioni di base associate al poliedro dei vincoli.
• In generale, a ciascuna matrice di base B ( ammissibile) corrisponde
una sola soluzione di base (ammissibile).
• Viceversa, ad una soluzione di base (
ammissibile) possono
corrispondere più matrici di base. Questi casi sono associati
a
soluzioni dette degeneri, ovvero per cui qualche componente del
vettore di base x B risulta nullo.
Un esempio.
max x0 = 2 x1 + x2
x1 + x2 ≤ 5
− x1 + x2 ≤ 0
(1)
( 2)
6x1 + 2 x2 ≤ 21 (3)
x1 ≥ 0 x2 ≥ 0
Il problema non è in forma standard !
(continua)
37
Trasformazione dei problemi in forma standard.
⇒ Vincoli ≤
Si introducono variabili ausiliarie positive dette Variabili di Slack
(scarto):
n
∑ a ijx j ≤ bi
j=1
n
→ ∑ a ijx j + si = bi
j=1
⇒ Vincoli ≥
Si introducono variabili ausiliarie
Surplus (eccedenza):
n
n
j=1
j=1
si ≥ 0
positive dette
∑ aijx j ≥ bi → ∑ aijx j − si = bi
Variabili di
si ≥ 0
⇒ Variabili non vincolate in segno (variabili libere)
Si sostituisce la variabile libera con due variabili ausiliarie positive
(il problema diventa ad n+1 variabili):
x j libera → x j = u j − v j con u j ≥ 0 v j ≥ 0
⇒ Termini noti dei vincoli negativi
Si moltiplicano entrambe i membri per -1 e si cambia il verso della
disuguaglianza
⇒ Problema di minimo
Si trasforma il problema
funzione obiettivo.
in massimo moltiplicando per -1 la
38
Un esempio (seguito).
Il problema trasformato in forma standard:
max x0 = 2 x1 + x2
x1 + x 2 + x3
= 5 (1)
− x1 + x2
+ x4
= 0 (2)
+ x5 = 21 ( 3)
6x1 + 2 x2
x1 ≥ 0 x2 ≥ 0 x3 ≥ 0 x4 ≥ 0 x5 ≥ 0
x2
(3)
5
(1)
4
(2)
3
P2
2
x0 = 0
x 0 = 7.75
1
P3 Ottimo
X
x1
P4
P1
1
2
3
4
5
 1 1 1 0 0
A =  − 1 1 0 1 0


 6 2 0 0 1
39
5
b=0
 
21
Il massimo numero di possibili basi corrisponde al numero di possibili
estrazioni di m colonne su n colonne di A:
 n
n!
 =
 m m!( n − m)!
 5
 3
Nell’esempio   =
5!
= 10
3! 2 !
In generale, non tutte le possibili sottomatrici mxm sono non-singolari
(quindi invertibili). Inoltre, non tutte le matrici di base danno luogo a
soluzioni ammissibili (ossia, positive).
Per questo fatto il numero delle combinazioni corrisponde ad un limite
superiore.
Nell’esempio solo 6 combinazioni danno luogo a basi ammissibili:
 1 1 0
B1 = − 1 1 1


 6 2 0
 x1 
11 4 
x1B = x2  = B1−1 b =  9 4  ⇒ P3
 


x4 
 1 2 
dove
 x1  5 2
x2B =  x2  = 5 2 ⇒ P2
   
 x5   1 
 x1  7 2
x3B =  x3  = 3 2  ⇒ P4
   
x4  7 2
 x1 
 x2 
 x4   0 
x4B = x3  = x5B =  x3  = x6B =  x3  =  5  ⇒ P1
 
 
   
 x5 
 x5 
 x5  21
40
(soluzioni degeneri)
Dalla corrispondenza delle soluzioni di base ammissibili con i punti
estremi del poliedro X deriva il seguente teorema.
4. Teorema Fondamentale della PL
Se un problema di PL ammette soluzione , allora esiste una
soluzione ammissibile di base.
Se un problema di PL ha soluzione ottima finita , allora ha anche
una soluzione di base ottima.
• Poiché il massimo numero di possibili basi di un problema di PL è
finito, tali problemi hanno una struttura discreta.
• I problemi di ottimizzazione corrispondenti alla selezione tra un
numero finito di alternative si dicono problemi combinatorici.
• La PL è quindi un problema combinatorico.
• Un possibile algoritmo per determinare la soluzione ottima potrebbe
consistere nella generazione esplicita
di tutte le soluzioni
ammissibili di base, quindi nella scelta di quella soluzione che rende
massimo l’obiettivo.
• Tale strategia non è conveniente poichè il numero massimo delle
possibili basi cresce in maniera esponenziale col crescere delle
dimensioni del problema (numero di variabili e vincoli).
• Algoritmi che richiedono in generale un numero di passi che cresce
in maniera esponenziale con le dimensioni del problema non sono
efficienti.
41
Calcolo della soluzione ottima di un problema di PL.
Supponendo di aver individuato una base B ammissibile, riscriviamo
la funzione obiettivo:
 xB  T
c N ]   = c B x B + cT
N xN
x
 N
x 0 = cT x = [ c B
(1)
Sostituiamo in (1) l’espressione delle variabili di base:
x B = B−1 b − B−1Nx N
ottenendo:
(
(2)
)
−1
T −1
T
x0 = cT
BB b − c BB N − c N x N
(3)
T −1
Il valore dell’obiettivo corrispondente alla base B è x0 = cBB b
Le relazioni (2) e (3) esprimono rispettivamente i vincoli e la funzione
obiettivo in funzione delle variabili fuori base.
Raccogliamo (2) e (3) in in forma matriciale:

 x 0  c T
B−1 b  cT
B−1N − cT
B
B
N x
=
−
 N
 x   −1  
−1N
B
b
B
 B  
 

Le (4) sono m+1 equazioni.
42
(4)
Trasformiamo le (4) in una forma più compatta.
In particolare, si pone:
• R l’insieme degli indici delle variabili fuori base, ovvero
delle colonne di N
x B0 = x0
e
 xB 
 1
xB =  M 
x B 
 m
 y00 
cTBB−1 b   y10 

• y0 =  −1  = 
 B b   M 
y 
 m0 
vettore (m+1)-dim
 y0 j 
−1
c T
  y1 j 
BB a j − c j
 ∀j ∈ R
=
• yj = 
 B−1a j   M 
y 
 mj 
n-m vettori (m+1)-dim
dove a j e c j sono rispettivamente la colonna di N ed il coefficiente di
c N che moltiplicano la j-esima variabile fuori base.
43
Le (4) si possono quindi riscrivere come segue
x Bi = yi 0 − ∑ y ijx j
∀i = 0,1,K, m
j∈R
(5)
Ponendo nelle (5) x j = 0 ∀j ∈ R si ottengono il valore dell’obiettivo
(i=0) e le soluzioni di base (i=1,...,m) corrispondenti alla base attuale.
Verifichiamo se la soluzione corrente è ottima.
Consideriamo l’obiettivo:
x B0 = y 00 − ∑ y 0 jx j
j∈R
Supponiamo che esista un coefficiente y 0k<0, e consideriamo come
varia l’obiettivo facendo diventare positiva la variabile fuori base x k,
attualmente nulla.
>0
}
x B0 = y 00 − y 0 k x k > y 00
<0
L’obiettivo migliora !
>0
Allora si potrebbe pensare
di aumentare indefinitivamente x
migliorando sempre l’obiettivo.
Tuttavia, aumentando x k anche le equazioni (5) corrispondenti ai
vincoli variano, modificando i valori delle variabili di base.
44
k
Consideriamo la generica equazione i- esima in funzione della
variabile fuori base xk che stiamo incrementando:
xBi = yi0 − yik xk
Se yik>0, aumentando xk la xBi diminuisce.
E’ quindi possibile aumentare xk fino a che xBi ≥ 0 (ammissibile).
Il valore limite di x k perché la i- esima variabile di base
ammissibile è quindi:
resti
y
xk = i0 ⇒ xBi = 0
yik
Facendo assumere ad x k un valore positivo significa
portare la
variabile in base.
Nello stesso tempo il valore delle altre variabili di base per cui y ik>0
diminuisce.
Il valore che x
quello corrispondente
k assume in base è
all’annullamento della prima variabile di base, ad es. xBr,cioè
y 
yr 0
= min  i0 
y rk i =1,..., M yik 
yik >0
La variabile xk entra in base con tale valore, ed in corrispondenza la
variabile xBr esce di base.
45
Il coefficiente y rk è detto Pivot, ( l’aggiornamento della base si dice
Pivoting) e viene usato per aggiornare i valori delle variabili in base
dopo l’ingresso in base di xk:
y
x Bi = yi0 − yik r 0
y rk
∀i = 0,..., m; i ≠ r
y
xk = r 0
y rk
xj = 0
∀j ∈ R' = R − {k}
La nuova soluzione di
base
x Br = 0 Le nuove variabili fuori base
Con il cambio delle variabili in base, la nuova matrice di base
risulta composta delle stesse colonne della vecchia
base ad
eccezione del fatto che la colonna associata a xBrè stata sostituita
dalla colonna associata a xk.
Aggiorniamo le equazioni (5) dopo il cambio di base:
y rj 
y rj

y r0
x Bi = y i0 − y ik
− ∑  y ij − y ik
x Br
xj +
y rk j∈R − {k} 
y rk 
y rk
∀i = 0,1,K, m; i ≠ r
(5’)
y rj
yr0
1
xk =
− ∑
xj −
x Br
y rk j∈R − {k} y rk
y rk
46
I nuovi valori delle variabili in base si ottengono ponendo nelle (5’)
xj = 0
∀j ∈ R − {k} x Br = 0
La nuova soluzione di base ha migliorato il valore della funzione
obiettivo:
>0
}
y
x B 0 = y 00 − y 0k r 0 > y 00
{ y rk
<0 {
>0
E’ possibile iterare il procedimento fino a che esiste qualche variabile
fuori base che può migliorare l’obiettivo se portata in base.
5. Teorema (Condizione di ottimalità)
Una soluzione di base non
ottima se e solo se:
degenere di un problema di PL è
1) y i0 ≥ 0
i = 1,..., m
(ammissibile)
2) y 0 j ≥ 0
∀j ∈ R
(non migliorabile)
Nel caso di soluzione degenere possono esistere soluzioni ottime in
cui il punto (2) del terorema 5 non è soddisfatto.
Tuttavia, se un problema ammette soluzione ottima finita allora
ammette una soluzione di base ottima che soddisfa le condizioni (1) e
(2) del teorema 5.
47
Scelta della variabile entrante.
Quando la condizione di ottimalità non è verificata è sempre possibile
scegliere una variabile fuori base x k da portare in base per migliorare
l’obiettivo.
Quando esistono più
alternative la
scelta non preclude
il
raggiungimento della soluzione ottima, ma può al peggio aumentare il
tempo necessario per la sua ricerca.
Esistono due criteri di scelta della variabile entrante:
a) Il metodo del gradiente (il più utilizzato)
Sceglie la variabile che localmente fa aumentare più rapidamente
l’obiettivo:
y = min y
0k
j∈R
y0j <0
0j
b) Il metodo del massimo incremento
Sceglie la variabile che effettivamente provoca il maggior
aumento dell’obiettivo:

yr 0 

k = arg max − y 0 j
y
rj 
j∈R 
y0j <0
dove r è l’indice della variabile che lascia la base a causa
dell’ingresso in base di xj.
48
Scelta della variabile uscente.
Determinata la variabile fuori base x k da portare in base, si deve
scegliere la variabile uscente. Esistono due situazioni alternative:
a)
yrk>0 per almeno un r
Allora si può aggiornare la base come visto.
b) y ik ≤ 0 ∀i = 1,..., m
Allora la soluzione del problema è illimitata (non esiste
ottimo finito).
In questo caso facendo aumentare xk il valore di nessuna
variabile di base diminuisce:
>0
}
x B i = y i 0 − y ik x k ≥ 0 sempre !
{{
<0 >0
Nota.
Se per una variabile di base i si ha che y ik>0 e y r0= 0 ( soluzione
degenere), xk entra in base con valore nullo.
In questo caso la soluzione non cambia, ed in particolare rimane
degenere.
Per questa ragione la ricerca della soluzione potrebbe rimanere
bloccata generando sempre la medesima soluzione (cycling).
Il cycling è piuttosto raro e comunque esistono strategie per evitalo.
49
L’algoritmo del Simplesso
1. Inizializzazione.
Determinare una soluzione di base ammissibile.
2. Verifica dell’ottimalità.
Se y 0 j ≥ 0 ∀ j ∈ R
allora la soluzione corrente è ottima e l’algoritmo termina.
Altrimenti andare al passo 3.
3. Scelta della variabile entrante in base.
Scegliere una variabile fuori base xk tale che y0k<0 (ad esempio, con
il metodo del gradiente), ed andare al passo 4.
4. Scelta della variabile uscente dalla base.
Scegliere la variabile xBr tale che
y 
yr 0
= min  i0 
y rk i =1,..., M yik 
yik >0
Se y ik ≤ 0 ∀i = 1,..., m , allora la soluzione del problema è
illimitata (non esiste ottimo finito), e l’algoritmo termina.
5. Pivoting.
Risolvere le equazioni (5) ricavando xk e xBi , i ≠ r in funzione di
x j , j ∈ R − {k} e di xB .
r
La nuova soluzione si ottiene ponendo x j = 0, j ∈ R − {k} e xBr = 0 .
Andare al passo 2.
50
Il Tableau
L’algoritmo del simplesso può essere eseguito utilizzando una tabella ,
detta Tableau, in cui vengono disposti i coefficienti della funzione
obiettivo e dei vincoli.
Tali coefficienti sono quelli delle equazioni (5) in cui tutte le variabili
sono state portate al primo membro:
x B i + ∑ y ijx j = y i 0
∀i = 0,1,K , m
j∈R
valore dell’obiettivo
(soluzione corrente)
coeff. dell’obiettivo
nomi delle variabili fuori base
nomi delle variabili in base
0
L x Br
L
0
x B1
M
1
M
L
O
0
M
L
x Br
0
L
1
M
M
M
x Bm
0
x0
x B1
L
0
L x Bm
L
0
L
xj
L
xk
L
0
M
L y0j L
L y1 j L
M
y 0k
y1k
M
L
y10
M
L
0
L
y rj
y rk
L
yr0
O
L
M
M
1
L
M
L y mj L y mk
L
y 00
M
L y m0
valori delle variabili in base
(soluzione corrente)
coeff. delle variabili fuori base
coeff. delle variabili in base
51
L’algoritmo del simplesso applicato al Tableau
1. Inizializzazione.
Costruire il tableau iniziale con una soluzione di base ammissibile.
2. Verifica dell’ottimalità.
Se nella riga di x0 non esistono coefficienti negativi la soluzione
corrente è ottima e l’algoritmo termina. Altrimenti andare al passo 3.
3. Scelta della variabile entrante in base.
Scegliere una variabile fuori base xk tale che y0k<0 (ad esempio,
scegliere il coefficiente più piccolo), ed andare al passo 4.
4. Scelta della variabile uscente dalla base.
Se tutti i coefficienti nella colonna di xk sono y ik ≤ 0 ∀ i = 1,..., m
non esiste ottimo finito e l’algoritmo termina. Altrimenti calcolare i
rapporti
y i0
y ik
i = 1,..., m
tra i coeff. dell’ultima colonna con i coeff. positivi della colonna di
xk, e scegliere la riga r-esima associata al rapporto più piccolo.
Il coeff. yrk è il pivot.
5. Pivoting.
Portare in base xk al posto di xBr dividendo la riga r-esima per il
pivot, quindi sottraendo la nuova riga r alle altre righe del tableau,
obiettivo incluso, dopo averla moltiplicata per il corrispondente
coeff. della colonna k. In questo modo la nuova colonna k sarà
formata da tutti coeff. nulli tranne il coeff. r-esimo uguale ad 1.
Scambiare i nomi delle variabili xk e xBr . Andare al passo 2.
52
L’inizializzazione dell’algoritmo del simplesso
Il problema dell’inizializzazione corrisponde a verificare se il problema
di PL ammette soluzione, ed in caso positivo a determinarne una.
Inizializzazione con variabili di slack.
Un caso semplice è quello in cui tutti i vincoli sono disuguaglianze ≤ .
x 
A x ≤ b ⇒ A x + Is = b ⇒ [ A I ]  = b
s 
quindi si può scegliere B=I come base iniziale, corrispondente alla
soluzione ammissibile
 x B   s  b
x  = x = 0
 N    
In generale , tutte le volte che la matrice A contiene una matrice
identica I come minore mxm è possibile scegliere B= I come base
iniziale, e mettere nella base iniziale le m variabili corrispondenti alle
colonne di I.
Metodi generali di inizializzazione.
Esistono due metodi generali:
a) Il metodo a due fasi (“Two-Phases” Method)
b) Il metodo del “Big-M” (o delle penalità)
53
Il metodo a due fasi
E’ un metodo che può essere usato
per verificare l’esistenza
soluzioni in un sistema di disuguaglianze.
max x 0 = c T x
Ax = b
E’ dato il problema (P)
x≥0
I Fase (Definizione e soluzione del problema ausiliario)
Si definisce un problema ausiliario (A)
min
z = 1T y =
m
∑ yi
j=1
dove
A x + Iy = b
x≥0 y≥0
1 1
1 = M  M

1 m
 y  m var.
Posto z =  
 x  n var.
è sempre possibile definire come soluzione di base iniziale per (A)
zB 
z  =
 N
 y b 
x = 0 
   
quindi risolvere (A) con l’algoritmo del simplesso.
54
di
II Fase (Inizializzazione e soluzione del problema originale)
Se la soluzione ottima di (A) è tale che z=0, allora nessuna variabile y i,
i= 1,...,m, è rimasta in base all’ottimo , ed in tal caso il problema
originale (P) ammette soluzione.
Infatti, sia
 y* 
*
z = 
x*


la soluzione ottima di (A), con y* = 0 .
Allora A x * + Iy* = b ⇒ A x * = b
quindi x* è anche soluzione di (P)
e può essere usata come soluzione iniziale per risolvere (P).
Se invece z>0, allora qualche variabile y i, i= 1,...,m, è rimasta in base
all’ottimo, ed assume valore positivo.
In questo caso il problema originale (P) non ammette soluzione.
Se, infatti , fosse stato possibile determinare un vettore
x tale da
soddisfare i vincoli di (P), la soluzione di (A) lo avrebbe certamente
utilizzato per annullare (quindi minimizzare) l’obiettivo z.
55
Il metodo del “Big-M”
Con questo metodo si introducono delle variabili ausiliarie come nel
metodo a due fasi.
Quindi si risolve una versione modificata del problema originale
,
penalizzando nella funzione obiettivo le variabili ausiliarie.
E’ dato il problema (P)
max x 0 = c T x
Ax = b
x≥0
Si costruisce una versione modificata
(P’) del problema
introducendo m variabili ausiliarie (una variabile per vincolo)
(P)
m
n
T
T
max c x − M1 y = ∑ ci x i − M ∑ y j
j=1
i =1
Ax + Iy = b
x≥0 y≥0
1 1
dove 1 = M M e M è un coeff. scalare tale che M >> ci , b j , a ij
1 m
y
z
=
Posto
x
 
una soluzione di base iniziale per (P’) è
 zB  y b
z  = x = 0
 N    
56
∀i , j
Risolvendo (P’) le variabili y j, penalizzate dai “big-M” nell’obiettivo ,
sono forzate ad uscire dalla base.
Se nella soluzione ottima di (P’) tutte le yj sono fuori base, si ha che
y*  0 
*
z =   =  * ⇒ Ax* + Iy* = b ⇒ Ax* = b
x* x 
il vettore x* è anche la soluzione ottima di (P).
Rispetto al metodo a due fasi risolvere il problema
risolvere il problema originale (P).
57
(P’) equivale a
Esempi di Problemi di Programmazione Lineare
Esempio 1: Soluzione con l’algoritmo del simplesso dell’esempio in
forma standard
max x 0 = 2 x1 + x 2
x1 + x 2 + x 3
=5
− x1 + x 2
+x4
=0
6x1 + 2 x 2
+ x 5 = 21
x1 ≥ 0 x 2 ≥ 0 x 3 ≥ 0 x 4 ≥ 0 x 5 ≥ 0
Il problema può essere inizializzato usando le variabili di slack.
x3  5 
x 6B =  x 4  =  0 
   
 x5   21
è la base iniziale (degenere).
Il tableau iniziale
x0
x3
x4
uscente x 5
x3 x4
0
0
1
0
0
1
0
0
entrante
x 5 x1 x 2
0 − 2 −1 0
0
1
1 5
0 −1
1 0
1
6
2 21
il Pivot
1a iterazione: x1 entra in base x5 esce dalla base
58
51
−
21 6 = 7 2
Il tableau dopo la 1a iterazione.
x0
uscente x 3
x4
x1
x3
x4
1
0
0
1
0
0
0
0
nuovo
valore
obiettivo
il Pivot entrante
x 5 x1
x2
1 3 0 −1 3
7
−1 6
0
2 3 3 2 3 2 ⋅ 3 2 = 9 4 (= 2 ,25)
16
0
4 3 7 2 7 2 ⋅ 3 4 = 21 8 (= 2 ,62 )
16
1
1 3 7 2 7 2 ⋅ 3 = 21 2 (= 10,5)
2a iterazione: x2 entra in base x3 esce dalla base
Il tableau dopo la 2a iterazione.
x0
base
ottima
x2
x4
x1
valore ottimo
obiettivo
coeff. non negativi
x3 x4
x 5 x1 x 2
12
0
14
0
0 31 4
32
0 −1 4
0
1 9 4
−2
1
12
0
0 12
−1 2
0
14
1
0 11 4
Il tableau è ottimo!
59
soluzione
ottima
Esempio 2: L’azienda che produce vernici.
max Z = 3x E + 2 x I
x E + 2x I ≤ 6
2x E + x I ≤ 8
−xE + xI ≤ 1
xE ≥ 0
Deve essere trasformato
in forma standard.
xI ≤ 2
xI ≥ 0
max Z = 3x E + 2 x I
x E + 2 x I + s1
=6
2x E + x I
+ s2
=8
−xE + xI
+ s3
=1
xI
+ s4 = 2
x E ≥ 0, x I ≥ 0, s1 ≥ 0, s2 ≥ 0, s3 ≥ 0, s4 ≥ 0
Forma standard:
n=6, m=4
Il problema può essere inizializzato usando le variabili di slack.
 s1   6
 s   8
xB =  2  =  
 s3   1 
 s   2
 4  
La base iniziale
60
Il tableau iniziale
entrante
x E x I s1 s2 s3 s 4
z −3 −2 0 0 0 0
il Pivot
1
2 1 0 0 0
s1
2
1 0
1 0 0
uscente s 2
1 0 0 1 0
s3 − 1
0
1 0 0 0
1
s4
0
6
8
1
2
61
82
−
−
1a iterazione: xE entra in base s2 esce dalla base
Il tableau dopo la 1a iterazione.
il Pivot entrante
xE
x I s1
s 2 s 3 s4
z
0 −1 2 0
3 2 0 0 12
0
3 2 1 −1 2 0 0 2
uscente s1
xE
1
12 0
12 0 0 4
s3
0
32 0
12 1 0 5
s4
0
1 0
0 0
1 2
2a iterazione: xI entra in base s1 esce dalla base
61
2⋅ 2 3 = 4 3
4⋅ 2 = 8
5⋅ 2 3 = 10 3
2
Il tableau dopo la 2a iterazione.
valore ottimo
obiettivo
coeff. non negativi
base
ottima
xE xI
0
0
z
0
1
xI
xE
s3
s4
1
0
0
s1
s2 s3 s 4
13
4 3 0 0 38 3
2 3 −1 3 0 0 4 3
0 −1 3
0
−1
0 −2 3
2 3
1
13
0
1
0
Il tableau è ottimo!
62
0 10 3
0
3
1 2 3
soluzione
ottima
Esempio 3: Soluzione illimitata.
Un problema molto semplice:
In forma standard
max x 0 = x1
x1 + x 2 ≥ 1
x1 ≥ 0 x 2 ≥ 0
max x 0 = x1
x1 + x 2 − x 3 = 1
x1 ≥ 0 x 2 ≥ 0 x 3 ≥ 0
x2
2
1
La regione di ammissibilità X è aperta
X
1
2
x1
Il problema ha n=3, m=1
Adottiamo il punto (1,0) come soluzione di base iniziale.
x 2 
xN =   = 0
x3 
x B = [ x1 ] = [ 1]
63
Costruendo il tableau iniziale si nota che l’obiettivo deve essere
espresso in funzione delle variabili fuori base (si deve eliminare x1).
le variabili in base
devono avere coeff.
nullo nell’obiettivo
x0
x1 x2
−1 0
1 −1 1
1
x1
x3
0 0
Il tableau iniziale si ricava eliminando x1 dalla riga dell’obiettivo.
ora anche il valore
dell’obiettivo è corretto
x1 x2 x3
1 −1 1
x0 0
1 −1 1
x1 1
la variabile x3 entra in base
senza mai violare il vincolo.
La soluzione ottima è all’infinito.
Aumentando x3 ci si muove lungo l’asse x1 (direzione estrema).
funz. obiettivo
x2
2
1
X
...
1
2
64
x1
Quante sono le possibili direzioni estreme di un poliedro X?
d B 
Ad = 0 ⇒ [ B N ]  = 0 ⇒ Bd B + Nd N = 0
d N 
⇒ d B = − B −1Nd N
quindi è possibile fissare arbitrariamente d N e calcolare una
direzione estrema come
d B 
d= =
d N 
 − B −1Nd 
N


e


j
Una scelta possibile è fissare
1
0
M
 
d N = e j = 1  j − esimo e j ∈ R n − m
M
 
0  n − m
 − B −1 a j 
⇒d=

e


j
dove a j è la j-esima colonna di N.
Per ogni matrice B possono essere scelti n-m vettori a j distinti.
Quindi il numero massimo di possibili direzioni estreme è
 n
( n − m) 
 m
65
Nell’esempio l’asse di x1 corrisponde a
 − B −1 a j 
d=
=
 e j 
 − 1 ⋅ − 1
 0 =


 1 
1
0
 
 1 
( j = 2)
Si può verificare che
1
Ad = 0 ⇒ [1 1 − 1]  0 = 1 − 1 = 0
 
 1
La possibilità di avere soluzioni ottime
seguente teorema
( n = 3, m = 1)
finite è
regolata dal
6. Teorema
Dato il problema di PL
max x0 = cT x
Ax = b
x≥0
siano dj, j=1,...,D le direzioni estreme del poliedro X non vuoto
dei vincoli.
Condizione necessaria e sufficiente perchè esista soluzione
ottima finita è
cT d j ≤ 0 ∀j = 1,..., D
in tal caso l’ottimo coincide con un punto estremo di X.
66
Esempio 4: Inizializzazione con il “Two-phases method” .
min x 0 = 4 x1 + x 2
3x1 + x 2 = 3
4 x1 + 3x2 ≥ 6
x1 + 2 x 2 ≤ 4
x1 ≥ 0, x 2 ≥ 0
in forma standard
max x 0 = −4 x1 − x 2
3x1 + x 2
=3
4 x1 + 3x 2 − x 3
=6
+ x4 = 4
x1 + 2 x 2
x1 ≥ 0, x 2 ≥ 0, x 3 ≥ 0, x 4 ≥ 0
I Fase (Definizione e soluzione del problema ausiliario)
⇒ max z = − y1 − y 2
min z = y1 + y 2
3x1 + x 2
+ y1
=3
4 x1 + 3x 2 − x 3
+ y2 = 6
x1 + 2 x 2
+ x4
=4
x1 ≥ 0, x 2 ≥ 0, x 3 ≥ 0, x 4 ≥ 0, y1 ≥ 0, y 2 ≥ 0
67
z
y1
y2
x4
x1
x2
x3
x4
y1
y2
3
1
0
0
1
0
4
3 −1
0
0
1 6
1
2
1
0
0 4
0
0
0
0
0
1
si devono eliminare le
var. di base dalla riga
dell’obiettivo
1 0
3
Il tableau iniziale
Il tableau finale
z
x1
x2
x4
z
x1
−7
y1
y2
x4
3
4
1
x2
−4
x 3 x 4 y1 y 2
1
0 0
0 −9
1
0
3 −1
2
0
0
0
1
1
0
0
0
1
0
3
6
4
x1 x 2
x3 x4
y1
y2
0
0
0
0
1
1
0
1
0
15
0
3 5 −1 5 3 5
0
1 −3 5
0 −4 5
35 65
0
0
1
1
1
−1
1
con questi valori può essere inizializzato il tableau del problema originale
68
II Fase (Inizializzazione e soluzione del problema originale)
si devono eliminare le
var. di base dalla riga
dell’obiettivo
x0
x1
x2
x4
x1
4
1
0
0
x2
1
x3
0
15
1 −3 5
0
1
Il tableau iniziale del problema originale
x0
x1
x2
x4
x1 x 2
x3 x4
0
0 −1 5
0 − 18 5
1
0
15
0
35
0
1 −35
0
65
0
0
1
1
1
69
0
x4
0
0
0 35
0 65
1
1
Programmazione Matematica a Numeri Interi
(Integer Programming - IP)
Problema di ottimizzazione di una funzione obiettivo lineare
soggetta al rispetto di un insieme di vincoli lineari in cui tutte o
parte delle variabili possono assumere solo valori interi
Mixed IP Problem - MIP
max cT x + hT y
Ax + Gy ≤ b
x ∈Z +n y ∈ R p+
x è il vettore delle variabili intere positive
y è il vettore delle variabili reali positive
I problemi in cui sono presenti variabili intere sono spesso anche
indicati come Problemi Combinatorici.
Alcuni esempi di applicazioni:
• Production Scheduling (assegnazione e sequenziazione di operazioni su
macchine)
• Distribuzione di beni
• Facility location (localizzazione di impianti)
• Progettazione di reti (trasporto e comunicazione)
• Pianificazione di investimenti
70
Formulazione di problemi a numeri interi
I modelli di ottimizzazione a numeri interi vengono introdotti
quando si deve ottimizzare l’uso di risorse non divisibili o la scelta
tra alternative discrete.
Un tipo di modello molto importante e comune è quello in cui le
variabili intere possono assumere
solo i valori 0 e 1 (0-1
Programming).
Valori binari sono usati
per rappresentare la scelta tra
possibilità o il verificarsi o meno di una condizione:
1
x=
0
se l' evento si verifica
se l' evento non si verifica
Esempi di IP:
• Il problema dello zaino (Knapsack Problem)
• Il problema dell’assegnazione (Matching Problem)
• Il problema del costo fisso (Fixed Charge Problem)
• Il problema del sequenziamento (Sequencing Problem)
• I problemi di copertura, partizione ed impaccamento
(Set Covering, Partitioning and Packing Problems)
• Problemi sui grafi (Teoria dei Grafi):
• Percorso minimo (Shortest Path)
• Commesso viaggiatore (Traveling Salesman Problem)
71
due
Il problema dello zaino
(Knapsack Problem)
Si hanno n possibili progetti da realizzare con un budget massimo b
disponibile.
Se un progetto j, j=1,...,n, viene finanziato deve essere investito un
capitale aj.
Dalla realizzazione di un progetto j si ricava un guadagno cj.
Un progetto non può essere realizzato parzialmente, ma può essere
eseguito completamente o non eseguito affatto.
Il problema: stabilire quali progetti realizzare per ottenere il massimo
guadagno senza superare il budget disponibile.
Il problema si formula introducendo n variabili binarie:
il progetto j è finanziato
1
xj = 
il progetto j non è finanziato
0
j = 1,..., n
n
Knapsack binario
max ∑ c jx j
j=1
n
∑ a jx j ≤ b
j=1
x j ∈{0,1} = B ∀j = 1,..., n
72
Problema dello zaino: si deve stabilire quali tra n oggetti portare in
uno zaino sapendo che il peso massimo trasportabile è b, che ogni
oggetto j pesa aj e che ad ogni oggetto è associata un’utilità (valore) cj.
Una variante: la realizzazione di progetti nell’arco di m mesi.
Supponendo che la realizzazione di ciascun progetto richieda un
finanziamento nell’arco di m mesi:
• aij il finanziamento per il progetto j nel mese i, j=1,...,n; i=1,...,m
• bi budget disponibile nel mese i, i=1,...,m
n
Knapsack
multidimensionale
max ∑ c jx j
j=1
n
∑ a ijx j ≤ bi
j=1
∀i = 1,..., m
x j ∈{0,1} = B ∀j = 1,..., n
73
Il problema dell’assegnamento
(Matching Problem)
Si devono assegnare m attività ad n persone (sia n ≥ m).
Una volta stabilito l’assegnamento , ogni persona eseguirà solo
l’attività che gli viene assegnata.
Se alla persona j, j= 1,...,n, viene assegnata l’attività i, i= 1,..., m, il
costo pagato è cij.
Il problema : assegnare tutte le attività alle persone
minimizzare il costo pagato.
in modo da
Si può rappresentare il problema con un grafo:
Attività (i)
M
cij
M
Persone (j)
Il problema consiste nello stabilire quali archi introdurre tra i nodi
“attività“ ed i nodi “persona” in modo che su ogni nodo “attività“
incida esattamente un arco e su ogni nodo “persona” incida al più un
arco.
74
Il problema si formula introducendo mxn variabili binarie:
1
xij = 
0
l' attività i è assegnata alla persona j
l' attività i non è assegnata alla persona j
i = 1,..., m
j = 1,..., n
Matching binario
m
n
min ∑ ∑ cijx ij
i =1 j=1
n
∑ x ij = 1 ∀i = 1,..., m ( a )
j=1
m
∑ xij ≤ 1 ∀j = 1,..., n
i =1
( b)
x ji ∈{0,1} = B ∀i = 1,..., m ∀j = 1,..., n
Vincoli (a): ogni attività e’ assegnata ad una persona
Vincoli (b): ogni persona svolge al più una sola attività
75
Il problema del costo fisso
(Fixed Charge Problem)
Si consideri un problema
di trasporto tra m produttori ed
consumatori (ad esempio, un trasporto di gas o petrolio).
n
Ogni produttore è connesso ad ogni consumatore da un canale
attraverso cui può avvenire il trasporto (e.g., un gasdotto).
Per avere un flusso trasportato tra un produttore
i, i= 1,...,m, ed un
consumatore j=1,...,n, si deve:
• pagare un costo fisso fij per l’affitto del canale di trasporto tra i e j;
• pagare cij per ogni unità trasportata tra i e j.
La disponibilità massima del produttore i è si, i=1,...,m.
La richiesta del consumatore j che deve essere soddisfatta è rj, j=1,...,n.
Il problema : stabilire quali canali di trasporto tra i produttori ed i
consumatori affittare e quale flusso trasportare su tali canali in modo
da minimizzare il costo totale
, soddisfacendo la richiesta dei
consumatori.
Le variabili:
• x ij ∈R, i=1,...,m; j=1,...,n, la quantità trasportata tra i e j
1 se si utilizza il canale tra i e j
• y ij ∈B , i=1,...,m; j=1,...,n, yij = 
0 se non si utilizza il canale tra i e j
76
La funzione di costo ha una discontinuità nell’origine.
Ad esempio per la variabile xij
costo totale
cijxij
fij
Il problema del
trasporto con costo
fisso
xij
m
n
min ∑ ∑ ( c ijx ij + f ijy ij )
i =1 j= 1
n
∑ x ij ≤ si ∀i = 1,..., m ( a )
j= 1
m
∑ x ij = r j ∀j = 1,..., n ( b )
i =1
x ij ≤ My ij ∀i , j
( c)
x ij ∈ R + y ij ∈ B ∀i = 1,..., m ∀j = 1,..., n
Vincoli (a) e (b): i vincoli del problema del trasporto.
Vincoli (c): un flusso x ij può esistere solo se si paga il costo fisso per
usare il canale tra i e j. M è un coefficiente molto più grande della
massima quantità trasportabile tra i e j. Se fosse specificato il flusso
massimo, qij, tra i e j, i vincoli (c) risulterebbero
x ij ≤ q ijy ij
77
∀i , j
Il problema del sequenziamento
(Sequencing Problem)
Si devono sequenziare n attività (job) indipendenti su una macchina.
La macchina può eseguire solo un job alla volta.
L’esecuzione dei job non può essere interrotta.
Il tempo necessario per l’esecuzione (processing time) del job i,
i=1,...,n, è pi.
Viene pagato un costo che , in generale , è funzione del tempo
necessario a completare i job (ad
es ., il tempo medio di
completamento dei job).
Il problema : determinare la sequenza con cui eseguire i job sulla
macchina in modo da minimizzare il costo.
Le variabili continue :
•
t i ∈ R + , i=1,...,n, l’istante di inizio esecuzione del job i.
Dati due job i e j, si possono verificare due casi:
1.
i precede j
2.
j precede i
⇒ t j ≥ t i + pi 

 Vincoli disgiuntivi
⇒ ti ≥ t j + p j 

I due casi sono mutuamente esclusivi, quindi solo un vincolo tra 1. e
2. può essere soddisfatto da una soluzione del problema.
78
Si introduce un variabile binaria:
1
yij = 
0
y ij ∈ B, i = 1,..., n; j = 1,..., n
se i precede j
se j precede i
quindi per ogni coppia di job, i, j, i vincoli disgiuntivi del problema si
esprimono come:
t j ≥ t i + p i − M (1 − y ij ) (a )
t i ≥ t j + p j − My ij
( b)
dove M è un coefficiente costante positivo scelto molto maggiore di
n
ogni altro coefficiente (in particolare della ∑ pi ) del problema.
i =1
Se yij=1:
• il vincolo (a) coincide con il vincolo 1.
• il vincolo (b) è sempre soddisfatto poichè M>>tj-ti+pj
Se yij=0:
• il vincolo (a) è sempre soddisfatto poichè M>>ti-tj+pi
• il vincolo (b) coincide con il vincolo 2.
Il vettore delle yij rappresenta l’ordine di esecuzione dei job.
79
Metodi di soluzione dei problemi di IP
Consideriamo un problema (IP)
(IP) max x0 = cT x
Ax = b
x ∈Z +n
Il poliedro P associato ai vincoli di (IP) contiene tutti e soli i punti
interi che sono soluzioni di (IP):
{
}
P = x ∈ Z n : Ax = b, x ≥ 0
Il rilassamento lineare (RL) di (IP) corrisponde a rimuovere da
(IP) il vincolo di integrità:
( RL) max x0 = cT x
Ax = b
x ∈R +n
Il poliedro P’ associato al (RL) è
{
}
P' = x ∈ R n : A x = b, x ≥ 0
P = P '∩Z n
quindi P’ contiene anche tutte le soluzioni ammissibili per (IP).
80
Sia x* la soluzione ottima per (IP) (se esiste) e sia x la soluzione
ottima per (RL).
T
T *
E’ evidente che c x ≥ c x .
Quindi se x ∈ P , la soluzione ottima di (RL) è anche la soluzione
ottima di (IP).
In generale, tuttavia, x ∉ P .
Esistono tre classi di metodi di soluzione dei problemi (IP):
1) Metodi basati su una enumerazione implicita delle soluzioni
(Branch and Bound Methods)
2) Metodi basati sull’uso di “piani di taglio”
(Cutting Planes Methods)
3) Metodi specifici per particolari classi di problemi
(ad esempio, per il set covering, knapsack, ecc.)
81
Il metodo dei “Piani di Taglio”
(Cutting Planes Method)
E’ un metodo di soluzione dei problemi (IP) di tipo generale.
L’idea di base:
Se la soluzione di (RL) non è intera allora la soluzione ottima
intera è interna al poliedro P.
Si aggiungono vincoli a P cercando di “ restringerlo”, in
particolare eliminando solamente parti di P che non contengono
soluzioni intere.
Si risolve una sequenza di problemi rilassati sempre più vincolati.
Sia
(IP) max x0 = cT x
Ax = b
x ∈ Z +n
{
⇒
x* la soluzione ottima di (IP)
Il primo problema considerato
rilassando (IP)
( RL) max x 0 = cT x
Ax = b
x ∈R n+
}
P = x ∈ Z n : Ax = b, x ≥ 0
è il problema
{
(RL) ottenuto
}
P0 = x ∈ R n : A x = b, x ≥ 0
⇒
x° la soluzione ottima di (RL)
82
Si può costruire una sequenza di poliedri, detta sequenza di Gomory,
tale che:
•
P0 ⊃ P1 ⊃ K ⊃ Pt
•
Pi ∩ Z n = P
•
x oi −1 ∉ Pi
•
x ot ≡ x*
La sequenza è costruita aggiungendo via via a P
vincoli detti tagli.
0
un insieme di
Definizione.
T
Una disuguaglianza a x ≥ èa 0
un taglio per un poliedro P’
associato al (RL) di un problema (IP) se, detta x° la soluzione
ottima non intera del (RL), si ha:
1)
aT y ≥ a0
2)
a T xo < a 0
∀y soluzione ammissibile di (IP)
(la disuguaglianza si dice valida);
(non è soddisfatta da x° )
Il metodo dei piani di taglio determina la soluzione ottima intera
introducendo un numero finito di tagli.
Ogni taglio separa la soluzione non intera del (RL) corrente dalle
soluzioni ammissibili per (IP).
83
Il taglio di Gomory (Taglio Frazionario)
Supponiamo di avere determinato la soluzione ottima di un (RL) di
(IP). Le m variabili in base possono essere espresse come:
x Bi = yi 0 − ∑ y ijx j
j∈R
i = 1,K, m
(1)
dove R è l’insieme degli indici delle variabili fuori base.
La soluzione corrispondente è quindi:
xBi = yi0
i =1,K,m;
x j =0
∀j∈R
Supponiamo che non tutti i y i0 siano interi . Scegliamo una
componente della base con valore non intero e cerchiamo di definire
le condizioni che devono essere rispettate perchè essa sia invece
intera.
Sia i la componente non intera. Allora
y i 0 =  y i 0  + fi 0
0 < fi 0 < 1
y ij =  y ij  + f ij
0 ≤ f ij < 1
dove a  rappresenta il più grande intero che non supera a.
84
Si può riscrivere il primo membro della i-esima equazione (1)
y ij  x j + ∑ fijx j ≥ x Bi + ∑  y ij  x j

j∈R
j∈R
j∈R
y i 0 = x Bi + ∑
{
≥0
xBi + ∑  yij  x j ≤ yi0 =  yi0  + fi0
cioè
j∈R
{
(*)
Poichè si vuole imporre che x Bi sia intero, (*) risulta intero.
Ma allora se (*) è intero non può essere superiore a  y i0 
poichè fi0<1.
Quindi
xBi + ∑  yij  x j ≤  yi0 
j∈R
Cambiando segno alla disuguaglianza e sostituendo x Bidalla i-esima
equazione (1)
∑  yij  x j + ∑ fijx j −  yi0  − fi0 − ∑  yij  x j ≥ − yi0 
j∈R
j∈R
j∈R
quindi semplificando, si ottiene il taglio di Gomory (taglio frazionario)
∑ fijx j ≥ fi0
j∈R
85
6. Teorema
Per ogni componente i non intera della soluzione di un (RL) la
disequazione
∑ fijx j ≥ fi0
(2)
j∈R
è un taglio rispetto al poliedro P.
Dimostriamo che (2) è soddisfatta da ogni soluzione
Dim.
ammissibile di (IP).
Supponiamo per assurdo che esista una soluzione w ammissibile per
(IP) tale che
∑ fijw j < fi0
(#)
j∈R
Poichè w è ammissibile ogni sua componente soddisfa il sistema
A x = Bx B + N x N = b
in particolare la componente wi soddisfa l’i-esima equazione
wi = yi0 − ∑ yijw j =  yi0  + fi0 − ∑  yij  w j − ∑ fijw j
j∈R
j∈R
poichè w è intero fi 0 − ∑ fijw j = β
j∈R
fij > 0 e w j ≥ 0
⇒
β < fi 0 < 1
j∈R
deve essere intero, e poichè
allora β intero è negativo o nullo
β ≤ 0 ⇒ −β ≥ 0 ⇒ ∑ fijw j ≥ fi0
che contraddice l’ipotesi (#).
j∈R
86
Dimostriamo che (2) non è soddisfatta dalla soluzione di base non
intera x° da cui la disequazione (2) è stata generata ((2) separa x° dal
nuovo poliedro ottenuto aggiungendo (2) al poliedro di (RL)).
Sia x i° la componente i- esima frazionaria della soluzione
verifichiamo che x° soddisfa
o
∑ fijx j < fi0
j∈R
(*)
Poichè la componente i-esima della soluzione di base è frazionaria
si ha
xoi > 0 ⇒ xoi =  y i0  + fi 0 > 0 ⇒ fi0 > 0
e sostituendo la soluzione in (*) si ottiene
xoj = 0
∀j ∈ R
quindi x° soddisfa la (*).
87
⇒ 0 < fi 0
,
Un esempio
max x0 = 2 x1 + x2
x1 + x2 ≤ 5
(1)
− x1 + x2 ≤ 0 (2)
6x1 + 2 x2 ≤ 21 (3)
x1, x2 ≥ 0
x1, x2 ∈Z
max x0 = 2 x1 + x2
x1 + x2 + x3
=5
− x1 + x2 +
x4 = 0
6x1 + 2 x2 +
x5 = 21
x1, x2 , x3 , x4 , x5 ≥ 0
x1, x2 ∈Z
⇒
Costruiamo un taglio dalla seconda riga del tableau ottimo di (RL)
x 3 x4
x5 x1 x2
x0
12
0
14 0
0 31 4
x2
32
0 −1 4 0
1 94
x4
−2
1
12 0
0 12
x1 − 1 2
0
1 4 1 0 11 4
i coefficienti
3
1
= 1+
2
2
1
3
− = −1 +
4
4
9
1
=2+
4
4
il taglio
88
1
3
1
x 3 + x5 ≥
2
4
4
x2
(3)
4
(2)
3
(11/4, 9/4)
2
(1)
1
(fractional cut)
x1
0
0
1
sostituendo x1 ed x2 in
si ottiene
2
1
3
1
x 3 + x5 ≥
2
4
4
5x1 + 2 x 2 ≤ 18
che non è soddisfatta dal punto (11/4, 9/4)
89
3
4
Il Metodo del Branch-and-Bound
E’ una strategia di esplorazione dello spazio delle soluzioni basata
su l’enumerazione implicita delle soluzioni:
il metodo esamina sottinsiemi disgiunti di soluzioni (branching) e li
valuta sulla base di una stima della funzione obiettivo (bounding),
eliminando quegli insiemi di soluzioni che non contengono la
soluzione ottima.
L’esplorazione viene effettuata risolvendo una sequenza
associati a sottinsiemi disgiunti di soluzioni.
di (RL)
Consideriamo il problema a numeri interi
(IP) max x0 = cT x
Ax = b
x ∈Z +n
si risolve il (RL) associato, determinando x0.
0
Scelta x juna componente non intera della soluzione , la regione di
ammissibilità del (RL) costituita dal poliedro
{
}
P ' = x ∈ R n : A x = b, x ≥ 0
può essere partizionata in due regioni disgiunte , dando luogo a due
nuovi problemi rilassati ottenuti aggiungendo a P rispettivamente uno
tra i due seguenti vincoli.
x j ≤ x0j
x j ≥ x0j + 1
 
 
90
In questo modo si separa il problema originale
in due problemi
disgiunti. Quindi si considerano i nuovi due problemi iterando il
procedimento.
L’esplorazione dello spazio delle soluzioni effettuato dal metodo del
Branch-and-Bound si può rappresentare per mezzo di un albero
(“enumeration tree”).
Ad ogni nodo è associato un (RL)
nodo 0 ⇒ (RL) associato al (IP) originale
x j ≤ x0j
 
0
1
x j ≥ x0j + 1
 
2
Si procede risolvendo gli (RL) associati ai nuovi nodi 1 e 2. Se la
soluzione non è intera si ramifica
(branching) ulteriormente
l’albero. Perchè l’esplorazione non sia totale , il branching deve
essere fermato quando:
• il (RL) associato ad un nodo non ammette soluzione;
• la soluzione di (RL) associato al nodo è intera;
• la soluzione di (RL) associato al nodo non è intera , ma è
possibile stabilire che l’esplorazione della porzione di albero al
di sotto del nodo non conduce alla soluzione ottima (bounding).
91
Bounding: il principio base
Supponiamo di aver trovato una soluzione intera per (IP) risolvendo il
(RL) associato al nodo 3.
0
x j ≤ x 0j
 
x k ≤ x1k
 
soluzione
intera
3
1
x j ≥ x0j + 1
 
2
x k ≥ x1k + 1
 
4
x0 = x20
x20 ≤ x30
x0 = x40
x 0 = x 30
x 30
Il valore dell’obiettivo x 0 =rappresenta
la miglior soluzione
corrente. Poichè stiamo massimizzando , è il limite inferiore ( lower
bound) corrente per la soluzione di (IP).
Quando si ramifica un nodo , il valore dell’obiettivo associato ai nodi
successori non può essere migliore dell’obiettivo associato al nodo
padre, poichè i (RL) dei nodi successori sono più vincolati del (RL)
del nodo padre.
Il valore dell’obiettivo associato ad un nodo il cui (RL) ha soluzione
non intera rappresenta quindi il limite superiore (upper bound) rispetto
qualsiasi soluzione determinabile ramificando tale nodo.
2
3
Quindi se, ad esempio, x0 ≤ x0 non ha più senso esplorare l’albero
sotto il nodo 2 poichè le soluzioni associate ai suoi nodi non possono
migliorare la soluzione intera corrente.
92
In generale, dati:
• il (RL)i associato ad un nodo i (dove A ix=bi è l’insieme dei vincoli
originali più i vincoli via via aggiunti ad ogni branching)
( RL) i max x0 = cT x
A i x = bi
x ∈R +n
• xlb, la migliore soluzione intera sino
l’albero
ad ora trovata esplorando
• xub, la soluzione non intera di (RL)i
T int
T ub
T ub
T lb
se vale c x ≤ c x , poichè è noto che c x ≤ c x
dove xint è soluzione ottima intera di
(IP)i max x0 = cT x
A i x = bi
x ∈Z +n
T int
T ub
T lb
allora ne consegue che c x ≤ c x ≤ c x
Quindi la migliore soluzione intera contenuta in
{
}
Pi = x ∈R n: A i x = bi , x ≥ 0
non potrà mai essere migliore della soluzione intera corrente xlb.
93
nodo “pruned”
soluzione intera
0
x j ≤ x 0j
 
x j ≥ x 0j + 1
1
x k ≤ x1k
 
 
x 0 = x 20 ( x20 ≤ x30 )
2
x k ≥ x1k + 1
 
3
x 0 = x 40 ( x40 ≥ x30 )
4
x 0 = x30
x f ≥ x 4f + 1
 
x f ≤ x4f
 
Soluzione ⇒ x5
Ottima Intera
6
5
x0 = x60 (x60 ≤ x50 )
x 0 = x50
( x50 ≥ x30 )
I nodi che non vengono tagliati (pruned) sono detti nodi attivi e
vengono esplorati.
L’esplorazione termina quando non ci sono più nodi attivi.
94
L’algoritmo del Branch-and-Bound
1. Inizializzazione
Sia (0) il nodo attivo e P0 il poliedro associato al (RL).
lb
Sia z = −∞ il valore corrente dell’obiettivo (lower bound), e
z 0 = ∞ il valore iniziale dell’obiettivo del nodo (0) (upper bound
di (0)).
2. Branching
Se non esiste un nodo attivo andare al passo 7, altrimenti scegliere
il nodo attivo (j).
Se il (RL) di (j) è stato risolto andare al passo 3, altrimenti al 4.
3. Separazione
j
Scegliere una variabile frazionaria di base x Bi = y i0 e
partizionare Pj in
{
 }
P j ∩ x: x Bi ≤ y ij0
{
}
P j ∩ x: x Bi ≥ y ij0 + 1
 
creando due nuovi nodi con lo stesso upper bound del nodo j.
Vai a 2.
95
4. Soluzione di (RL)
Risolvere il (RL) associato a (j). Se non esiste soluzione tagliare il
nodo (il nodo non è più attivo) ed andare a 2.
j
j
j
Se esiste soluzione ottima x porre z = x0 ed andare al passo 5.
5. Pruning per integrità
j
Se x non è intera andare al passo 6. Altrimenti tagliare il nodo (j)
{
}
lb
lb j
e porre z = max z , z . Se il lower bound viene aggiornato, la
nuova soluzione corrente è quella associata al nodo (j).
Andare al passo 6.
6. Pruning per bound
k
lb
Tagliare ogni nodo attivo (k) tale che z ≤ z
Andare al passo 2.
7. Terminazione
L’algoritmo termina.
lb
Se z = −∞ allora (IP) non ammette soluzione.
lb
lb
Se z ≥ −∞ la soluzione corrente associata a z è ottima.
96
Osservazioni sull’algoritmo di Branch-and-Bound
• La convergenza in un numero finito
di passi è garantita se il
problema ha soluzioni ottime finite.
• Le prestazioni dell’algoritmo sono influenzate dalle diverse politiche
di scelta del nodo da ramificare al passo 3.
Due strategie limite:
• Depth First (esplorazione in profondità):
se il nodo corrente non è tagliato generare i due nodi figli e
proseguire ad esplorare uno di essi al livello successivo.
• Breadth First (esplorazione in ampiezza):
si esplorano tutti i nodi allo stesso livello prima di passare al
livello successivo.
La strategia depth first richiede minor occupazione di memoria della
breadth first ma può richiedere maggior tempo
97
Un esempio (grafico)
x2
4
obiettivo
P
3
2
1
0
1
2
3
x1
4
0
x1 ≤ 1
Q
4
1
N
x2
4
3
2
1
2
x2
3
2
Q
1
0
x1 ≥ 2
P
2
3
4
N
1
x1
0
98
1
2
3
4
x1
0
x1 ≤ 1
Q
3
3
2
1
0
x2 ≤ 2
R
4
non ammissibile
intera
ottima
x2
4
M
2
3
4
0
99
6
non ammissibile
x2
R
1
x1
x2 ≥ 3
5
3
2
1
2
N
x2 ≥ 2
peggiore di R
4
P
1
x2 ≤ 1
M
x1 ≥ 2
1
2
3
x1
Teoria della Dualità
Ad ogni problema di PL (Primale) è associato un problema Duale
Problema Primale (P)
Problema Duale (D)
min c1x1 +L+ c n x n
s. t.
a11x1 +L+ a1n x n ≥ b1
max b1y1 +L+ b m y m
s. t.
a11y1 +L+ a m1y m ≤ c1
M
M
a m1x1 +L+ a mn x n ≥ b m
a1n y1 +L+ a mn y m ≤ c n
(m variabili, n vincoli)
(n variabili, m vincoli)
Il problema D ha tante variabili quanti sono i vincoli di P e tanti
vincoli quante sono le variabili di P.
In forma matriciale:
( D) max bT y
( P) min cT x
Ax ≥ b
x≥0
AT y ≤ c
y≥0
x ∈ℜ n
y ∈ℜ m
100
Forma simmetrica della dualità: regole di trasformazione
(P)
(D)
max
min
vincoli
≥
min
max
vincoli
≤
Duale di un Primale con vincoli di uguaglianza:
( P) min cT x
Ax = b
x≥0
( D) max bT y
AT y ≤ c
y var.libere
x ∈ℜ n
y ∈ℜ m
Infatti:
Ax = b
equivale a
Ax ≥ b
Ax ≤ b ⇒ − Ax ≥ − b
quindi si introducono 2m variabili duali, u e v
max( bT u − bT v)
AT u − AT v ≤ c
u≥0 v≥0
e sostituendo y= u - v si ottiene D
u, v ∈ℜ m
101
Forma non simmetrica della dualità: regole di trasformazione
(P)
(D)
max
min
vincoli
≥
min
max
vincoli
≤
vincolo =
var. libera
var. libera
vincolo =
Le trasformazioni sono reversibili: il duale del duale è il primale.
La teoria della Dualità è importante perchè:
•
le soluzioni di P e D sono legate tra loro;
•
le soluzioni duali hanno un’interpretazione economica utile
per l’analisi di sensitività (post-ottimalità);
•
sulla teoria della dualità sono basati algoritmi, quali il
Simplesso Duale e l’Algoritmo Primale-Duale, alternativi al
Simplesso (Primale) utili per certe classi di problemi;
•
può in certi casi essere conveniente risolvere D al posto di P
(conviene risolvere il problema con il minor numero di
vincoli)
102
Risultati fondamentali della Teoria della Dualità
Siano dati i problemi
( D) max bT y
( P) min cT x
Ax ≥ b
AT y ≤ c
x≥0
y≥0
1.Teorema (debole) della dualità
Siano x e y soluzioni ammissibili rispettivamente per (P) e
(D), allora
cT x ≥ b T y
Dim.
ysoluzione ⇒ A T y ≤ c
x soluzione ⇒ Ax ≥ b
x ≥ 0 ⇒ ( A T y)T x ≤ cT x
y ≥ 0 ⇒ ( A x )T y ≥ b T y
cT x ≥ ( A T y)T x = x T A T y = ( Ax )T y ≥ b T y
103
Corollario
Se (P) è illimitato
(D) non è ammissibile
Se (D) è illimitato
(P) non è ammissibile
Se (P) ha soluzione
ottima finita
(D) ha soluzione ottima
finita
Se (D) ha soluzione
ottima finita
(P) ha soluzione ottima
finita
2.Teorema (forte) della dualità
Se (P) e (D) ammettono soluzione ottima finita, allora per
ogni ottimo x* per (P) esiste una soluzione ottima y* per (D)
tale che
c T x* = b T y*
La dimostrazione del Teorema della dualità forte evidenzia
che il valore della soluzione ottima di (D) corrispondente alla
*T = cT B−1
* = B−1 b
y
x
soluzione ottima di (P)
vale
B
B
104
Dim.
Sia B la base associata a x*
 x*B   B−1 b 
*
x = * =
 quindi
x N   0 
Se
* = cT B−1b
cT x* = cT
x
B B
B
cT x* = b T y* allora cT B−1 b = b T y*
B
e
T
−1
*
y = cT
BB
T
*
Dimostriamo che y è ammissibile per (D):
T
T
−1A ≤ cT
*
*
A y ≤ c ⇒ y A ≤ cT ⇒ c T
B
B
−1
T≤0
cT
B
A
−
c
B
−1
T | c T = cT − cT | c T B−1N − cT =
cT
B
B
N
−
c
|
[
]
B
B N
B
B B
N
[
[
]
][
]
−1
T
= 0| cT
BB N − c N ≤ 0
Poichè cTBB−1N − cTN ≤ 0
è la condizione di ottimalità per
(P) (problema di minimizzazione), è verificata l’ammissibilità.
T
T * T
Per la dualità debole b y ≤ c x ≤ c x ∀yammissibile
cT x*
è estremo superiore per (D),
T
*
T −1
quindi la soluzione y = c BB
T *
T *
ammissibile per cui c x = b y
è ottima per (D).
105
La base B è ottima per (P) e per (D). Siano infatti X e Y
rispettivamente gli insiemi delle soluzioni ammissibili per (P) e
(D)
A = [B | N ]
T
min cT
B x B + cN x N
cT x* = bT y*
max bT y
yT B ≤ cT
B
Bx B + N x N = b
xB ≥ 0
yT N ≤ cT
N
xN ≥ 0
y var.libere
una sol. di base per (P)
la corrispondente per (D)
 x B  B−1 b
x= =

x
 N   0 
−1
yT = cT
B
B
l’ammissibilità per (D)
l’ammissibilità per (P)
 a)
T
y ∈Y ⇒
x ∈ X ⇒ B−1 b ≥ 0

b)
a)
b)
T
≤
cT
c
B
B
−1
T
(cT
BB ) B ≤ cB
−1
(cT
B
)N ≤ cT
B
N
(vera sempre)
−1
cT
B
N − cT
B
N ≤0
−1 j
cT
B
a − cj ≤ 0
B
j ∈R
sono le (n-m) condizioni di
ottimalità (costi ridotti) di (P)
T
La base B è ottima se x e y sono rispettivamente ammissibili
per (P) e (D).
106
• Solo in corrispondenza dell’ottimo dalla base B ammissibile
per (P) si ottiene una soluzione ammissibile per (D) (che in
particolare è anche ottima).
• Ad una generica iterazione del simplesso dalla base corrente
−1
B
per (P) si può costruire un vettore πT = cT
B
che non è soluzione di (D).
• Tale vettore è detto dei MOLTIPLICATORI DEL SIMPLESSO
è compare nel calcolo dei coefficienti di costo ridotto
(problema di max):
( c − [ c B ]N )
T −1
B
T
N
xB
Il tableau ottimo:
xN
x0
B −1 N
I
−1
T
cT
BB N − c N
0
B −1 b
−1
cT
BB b
Nota: se la base iniziale è formata solamente da slack e tutte le slack sono
fuori base all’ottimo, allora nel tableau ottimo si possono leggere
direttamente sia l’inversa della base ottima che il valore ottimo delle variabili
duali.
s
xB
x N x0
s
x
x0
I
0T
s
B−1
−1
cT
B
B
A
− cT
xB
I
0
I
0T
b
0
xN
B−1N
−1
T
cT
B
N
−
c
B
N
x0
B−1 b
−1
cT
B
b
B
107
B
− cT
B
N
− cT
N
b
0
Il Teorema dello “scarto complementare”
(Complementary Slackness Theorem)
Consideriamo la coppia di problemi (P) e (D) in forma canonica e
trasformiamoli in forma standard
( P) min cT x
Ax ≥ b
Ax − Is = b
x≥0
n var.
s≥0
m var. di surplus
x≥0
( D) max bT y
A T y + Iv = c
AT y ≤ c
y≥0
y≥0
m var.
v≥0
n var.dislack
Ad ogni variabile di (P) è associato un vincolo di (D) e quindi la
corrispondente variabile di slack e viceversa.
3.Teorema della slackness complementare
Data la coppia di soluzioni x e y rispettivamente ammissibili
per (P) e (D), x e y sono ottime per (P) e (D) se e solo se
s j y j = ( a j x − b j ) y j = 0 j = 1,K, m
v i x i = (ci − a T
i y )x i = 0 i = 1,K, n
j
dove a è il vettore riga j-esima di A
a i è il vettore colonna i-esima di A
108
Nota: Il teorema stabilisce che:
a.
b.
xi > 0 ⇒ aT
i y = c i (vincolo duale saturo: vi=0)
aT
i y < c i ⇒ x i = 0 (vincolo duale non saturo: vi>0)
c.
y j > 0⇒ a jx = b j
d.
a j x > b j ⇒ y j = 0 (vincolo primale non saturo: sj>0)
(vincolo primale saturo: sj=0)
Dim. (Necessità)
* *
T *
T *
Siano x e y le soluzioni ottime. Allora si ha c x = b y
Inoltre
T
T
T *
*
*
T
*
T
*
*
A y ≤ c ⇒ y Ax ≤ c x ⇒ c x ≥ y Ax*
e
T
T
*
*
*
*
Ax ≥ b⇒ y Ax ≥ y b
da cui
T
T
c T x* ≥ y* A x* ≥ y* b
quindi poichè vale la dualità forte le relazioni precedenti sono
verificate come uguaglianze. Consideriamo ad es. la prima
T *
T
T
*
*
T
*
c x = y Ax ⇒(c − y A)x* = 0
poichè per ipotesi
T
T
*
c − y A ≥ 0 e x* ≥ 0
il prodotto deve annullarsi termine per temine e quindi segue
* )x* = 0 i = 1,K, n
( ci − a T
y
i
i
Analogamente si giunge alla seconda relazione.
109
Dim. (Sufficienza)
Consideriamo vere le condizioni di slackness complementare per
la coppia di soluzioni x e y:
(a j x − b j ) y j = 0
j = 1,K, m
( ci − a T
i y) xi = 0
i = 1,K, n
In forma vettoriale
yT ( b − Ax ) = 0 ⇒ yT b = yT Ax
( cT − yT A )x = 0 ⇒ cT x = yT Ax
da cui segue
cT x = bT y
quindi per la dualità forte le due soluzioni sono ottime.
110