Lezionidi RicercaOperativa Lezionen 12 °

Lezione n

°

12

Algoritmo del Simplesso:

- Metodo delle 2 Fasi - Metodo del Big-M - Esempi

R. Cerulli

–

F. Carrabs

Lezioni di Ricerca Operativa

Università degli Studi di Salerno

Metodo Delle Due Fasi

Dato il seguente problema di PL in forma STANDARD:

dove A è una matrice mxn, con m<n, a rango pieno e b ≥ 0, supponiamo di voler utilizzare il metodo del simplesso per risolvere il problema.

Ci occorre una base iniziale

𝑚𝑖𝑛 𝑧 = 𝑐

!

𝑥

A𝑥 = 𝑏

Metodo Delle Due Fasi

Se tra le colonne di A non è presente la matrice identità, l’individuazione di una sottomatrice quadrata mxm di A (ossia una base

di Rm _{da cui partire) può essere un’operazione costosa.}

Il problema viene risolto modificando artificialmente il sistema dei vincoli come segue:

Si aggiunge una variabile artificiale y_i ad ogni vincolo del sistema. Per costruzione, nel nuovo sistema è presente una matrice identità

(associata alle variabili y).

A𝑥 = 𝑏

𝑥 ≥ 0

A𝑥 + 𝐼𝑦 = 𝑏

𝑥 ≥ 0, 𝑦 ≥ 0

Metodo Delle Due Fasi

Una soluzione (x’,y’) del nuovo sistema sarà soluzione anche del sistema di partenza se e solo se y’=0.

Per ottenere una tale soluzione (se esiste) risolviamo il seguente problema di PL.

𝑚𝑖𝑛 𝑔 = .

!

𝑦

_𝑖

A𝑥 + 𝐼𝑦 = 𝑏

𝑥 ≥ 0, 𝑦 ≥ 0

Metodo Delle Due Fasi

Per risolvere il nuovo problema possiamo utilizzare il simplesso a partire dalla matrice identità generata dalle colonne associate alle variabili artificiali y.

Quindi nella prima fase del metodo si risolve il problema:

Si noti che inizialmente tutte le variabili y sono in base mentre tutte le variabili x sono fuori base.

𝑚𝑖𝑛 𝑔 = '

!

𝑦_𝑖 A𝑥 + 𝐼𝑦 = 𝑏 𝑥 ≥ 0, 𝑦 ≥ 0

Se il problema originale ammette una soluzione ottima finita, quale sarà il minimo numero di iterazioni necessarie al simplesso per azzerare le variabili artificiali?

Metodo Delle Due Fasi

Alla fine della prima fase possono verificarsi due casi:

1) g* > 0

Þ Ax=b non ammette soluzione. Il problema di

partenza è inammissibile e non si passa alla seconda fase.

2) g* = 0

Þ Ax=b ammette soluzione.

Si passa alla seconda fase risolvendo il problema iniziale

utilizzando la base ottima della prima fase come base di

partenza per il simplesso.

Perché non avremo mai un ottimo illimitato per il problema

della prima fase?

Metodo Delle Due Fasi: Esempio

Problema della

prima fase

𝑚𝑖𝑛 𝑧 = −𝑥₁ − 2𝑥₂ 𝑥₁ + 𝑥₂ ≥ 1 𝑥₁ + 2𝑥₂ ≤ 4 𝑥 ≥ 0 𝑚𝑖𝑛 𝑧 = −𝑥₁ − 2𝑥₂ 𝑥₁ + 𝑥₂ − 𝑥₃ = 1 𝑥₁ + 2𝑥₂ + 𝑥₄ = 4 𝑥 ≥ 0 𝑚𝑖𝑛 𝑔 = 𝑥_"# 𝑥₁ + 𝑥₂ − 𝑥₃ + 𝑥_"# = 1 𝑥₁ + 2𝑥₂ + 𝑥₄ = 4 𝑥 ≥ 0, 𝑥_"# ≥ 0 Forma standard

