Lezionidi RicercaOperativa Lezionen 12 °

Lezione n

°

12

Algoritmo del Simplesso: - Metodo delle 2 Fasi

- Esempio

R. Cerulli

–

Lezioni di Ricerca Operativa

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𝑥 = 𝑏

𝑥 ≥ 0

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

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)

B = {5,4}

N = {1,2,3}

Metodo Delle Due Fasi:

𝟏

°

fase

Test di Ottimalità: calcolo di z

– c

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

𝐴

= 1 0

0 1

𝑥

= 𝐴

𝑏 ⟹ 𝑥

= 𝐼𝑏 ⟹ 𝑥

= 𝑏

𝑥

𝑥

=

𝐴

𝑏 = 1 0

0 1

4

1

= 1

4

𝑥

= 1,

𝑥

= 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

𝑦

= 𝐴

_𝑎

= 𝐼 1

₂

= 1

₂

𝑥

= min

𝑏

𝑦

: 𝑦𝑖𝑘 > 0 = min

1

1

,

4

2

= 1 =

𝑏

𝑦

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

Metodo Delle Due Fasi:

𝟏

°

fase

Test di Ottimalità: calcolo di z

– c

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

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}

Metodo Delle Due Fasi:

𝟐

°

fase

Test di Ottimalità: calcolo di z

– c

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

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

₂

𝑦

= 𝐴

𝑎

= 1

−2 1

0

−1

0

= −1

2

𝑥

= min

𝑏

𝑦

: 𝑦𝑖𝑘 > 0 = min

2

2

= 1 =

𝑏

𝑦

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

Metodo Delle Due Fasi:

𝟐

°

fase

Test di Ottimalità: calcolo di z

– c

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

Metodo Del Big M

Si modifica artificialmente

il sistema dei vincoli:

0

,

0

0

min

³

³

®

³

=

+

®

=

y

x

x

b

y

I

x

A

b

x

A

x

c

con l’aggiunta di una variabile artificiale

y

ad ogni

vincolo del sistema. Nel nuovo sistema è presente una

matrice identità (associata alle variabili y).

Alla funzione obiettivo originale vengono

sommate

(nel

caso di un problema di minimo) le variabili artificiali

moltiplicate per un coefficiente M molto grande.

y

M

x

c

1