Data - Informatica

Algoritmo del Simplesso: Propriet`a e
Introduzione alla Dualit`a
Andrea Scozzari
a.a. 2013-2014
March 25, 2014
Andrea Scozzari (a.a. 2013-2014)
Algoritmo del Simplesso: Propriet`
a e Introduzione alla Dualit`
March
a
25, 2014
1/1
Propriet`
a Algoritmo del simplesso
Osservazione
Se nel corso dell’esecuzione dell’algoritmo si ritrova una base gi`a ottenuta
in precedenza, allora le soluzioni basiche ammissibili associate ai due
sistemi che danno la stessa base debbono coincidere.
Osservazione
Se a una data iterazione, scelta la variabile entrante in base, l’incremento
del valore di tale variabile `e strettamente positivo (pivot non degenere),
allora la funzione obiettivo aumenta strettamente dopo tale iterazione.
Andrea Scozzari (a.a. 2013-2014)
Algoritmo del Simplesso: Propriet`
a e Introduzione alla Dualit`
March
a
25, 2014
2/1
Propriet`
a Algoritmo del simplesso
Sia xh la variabile entrante, l’incremento ∆ della F.O. `e dato dal prodotto
ch × θ = min {
bi
|
aih
aih > 0,
i = 1, . . . , m}
θ = collo di bottiglia
Dato che per ipotesi ch > 0, e θ > 0
⇒ ∆ > 0.
Di conseguenza se nessun pivot `e degenere, nessuna base pu`o essere
ripetuta.
Andrea Scozzari (a.a. 2013-2014)
Algoritmo del Simplesso: Propriet`
a e Introduzione alla Dualit`
March
a
25, 2014
3/1
Propriet`
a Algoritmo del simplesso
Osservazione
Per un problema di PL in forma standard con m equazioni ed n variabili
m ≤ n, il massimo numero di iterazioni, nell’ipotesi che nessun pivot sia
degenere `e:
n
−1
m
Teorema
Se nessun pivot `e degenere, l’Algoritmo del Simplesso termina dopo un
numero finito di iterazioni.
Andrea Scozzari (a.a. 2013-2014)
Algoritmo del Simplesso: Propriet`
a e Introduzione alla Dualit`
March
a
25, 2014
4/1
Propriet`
a Algoritmo del simplesso
Osservazione
L’algoritmo del Simplesso non `e polinomiale
Esempio: V. Klee and G.J. Minty, 1972
max
n
P
10n−j xj
j=1
2
n
P
10i−j xj + xj ≤ 100i−j
i = 1, 2, . . . , n
j=1
xj ≥ 0
j = 1, 2, . . . , n
L’algoritmo compie 2n − 1 iterazioni.
Andrea Scozzari (a.a. 2013-2014)
Algoritmo del Simplesso: Propriet`
a e Introduzione alla Dualit`
March
a
25, 2014
5/1
Propriet`
a Algoritmo del simplesso
Caso n = 3
max
100x1 + 10x2 + x3
x1 ≤ 1
20x1 + x2 ≤ 100
200x1 + 20x2 + x3 ≤ 10000
x1 , x2 , x3 ≥ 0
1. Risolvere il problema scegliendo alla prima iterazione la variabile
entrante col massimo coefficiente nella F.O.
2. Risolvere l’esercizio scegliendo alla prima iterazione come variabile
entrante x3 .
Andrea Scozzari (a.a. 2013-2014)
Algoritmo del Simplesso: Propriet`
a e Introduzione alla Dualit`
March
a
25, 2014
6/1
Propriet`
a Algoritmo del simplesso
Regole di scelta per un pivot non degenere
1. Se vi sono pi`
u variabili candidate ad entrare nella base, ossia che
hanno beneficio ridotto positivo massimo, si sceglie come variabile
quella con indice minore
2. Se vi sono pi`
u variabili candidate ad uscire nella base, ossia che
presentano valore θ minimo, si sceglie quella con indice minore
Andrea Scozzari (a.a. 2013-2014)
Algoritmo del Simplesso: Propriet`
a e Introduzione alla Dualit`
March
a
25, 2014
7/1
Propriet`
a Algoritmo del simplesso
Regole di scelta della varibile entrante
1. Si sceglie come variabile entrante quella col beneficio ridotto positivo
massimo
2. Se vi sono pi`
u variabili candidate ad entrare nella base, ossia che
hanno beneficio ridotto positivo massimo, si sceglie come variabile
quella con indice minore (Regola di Bland)
3. Si sceglie come variabile entrante quella che fornisce il massimo
incremento dell Funzione obiettivo, ossia quella variabile xh che
massimizza
∆h = ch θh
Andrea Scozzari (a.a. 2013-2014)
Algoritmo del Simplesso: Propriet`
a e Introduzione alla Dualit`
March
a
25, 2014
8/1
La Dualit`a
Consideriamo il problema di Massimo in forma generale
Z = max
n
P
cj xj
j=1
(1)
n
P
aij xj ≤ bi
i = 1, 2, . . . , m
j=1
xj ≥ 0
j = 1, 2, . . . , n
Problema: Trovare delle stime per eccesso per il valore ottimo Z ∗ del
problema
Andrea Scozzari (a.a. 2013-2014)
Algoritmo del Simplesso: Propriet`
a e Introduzione alla Dualit`
March
a
25, 2014
9/1
La Dualit`a
Moltiplichiamo ciscuna disequazione per un coefficiente ui , i = 1, . . . , m e
poi sommiamo tra loro tutte le disequazioni.
u1 (
n
P
a1j xj ) + u2 (
n
P
a2j xj ) + . . . + um (
amj xj ) ≤
m
P
ui bi
i=1
j=1
j=1
j=1
n
P
Svolgendo i prodotti e mettendo in evidenza le variabili x si ha:
x1 (
m
P
ai1 ui ) + x2 (
i=1
Andrea Scozzari (a.a. 2013-2014)
m
P
i=1
ai2 ui ) + . . . + xn (
m
P
i=1
ain ui ) ≤
m
P
ui bi
i=1
Algoritmo del Simplesso: Propriet`
a e Introduzione alla Dualit`
March
a 25, 2014
10 / 1
La Dualit`a
Data una soluzione ottima x ∗ del problema di partenza, per una
assegnazione delle variabili ui ≥ 0, i = 1, . . . , m tali che
m
P
aij ui ≥ cj
j = 1, . . . , n
(2)
i=1
avremo
Z ∗ = c1 x1∗ + . . . + cn xn∗ ≤ x1 (
m
P
ai1 ui ) + . . . + xn (
m
P
i=1
i=1
ain ui ) ≤
m
P
ui bi
i=1
Pertanto, la quantit`a
m
X
ui bi
i=1
`e una limitazione superiore (Upper Bound) per il valore ottimo del
problema di partenza
Andrea Scozzari (a.a. 2013-2014)
Algoritmo del Simplesso: Propriet`
a e Introduzione alla Dualit`
March
a 25, 2014
11 / 1
La Dualit`a
Tra tutte le limitazioni superiori per Z ∗ l’obiettivo `e quello di assegnare
alle variabili ui dei valori che rispettino le relazioni (2) e tali che
restituiscano il valore pi`
u basso per
m
X
ui bi
i=1
Di fatto stiamo cercando di risolvere il seguente problema
min
m
P
ui bi
i=1
m
P
aij ui ≥ cj
j = 1, . . . , n
(3)
i=1
ui ≥ 0
Andrea Scozzari (a.a. 2013-2014)
i = 1, . . . , m
Algoritmo del Simplesso: Propriet`
a e Introduzione alla Dualit`
March
a 25, 2014
12 / 1
La Dualit`a
Il problema (3) `e detto problema Duale (D), del problema (1) che viene a
sua volta definito come problema Primale (P). Vale la seguente
trasformazione
(P) - Problema di Massimo:
max
n
P
cj xj
(D) - Problema di Minimo:
min
j=1
n
P
ui bi
i=1
aij xj ≤ bi
i = 1, 2, . . . , m
j=1
xj ≥ 0
m
P
m
P
aij ui ≥ cj
j = 1, 2, . . . , n
i=1
j = 1, 2, . . . , n
Andrea Scozzari (a.a. 2013-2014)
ui ≥ 0
i = 1, 2, . . . , m
Algoritmo del Simplesso: Propriet`
a e Introduzione alla Dualit`
March
a 25, 2014
13 / 1
La Dualit`a
In generale abbiamo
(P) - Problema di Massimo:
(D) - Problema di Minimo:
1. Massimo
1. Minimo
2. Disequazioni di tipo ≤
2. Disequazioni di tipo ≥
3. numero di vincoli
3. numero di variabili
4. numero di variabili
4. numero di vincoli
5. coefficienti della funzione
obiettivo
5. Termini noti del sistema di
disequazioni
6. Termini noti del sistema di
disequazioni
6. coefficienti della funzione
obiettivo
7. matrice A dei coefficienti
7. matrice AT dei coefficienti
Andrea Scozzari (a.a. 2013-2014)
Algoritmo del Simplesso: Propriet`
a e Introduzione alla Dualit`
March
a 25, 2014
14 / 1
La Dualit`a
In forma matriciale assumendo x ∈ Rn e b ∈ Rm due vettori colonna e
u ∈ Rm e c ∈ Rn due vettori riga
(P) - Problema di Massimo:
max
cx
(D) - Problema di Minimo:
min
ub
Ax ≤ b
uA ≥ c
x ≥0
u≥0
Andrea Scozzari (a.a. 2013-2014)
Algoritmo del Simplesso: Propriet`
a e Introduzione alla Dualit`
March
a 25, 2014
15 / 1
La Dualit`a
max
n
P
min
aij xj ≤ bi
ui ≥ 0
aij xj = bi
ui
j=1
n
P
libera
j=1
xj ≥ 0
m
P
aij ui ≥ cj
i=1
xj
libera
m
P
aij ui = cj
i=1
n
P
j=1
Andrea Scozzari (a.a. 2013-2014)
cj xj
m
P
bi ui
i=1
Algoritmo del Simplesso: Propriet`
a e Introduzione alla Dualit`
March
a 25, 2014
16 / 1
La Dualit`a: Teoremi
Teorema
La relazione di dualit`a `e involutoria, ovvero il duale del duale coincide col
primale
Teorema
Teorema di Dualit`a in forma debole: Data una coppia di problemi
Primale (P) e Duale (D), per ogni soluzione ammissibile x del primale e
per ogni soluzione ammissibile u per il duale vale:
cx ≤ ub
Andrea Scozzari (a.a. 2013-2014)
Algoritmo del Simplesso: Propriet`
a e Introduzione alla Dualit`
March
a 25, 2014
17 / 1
La Dualit`a: Teoremi
Dimostrazione
Assumiamo x ∈ Rn e b ∈ Rm due vettori colonna e u ∈ Rm e c ∈ Rn due
vettori riga.
Sia x una soluzione ammissibile per (P) allora vale: Ax ≤ b.
Sia u una soluzione ammissibile per (D) allora vale: uA ≥ c.
Pertanto, premoltiplicando il primo sistema per u e postmoltiplicando il
secondo sitema per x si ha:
cx ≤ uAx ≤ ub
Da cui la tesi
Andrea Scozzari (a.a. 2013-2014)
Algoritmo del Simplesso: Propriet`
a e Introduzione alla Dualit`
March
a 25, 2014
18 / 1
La Dualit`a: Teoremi
Lemma
Condizione sufficiente di ottimlit`
a: se x¯ `e una soluzione ammissibile per
il primale, u¯ una soluzione ammissibile per il duale e se c x¯ = u¯b, allora x¯ e
u¯ sono soluzioni ottime, rispettivamente, per (P) e (D).
Andrea Scozzari (a.a. 2013-2014)
Algoritmo del Simplesso: Propriet`
a e Introduzione alla Dualit`
March
a 25, 2014
19 / 1
La Dualit`a: Teoremi
Dimostrazione
Data una qualsiasi soluzione ammissibile, per il teorema di dualit`
a in forma debole
abbiamo:
cx ≤ u
¯b
e
c x¯ ≤ ub
Dato che per ipotesi c x¯ = u
¯b, si ha:
cx ≤ u
¯b = c x¯ ≤ ub
Per cui, per ogni soluzione ammissibile x di (P) e u di (D) abbiamo:
cx ≤ c x¯
e
u
¯b ≤ ub
Pertanto, x¯ e u
¯ sono soluzioni ottime per (P) e (D), rispettivamente.
Andrea Scozzari (a.a. 2013-2014)
Algoritmo del Simplesso: Propriet`
a e Introduzione alla Dualit`
March
a 25, 2014
20 / 1
La Dualit`a: Teoremi
Lemma
1. Se il problema Primale (P) `e illimitato superiormente allora il
problema duale (D) `e inammissibile
2. Se il problema Duale (D) `e illimitato inferiormente allora il problema
Primale (P) `e inammissibile
Andrea Scozzari (a.a. 2013-2014)
Algoritmo del Simplesso: Propriet`
a e Introduzione alla Dualit`
March
a 25, 2014
21 / 1

Download Report