D’ora in poi indicheremo le variabili artificiali con l’apice a per poterle distinguere dalle variabili del problema di partenza.

Metodo Delle Due Fasi:

𝟏

°

fase

Matrice Identità

(Base Iniziale)

𝑚𝑖𝑛 𝑔 = 𝑥_"# 𝑥₁ + 𝑥₂ − 𝑥₃ + 𝑥_"# = 1 𝑥₁ + 2𝑥₂ + 𝑥₄ = 4 𝑥 ≥ 0, 𝑥_"# ≥ 0

B = {5,4}

N = {1,2,3}

Metodo Delle Due Fasi:

𝟏

°

fase

Test di Ottimalità: calcolo di z

_j

– c

_j

per j∈N = {1,2,3}

𝐴

_"

= 1 0

0 1

𝑥

𝐵

= 𝐴

"#$

𝑏 ⟹ 𝑥

𝐵

= 𝐼𝑏 ⟹ 𝑥

𝐵

= 𝑏

𝑥

_%&

𝑥

₄

=

𝐴

#$"

𝑏 = 1 0

0 1

4

1

= 1

4

𝑥

78

= 1,

𝑥

4

= 4

𝑧

₁

− 𝑐

₁

= 1 0 𝐼 1

1

− 0 = 1

𝑧

₂

− 𝑐

₂

= 1 0 𝐼 1

2

− 0 = 1

𝑧

₃

− 𝑐

₃

= 1 0 𝐼 −1

0

− 0 = −1

Metodo Delle Due Fasi:

𝟏

°

fase

x

₂

entra in base

Quale variabile esce dalla base?

Test dei minimi rapporti:

𝑥

_%&

esce dalla base; x

₂

entra in base con valore 1

𝑥

_%&

𝑥

₄

= 𝑏 = 1

4

𝑦

2

= 𝐴

" #$

_𝑎

2

= 𝐼 1

₂

= 1

₂

𝑥

₂

= min

$'(')

𝑏

_𝑖

𝑦

_𝑖𝑘

: 𝑦𝑖𝑘 > 0 = min

$'(')

1

1

,

4

2

= 1 =

𝑏

₁

𝑦

_1𝑘

Nuova base: B = {2,4} N = {1,3,5}

Metodo Delle Due Fasi:

𝟏

°

fase

Test di Ottimalità: calcolo di z

_j

– c

_j

per j∈N = {1,3,5}

𝐴

_"

= 1 0

2 1

𝑥

₂

𝑥

₄

=

𝐴

"#$

𝑏 = 1

_{−2 1}

0

1

₄

= 1

₂

𝑧

₁

− 𝑐

₁

= 0 0

1

0

−2 1

1

1

− 0 = 0

𝐴

_"#$

= 1

0

−2 1

𝑧

₃

− 𝑐

₃

= 0 0

1

0

−2 1

−1

0

− 0 = 0

𝑧

₅

− 𝑐

₅

= 0 0

1

0

−2 1

1

0

− 1 = −1

Soluzione ottima

Metodo Delle Due Fasi:

𝟏

°

fase

Soluzione Ottima della Prima fase

Si può passare alla seconda fase

Si risolve il problema iniziale utilizzando come base di partenza:

𝑔

∗

= 𝑐

_𝐵

𝐴

_"#$

𝑏

𝑔

∗

= 0 0

1

0

−2 1

1

4

= 0

B = {2,4} N = {1,3,5}

𝑚𝑖𝑛 𝑧 = −𝑥₁ − 2𝑥₂ 𝑥₁ + 𝑥₂ − 𝑥₃ = 1 𝑥₁ + 2𝑥₂ + 𝑥₄ = 4 𝑥 ≥ 0

Metodo Delle Due Fasi:

𝟐

°

fase

