x - Informatica

Programmazione Lineare - Algoritmo del Simplesso
Andrea Scozzari
a.a. 2013-2014
March 21, 2014
Andrea Scozzari (a.a. 2013-2014)
Programmazione Lineare - Algoritmo del Simplesso
March 21, 2014
1/7
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 - Algoritmo del Simplesso
March 21, 2014
2/7
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 - Algoritmo del Simplesso
March 21, 2014
3/7
Algoritmo del Simplesso
Come trovare una SBA se il sistema Ax = b non `e in Forma Canonica
Ammissibile (FCA)?
FASE I:
Trovare un sistema di equazioni equivalente a Ax = b in FCA. Dato
S : ai1 x1 + ai2 x2 + . . . + ain xn = bi
i = 1, . . . , m
Si introducano m nuove variabili (artificiali) y1 , . . . , ym ≥ 0 e si riscriva il
sistema
ai1 x1 + ai2 x2 + . . . + ain xn + yi = bi
i = 1, . . . , m
Si definisce una nuova funzione obiettivo
w0 = min y1 + . . . + ym
Andrea Scozzari (a.a. 2013-2014)
Programmazione Lineare - Algoritmo del Simplesso
March 21, 2014
4/7
Algoritmo del Simplesso
Si risolve il problema
w0 = min y1 + . . . + ym =
m
P
(bi ) −
i=1
ai1 x1 + ai2 x2 + . . . + ain xn + yi = bi
xj ≥ 0
yi ≥ 0
m
n P
P
( aij )xj
j=1 i=1
i = 1, . . . , m
j = 1, . . . , n
i = 1, . . . , m
Il problema di FASE I `e sicuramente ammissibile dato che esiste almeno
una SBA ponendo xj = 0, j = 1, . . . , n, e yi = bi , i = 1, . . . , m.
Il problema di FASE I non `e illimitato inferiormente poich´e w0 ≥ 0.
Andrea Scozzari (a.a. 2013-2014)
Programmazione Lineare - Algoritmo del Simplesso
March 21, 2014
5/7
Algoritmo del Simplesso
Si risolve il problema
w0 = min y1 + . . . + ym =
m
P
(bi ) −
i=1
ai1 x1 + ai2 x2 + . . . + ain xn + yi = bi
xj ≥ 0
yi ≥ 0
m
n P
P
( aij )xj
j=1 i=1
i = 1, . . . , m
j = 1, . . . , n
i = 1, . . . , m
Teorema
Il sistema S ammette soluzioni non negative se e solo se w0 = 0
Andrea Scozzari (a.a. 2013-2014)
Programmazione Lineare - Algoritmo del Simplesso
March 21, 2014
6/7
Algoritmo del Simplesso
Dal teorema:
1. w0 = 0, Esiste un sistema in FCA equivalente ad S
2. w0 > 0 S non ammette soluzioni a componenti non negative ⇒ Il
problema di partenza `e inammissibile
Nel caso 1. L’ultimo sistema di equazioni in corrispondenza delle sole
variabili originarie x rispetto al quale l’algoritmo si ferma con w0 = 0, `e il
sistema S 0 in FCA equivalente ad S. Una Soluzione Basica Ammissibile di
S 0 `e la SBA di partenza per il problema originario.
Andrea Scozzari (a.a. 2013-2014)
Programmazione Lineare - Algoritmo del Simplesso
March 21, 2014
7/7
Problema
Consideriamo il seguente problema di PL
Modello di PL
max Z  4 x1  3x2
x1  x2  100
2 x1  x2  150
3x1  4 x2  360
x1 , x2  0
Modello in Forma Canonica
Ammissibile
max Z  4 x1  3x2
x1  x2  x3
 100
2 x1  x2
 x4
 150
3x1  4 x2
 x5  360
x1 , x2 , x3 , x4 , x5  0
Quale è la Soluzione Basica Ammissibile?
1
Individuazione della prima SBA
Modello in FCA
max Z  4 x1  3x2
x1  x2  x3
 100
2 x1  x2
 x4
 150
3x1  4 x2
 x5  360
x1 , x2 , x3 , x4 , x5  0
1 0 0
1
B  0 1 0, N  2
0 0 1
3
Z=0
1
1
4
1 1 1 0 0
100
A  2 1 0 1 0, b  150
3 4 0 0 1
360
 x3 
xB   x4 ,
 x5 
 x  0
xN   1    
 x 2  0
100 
 x3  100 
xB  B 1 150    x4   150 
360
 x5  360
2
Verifica dell’ottimalità della SBA corrente
La soluzione del problema è ottima?
CRITERIO e TEST di OTTIMALITA’
Una SBA è ottima se i benefici ridotti sono tutti minori o uguali a
zero. Infatti, prendiamo una SBA x=(xB,xN), il valore della
Funzione Obiettivo Z può essere riscritto in maniera equivalente:
1
1
Z  (c  c B N ) x N  c B b
T
N
T
B
T
B
Dato che x è una SBA (xB=B-1b ≥ 0; xN = 0) :
Per ogni altra soluzione con xN ≥ 0 per cui
si avrà:
Z  cBT B1b
Z  cBT B1b
  (cTN  cBT B 1 N )  0
