Programmazione Matematica: IV- L’algoritmo del simplesso · 2006. 10. 13. · 13/10/2003 1...
Transcript of Programmazione Matematica: IV- L’algoritmo del simplesso · 2006. 10. 13. · 13/10/2003 1...
-
13/10/2003
1
Programmazione Matematica:IV- L’algoritmo del simplesso
Daniele VigoD.E.I.S. – Università di Bologna
rev. 3.3 – Settembre 2003
Pmat.Simpl.2D. Vigo
Algoritmo del Simplesso• Metodo algebrico per la soluzione di problemi LP
(G.B. Dantzig, 1947)• Se esiste una soluzione ottima, essa coincide con
un vertice• I vertici ammissibili sono in un numero finito,
proporzionali a nm)(• Per LP l’intorno Nε è esatto ∀ε > 0
È esatto anche l’intorno NA(x) :={vertici ammissibili adiacenti ad x}
-
13/10/2003
2
Pmat.Simpl.3D. Vigo
P
Intorni ed LP• Dato x vertice corrente ed i suoi vertici adiacenti,
sia P l’insieme dei punti comb. conv. di tali punti∃ ε’ : i punti ammissibili dell’intorno Nε ’(x) , appartengono a P
xper verificare l’ottimalità e sufficiente farlo rispetto a NA(x)
Pmat.Simpl.4D. Vigo
Algoritmo1) Inizializzazione: parti da un vertice ammissibile
2) Ottimalità: esamina i vertici ammissibili e non esplorati adiacenti al corrente: se non esiste vertice migliore STOP
3) Iterazione: muovi verso un vertice ammissibile migliore e vai al passo 2
-
13/10/2003
3
Pmat.Simpl.5D. Vigo
z = 36
x2
x1
(0,6) (2,6)
(0,0)
(4,3)
(4,0)
Esempio
max z = 3x1 + 5x2∇ = (3,5)
C,27
B,36A,30
D,12E,0
Pmat.Simpl.6D. Vigo
Versione algebrica• Per rendere l’algoritmo del simplesso utilizzabile
(ad es su computer) è necessario trasformarlo da metodo geometrico
(basato su concetti di vertice ed intorno) a metodo algebrico
(basato sulla soluzione di sistemi di equazioni)
• Definizione di una procedura algebrica:
disequazioni equazioni forma standard
-
13/10/2003
4
Pmat.Simpl.7D. Vigo
Esempio
max z = 3x1 +5x2s.t. x1 ≤4
2x2 ≤123x1 +2x2 ≤18
x1 , x2 ≥0
min –z = –3x1 –5x2s.t. x1 + x3 =4
2x2 + x4 =123x1 +2x2 + x5 =18
x1 , x2 , x3 , x4 , x5 ≥0
• si passa da: Rt ( f. canonica) a: Rn (f. standard)
con n=t+m
(P’)
(P)
Pmat.Simpl.8D. Vigo
Soluzione aumentataDef.: Soluzione aumentata: soluzione di (P’)
corrispondente ad una soluzione di (P)
Si ottiene sostituendo in (P’) i valori delle t variabili originarie e ricavando i valori delle m rimanenti
Es. (3,2) → x1=3, x2=2
min –z = –3x1 –5x2s.t. x1 + x3 =4
2x2 + x4 =123x1 +2x2 + x5 =18x1 , x2 , x3 , x4 , x5 ≥0
→ (3,2,1,8,5)
–4 = 8–9 –4 = 5
–3 = 1
-
13/10/2003
5
Pmat.Simpl.9D. Vigo
Assunzioni
• n > m (più variabili di vincoli)
• A è di rango m(sottomatrici m x m non singolari)
Pmat.Simpl.10D. Vigo
Caratterizzazione dei vertici (1)
min –z = –3x1 –5x2s.t. x1 + x3 = 4
2x2 + x4 = 123x1 +2x2 + x5 = 18
x1 , x2 , x3 , x4 , x5 ≥ 0
(P’)
• Soluzione generica di (P’): valori arbitrari a tvariabili e si ricavano le rimanenti m
• Es. x4 = 8 , x5 = 5 → (3,2,1,8,5)x3 = 0 , x4 = 0 → (4,6,0,0,–6)
-
13/10/2003
6
Pmat.Simpl.11D. Vigo
Caratterizzazione dei vertici (2)• Si vuole lavorare su (P’) ed individuare le
soluzioni corrispondenti ai vertici di (P):• porre uguali a zero t variabili (⇒ sistema di m
equazioni in m incognite : BxB= d )• ricavare le altre m in modo univoco dal sistema
BxB = d • Si può dimostrare che in questo modo si
costruiscono tutte le soluzioni aumentate corrispondenti ai vertici di P
B–1 B–1
Pmat.Simpl.12D. Vigo
Esempio
min –z = –3x1–5x2s.t. x1 + x3 =4
2x2 + x4 =123x1+2x2 + x5 =18x1 , x2 , x3 , x4 , x5 ≥0
x2
x1
(0,6) (2,6)
(0,0)
(4,3)
(4,0)
(4,6)
(4,6,0,0,–6)
(4,3,0,6,0)
(3,2,1,8,5)
(3,2)
non è detto che siottenga un vertice :
(4,2,0,8,2)(4,2)
-
13/10/2003
7
Pmat.Simpl.13D. Vigo
Soluzioni Base (1)
• Una base di A è una collezione di m colonne linearmente indipendenti:
B = { Aβ(1),…, Aβ(m) }
vincoliA x = d
x ≥ 0
Pmat.Simpl.14D. Vigo
Soluzioni Base (2)• E’ possibile permutare le colonne di A in modo
che le Aj ∈ B siano le prime m:
A= [ A1,…, Am | Am+1,…, An ] = [ B | F ]
in base fuori base
con B matrice m x m non singolare, da cui
[ ] [ ]dxx
B|FF
B =
⇒ dFxBx FB =+⇒dAx =
-
13/10/2003
8
Pmat.Simpl.15D. Vigo
Soluzioni Base (3)
• È quindi possibile ricavare le xB a partire dalle xF(arbitrarie)
xB = B–1d – B–1F xF• Una soluzione base (SB), x’, si ottiene ponendo
[xF]=[0]
==∉=
=)1( di componente esima
per0: 1 ,...,mkd Bk-x
A xx' -
β(k)
jj B
variabili base
variabili non base
Pmat.Simpl.16D. Vigo
Esempio (1)B ={ A1, A2, A4}min –z = –3x1 –5x2s.t. x1 + x3 =4
2x2 + x4 =123x1 +2x2 + x5 =18x1 , x2 , x3 , x4 , x5 ≥0
B
=
023120001
=
18124
dF
=
100001
|B|
||Bb j i
ji-i j
+−=
)1(1
B
−−=−
1132/102/3001
1
−−−
==
5
411
4
2
1
132/12/301
634
xx
Fxd-B B xxx
F--
-
13/10/2003
9
Pmat.Simpl.17D. Vigo
Esempio (2)
• Manualmente si poteva procedere anche partendo dal sistema originario:
1. ricavando x1 = 4 – x3 dalla 1a equazione
2. sostituendo nella 3a ⇒ x2 = 3 + (3/2)x3 – (1/2) x53. sostituendo nella 2a ⇒ x4 = 6 – 3x3 + x5
min –z = –3x1 –5x2s.t. x1 + x3 =4
2x2 + x4 =123x1 +2x2 + x5 =18x1 , x2 , x3 , x4 , x5 ≥0
Pmat.Simpl.18D. Vigo
Soluzioni Base Ammissibili• Una SB, x’, soddisfa Ax = d, ma non
necessariamente x ≥ 0• SB Ammissibile (SBA) se x’ ≥ 0• SB non Ammissibile se ∃ xj’ < 0
Th.:x è un vertice del politopo
F={ x ∈ Rn : Ax = d , x ≥ 0 } se e solo se x è SBA del sistema Ax = d
-
13/10/2003
10
Pmat.Simpl.19D. Vigo
Algoritmo del Simplesso (1a versione)1. Scegli la base B = { Aβ(1),…, Aβ(m) } iniziale
(corrispondente ad una SBA)2. Calcola la SBA, x* , corrispondente a B3. Se x* è ottima STOP (test di ottimalità ) 4. Aggiorna B in modo che individui una SBA
adiacente e di costo migliore (inferiore) 5. Vai al passo 2
Dobbiamo vedere come realizzare i passi 1,3 e 4
Pmat.Simpl.20D. Vigo
Condizione di Ottimalità (1)min –z = –3x1 –5x2s.t. x1 + x3 =4
2x2 + x4 =123x1 +2x2 + x5 =18x1 , x2 , x3 , x4 , x5 ≥0
x2
x1
(0,6) (2,6)
(0,0)
(4,3)
(4,0)
A
E D
C
B
Vertice C corrispondente a B ={ A1 , A2 , A4 }
min –z = –3x1 –5x2s.t. x1 + x3 =4
2x2 + x4 =123x1 +2x2 + x5 =18x1 , x2 , x3 , x4 , x5 ≥0
min –z = –3x1 –5x2s.t. x1 + x3 =4
2x2 + x4 =123x1 +2x2 + x5 =18x1 , x2 , x3 , x4 , x5 ≥0
si ricavano le x1,x2,x4 in funzione di x3, x5x1 = 4 – x3x2 = 3 +(3/2) x3 – (1/2) x5x4 = 6 – 3 x3 + x5
– z = – cTx = –3x1 – 5x2 = –3(4–x3)–5(3+(3/2) x3–(1/2) x5) = – 27 – (9/2) x3 + (5/2) x5
-
13/10/2003
11
Pmat.Simpl.21D. Vigo
Condizione di Ottimalità (2)min –z = –3x1 –5x2s.t. x1 + x3 =4
2x2 + x4 =123x1 +2x2 + x5 =18x1 , x2 , x3 , x4 , x5 ≥0
x2
x1
(0,6) (2,6)
(0,0)
(4,3)
(4,0)
A
E D
C
B• attualmente x3=x5=0 (fuori base) e z=27
• aumentando x5 (muovendosi verso D) –z aumenta
• aumentando x3 (muovendosi verso B) –z diminuisce
Vertice C corrispondente a B ={ A1 , A2 , A4 }
– z = – cTx = –3x1 – 5x2 = –3(4–x3)–5(3+(3/2) x3–(1/2) x5) = – 27 – (9/2) x3 + (5/2) x5
Pmat.Simpl.22D. Vigo
Condizione di Ottimalità (3)• Pivoting = ingresso in base di una variabile
Analiticamente (problema di minimo)• Si sa che xB = B–1d – B–1FxF
da cui
x cT =+= xcx c FT
FBT
B[ ] xx
cc F
BTF
TB
=
=+= −− xcFxBd - cB c FT
FFT
BT
B11
FT
BT
FT
B F) xBc(cdBc11 −− −+=
costante
-
13/10/2003
12
Pmat.Simpl.23D. Vigo
Condizione di Ottimalità (4)Quindi
FT*T xc cx c '0 +=
dove[ ] ' 11 FBcc|BBcc c TBTFTBTBT −− −−=
0 TFc'
' 1 ABc cc BTT −−=
è il vettore dei costi ridotti (o residui)
Pmat.Simpl.24D. Vigo
Condizione di Ottimalità (5)• Se esiste un c’j < 0
facendo entrare in base xj , con xj =ϑ > 0
⇒ il costo diminuisce di ϑ c’j
• c’j è la variazione di z conseguente all’ingresso di un’unità di xj in base
• derivata direzionale di z rispetto alla direzione associata all’ingresso di xj
-
13/10/2003
13
Pmat.Simpl.25D. Vigo
Condizione di Ottimalità (6)Condizione di ottimalità
x* =(x*B|0) è ottimo se c’ ≥ 0
Infatti
xcT
Per le variabili in base c’j = 0 ⇒ Se esiste più di una colonna con c’j < 0 ,
quale fare entrare in base?
FTF
* xcc '0 += *c0≥∗= B
TB xc
Pmat.Simpl.26D. Vigo
Spostamento da SBA a SBA (1)• Se esiste Ah ∉ B tale che c’h < 0 bisogna farla
entrare in base
• Basi adiacenti: differiscono per una colonnaEs. {A1 , A2 , A4} e {A1 , A2 , A3}
• Una base adiacente si ottiene dalla attuale:• mantenendo xj = 0 ogni Aj ∉ B , j ≠ h• aumentando xh il più possibile mantenendo la soluzione
ammissibile
-
13/10/2003
14
Pmat.Simpl.27D. Vigo
Regole di Pivoting (1)• Nello spostamento tra basi adiacenti si hanno 2
gradi di libertà:1. scelta della variabile che entra in base2. scelta della variabile che lascia la base
Se due scelte arbitrarie ⇓
possibilità di SB non ammissibili
Pmat.Simpl.28D. Vigo
Esempiox2
x1
(0,6) (2,6)
(0,0)
(4,3)
(4,0)
A
E D
C
BVertice C corrispondente a
B = {A1 , A2 , A4} Se entra A3 ho 3 Basi Adiacenti:
B1 = {A1 , A2 , A3} Vertice B
min –z = –3x1 –5x2s.t. x1 + x3 =4
2x2 + x4 =123x1 +2x2 + x5 =18x1 , x2 , x3 , x4 , x5 ≥0
G
FB2 = {A1 , A3 , A4} Punto F
B3 = {A3 , A2 , A4} Punto G
-
13/10/2003
15
Pmat.Simpl.29D. Vigo
Regole di Pivoting (2)Algoritmo del Simplesso
• Entra in base una delle variabili che possono migliorare z (c’j < 0 )
• La variabile che esce viene determinata in modo che si ottenga una SBA
Pmat.Simpl.30D. Vigo
Esempio (1)
x2
x1
(0,6) (2,6)
(0,0)
(4,3)
(4,0)
A
E D
C
B
Vertice C corrispondente a B = { A1 , A2 , A4 }
x1 = 4 – x3x2 = 3 +(3/2) x3 – (1/2) x5x4 = 6 – 3 x3 + x5
– z = – cTx = –3x1 – 5x2 = – 27 – (9/2) x3 + (5/2) x5
• Conviene far entrare in base x3 (mantenendo x5 =0)
• Affinchè la soluzione rimanga ammissibile:
x1 = 4 – x3 ≥0 ⇒ x3 ≤ 4x2 = 3 +(3/2) x3 ≥0 ⇒ x3 ≥ –2x4 = 6 – 3 x3 ≥0 ⇒ x3 ≤ 2
Il massimo aumento ammissibile di x3è 2
-
13/10/2003
16
Pmat.Simpl.31D. Vigo
Esempio (2)
x2
x1
(0,6) (2,6)
(0,0)
(4,3)
(4,0)
A
E D
C
B
x1 = 4 – x3x2 = 3 +(3/2) x3x4 = 6 – 3 x3
= 4 – 2 = 2= 3 + 3 = 6= 6 – 2 = 0
x4 esce dalla base! x = (2,6,2,0,0)
Pmat.Simpl.32D. Vigo
∇
Esempio (3)
x2
x1
(0,6) (2,6)
(0,0)
(4,3)
(4,0)
A
E D
C
Bx1 = 2 +(1/3) x4 – (1/3) x5x2 = 6 – (1/2) x4x3 = 2 – (1/3) x4 +(1/3) x5
min –z = –3x1 –5x2s.t. x1 + x3 =4
2x2 + x4 =123x1 +2x2 + x5 =18x1 , x2 , x3 , x4 , x5 ≥0
– z = – cTx = –3x1 – 5x2 = – 36 + (3/2) x4 + x5
z = 36
OTTIMA!!!
-
13/10/2003
17
Pmat.Simpl.33D. Vigo
Spostamento da SBA a SBA (2)• Effetto dell’ingresso in base di xh :
xB = B–1d – B–1FxF [ ] [ ] [ ] [ ]
−=⇒ −−
M
M
hhB x ......A BdBx11
Tra le xF solo xh è diversa da 0
[ ] [ ] [ ] [ ] [ ] hhhhB xA'd'xABdBx −=−= −− 11 La formula di aggiornamento è:
,..., m ixa'd'x hihiβ(i) 1=−=
Pmat.Simpl.34D. Vigo
Spostamento da SBA a SBA (3)
• Si deve mantenere l’ammissibilità
⇒ xβ(i) ≥ 0 ∀i
• Dato che xh > 0 e d’i ≥ 0 si hanno 2 possibilità:
• a’ih ≤ 0 ⇒ xβ(i) ≥ 0 qualunque sia xh > 0
• a’ih > 0 ⇒ xβ(i) ≥ 0 solo per xh ≤ d’i / a’ih
,..., m ixa'd'x hihiβ(i) 1=−=
-
13/10/2003
18
Pmat.Simpl.35D. Vigo
Spostamento da SBA a SBA (4)• xh può crescere di
lh
lih
ih
i
a'd' ',..., m :a , i
a'd'
=
>== 01minϑ
xh entra in base a livello ϑ, ed xβ(l) esce dalla base(pivoting)
Se a’ih ≤ 0 ∀ixh → + ∞problema ILLIMITATO
x2
x1
F
Pmat.Simpl.36D. Vigo
SBA degeneri (1)• Una base B determina univocamente una SBA ,
per cui
SBA’ ≠ SBA” ⇒ B’ ≠ B”
Invece:
B’ ≠ B” ⇒ SBA’ ≠ SBA”
-
13/10/2003
19
Pmat.Simpl.37D. Vigo
Esempio
=
560
d
=
100120103000121
A
B’ = {A1,A4,A5} : (B’)–1 =
− 102010001
x’=(0,0,0,6,5)
B” = {A3,A4,A5} : (B”)–1 = I x”=(0,0,0,6,5)
più di n–m zeri
Pmat.Simpl.38D. Vigo
SBA degeneri (2)• Una SBA si dice degenere se contiene più di n–m
zeri
Th. Se 2 basi distinte B’ e B” corrispondono alla stessa SBA x, questa è degenere
DIM.x ha n – m zeri nelle colonne che non sono in B’ ed altri zeri nelle colonne di B’\B” (≠∅)
-
13/10/2003
20
Pmat.Simpl.39D. Vigo
SBA degeneri (3)• Non è detto che cambiando base si cambi anche
SBA (vertice) ⇒ cicli nell’algoritmo• La degenerazione si ha quando si verificano parità
nella scelta della variabile che esce dalla base (si azzera più di una variabile)
x2
x1
In pratica un vertice èsovradefinito
Pmat.Simpl.40D. Vigo
Algoritmo del Simplesso (1a versione)1. Scegli la base B = { Aβ(1),…, Aβ(m) } iniziale
(corrispondente ad una SBA)2. Calcola la SBA, x* , corrispondente a B3. Se x* è ottima STOP (test di ottimalità ) 4. Aggiorna B in modo che individui una SBA
adiacente e di costo migliore (inferiore) 5. Vai al passo 2
Dobbiamo vedere come realizzare i passi 1,3 e 4
-
13/10/2003
21
Pmat.Simpl.41D. Vigo
Algoritmo del Simplesso (2a versione)1) Inizializzazione
Sia B = { Aβ(1),…, Aβ(m) } una base iniziale (corrispondente ad una SBA)
2) Definisci B = [ Aβ(1),…, Aβ(m) ] e calcola la SBA
0con 00
1
≥
=
=
=
−
∗
∗
d' d'dB
xx
x*F
B
Pmat.Simpl.42D. Vigo
3) Test di ottimalitàCalcola i costi ridotti delle variabili fuori base
B∉∀−= − hhT
BT
hT
h A ABccc1'
0 A c' hh B∉∀≥
FBccc TBT
FT
F1' −−=
ovvero
Se STOP (x* soluzione ottima)
Algoritmo del Simplesso (2a versione)
-
13/10/2003
22
Pmat.Simpl.43D. Vigo
4) PivotingScegli Ah ∉ B tale che c’h < 0 e calcola
A’h = B–1Ah
Se a’hi ≤ 0 ∀i STOP (problema illimitato)
altrimenti calcola
>= = 0minarg 1 ihih
i,...,mi :a'a'
d'l
ed inserisci xh in base al posto di xβ(l)
Algoritmo del Simplesso (2a versione)
Pmat.Simpl.44D. Vigo
5) Vai al passo 2
In assenza di degenerazione ad ogni iterazionez decresce:⇒ l’algoritmo converge in un numero finito di
passi (nel caso peggiore dopo aver esaminato tutti i vertici )
Algoritmo del Simplesso (2a versione)
-
13/10/2003
23
Pmat.Simpl.45D. Vigo
Esempiomax z = x1 + x2s.t. 6 x1 + 4 x2 ≤ 24
3 x1 – 2 x2 ≤ 6x1 , x2 ≥0
x2
x1
(0,6)
(0,0)
(3,3/2)
(2,0)
A
D
C
B
min – z = – x1 – x2s.t. 6 x1 + 4 x2 + x3 = 24
3 x1 – 2 x2 + x4 = 6x1 , x2 , x3 , x4 ≥0
Pmat.Simpl.46D. Vigo
Inizializzazione
x2
x1
(0,6)
(0,0)
(3,3/2)
(2,0)
A
D
C
B
1) Inizializzazione2) Calcola la SBA, x*3) Test di ottimalità4) Pivoting5) Vai al passo 2
base iniziale
max z = x1 + x2s.t. 6 x1 + 4 x2 ≤ 24
3 x1 – 2 x2 ≤ 6x1 , x2 ≥0
min – z = – x1 – x2s.t. 6 x1 + 4 x2 + x3 = 24
3 x1 – 2 x2 + x4 = 6x1 , x2 , x3 , x4 ≥0
β = {3, 4}
x* = (0,0,24,6) punto A
B = {A3, A4}
-
13/10/2003
24
Pmat.Simpl.47D. Vigo
1a iterazione (1)
x2
x1
(0,6)
(0,0)
(3,3/2)
(2,0)
A
D
C
B
1) Inizializzazione2) Calcola la SBA, x*3) Test di ottimalità4) Pivoting5) Vai al passo 2
– z = c0* +c’FT xFxB = B–1d – B–1FxF
–z = 0 – x1 – x2x3 =24 – 6 x1 – 4 x2x4 = 6 – 3 x1 +2 x2
max z = x1 + x2s.t. 6 x1 + 4 x2 ≤ 24
3 x1 – 2 x2 ≤ 6x1 , x2 ≥0
min – z = – x1 – x2s.t. 6 x1 + 4 x2 + x3 = 24
3 x1 – 2 x2 + x4 = 6x1 , x2 , x3 , x4 ≥0
B = {A3, A4}
Pmat.Simpl.48D. Vigo
1a iterazione (2)
x2
x1
(0,6)
(0,0)
(3,3/2)
(2,0)
A
D
C
B
1) Inizializzazione2) Calcola la SBA, x*3) Test di ottimalità4) Pivoting5) Vai al passo 2
Pivot su x1x3 =24 – 6 x1 ≥0 ⇒ x1 ≤ 4x4 = 6 – 3 x1 ≥0 ⇒ x1 ≤ 2
x1 entra in base a livello 2, esce x4
max z = x1 + x2s.t. 6 x1 + 4 x2 ≤ 24
3 x1 – 2 x2 ≤ 6x1 , x2 ≥0
–z = 0 – x1 – x2x3 =24 – 6 x1 – 4 x2x4 = 6 – 3 x1 +2 x2
-
13/10/2003
25
Pmat.Simpl.49D. Vigo
2a iterazione (1)
x2
x1
(0,6)
(0,0)
(3,3/2)
(2,0)
A
D
C
B
1) Inizializzazione2) Calcola la SBA, x*3) Test di ottimalità4) Pivoting5) Vai al passo 2
x* = (2,0,12,0) punto B
–z =–2– (5/3) x2 +(1/3) x4x1 = 2 +(2/3) x2 – (1/3) x4x3 =12 – 8 x2 +2 x4
max z = x1 + x2s.t. 6 x1 + 4 x2 ≤ 24
3 x1 – 2 x2 ≤ 6x1 , x2 ≥0
in forma canonica rispetto alla nuova base:
–z = 0 – x1 – x2x3 =24 – 6 x1 – 4 x2x4 = 6 – 3 x1 +2 x2
Pmat.Simpl.50D. Vigo
2a iterazione (2)
x2
x1
(0,6)
(0,0)
(3,3/2)
(2,0)
A
D
C
B
1) Inizializzazione2) Calcola la SBA, x*3) Test di ottimalità4) Pivoting5) Vai al passo 2
Pivot su x2x1 = 2 + (2/3) x2 ≥0 ⇒ x2 ≥ –3x3 =12 – 8 x2 ≥0 ⇒ x2 ≤ 3/2
x2 entra in base a livello 3/2, esce x3
max z = x1 + x2s.t. 6 x1 + 4 x2 ≤ 24
3 x1 – 2 x2 ≤ 6x1 , x2 ≥0
–z =–2– (5/3) x2 +(1/3) x4x1 = 2 +(2/3) x2 – (1/3) x4x3 =12 – 8 x2 +2 x4
-
13/10/2003
26
Pmat.Simpl.51D. Vigo
3a iterazione (1)
x2
x1
(0,6)
(0,0)
(3,3/2)
(2,0)
A
D
C
B
1) Inizializzazione2) Calcola la SBA, x*3) Test di ottimalità4) Pivoting5) Vai al passo 2
x* = (3,3/2,0,0) punto C
–z =– (9/2) +(5/24) x3 – (1/12) x4x2 = (3/2) – (1/8) x3 + (1/4) x4x1 = 3 – (1/12) x3 – (1/6) x4
max z = x1 + x2s.t. 6 x1 + 4 x2 ≤ 24
3 x1 – 2 x2 ≤ 6x1 , x2 ≥0
–z =–2– (5/3) x2 +(1/3) x4x1 = 2 +(2/3) x2 – (1/3) x4x3 =12 – 8 x2 +2 x4
in forma canonica rispetto alla nuova base:
Pmat.Simpl.52D. Vigo
3a iterazione (2)
x2
x1
(0,6)
(0,0)
(3,3/2)
(2,0)
A
D
C
B
1) Inizializzazione2) Calcola la SBA, x*3) Test di ottimalità4) Pivoting5) Vai al passo 2
Pivot su x4x2 =3/2 + (1/4) x4 ≥0 ⇒ x4 ≥ –6x1 = 3 – (1/6) x4 ≥0 ⇒ x4 ≤ 18
x4 entra in base a livello 18ed esce x1
max z = x1 + x2s.t. 6 x1 + 4 x2 ≤ 24
3 x1 – 2 x2 ≤ 6x1 , x2 ≥0
–z =– (9/2) +(5/24) x3 – (1/12) x4x2 = (3/2) – (1/8) x3 + (1/4) x4x1 = 3 – (1/12) x3 – (1/6) x4
-
13/10/2003
27
Pmat.Simpl.53D. Vigo
4a iterazione (1)
x2
x1
(0,6)
(0,0)
(3,3/2)
(2,0)
A
D
C
B
1) Inizializzazione2) Calcola la SBA, x*3) Test di ottimalità4) Pivoting5) Vai al passo 2
x* = (0,6,0,18) punto D
–z = – 6 +(1/2) x1 + (1/4) x3x4 = 18 – 6 x1 – (1/2) x3x2 = 6 – (3/2) x1 – (1/4) x3
max z = x1 + x2s.t. 6 x1 + 4 x2 ≤ 24
3 x1 – 2 x2 ≤ 6x1 , x2 ≥0
OTTIMO!!!
–z =– (9/2) +(5/24) x3 – (1/12) x4x2 = (3/2) – (1/8) x3 + (1/4) x4x1 = 3 – (1/12) x3 – (1/6) x4
in forma canonica rispetto alla nuova base:
Pmat.Simpl.54D. Vigo
Inizializzazione
x2
x1
(0,6)
(0,0)
(3,3/2)
(2,0)
A
D
C
B
1) Inizializzazione2) Calcola la SBA, x*3) Test di ottimalità4) Pivoting5) Vai al passo 2
base iniziale
max z = x1 + x2s.t. 6 x1 + 4 x2 ≤ 24
3 x1 – 2 x2 ≤ 6x1 , x2 ≥0
min – z = – x1 – x2s.t. 6 x1 + 4 x2 + x3 = 24
3 x1 – 2 x2 + x4 = 6x1 , x2 , x3 , x4 ≥0
β = {3, 4}B = {A3, A4}
-
13/10/2003
28
Pmat.Simpl.55D. Vigo
1a iterazione (1)
x2
x1
(0,6)
(0,0)
(3,3/2)
(2,0)
A
D
C
B
1) Inizializzazione2) Calcola la SBA, x*3) Test di ottimalità4) Pivoting5) Vai al passo 2
max z = x1 + x2s.t. 6 x1 + 4 x2 ≤ 24
3 x1 – 2 x2 ≤ 6x1 , x2 ≥0
min – z = – x1 – x2s.t. 6 x1 + 4 x2 + x3 = 24
3 x1 – 2 x2 + x4 = 6x1 , x2 , x3 , x4 ≥0
x* = (0,0,24,6) punto A
=
=
−
∗
∗
0
1dBxx
x*F
B 1
1001 −=
= BB
β = {3, 4}
Pmat.Simpl.56D. Vigo
1a iterazione (2)
x2
x1
(0,6)
(0,0)
(3,3/2)
(2,0)
A
D
C
B
1) Inizializzazione2) Calcola la SBA, x*3) Test di ottimalità4) Pivoting5) Vai al passo 2
max z = x1 + x2s.t. 6 x1 + 4 x2 ≤ 24
3 x1 – 2 x2 ≤ 6x1 , x2 ≥0
min – z = – x1 – x2s.t. 6 x1 + 4 x2 + x3 = 24
3 x1 – 2 x2 + x4 = 6x1 , x2 , x3 , x4 ≥0
[ ] [ ] [ ]110011 1 −−=⋅−−−= − FBFBccc TB
TF
TF
1−−=′
β = {3, 4}
1
1001 −=
= BB
-
13/10/2003
29
Pmat.Simpl.57D. Vigo
1a iterazione (3)
x2
x1
(0,6)
(0,0)
(3,3/2)
(2,0)
A
D
C
B
1) Inizializzazione2) Calcola la SBA, x*3) Test di ottimalità4) Pivoting5) Vai al passo 2
Pivot su x1
max z = x1 + x2s.t. 6 x1 + 4 x2 ≤ 24
3 x1 – 2 x2 ≤ 6x1 , x2 ≥0
min – z = – x1 – x2s.t. 6 x1 + 4 x2 + x3 = 24
3 x1 – 2 x2 + x4 = 6x1 , x2 , x3 , x4 ≥0
l=arg min { (24/6) , (6/3) } = 2 ϑ = 2
esce β (2) = 4
111
1' AABA ==−
β = {1, 3}
Pmat.Simpl.58D. Vigo
2a iterazione (1)
x2
x1
(0,6)
(0,0)
(3,3/2)
(2,0)
A
D
C
B
1) Inizializzazione2) Calcola la SBA, x*3) Test di ottimalità4) Pivoting5) Vai al passo 2
max z = x1 + x2s.t. 6 x1 + 4 x2 ≤ 24
3 x1 – 2 x2 ≤ 6x1 , x2 ≥0
min – z = – x1 – x2s.t. 6 x1 + 4 x2 + x3 = 24
3 x1 – 2 x2 + x4 = 6x1 , x2 , x3 , x4 ≥0
x* = (2,0,12,0) punto B
=
=
−
∗
∗
0
1dBxx
x*F
B
β = {1, 3}
−
=−213/101B
B
=
0316
-
13/10/2003
30
Pmat.Simpl.59D. Vigo
2a iterazione (2)
x2
x1
(0,6)
(0,0)
(3,3/2)
(2,0)
A
D
C
B
1) Inizializzazione2) Calcola la SBA, x*3) Test di ottimalità4) Pivoting5) Vai al passo 2
max z = x1 + x2s.t. 6 x1 + 4 x2 ≤ 24
3 x1 – 2 x2 ≤ 6x1 , x2 ≥0
min – z = – x1 – x2s.t. 6 x1 + 4 x2 + x3 = 24
3 x1 – 2 x2 + x4 = 6x1 , x2 , x3 , x4 ≥0
FBccc TBT
FT
F1−−=′
β = {1, 3}
−
=−213/101B
[ ] [ ] =
⋅
−
⋅−−−=′1204
21310
0101-
/c TF
[ ]3/12/5−=
Pmat.Simpl.60D. Vigo
2a iterazione (3)
x2
x1
(0,6)
(0,0)
(3,3/2)
(2,0)
A
D
C
B
1) Inizializzazione2) Calcola la SBA, x*3) Test di ottimalità4) Pivoting5) Vai al passo 2
Pivot su x2
max z = x1 + x2s.t. 6 x1 + 4 x2 ≤ 24
3 x1 – 2 x2 ≤ 6x1 , x2 ≥0
min – z = – x1 – x2s.t. 6 x1 + 4 x2 + x3 = 24
3 x1 – 2 x2 + x4 = 6x1 , x2 , x3 , x4 ≥0
l=arg min { (12/8) } = 2 ϑ = 3/2
esce β (2) = 3
β = {1, 2}
−== −
83/2
' 21
2 ABA
-
13/10/2003
31
Pmat.Simpl.61D. Vigo
3a iterazione (1)
x2
x1
(0,6)
(0,0)
(3,3/2)
(2,0)
A
D
C
B
1) Inizializzazione2) Calcola la SBA, x*3) Test di ottimalità4) Pivoting5) Vai al passo 2
max z = x1 + x2s.t. 6 x1 + 4 x2 ≤ 24
3 x1 – 2 x2 ≤ 6x1 , x2 ≥0
min – z = – x1 – x2s.t. 6 x1 + 4 x2 + x3 = 24
3 x1 – 2 x2 + x4 = 6x1 , x2 , x3 , x4 ≥0
x* = (3,3/2,0,0) punto C
=
=
−
∗
∗
0
1dBxx
x*F
B
β = {1, 2}
−
=−4/18/1
6/112/11B
−
=23
46B
Pmat.Simpl.62D. Vigo
3a iterazione (2)
x2
x1
(0,6)
(0,0)
(3,3/2)
(2,0)
A
D
C
B
1) Inizializzazione2) Calcola la SBA, x*3) Test di ottimalità4) Pivoting5) Vai al passo 2
max z = x1 + x2s.t. 6 x1 + 4 x2 ≤ 24
3 x1 – 2 x2 ≤ 6x1 , x2 ≥0
min – z = – x1 – x2s.t. 6 x1 + 4 x2 + x3 = 24
3 x1 – 2 x2 + x4 = 6x1 , x2 , x3 , x4 ≥0
FBccc TBT
FT
F1−−=′
β = {1, 2}
−
=−4/18/1
6/112/11B
[ ] [ ]
−
−−−=′1001
418161121
1100 //
// c TF
[ ]12/124/5 −=
-
13/10/2003
32
Pmat.Simpl.63D. Vigo
3a iterazione (3)
x2
x1
(0,6)
(0,0)
(3,3/2)
(2,0)
A
D
C
B
1) Inizializzazione2) Calcola la SBA, x*3) Test di ottimalità4) Pivoting5) Vai al passo 2
Pivot su x4
max z = x1 + x2s.t. 6 x1 + 4 x2 ≤ 24
3 x1 – 2 x2 ≤ 6x1 , x2 ≥0
min – z = – x1 – x2s.t. 6 x1 + 4 x2 + x3 = 24
3 x1 – 2 x2 + x4 = 6x1 , x2 , x3 , x4 ≥0
l=arg min { 3·6 } = 1 ϑ = 18
esce β (1) = 1
β = {2, 4}
−
== −4/1
6/1' 4
14 ABA
Pmat.Simpl.64D. Vigo
4a iterazione (1)
x2
x1
(0,6)
(0,0)
(3,3/2)
(2,0)
A
D
C
B
1) Inizializzazione2) Calcola la SBA, x*3) Test di ottimalità4) Pivoting5) Vai al passo 2
max z = x1 + x2s.t. 6 x1 + 4 x2 ≤ 24
3 x1 – 2 x2 ≤ 6x1 , x2 ≥0
min – z = – x1 – x2s.t. 6 x1 + 4 x2 + x3 = 24
3 x1 – 2 x2 + x4 = 6x1 , x2 , x3 , x4 ≥0
x* = (0,6,0,18) punto D
=
=
−
∗
∗
0
1dBxx
x*F
B
β = {2, 4}
−
=1204
B
=−
12/104/11B
-
13/10/2003
33
Pmat.Simpl.65D. Vigo
4a iterazione (2)
x2
x1
(0,6)
(0,0)
(3,3/2)
(2,0)
A
D
C
B
1) Inizializzazione2) Calcola la SBA, x*3) Test di ottimalità4) Pivoting5) Vai al passo 2
max z = x1 + x2s.t. 6 x1 + 4 x2 ≤ 24
3 x1 – 2 x2 ≤ 6x1 , x2 ≥0
min – z = – x1 – x2s.t. 6 x1 + 4 x2 + x3 = 24
3 x1 – 2 x2 + x4 = 6x1 , x2 , x3 , x4 ≥0
FBccc TBT
FT
F1−−=′
β = {2, 4}
=−
12/104/11B
[ ] [ ]
−−−=′
0316
121041
0101 //
c TF
[ ]4/12/1= OTTIMO!!!
Pmat.Simpl.66D. Vigo
Regole di Pivoting (3)• Ad una generica iterazione:
quale tra le xj con c’j < 0 far entrare in base ?• la prima con c’j negativo ≤ n - m• quella con c’j più negativo = n –m • quella con | ϑ j c’j | massimo = (n-m) m• ……
• Se SBA corrente degenere
00min 1 =
>= = ihih
i,...,mi :a'a'
d'ϑ
⇒ z non diminuisce ⇒ rischio di cicli (degenerazione ciclante)
-
13/10/2003
34
Pmat.Simpl.67D. Vigo
Regola di BlandConsente di evitare la degenerazione ciclante
a) Entra la colonna favorevole di indice minimo
{ }0:min
-
13/10/2003
35
Pmat.Simpl.69D. Vigo
Determinazione SBA iniziale (2)• Il problema equivale a trovare una soluzione
ammissibile di
(x, y) in cui y = 0 ( y variabili artificiali)
• Il secondo problema ha una SBA iniziale ovvia ( x = 0, y = d )
Ax + I y = d
x, y ≥ 0
Pmat.Simpl.70D. Vigo
Metodo delle due fasi (1)1) Si determina la SBA iniziale risolvendo il
problema
• se alla fine w > 0 STOP (problema inammissibile)
• se w = 0 normalmente tutte le y sono fuori base e sono in base alcune x (⇒ SBA iniziale)
min w = yTAx + I y = d
x, y ≥ 0
-
13/10/2003
36
Pmat.Simpl.71D. Vigo
Metodo delle due fasi (2)2) Si eliminano le variabili artificiali y
si ripristina la funzione obiettivo originaria min z = c’x
e si prosegue con il simplessopartendo dalla SBA corrente
Pmat.Simpl.72D. Vigo
Casi “patologici”• se w = 0 ma esiste yh in base (ad es. sulla riga i)• la soluzione deve essere degenere yh=01. se esiste almeno un a’ij ≠ 0 in corrispondenza di
una variabile originale• si può fare una operazione di pivot su tale a’ij per
portare in base xj al posto di yh2. se tutti gli a’ij = 0 (la riga è tutta di 0)
• è comb. lineare di altre righe della matrice A• A non è di rango massimo e la riga può essere
rimossa (rimuovendo in tal modo anche la yh )