Test di Ottimalità: calcolo di z

_j

– c

_j

per j∈N = {1,3}

𝐴

_"

= 1 0

2 1

𝑥

₂

𝑥

₄

=

𝐴

"#$

𝑏 = 1

_{−2 1}

0

1

₄

= 1

₂

𝑧

₁

− 𝑐

₁

= −2 0

1

0

−2 1

1

1

− −1 = −1

𝐴

_"#$

= 1

0

−2 1

𝑧

₃

− 𝑐

₃

= −2 0

1

0

−2 1

−1

0

− 0 = 2

x3 entra in base

Metodo Delle Due Fasi:

𝟐

°

fase

x

₃

entra in base

Quale variabile esce dalla base?

Test dei minimi rapporti:

x

₄

esce dalla base; x

₂

entra in base con valore 1

𝑥

₂

𝑥

₄

= 1

₂

𝑦

3

= 𝐴

"#$

𝑎

3

= 1

−2 1

0

−1

0

= −1

2

𝑥

₃

= min

$'(')

𝑏

_𝑖

𝑦

_𝑖𝑘

: 𝑦𝑖𝑘 > 0 = min

$'(')

2

2

= 1 =

𝑏

₂

𝑦

_2𝑘

Nuova base: B = {2,3} N = {1,4}

Metodo Delle Due Fasi:

𝟐

°

fase

Test di Ottimalità: calcolo di z

_j

– c

_j

per j∈N = {1,4}

𝐴

_"

= 1 −1

2

0

𝑥

₂

𝑥

₃

=

𝐴

"#$

𝑏 =

0

⁄

$ +

−1

$

⁄

+

1

4

= 2

1

𝑧

₁

− 𝑐

₁

= −2 0

0

1

?

2

−1

1

?

₂

1

1

− −1 = −1 + 1 = 0

𝐴

#$_"

=

0

1

?

2

−1

1

?

₂

𝑧

₄

− 𝑐

₄

= −2 0

0

1

?

2

−1

1

?

₂

0

1

− 0 = −1

Soluzione ottima

Metodo Del Big-M

Ø Nella prima fase del metodo delle due fasi, la funzione obiettivo del problema originale è completamente ignorata.

Ø La prima fase ha, infatti, come obiettivo l’individuazione di una qualsiasi soluzione di base ammissibile del problema originale e quindi non necessariamente una buona soluzione di base ammissibile.

Ø Il Big-M è un metodo alternativo al metodo delle 2 fasi che tiene conto anche della funzione obiettivo originale durante la risoluzione del problema.

Metodo Del Big-M

Il problema di PL viene risolto modificando artificialmente il sistema dei vincoli esattamente come fatto per il due fasi aggiungendo le

variabili artificiali al sistema.

Ciò che cambia è la funzione obiettivo usata dal metodo del Big-M.

Alla funzione obiettivo di P vengono sommate (nel caso di un problema di minimo) le variabili artificiali moltiplicate per un coefficiente M ”molto grande”.

𝑃 𝑀

𝑚𝑖𝑛 𝑧 = 𝑐

𝑇

_{𝑥 + 𝑀𝑦}

A𝑥 + 𝐼𝑦 = 𝑏

𝑥 ≥ 0, 𝑦 ≥ 0

𝑃 𝑚𝑖𝑛 𝑧 = 𝑐

𝑇

_𝑥

A𝑥 = 𝑏

𝑥 ≥ 0

Metodo Del Big-M

Problema del Big-M