4
     0 Il test Fallisce
3
Costruzione della nuova SBA
Come migliorare il valore della soluzione del problema?
Osserviamo la funzione obiettivo. L’unico modo per aumentare Z
è quello di aumentare il valore di x1 o di x2.
max Z  4 x1  3x2
Questo comporta scambiare di ruolo una variabile non basica con
una variabile basica.
x1  x2  x3  100
Come faccio a garantire l’ammissibilità dei vincoli effettuando lo
scambio? Di quanto posso aumentare x1 o x2?
2 x1  x2  x4  150
4
Costruzione della nuova SBA
I coefficienti della funzione obiettivo rappresentano il “tasso” di
miglioramento del valore di Z.
max Z  4 x1  3x2
Dato che il problema è di massimo, si sceglierà, ad esempio, la
variabile col massimo tasso di miglioramento. In questo caso x1.
Esattamente una tra le variabili x3, x4, x5. deve uscire dalla base, ed
assumerà valore nullo, ma le restanti variabili di base devono
continuare a soddisfare i vincoli di non-negatività:
x1  x2  x3
 100
2 x1  x2
 x4
 150
3x1  4 x2
 x5  360
x1 , x2 , x3 , x4 , x5  0
se x1  100/1  x3  0
se x1  150/2  x4  0
se x1  360/3  x5  0
5
Verifica dell’illimitatezza del Problema
TEST di ILLIMITATEZZA
Il problema è illimitato superiormente se per qualche variabile xi
fuori dalla base :
i)   0
i)   0
i
ii) B 1 Nei  0
1
ii ) B 1 N  2
3
1
1
4
Il test Fallisce
6
Significato del Test di Illimitatezza
TEST di ILLIMITATEZZA
Il problema è illimitato superiormente se per qualche variabile xi
fuori dalla base :
i)   0
i)   0
i
ii) B 1 Nei  0
1
ii ) B 1 N  2
3
1
1
4
Il test Fallisce
Consideriamo la colonna della variabile entrante x1. La scelta della
variabile uscente di base può scriversi:
Rapporto
x1
b
1
2,
 
3
100
150,
 
360
100/1
150/2, min100 , 150 , 360 




 1 2 3 
360/3
x1  x2  x3  100
7
Costruzione della nuova SBA
Si sceglierà quel valore dell’incremento di x1 che “garantisce”
l’ammissibilità della nuova soluzione
min 100, 75, 120  75

x4 esce dalla base
1 1 0
1 0
B  0 2 0, N  1 1
0 3 1
4 0
1 1 1 0 0
A  2 1 0 1 0
3 4 0 0 1
 x3 
xB   x1 ,
 x5 
 x  0
xN   2    
 x 4  0
100 
 x3   25 
xB  B 1 150    x1    75 
360
 x5  135
8
Definizione della nuova forma canonica
Questa nuova soluzione è ottima o è possibile ottenere un valore
migliore?
max Z  4 x1  3x2
Nell’espressione di Z compare una variabile basica ed una fuori
dalla base. Se si decide di variare x2, per garantire l’ammissibilità,
si dovrà modificare anche x1.
2x1  x2
 x4
 150
RISCHIO: x1 potrebbe diminuire facendo diminuire anche Z.
Idea. Far “sparire” la variabile x1 dalla funzione obiettivo in modo
tale che Z dipenda solo dalle variabili non basiche.
9
Definizione della nuova forma canonica
A partire dall’equazione vincolare che ha individuato la variabile
x4, si ricava x1:
1
1
x1  75  x2  x4
2
2
Da cui :
1
1 

Z  4 x1  3x2  4 75  x2  x4   3x2  300  x2  2 x4
2
2 

max Z  300  x2  2 x4
1
1
x2  x4  x3
 25
2
2
1
1
x2  x4
 x1
 75
2
2
5
3
x2  x4
 x5  135
2
2
x1 , x2 , x3 , x4 , x5  0
Il nuovo problema si trova
nuovamente in FCA, come nel
problema di partenza
10
Individuazione della SBA
Ripetendo gli stessi ragionamenti si ottiene:
1 1 0
1
B  1 2 0, N  0
4 3 1
0
0
1
0
 x2 
xB   x1 ,
 x5 
 x  0
xN   3    
 x 4  0
100 
 x2  50
xB  B 1 150    x1   50
360
 x5  10 
max Z  350  2 x3  x4
2 x3  x4  x2
 50
 x3  x4
 x1
 50
 5 x3  x4
 x5  10
x1 , x2 , x3 , x4 , x5  0
11
Verifica dell’ottimalità della SBA corrente
La soluzione del problema è ottima?
TEST di OTTIMALITA’
La SBA è ottima se i benefici ridotti sono tutti minori o uguali a
zero:
Z  350  2x3  x4
Dato che le variabili devono essere tutte non-negative, risulta:
Z  350
Dato che la Soluzione Basica Ammissibile corrente ha valore
esattamente pari a 350, questa soluzione è ottima.
12

Download Report