Data - Informatica

Programmazione Lineare
Andrea Scozzari
a.a. 2013-2014
March 18, 2014
Andrea Scozzari (a.a. 2013-2014)
Programmazione Lineare
March 18, 2014
1 / 18
Teorema Fondamentale della Programmazione Lineare
Si consideri il seguente problema generale di PL
max c T x
Ax ≤ b
Teorema
Si supponga che il poliedro P = {x ∈ Rn : Ax ≤ b} non contenga rette.
Allora una e una sola delle seguenti tre affermazioni `e vera:
1. Il problema `e inammissibile, ovvero P = ∅;
2. Il problema `e illimitato superiormente;
3. Il problema ammette soluzioni ottime e almeno una di queste
soluzioni `e un vertice del poliedro P.
Andrea Scozzari (a.a. 2013-2014)
Programmazione Lineare
March 18, 2014
2 / 18
Teorema Fondamentale della Programmazione Lineare
Il teorema ci dice che in pratica si possono verificare solo le seguenti
situazioni:
1. Il problema ammette soluzione ottima (che pu`
o essere o non essere
unica) in un vertice del pliedro che delimita la regione ammissibile;
2. il problema non ammette soluzione ottima perch´e
2.1 la regione ammissibile `e vuota
2.2 la regione ammissibile `e illimitata e la funzione obiettivo `e illimitata
superiormente (se il problema `e di massimizzazione) o illimitata
inferiormente (se il problema `e di minimizzazione).
Il teorema e la propriet`a 1. `e ci dice che la ricerca delle soluzioni ottime di
un problema di PL pu`o restringersi all’analisi dei soli vertici del poliedro P.
Andrea Scozzari (a.a. 2013-2014)
Programmazione Lineare
March 18, 2014
3 / 18
Metodo del Simplesso: Teorema di caratterizzazione delle SBA
Teorema
Sia dato un problema di PL in forma standard e sia Ax = b il relativo
sistema dei vincoli con A ∈ Rm×n e rango(A) = m e x ≥ 0. x `e una SBA
per il sistema dato se e solo se le colonne di A = {a1 , a2 , . . . , an } relative
alle componenti positive di x sono linearmente indipendenti (diremo anche
che x usa colonne linearmente indipendenti della matrice A).
NOTA: Il fatto che rango(A) = m implica m ≤ n e garantisce l’esistenza di almeno una
sottomatrice B non singolare.
Dimostrazione
Necessit`
a (⇒): Supponiamo che x sia una SBA. Allora esiste una base B tale che
xN = 0,
BxB = b
j
Pertanto x usa colonne a con j ∈ B. Dato che B `e non singolare e le sue colonne sono
linearmente indipendenti, allora anche le colonne aj ”usate” da x sono linearmente
indipendenti.
Andrea Scozzari (a.a. 2013-2014)
Programmazione Lineare
March 18, 2014
4 / 18
Metodo del Simplesso
Dimostrazione
Sufficienza (⇐): Supponiamo che x sia una soluzione e che usi k colonne
linearmente indipendenti di A. Allora k ≤ m (m `e il rango di A), e
supponiamo che queste colonne siano le prime k, a1 , a2 , . . . , ak . Dato che
x `e comunque una soluzione del sistema allora vale:
a1 x1 +a2 x2 +. . .+ak xk = b
x1 , x2 , . . . , xk > 0
e
xk+1 , xk+2 , . . . , xn = 0
Pertanto vale anche:
a1 x1 + a2 x2 + . . . + an xn = b
Andrea Scozzari (a.a. 2013-2014)
Programmazione Lineare
March 18, 2014
5 / 18
Metodo del Simplesso
Dimostrazione
Si hanno 2 casi:
Caso 1: k = m
In questo caso la sottomatrice che fa riferimento alle colonne
a1 , a2 , . . . , am `e una matrice di base B dato le colonne sono linearmente
indipendenti. Per cui B `e invertibile e la soluzione x pu`o riscriversi
xB = B −1 b ≥ 0,
Andrea Scozzari (a.a. 2013-2014)
xN = 0
Programmazione Lineare
March 18, 2014
6 / 18
Metodo del Simplesso
Dimostrazione
Caso 2: k < m
Dato che il rango di A `e m, alle k colonne aj (linearmente indipendenti) ne
possiamo aggiungere m − k per ottenere una base
a1 , a2 , . . . , ak , ak+1 , . . . , am dello spazio vettoriale generato dalle colonne di
A. Consideriamo B la sottomatrice ottenuta estraendo tali colonne da A e
per l’ipotesi che x sia una soluzione del sistema avremo
a1 x1 + a2 x2 + . . . + ak xk + ak+1 xk+1 + . . . + am xm = b
con ak+1 xk+1 , . . . , am xm tutti nulli e xN = 0 per ipotesi. Allora la
soluzione x = (xB , xN ) `e una SBA ed in particolare essa `e degenere con le
componenti xk+1 , . . . , xm tutte nulle.
Andrea Scozzari (a.a. 2013-2014)
Programmazione Lineare
March 18, 2014
7 / 18
Metodo del Simplesso
Teorema
Sia A una matrice m × n con m ≤ n e rango(A) = m. Dato il sistema di
equazioni lineari
Ax = b
le Soluzioni Basiche Ammissibili del sistema sono tutti e soli i punti
estremi del poliedro
P = {x ∈ Rn : Ax = b, x ≥ 0}
Andrea Scozzari (a.a. 2013-2014)
Programmazione Lineare
March 18, 2014
8 / 18
Metodo del Simplesso
Dimostrazione
Necessit`a: Sia x una SBA del sistema Ax = b e assumiamo per assurdo
che x non sia un vertice del poliedro P. Esistono due punti y , z ∈ P,
y 6= z, e 0 < α < 1 tali che:
x = αy + (1 − α)z
Dato che x `e una SBA, esiste una base B tale che:
x = (xB , xN ) = (B −1 b, 0). In particolare, si avr`a
xN = αyN + (1 − α)zN = 0
Dato che 0 < α < 1, l’equazione sopra vale se yN = zN = 0
Andrea Scozzari (a.a. 2013-2014)
Programmazione Lineare
March 18, 2014
9 / 18
Metodo del Simplesso
Dimostrazione
Dato che y , z ∈ P sono soluzioni ammissibili per il sistema Ax = b e deve
aversi
ByB + NyN = b
BzB + NzN = b
Ossia
ByB = b
⇒
yB = B −1 b
BzB = b
⇒
zB = B −1 b
da cui anche yB = zB e pertanto,
y =z
Dunque non esistono due punti y , z ∈ P con y 6= z per cui x `e
combinazione convessa di questi e, pertanto, x `e un vertice di P.
Andrea Scozzari (a.a. 2013-2014)
Programmazione Lineare
March 18, 2014
10 / 18
Metodo del Simplesso
Dimostrazione
Sufficienza: Sia x un punto estremo di P. Per il teorema di
caratterizzazione si ha che x `e una SBA per Ax = b se e solo se usa
colonne linearmente indipendenti di A. Assumiamo che x usi le prime k
per cui:
a 1 x1 + . . . + a k xk = b
Supponiamo per assurdo che x non sia una SBA e quindi le k colonne
sono linearmente dipendenti. Pertanto, per definizione avremo:
a1 y1 + . . . + ak yk = 0
con gli scalari y j , j = 1, . . . , k non tutti nulli.
Andrea Scozzari (a.a. 2013-2014)
Programmazione Lineare
March 18, 2014
11 / 18
Metodo del Simplesso
Dimostrazione
Sia y = (y1 , . . . , yk , 0, 0, . . . , 0) un vettore ad n componenti. Consideriamo
due vettori z 1 e z 2 e > 0 tali che
z 1 = x + y
z 2 = x − y
Preso il vettore z 1 ed sufficientemente piccolo si ha:
z 1 = (x1 + y1 , . . . , xk + yk , 0, 0, . . . , 0)
Dato che xi > 0, i = 1, . . . , k si avr`a xi + yi > 0, i = 1, . . . , k, per cui
z1 > 0
Andrea Scozzari (a.a. 2013-2014)
Programmazione Lineare
March 18, 2014
12 / 18
Metodo del Simplesso
Dimostrazione
Dalla dipendenza delle k colonne si avr`
a anche
Ay = a1 y1 , . . . , ak yk , ak+1 yk+1 , . . . , an yn = 0
Pertanto,
Az 1 = A(x + y ) = Ax + Ay = Ax = b
Per cui z 1 ∈ P. In modo analogo si dimostra che z 2 ∈ P. Dato che z 1 6= z 2 , si ha
x + y
x − y
z1 + z2
=
+
=x
2
2
2
La relazione precedente implica che x pu`
o essere ottenuto come combinazione convessa
di due punti z 1 , z 2 ∈ P con z 1 6= z 2 e ci`
o `e assurdo perch´e x `e un vertice. Per cui x usa
colonne linearmente indipendenti di A ed `e una SBA.
Andrea Scozzari (a.a. 2013-2014)
Programmazione Lineare
March 18, 2014
13 / 18
Metodo del Simplesso
1. Il metodo del simplesso trasforma un problema di PL in un problema
Standard in modo tale che il poliedro P non contenga rette;
2. Cerca la soluzione ottima tra i vertici del poliedro della regione
ammissibile che sono in numero finito muovendosi da un vertice ad un
vertice adiacente;
3. Algebricamente si arriva alla soluzione ottima di un problema di PL
generando una sequenza di SBA contigue.
Definizione
Due matrici di base B e B 0 sono contigue se differiscono esattamente per
una colonna.
NOTA: Ad un insieme di indici di base (i.e., una base) `e associata esattamente una
SBA, ma una SBA pu`
o provenire da pi`
u basi differenti.
Andrea Scozzari (a.a. 2013-2014)
Programmazione Lineare
March 18, 2014
14 / 18
Algoritmo del Simplesso
Passi: Ogni iterazione dell’algoritmo consiste in 6 passi
1. Determinazione della SBA corrente
2. Test di ottimalit`a
3. Scelta della variabile che dovr`a entrare in base nella iterazione
successiva (variabile entrante)
4. Test di illimitatezza
5. Scelta della variabile uscente dalla base corrente
6. Aggiornamento del valore della F.O.
Andrea Scozzari (a.a. 2013-2014)
Programmazione Lineare
March 18, 2014
15 / 18
Algoritmo del Simplesso
Dato un problema di PL:
Trovare una Soluzione Basica `e (relativamente) facile
Trovare una SBA non `e banale
Andrea Scozzari (a.a. 2013-2014)
Programmazione Lineare
March 18, 2014
16 / 18
Algoritmo del Simplesso
La SBA di partenza si ottiene ponendo a zero le variabili originali, e
assegnando alle variabili ausiliarie (Slack) il valore del termine noto del
vincolo corrispondente.
` sempre possibile effettuare una tale assegnazione?
E
Andrea Scozzari (a.a. 2013-2014)
Programmazione Lineare
March 18, 2014
17 / 18
Algoritmo del Simplesso
La SBA di partenza si ottiene ponendo a zero le variabili originali, e
assegnando alle variabili ausiliarie (Slack) il valore del termine noto del
vincolo corrispondente.
` sempre possibile effettuare una tale assegnazione? No
E
min
2x1 − 5x2
x1 + 2x2 ≤ 5
4x1 − 3x2 = −6
x1 − x2 ≥ 1
x1 , x2 ≥ 0
Andrea Scozzari (a.a. 2013-2014)
Programmazione Lineare
March 18, 2014
17 / 18
Algoritmo del Simplesso
In forma standard
Z = − max
5x2 − 2x1
x1 + 2x2 + x3 = 5
−4x1 + 3x2 = 6
x1 − x2 − x4 = 1
x1 , x2 , x3 , x4 ≥ 0
Il sistema Ax = b non `e in Forma Canonica Ammissibile
Definizione
Un sistema di equazioni si dice:
1. in Forma Canonica se ad ogni equazione si pu`
o associare una variabile basica che
ha coefficiente 1 in quella equazione e 0 in tutte le altre.
2. in Forma Canonica Ammissibile se ha inoltre la propriet`
a che tutti i termini noti
sono maggiori od uguali a 0.
Andrea Scozzari (a.a. 2013-2014)
Programmazione Lineare
March 18, 2014
18 / 18

Download Report