𝑃 𝑚𝑖𝑛 𝑧 = −𝑥₁ − 2𝑥₂ 𝑥₁ + 𝑥₂ ≥ 1 𝑥₁ + 2𝑥₂ ≤ 4 𝑥 ≥ 0 𝑚𝑖𝑛 𝑧 = −𝑥₁ − 2𝑥₂ 𝑥₁ + 𝑥₂ − 𝑥₃ = 1 𝑥₁ + 2𝑥₂ + 𝑥₄ = 4 𝑥 ≥ 0 𝑃 𝑀 𝑚𝑖𝑛 𝑧 = −𝑥₁ − 2𝑥₂ + 𝑀𝑥_"# 𝑥₁ + 𝑥₂ − 𝑥₃ + 𝑥_"# = 1 𝑥₁ + 2𝑥₂ + 𝑥₄ = 4 𝑥 ≥ 0, 𝑥_"# ≥ 0 Forma standard

Matrice Identità

(Base Iniziale)

B = {5,4}

N = {1,2,3}

𝑃 𝑀 𝑚𝑖𝑛 𝑧 = −𝑥₁ − 2𝑥₂ + 𝑀𝑥_"# 𝑥₁ + 𝑥₂ − 𝑥₃ + 𝑥_"# = 1 𝑥₁ + 2𝑥₂ + 𝑥₄ = 4 𝑥 ≥ 0, 𝑥_"# ≥ 0

Test di Ottimalità: calcolo di z

_j

– c

_j

per j∈N = {1,2,3}

𝐴

_"

= 1 0

0 1

𝑥

_%&

𝑥

₄

=

𝐴

#$"

𝑏 = 1 0

0 1

1

4

= 1

4

𝑧

₁

− 𝑐

₁

= 𝑀 0 𝐼 1

1

− −1 = 𝑀 + 1

𝑧

₂

− 𝑐

₂

= 𝑀 0 𝐼 1

2

− −2 = 𝑀 + 2

𝑧

₃

− 𝑐

₃

= 𝑀 0 𝐼 −1

0

− 0 = −𝑀

𝐴

_"#$

= 1 0

0 1

𝑚𝑖𝑛 𝑧 = −𝑥₁ − 2𝑥₂ + 𝑀𝑥_!" 𝑥₁ + 𝑥₂ − 𝑥₃ + 𝑥_!" = 1 𝑥₁ + 2𝑥₂ + 𝑥₄ = 4 𝑥 ≥ 0, 𝑥_!" ≥ 0 Entra in base x₂

x

₂

entra in base

Quale variabile esce dalla base?

Test dei minimi rapporti:

𝑥

_%&

esce dalla base; x

₂

entra in base con valore 1

𝑥

_%&

𝑥

₄

= 𝑏 = 1

4

𝑦

2

= 𝐴

" #$

_𝑎

2

= 𝐼 1

₂

= 1

₂

𝑥

₁

= min

$'(')

𝑏

_𝑖

𝑦

_𝑖𝑘

: 𝑦𝑖𝑘 > 0 = min

$'(')

1

1

,

4

2

= 1 =

𝑏

₁

𝑦

_1𝑘

Nuova base: B = {2,4} N = {1,3,5}

Test di Ottimalità: calcolo di z

_j

– c

_j

per j∈N = {1,3,5}

𝐴

_"

= 1 0

2 1

𝑥

₂

𝑥

₄

=

𝐴

"#$

𝑏 = 1

_{−2 1}

0

1

₄

= 1

₂

𝑧

₁

− 𝑐

₁

= −2 0

1

0

−2 1

1

1

− −1 = −1

𝐴

_"#$

= 1

0

−2 1

𝑧

₃

− 𝑐

₃

= −2 0

1

0

−2 1

−1

0

− 0 = 2

x3 entra in base 𝑚𝑖𝑛 𝑧 = −𝑥₁ − 2𝑥₂ + 𝑀𝑥_!" 𝑥₁ + 𝑥₂ − 𝑥₃ + 𝑥_!" = 1 𝑥₁ + 2𝑥₂ + 𝑥₄ = 4 𝑥 ≥ 0, 𝑥_!" ≥ 0

𝑧

₅

− 𝑐

₅

= −2 0

1

0

−2 1

1

0

− 𝑀 = −𝑀 − 2

