Definizione: L’insieme , dove
e
, è detto poliedro.
Dunque, la regione ammissibile S di ogni problema di PL è un poliedro, dato che può essere descritta da vincoli di disuguaglianza del tipo .
In particolare, un insieme del tipo è un poliedro rappresentato in forma standard.
Un poliedro può essere limitato o illimitato:
Definizione: Un insieme è limitato se esiste una costante k tale che
Definiremo ora alcuni poliedri speciali, data la loro semplicità.
Definizione: Sia e sia
uno scalare.
Un poliedro è dato dall’intersezione di un numero finito di semispazi e di iperpiani.
Definizione: Un insieme è convesso se
e
risulta che
.
Si noti che v risulta dalla media pesata di x e y e dunque appartiene al segmento che unisce x ad y.
Infatti, si può in generale affermare che un insieme S è convesso se il segmento che unisce due punti qualunque di S è tutto contenuto in S stesso.
La definizione di convessità si può estendere al caso di media pesata di un numero finito di vettori.
Definizione: Siano e siano
scalari tali che
Il vettore è detto combinazione convessa dei vettori
.
Si dice inviluppo convesso dei vettori l’insieme di tutti i vettori combinazione convessa di
e si indica con
Valgono le seguenti proprietà, di cui trascuriamo in questo contesto la verifica.
Teorema
a. L’intersezione di insiemi convessi è un insieme convesso.
b. ogni poliedro è un insieme convesso.
c. La combinazione convessa di un numero finito di elementi di un insieme convesso S appartiene essa stessa all’insieme convesso S.
d. L’inviluppo convesso di un numero finito di vettori è un insieme convesso.
Come già osservato, una soluzione ottima finita di un problema di PL tende ad essere in corrispondenza di uno spigolo della regione ammissibile.
Nelle seguenti slides daremo tre definizioni equivalenti di spigolo come punto estremo, vertice e soluzione di base ammissibile.
Definizione: Sia P un poliedro. Un vettore x in P è detto punto estremo di P se non esistono due vettori y e z in P (y e z diversi da x) ed uno scalare , tali che
.
Definizione: Sia P un poliedro. Un vettore x in P è detto vertice di P se esiste un vettore c tale che c’x<c’y, per ogni y in P, y diverso da x.
La terza definizione equivalente di spigolo è algebrica e perciò utile ai fini algoritmici.
Per comprenderla, è necessaria un’ulteriori definizione, riportata di seguito.
Si consideri il seguente generico problema di PL:
Definizione: Se un vettore soddisfa
per qualche
, allora il corrispondente vincolo si dice attivo in
.
Ora abbiamo tutti gli strumenti per definire uno spigolo di un poliedro come soluzione ammissibile che attiva n vincoli linearmente indipendenti:
Definizione: Sia P un poliedro definito da vincoli di uguaglianza e/o disuguaglianza come in (P) e sia .
Il vettore è una soluzione di base se
tutti i vincoli di uguaglianza di (P) sono attivi in ;
attiva n vincoli linearmente indipendenti.
Se è una soluzione di base che soddisfa tutti i vincoli, allora è detta soluzione di base ammissibile.
I punti A, B, C, D, E ed F sono tutti soluzioni di base, dato che ciascuno di loro attiva due vincoli linearmente indipendenti. Tuttavia, solo i punti C, D, E ed F sono soluzioni di base ammissibili. Tratta da D. Bertsimas e J.N. Tsitsiklis, Introduction to Linear Optimization, Belmont - Massachusetts (USA), Dynamic Ideas and Athena Scientific, 2008. Rilucidata da Paola Festa
Esempio
.
I punti A, B, C e D attivano tre vincoli, mentre E attiva solo i seguenti due vincoli:
Come già anticipato, le tre differenti definizioni di spigolo di un poliedro sono perfettamente equivalenti fra loro:
Teorema
Sia P un poliedro non vuoto e sia x in P. Le seguenti tre affermazioni sono equivalenti:
x è un vertice di P;
x è un punto estremo di P;
x è una soluzione di base ammissibile.
Corollario: Dato un numero finito di vincoli lineari di disequazioni e/o equazioni, può esistere solo un numero finito di soluzioni di base e soluzioni di base ammissibili.
Definizione: Due distinte soluzioni di base di un poliedro P si dicono adiacenti se attivano gli stessi n-1 vincoli.
Se due soluzioni di base adiacenti sono anche ammissibili, come D e C in Figura, allora il segmento che li congiunge è detto lato del poliedro.
In Figura, ad esempio, B ed E sono entrambi adiacenti
a D, mentre A ed F sono adiacenti ad E.
Teorema
Si considerino i vincoli e
e si assuma che
sia una matrice a righe linearmente indipendenti.
Un vettore è soluzione di base se e solo se
I. ;
II. è possibile individuare indici tali che
le colonne sono linearmente indipendenti;
se , allora
.
Grazie alla validità del teorema appena enunciato, tutte le soluzioni di base di un poliedro descritto in forma standard possono essere ottenute applicando la semplice procedura riportata di seguito
Sia una soluzione di base ottenuta applicando la procedura appena descritta.
Se , allora
è detta soluzione di base ammissibile.
Viceversa, dal momento che ogni soluzione ammissibile di base è una soluzione di base, essa può essere ottenuta attraverso la semplice procedura sopra descritta.
Sia una soluzione di base,
le variabili sono dette variabili di base, mentre le restanti n-m variabili di decisione
sono dette variabili non di base;
le colonne sono dette colonne di base e formano una base di
;
è sempre possibile riordinare le colonne della matrice A, affinchè le colonne siano le prime m colonne, così ottenendo una sottomatrice quadrata
, detta matrice di base.
Le m variabili di base sono determinate risolvendo il sistema di m equazioni in m incognite
, la cui unica soluzione è data da
Sia P il poliedro in forma standard descritto dai seguenti vincoli di uguaglianza lineari:
La matrice dei coefficienti tecnologici A ed il vettore dei termini noti b sono i seguenti:
Se scegliamo le colonne
si ottiene la soluzione di base:
.
Dal momento che tale soluzione è non negativa, essa è una soluzione di base ammissibile.
Un’altra possibile scelta è .
La soluzione di base corrispondente è e
.
In tal caso la soluzione di base ottenuta non è ammissibile, perchè .
Definizione: Una soluzione di base è detta degenere se attiva più di n vincoli.
Osservazioni:
Esempi di soluzioni di base degeneri sono illustrati in Figura.
Osservazione:
Qualunque soluzione di base per poliedri in forma standard deve necessariamente attivare tutti gli m vincoli di uguaglianza. Dunque, l’unico modo per attivare più di n vincoli è che più di n-m variabili di decisione valgano 0. Infatti, vale la seguente definizione.
Definizione: Sia un poliedro in forma standard e sia
una soluzione di base.
Sia m il numero di righe di A, allora è detta soluzione di base degenere se più di n-m componenti di
sono nulle.
I punti A e C sono soluzioni di base ammissibili degeneri. I punti B ed E sono soluzioni di base ammissibili non degeneri. Il punto D è una soluzione di base non ammissibile degenere. Tratta da D. Bertsimas e J.N. Tsitsiklis, Introduction to Linear Optimization, Belmont - Massachusetts (USA), Dynamic Ideas and Athena Scientific, 2008. Rilucidata da Paola Festa
Come già osservato, una soluzione ottima finita di un problema di PL tende ad essere in corrispondenza di un punto estremo della regione ammissibile.
E’ chiaro che non tutti i poliedri hanno sempre almeno un punto estremo.
Un semispazio in , ad esempio, pur essendo un poliedro non ha punti estremi.
L’esistenza di almeno un punto estremo per un poliedro P dipende dalla presenza o meno in P di una retta:
Definizione: Un poliedro contiene una retta se esiste un vettore
ed un vettore non nullo
tale che
Teorema
Sia un poliedro non vuoto.
Le seguenti affermazioni sono equivalenti fra loro:
a. ha almeno un punto estremo;
b. non contiene una retta.
Corollario
Ogni poliedro limitato non vuoto ed ogni poliedro non vuoto descritto in forma standard ha almeno un punto estremo e, dunque, almeno una soluzione di base ammissibile.
Teorema
Si consideri il problema di PL consistente nel minimizzare c’x su un poliedro P che abbia almeno un punto estremo.
Allora, o il valore della soluzione ottima è oppure esiste un punto estremo di P che è soluzione ottima finita al problema.
Nel caso di problemi di PL generici, il Teorema non si applica direttamente se la regione ammissibile non ha punti estremi.
Tuttavia, sappiamo che un qualunque problema di PL può essere trasformato in un problema di PL equivalente formulato in forma standard, cui il Teorema invece si applica.
Corollario
Si consideri il problema di PL consistente nel minimizzare c’x su un poliedro P non vuoto.
Allora, o il valore della soluzione ottima è oppure esiste una soluzione ottima finita al problema.
Il Metodo del Simplesso si basa sui risultati teorici appena enunciati e cerca una soluzione ottima al problema muovendosi da una soluzione ammissibile di base ad una adiacente sempre nella direzione lungo la quale si verifica un decremento del valore corrente della funzione obiettivo.
Nel momento in cui viene raggiunta una soluzione ammissibile di base a partire dalla quale non è possibile intraprendere più alcuna direzione migliorativa del valore corrente della funzione obiettivo, la soluzione ammissibile di base corrente è ottima e l’algoritmo termina.
Corollario
Si consideri il problema di PL consistente nel minimizzare c’x su un poliedro P non vuoto.
Allora, o il valore della soluzione ottima è oppure esiste una soluzione ottima finita al problema.
Il Metodo del Simplesso si basa sui risultati teorici appena enunciati e cerca una soluzione ottima al problema muovendosi da una soluzione ammissibile di base ad una adiacente sempre nella direzione lungo la quale si verifica un decremento del valore corrente della funzione obiettivo.
Nel momento in cui viene raggiunta una soluzione ammissibile di base a partire dalla quale non è possibile intraprendere più alcuna direzione migliorativa del valore corrente della funzione obiettivo, la soluzione ammissibile di base corrente è ottima e l’algoritmo termina.
1. Presentazione del Corso ed Introduzione alla Programmazione Mat...
2. Introduzione ai Problemi di PL
6. Algoritmo del Simplesso Revisionato
7. Algoritmo del Simplesso Tabellare
10. Soluzione di Problemi di PL tramite Algoritmo del Simplesso
11. Problemi di Programmazione Lineare Intera
12. PLI con matrice dei vincoli unimodulare
13. Problemi di PLI: Branch & Bound
14. Il Problema dello Zaino 0/1 e il Problema dello Zaino Frazionar...
15. Il Problema dello Zaino 0/1: un algoritmo B&B
16. Il Problema dello Zaino 0/1: un algoritmo di Programmazione Din...
17. Richiami di Teoria dei Grafi: definizioni e notazioni
18. Il Problema del Vertex Cover Minimo di un Grafo
19. Il Problema dell'Albero di Copertura Minimo (MST)
20. Il Problema dell'Albero di Copertura Minimo (MST): esempio
D. Bertsimas e J.N. Tsitsiklis, Introduction to Linear Optimization, Belmont - Massachusetts (USA), Dynamic Ideas and Athena Scientific, 2008.
M. Fischetti, Lezioni di Ricerca Operativa, Padova, Edizioni Libreria Progetto Padova, 1999.
S. Martello, Fondamenti di Ricerca Operativa L-A, Bologna, Società Editrice Esculapio, 2004.
S. Martello, Ricerca Operativa LS, Bologna, Società Editrice Esculapio, 2004.
Dispense ed Appunti del Corso.