Programmazione Matematica: IV- L’algoritmo del simplesso · 2006. 10. 13. · 13/10/2003 1...

36
Programmazione Matematica: IV- L’algoritmo del simplesso Daniele Vigo D.E.I.S. – Università di Bologna [email protected] rev. 3.3 – Settembre 2003 Pmat.Simpl.2 D. 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 n m ) ( Per LP l’intorno N ε è esatto ε > 0 È esatto anche l’intorno N A (x) :={vertici ammissibili adiacenti ad x}

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

    [email protected]

    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 )