x

₃

entra in base

Quale variabile esce dalla base?

Test dei minimi rapporti:

x

₄

esce dalla base; x

₃

entra in base con valore 1

𝑥

₂

𝑥

₄

= 1

₂

𝑦

3

= 𝐴

"#$

𝑎

3

= 1

−2 1

0

−1

0

= −1

2

𝑥

₃

= min

$'(')

𝑏

_𝑖

𝑦

_𝑖𝑘

: 𝑦𝑖𝑘 > 0 = min

$'(')

2

2

= 1 =

𝑏

₂

𝑦

_2𝑘

Nuova base: B = {2,3} N = {1,4,5}

Test di Ottimalità: calcolo di z

_j

– c

_j

per j∈N = {1,4,5}

𝐴

_"

= 1 −1

2

0

𝑥

₂

𝑥

₃

=

𝐴

"#$

𝑏 =

0

⁄

$ +

−1

$

⁄

+

1

4

= 2

1

𝑧₁ − 𝑐₁ = −2 0 0 < 1 2 −1 1<₂ 1 1 − −1 = −1 + 1 = 0

𝐴

_"#$

=

0

1

?

2

−1

1

?

₂

𝑧₄ − 𝑐₄ = −2 0 0 < 1 2 −1 1<₂ 0 1 − 0 = −1 Soluzione ottima 𝑧₅ − 𝑐₅ = −2 0 0 < 1 2 −1 1<₂ 1 0 − 𝑀 = −𝑀

Metodo Del Big-M

𝑚𝑖𝑛 𝑧 = −𝑥₁ − 2𝑥₂ + 𝑀𝑥_!" 𝑥₁ + 𝑥₂ − 𝑥₃ + 𝑥_!" = 1

𝑥₁ + 2𝑥₂ + 𝑥₄ = 4 𝑥 ≥ 0, 𝑥_!" ≥ 0

Metodo Del Big-M: valore per M

Ø Quanto deve essere grande il valore della M affinchè il metodo del

Big-M lavori correttamente?

Il valore della M deve essere abbastanza grande da garantire che il valore della funzione obiettivo 𝑐𝑇_{𝑥, in una qualsiasi soluzione di base}

ammissibile del problema P, sia sempre minore del valore della funzione obiettivo del Big-M in una qualsiasi soluzione di base ammissibile del problema P(M) avente almeno una variabile artificiale maggiore di zero.

Perché il valore della M è sempre finito anche se la regione ammissibile di P è aperta?

Metodo Del Big-M: possibili soluzioni

Risoluzione del problema

P(M)

Ottimo finito Ottimo illimitato 𝑥𝑎 _{= 0} Soluzione ottima per P 𝑥𝑎 _{≠ 0} P è inammissibile 𝑥𝑎 _{= 0} Ottimo illimitato per P 𝑥𝑎 _{≠ 0} P è inammissibile

Metodo Del Big-M: difetti

1. Non è facile calcolare il valore della M;

2. L’utilizzo di un valore molto grande, nella computazione dell’algoritmo, può rendere più complessi i calcoli da effettuare;

3. Se il valore di M è troppo grande, si possono verificare errori di rounding-off, durante la computazione, che possono alterare la corretta selezione delle variabili che devono entrare in base.

Esercizi

Risolvere i seguenti problemi di PL utilizzando sia il metodo delle due fasi sia il metodo del Big-M.

𝑚𝑖𝑛 𝑧 = −4𝑥₁ − 𝑥₂ 2𝑥₁ + 𝑥₂ ≥ 4 𝑥₁ + 2𝑥₂ ≥ 4 𝑥 ≥ 0 𝑚𝑖𝑛 𝑧 = −4𝑥₁ − 𝑥₂ 2𝑥₁ + 𝑥₂ ≤ 1 𝑥₁ + 2𝑥₂ ≥ 4 𝑥 ≥ 0