Che materia stai cercando?

Programmazione lineare

In questo materiale didattico vengono trattati i seguenti argomenti. Programmazione lineare: ottimizzazione, funzioni obiettivo, funzioni vincolari, problemi in forma canonica, problemi in forma standard. Teoria della PL: insiemi convessi, involucro convesso; insiemi conici, involucro conico; iperpiani e vettori direzione; poliedro, direzione di recessione,... Vedi di più

Esame di Ricerca Operativa docente Prof. M. Castellani

Anteprima

ESTRATTO DOCUMENTO

L’algoritmo del simplesso

Soluzioni di base ammissibili

Cosa rappresentano gli indici dell’insieme N?

(12,

Esempio 3 (continua). Avevamo 2, 24, 0, 0) soluzione di base.

La soluzione di base corrisponde

6 = (12,

al vertice C 2)

Gli indici non in base corrispondono

D e x

alle variabili x 5

4

s

@

@ Il vertice C giace sulle rette

@ = =

associate a x 0 e x 0

@ 5

4

H

j

H

x

@

3 x Qual è la base associata a B?

5

@

S

@ {1,

La base è 3, 5} mentre

C

@

E

x AK {1,

x quella di C era 2, 3}

s s

2

- A

4

x 6

1 B -

A quindi. . . dsm

s s

Marco Castellani (L’Aquila) Ricerca Operativa La programmazione lineare 59 / 122

L’algoritmo del simplesso

Soluzioni di base ammissibili

. . . quindi, ricapitolando

gli indici dell’insieme N individuano gli iperpiani che realizzano il

vertice;

se due vertici sono adiacenti allora le relative basi sono

ammissibili e differiscono di un solo indice . . .

. . . tuttavia vedremo che il viceversa è falso: due basi ammissibili

che differiscono di un solo indice non identificano

necessariamente due vertici adiacenti ma potrebbero indicare lo

stesso vertice! Tali vertici saranno quelli degeneri. dsm

Marco Castellani (L’Aquila) Ricerca Operativa La programmazione lineare 60 / 122

L’algoritmo del simplesso

Criterio per l’ottimalità

Sappiamo che il massimo, se esiste, si trova in un vertice.

Il passo successivo è quello di individuare una condizione sufficiente

per dedurre quando un vertice è punto di massimo.

Abbiamo visto che data una base B possiamo esplicitare le variabili x B

in funzione delle variabili x .

N ⇓

Decomponiamo anche il vettore c in due sottovettori

il primo formato dalle m incognite di indice in B e che indichiamo

;

c B −

il secondo formato dalle n m incognite di indice in N e che

indichiamo c .

N

Il problema di PL si riscrive nella seguente maniera dsm

Marco Castellani (L’Aquila) Ricerca Operativa La programmazione lineare 61 / 122

L’algoritmo del simplesso

Criterio per l’ottimalità ⊺ ⊺

 +

x c x

max c B N

B N

 + =

A x A x b

B B N N

 ≥

,

x x 0

 B N

Esplicitando la x si ottiene

B ⊺ ⊺

 +

x c x

max c B N

B N

 −1 −1

=

x A b A A x

B N N

B B

 ≥

,

 x x 0

B N dsm

Marco Castellani (L’Aquila) Ricerca Operativa La programmazione lineare 62 / 122

L’algoritmo del simplesso

Criterio per l’ottimalità

Sostituendo x nella funzione obiettivo e raccogliendo x ricaviamo

B N

⊺ ⊺ ⊺

−1 −1

 −

+ (c )x

max c A b c A A N N

B B

B N B

 −1 −1

− ≥

A b A A x 0

N N

B B

 ≥

 x 0

N

Abbiamo diminuito il numero di variabili.

Definizione

Il vettore ⊺ ⊺

⊺ −1

=

c c c A A N

N B B

prende il nome di gradiente ridotto relativo alla base B. dsm

Marco Castellani (L’Aquila) Ricerca Operativa La programmazione lineare 63 / 122

L’algoritmo del simplesso

Criterio per l’ottimalità

Quindi la funzione obiettivo diventa

⊺ ⊺

−1

(x ) = +

f c A b c x

B N N

B B N

e le x devono avere tutte le componenti 0. Quindi. . .

N

Teorema (Condizione sufficiente per l’ottimalità) ≤

(c

Se il gradiente ridotto c ha tutte le componenti non positive 0)

N N

−1

(A

allora la soluzione di base ammissibile b, 0) associata alla base B

B

risulta essere il punto di massimo del problema di PL ed il massimo è

⊺ −1

A b.

c B B ≤

La condizione c 0 è anche necessaria? Dal punto di vista algebrico

N

SI ma dal punto di vista geometrico NI. Lo vedremo in seguito. dsm

Marco Castellani (L’Aquila) Ricerca Operativa La programmazione lineare 64 / 122

L’algoritmo del simplesso

Criterio per l’ottimalità

Esempio 4 (semplicissimo). Risolviamo il seguente problema

 +

max 3x 2x

1 2

 + =

2x x 4

1 2

,

x x 0

 1 2 {1}

=

Con base B mettiamo in evidenza x

1

6

(0, 4) 12

=

x 2 x

s

A 1 2

A Sostituendo nella funzione obiettivo si ha

A 12

(x ) = +

f 6 x

A 1 2 2

A {2}

=

Con base B mettiamo in evidenza x

2

A −

=

x 4 2x

A 2 1

(2, 0) -

A Sostituendo nella funzione obiettivo si ha

s −

(x ) =

f 8 x

2 1 1

{2}

=

La base ottima è B dsm

Marco Castellani (L’Aquila) Ricerca Operativa La programmazione lineare 65 / 122

L’algoritmo del simplesso

Il metodo

Per risolvere un problema di PL dobbiamo quindi determinare un

vertice (cioè una base ammissibile) per cui il gradiente ridotto della

funzione in quel punto abbia tutte le componenti non positive.

Il metodo del simplesso ha il seguente schema algoritmico:

Passo 0 Si determina una base iniziale e la relativa soluzione di

base associata (vertice del poliedro).

Passo 1 Si calcola il gradiente ridotto.

Passo 2 Se è verificata la condizione di ottimalità STOP.

Passo 3 Se non è verificata la condizione di ottimalità si determina

una opportuna nuova base e si ritorna al Passo 1. dsm

Marco Castellani (L’Aquila) Ricerca Operativa La programmazione lineare 66 / 122

L’algoritmo del simplesso

Il metodo

Determinare una nuova base significa, geometricamente, determinare

k , l’algoritmo del simplesso

un nuovo vertice: noto un vertice x

k +1

determina un vertice x adiacente al precedente. In realtà, per

quanto visto in precedenza, determiniamo una nuova base che

differisce da quella precedente di un solo elemento. Se ci va bene,

questa nuova base corrisponde ad un nuovo vertice!

Domanda: come determiniamo la nuova base?

Risposta: muovendoci lungo un segmento (spigolo) rispetto a cui la

funzione cresce, cioè spostandoci in un vertice in cui la funzione

obiettivo assume valore maggiore.

Se abbiamo l’imbarazzo della scelta, per ora, si sceglie quel segmento

in cui la funzione cresce maggiormente a parità di spostamento

(maggiore velocità di crescita). dsm

Marco Castellani (L’Aquila) Ricerca Operativa La programmazione lineare 67 / 122

L’algoritmo del simplesso

Il metodo geometrico

Esempio 3 (continua). Consideriamo il seguente problema di PL

 +

max 3x x

1 2

 −2x + + =

x x 2

 1 2 3

 − + =

x 2x x 8

1 2 4

+ + =

x x x 14

 5

1 2

 ≥

, , , ,

x x x x x 0

 5

1 2 3 4

La regione ammissibile è quella studiata precedentemente e la

rappresentiamo nelle variabili x e x .

1 2

= (0, = (8, = (12,

I vertici del poliedro sono A 0), B 0), C 2),

= (4, = (0,

D 10) e E 2).

Il vertice ottimo è C. dsm

Marco Castellani (L’Aquila) Ricerca Operativa La programmazione lineare 68 / 122

L’algoritmo del simplesso

Il metodo geometrico ◦ (A) =

Supponiamo di essere in A e f 0

6 ◦ {3,

Il vertice A corrisponde alla base 4, 5}

◦ Aumento sia verso B sia verso E

B

D ◦ La crescita è superiore verso B

s B

@ ◦ {1,

Vado in B con base 3, 5}

B B

@ B

B B B

@ ◦ Il punto B non è di massimo

B B B

@

H

j

H ◦

x Aumento solo verso C

B B

@ B

3 x

5

B B

@ B

S ◦ {1,

Vado in C con base 2, 3}

B B @ B

1 ◦

C La condizione di ottimalità

B B B

@

E

x AK

x

s s

x 2

B B

- A B

4 è verificata

1

1 6

1

B

B B -

B

A ◦ C è punto di massimo

s s

B B B

B B ◦ STOP

B B dsm

Marco Castellani (L’Aquila) Ricerca Operativa La programmazione lineare 69 / 122

L’algoritmo del simplesso

Il metodo geometrico

Riepiloghiamo i passaggi dell’algoritmo. {3,

Siamo partiti dal vertice A. Gli indici in base sono 4, 5} e quelli

{1,

non in base 2}. Il vertice non è soluzione. =

Ci siamo mossi lungo lo spigolo AB individuato da x 0.

2

Aumenta x (si dice che 1 entra in base) fino a quando non

1

diventa nulla x (si dice che 4 esce di base).

4 {1,

Siamo giunti nel vertice B. La nuova base è 3, 5} mentre gli

{2,

indici non in base sono 4}. Il vertice non è soluzione.

=

Ci siamo mossi lungo BC individuato da x 0. Aumenta x (2

4 2

(5 esce di base).

entra in base) ed alla fine diventa nulla x

5 {1,

Siamo giunti nel vertice C. La nuova base è 2, 3} mentre gli

{4,

indici non in base sono 5}. Il vertice è soluzione.

STOP dsm

Marco Castellani (L’Aquila) Ricerca Operativa La programmazione lineare 70 / 122

L’algoritmo del simplesso

Il metodo algebrico (informale)

A questo punto non resta che la formalizzazione algebrica.

Dall’esempio precedente introduciamo la cosiddetta tabella del

simplesso 3 1 0 0 0

−2 1 1 0 0 2

−2

1 0 1 0 8

1 1 0 0 1 14

Dobbiamo ricercare una base ammissibile cioè una sottomatrice di A

di dimensione 3 non singolare. La sottomatrice formata dalle ultime tre

colonne (quelle relative alle variabili x , x e x ) è la matrice identità ed

5

3 4

ha (ovviamente) il determinante non nullo. dsm

Marco Castellani (L’Aquila) Ricerca Operativa La programmazione lineare 71 / 122

L’algoritmo del simplesso

Il metodo algebrico (informale)

3 1 0 0 0 {3,

=

B 4, 5}

1

−2 1 1 0 0 2

−2

1 0 1 0 8 1 = (0,

x 0, 2, 8, 14)

1 1 0 0 1 14

Per calcolare il gradiente ridotto si devono mettere in evidenza x , x e

3 4

in funzione di x e x

x

5 1 2  −

= +

x 2 2x x

3 1 2

 −

= +

x 8 x 2x

4 1 2

− −

=

x 14 x x

 5 1 2

e sostituirli nella funzione obiettivo che in questo caso non cambia.

= (3,

Quindi c 1) e non è verificata la condizione di ottimalità.

N 1 dsm

Marco Castellani (L’Aquila) Ricerca Operativa La programmazione lineare 72 / 122

L’algoritmo del simplesso

Il metodo algebrico (informale)

Le componenti positive del gradiente ridotto indicano le direzioni di

crescita della funzione obiettivo.

Il valore della nostra funzione obiettivo aumenta incrementando sia x

1

sia x : avendo deciso di muoverci lungo la direzione di massima

2 >

crescita incrementiamo x (infatti 3 1)

1

Abbiamo deciso che x entra in base ma dobbiamo vedere chi esce.

1

Dovendo rimanere nella regione ammissibile, tutte le variabili devono

=

continuare ad essere non negative con x 0. Dal sistema si ricava

2

 ≥

= +

x 2 2x 0

3 1

 − ≥

=

x 8 x 0

 4 1

− ≥

= 14 x 0

x

5 1

 ≥

x 0

 1 dsm

Marco Castellani (L’Aquila) Ricerca Operativa La programmazione lineare 73 / 122

L’algoritmo del simplesso

Il metodo algebrico (informale)

Risolviamo il sistema di disequazioni rispetto a x (che rappresenta la

1

variabile che stiamo aumentando)

 ≥ −1

x disequazione relativa a x

1 3

 ≤

x 8 disequazione relativa a x

 1 4

x 14 disequazione relativa a x

5

1

 ≥

x 0

 1 ∈ [0, 8]; quindi. . .

la cui soluzione è x

1

. . . possiamo aumentare x fino ad assumere il valore 8 e tutte le altre

1 =

variabili restano non negative. Inoltre, quando x 8, si annulla la

1

variabile x che quindi esce di base.

4

Siamo quindi arrivati nel nuovo vertice individuato dalla base

2

{1,

= = (8,

B 3, 5} e le cui coordinate sono x 0, 18, 0, 6).

2 dsm

Marco Castellani (L’Aquila) Ricerca Operativa La programmazione lineare 74 / 122

L’algoritmo del simplesso

Il metodo algebrico (informale)

Vediamo come si risolvono questi passaggi utilizzando la tabella

simpliciale. (c =

Individuiamo il coefficiente del gradiente ridotto massimo 3)

1

Analizziamo la relativa colonna dei coefficienti (la prima)

3 1 0 0 0

−2 1 1 0 0 2

−2

1 0 1 0 8

1 1 0 0 1 14

Prendiamo in esame i coefficienti a 0 e consideriamo i rapporti

i1

tra i termini noti e tali coefficienti

b 8 b 14

2 3

= = = =

8 e 14.

a 1 a 1

21 31 dsm

Marco Castellani (L’Aquila) Ricerca Operativa La programmazione lineare 75 / 122

L’algoritmo del simplesso

Il metodo algebrico (informale)

Scegliamo la riga relativa al rapporto minore (la seconda) 2

La variabile uscente dalla base sarà quella relativa alla colonna e

della matrice identità.

−1

Dobbiamo calcolare A ed il gradiente ridotto. Svolgiamo i calcoli

B

2

utilizzando il metodo di Gauss–Jordan utilizzando a come pivot:

21

3 1 0 0 0

−2 1 1 0 0 2

−2

1 0 1 0 8

1 1 0 0 1 14 −2

= = =

Annulliamo il coefficiente c 1 ed i coefficienti a e a 1 in

1 11 31

2

maniera da ottenere la colonna e . dsm

Marco Castellani (L’Aquila) Ricerca Operativa La programmazione lineare 76 / 122

L’algoritmo del simplesso

Il metodo algebrico (informale)

Otteniamo la seguente tabella simpliciale

−3

0 7 0 0 {1,

=

B 3, 5}

2

−3

0 1 2 0 18

−2

1 0 1 0 8 2 = (8, 0, 18, 0, 6)

x

−1

0 3 0 1 6

Siamo arrivati alla soluzione precedente e, purtroppo, non è verificata

la condizione sufficiente (il gradiente ridotto non ha tutte le componenti

non positive)!

Ripetiamo il ragionamento: la condizione di ottimalità non è verificata e

dal gradiente ridotto si deduce che la variabile entrante è x .

2 dsm

Marco Castellani (L’Aquila) Ricerca Operativa La programmazione lineare 77 / 122

L’algoritmo del simplesso

Il metodo algebrico (informale) −3

0 7 0 0

−3

0 1 2 0 18

−2

1 0 1 0 8

−1

0 3 0 1 6

L’unico coefficiente non negativo nella seconda colonna è a , quindi la

32

variabile uscente è x . Scelto a pivot, otteniamo la nuova tabella

5 32

−2/3 −7/3

0 0 0 {1,

=

B 2, 3}

3

0 0 1 1 1 24

1 0 0 1/3 2/3 12 3 = (12,

x 2, 24, 0, 0)

−1/3

0 1 0 1/3 2

Siamo arrivati alla soluzione ottima! dsm

Marco Castellani (L’Aquila) Ricerca Operativa La programmazione lineare 78 / 122

L’algoritmo del simplesso

Il metodo algebrico (informale)

Esercizio

Risolvere il seguente problema di PL

 +

max x 2x

1 2

 ≤

+

x 3x 13

 1 2

 −x ≤

+ x 3

1 2

x 4

 1

 ≥

,

x x 0

 1 2

Per ottenere il problema in forma standard dobbiamo aggiungere tre

variabili di scarto ottenendo

 +

max x 2x

1 2

 + + =

x 3x x 13

 1 2 3

 −x + + =

x x 3

1 2 4

+ =

x x 4

 5

1

 dsm

, , , ,

x x x x x 0

 5

1 2 3 4

Marco Castellani (L’Aquila) Ricerca Operativa La programmazione lineare 79 / 122

L’algoritmo del simplesso

Il metodo algebrico (informale)

Partiamo! 1 2 0 0 0 {3,

=

B 4, 5}

1

1 3 1 0 0 13

−1 1 0 1 0 3 1 = (0,

x 0, 13, 3, 4)

1 0 0 0 1 4 13 3

>

Entra in base x ed esce x poiché . Facciamo pivot

2 4 3 1

=

sull’elemento a 1 ed otteniamo

22 −2

3 0 0 0 {2,

=

B 3, 5}

2

−3

4 0 1 0 4

−1 1 0 1 0 3 2 = (0,

x 3, 4, 0, 4)

1 0 0 0 1 4 4 41

<

ed esce x poiché .

Entra in base x dsm

1 3 4

Marco Castellani (L’Aquila) Ricerca Operativa La programmazione lineare 80 / 122

L’algoritmo del simplesso

Il metodo algebrico (informale) =

Facciamo pivot sull’elemento a 4 ed otteniamo

11

−3/4

0 0 1/4 0 {1,

=

B 2, 5}

3

−3/4

1 0 1/4 0 1

0 1 1/4 1/4 0 4 3 = (1, 4, 0, 0, 3)

x

−1/4

0 0 3/4 1 3

4 3

>

Entra in base x ed esce x poiché . Facciamo pivot

5

4 1/4 3/4

3

=

sull’elemento a ed otteniamo

34 4

−2/3 −1/3

0 0 0 {1,

=

B 2, 4}

4

1 0 0 0 1 4

−1/3

0 1 1/3 0 3 4 = (4,

x 3, 0, 4, 0)

−1/3

0 0 1 4/3 4

4

La soluzione x è ottima in quanto il gradiente ridotto ha tutte le dsm

componenti negative.

Marco Castellani (L’Aquila) Ricerca Operativa La programmazione lineare 81 / 122

L’algoritmo del simplesso

Il metodo algebrico (informale)

6

HH

H D

P

H

P

s P

H PP

H PPPP ◦ {3,

A con base 4, 5}

x

@

R H

3

C

P

x

H

H

P

E 4

HH HH

s s

HH ◦ {2,

E con base 3, 5}

◦ {1,

D con base 2, 5}

- x x

1

5 ◦ {1,

C con base 2, 4}

x

2

6

H -

H

s s

A B dsm

Marco Castellani (L’Aquila) Ricerca Operativa La programmazione lineare 82 / 122

L’algoritmo del simplesso

Casi particolari

Durante lo svolgimento dell’algoritmo del simplesso si possono

presentare alcuni casi particolari che andremo a discutere.

La soluzione ottima non è unica.

La soluzione ottima non esiste perché la funzione obiettivo è

superiormente illimitata.

Abbiamo raggiunto il vertice ottimo ma la condizione sufficiente di

ottimalità non funziona (vertice ottimo degenere).

L’algoritmo del simplesso si pianta su un vertice e non riesce a

determinare un vertice adiacente (regola dell’anticiclo di Bland).

La soluzione ottima non esiste perché la regione ammissibile è

vuota (utilizzo del problema ausiliario). dsm

Marco Castellani (L’Aquila) Ricerca Operativa La programmazione lineare 83 / 122

L’algoritmo del simplesso

Infinite soluzioni ottime

Esempio 5. Consideriamo il seguente problema

 + x

max x

1 2

 −x ≤

+ x 2

 1 2

 ≤

+

x x 8

1 2

≤ 5

x

 1

 ≥

,

x x 0

 1 2

la cui tabella del simplesso associata risulta

1 1 0 0 0 {3,

=

B 4, 5}

1

−1 1 1 0 0 2

1 1 0 1 0 8 1 = (0,

x 0, 2, 8, 5)

1 0 0 0 1 5 dsm

Marco Castellani (L’Aquila) Ricerca Operativa La programmazione lineare 84 / 122

L’algoritmo del simplesso

Infinite soluzioni ottime

La rappresentazione del problema è la seguente.

@ D

s

6 @

@ @ = (0,

A 0)

@

@

@ @

x @

@ 4 = (5,

B 0)

x

@

R 3 C

@ @

s

@ @

S

@ @ = (5,

C 3)

@

E s @

@ = (3,

D 5)

x

-

@ 5

x

1

@ @

x

2

@ @ = (0,

E 2)

6 -

@ @ B

s s

@ @

A

La soluzione ottima è lo spigolo CD dsm

Marco Castellani (L’Aquila) Ricerca Operativa La programmazione lineare 85 / 122

L’algoritmo del simplesso

Infinite soluzioni ottime

Entra in base x ed esce x ottenendo

5

1 −1

0 1 0 0 {1,

=

B 3, 4}

2

0 1 1 0 1 7

−1

0 1 0 1 3 2 = (5,

x 0, 7, 3, 0)

1 0 0 0 1 5

Entra in base x ed esce x ottenendo

2 4

−1

0 0 0 0 {1,

=

B 2, 3}

3

−1

0 0 1 2 4

−1

0 1 0 1 3 3 = (5,

x 3, 4, 0, 0)

1 0 0 0 1 5

= (−1,

c 0) 0 e quindi la soluzione è ottima,

Il gradiente ridotto N 3

tuttavia. . . dsm

Marco Castellani (L’Aquila) Ricerca Operativa La programmazione lineare 86 / 122

L’algoritmo del simplesso

Infinite soluzioni ottime

. . . il costo ridotto nullo associato alla variabile x indica la presenza di

5 ?

eventuali altre soluzioni ottime. Cosa succede se entra in base x

5

−1

0 0 0 0 {1,

=

B 2, 5}

4

−1/2

0 0 1/2 1 2

0 1 1/2 1/2 0 5 4 = (3,

x 5, 0, 0, 2)

−1/2

1 0 1/2 0 3

Abbiamo ottenuto una nuova soluzione ammissibile ottima diversa

dalla precedente! Quindi tutti i punti che si trovano sul segmento che li

congiunge sono a loro volta soluzioni ottime

3 4

− − − − ∈

= + (1 = (3 [0,

x tx t)x 2t, 5 5t, 4t, 0, 2 2t), t 1] dsm

Marco Castellani (L’Aquila) Ricerca Operativa La programmazione lineare 87 / 122

L’algoritmo del simplesso

Funzione obiettivo superiormente illimitata

Esempio 2 (continua). Riprendiamo il problema introdotto all’inizio

della PL  +

max x x

1 2

 −x ≤

+ x 1

 1 2

− ≤

x 2x 1

1 2

 ≥

,

x x 0

 1 2

la cui tabella del simplesso associata risulta {3,

=

1 1 0 0 B 4}

1

−1 1 1 0 1 1

−2 = (0,

x

1 0 1 1 0, 1, 1) dsm

Marco Castellani (L’Aquila) Ricerca Operativa La programmazione lineare 88 / 122

L’algoritmo del simplesso

Funzione obiettivo superiormente illimitata

La rappresentazione del problema è la seguente.

6 = (0,

A 0)

= (1,

B 0)

@ @

R = (0,

C 1)

x

3

@

@ S

@ x

K

A 4

@ A

@

C

s @

x

-

1

@

x

2

@ 6 @ -

A s s

@ @

B

Il problema è superiormente illimitato. dsm

Marco Castellani (L’Aquila) Ricerca Operativa La programmazione lineare 89 / 122

L’algoritmo del simplesso

Funzione obiettivo superiormente illimitata

Entra in base x ed esce x ottenendo

1 4

−1 {1,

0 3 0 =

B 3}

2

−1

0 1 1 2 2

−2 = (1,

1 0 1 1 x 0, 2, 0)

2

La soluzione di base x non è ottima: dovrebbe entrare in base x ma

2

non siamo in grado di individuare quale variabile esce di base in

quanto tutti i coefficienti della colonna relativa alla variabile x sono

2

negativi! In altre parole non ci sono elementi nella colonna di x

2

candidati a diventare pivot. dsm

Marco Castellani (L’Aquila) Ricerca Operativa La programmazione lineare 90 / 122

L’algoritmo del simplesso

Funzione obiettivo superiormente illimitata

Poiché x continua a rimanere fuori base il suo valore sarà 0 ed i due

4

vincoli diventano = + = +

x 2 x e x 1 2x

3 2 1 2

Come si vede, se x aumenta allora aumentano sia x (primo vincolo),

2 3

sia x (secondo vincolo).

1 arbitrariamente grande rimanendo nella

Quindi possiamo scegliere x

2

regione ammissibile e perciò la funzione obiettivo risulta

superiormente illimitata.

Se la colonna della matrice dei coefficienti relativa alla variabile

entrante è formata da elementi tutti non positivi allora il problema

superiormente illimitato. dsm

Marco Castellani (L’Aquila) Ricerca Operativa La programmazione lineare 91 / 122

L’algoritmo del simplesso

Soluzione ottima degenere

Domanda: come si individua un vertice degenere? Ed i vertici

degeneri portano guai?

Purtroppo la risposta alla seconda domanda è affermativa ma non ci

dobbiamo allarmare: tali guai sono stati risolti!

Procediamo per gradi. Iniziamo ricordando che un vertice si dice

degenere se risulta intersezione di un numero di iperpiani superiore

alla dimensione dello spazio in cui è immerso il poliedro e quindi, per

poterlo individuare utilizzando la rappresentazione standard . . .

. . . corrisponderà ad una soluzione di base ammissibile con alcune

delle variabili in base nulle!

Passiamo ad analizzare il comportamento dell’algoritmo del simplesso

in presenza di vertici degeneri. dsm

Marco Castellani (L’Aquila) Ricerca Operativa La programmazione lineare 92 / 122

L’algoritmo del simplesso

Soluzione ottima degenere

Utilizziamo l’algoritmo con le seguenti regole di scelta:

per determinare la variabile entrante prendiamo quella relativa alla

direzione di massima crescita e, in caso di ugual tasso di crescita,

scegliamo quella con indice minore;

per determinare la variabile uscente, in caso di uguali rapporti,

scegliamo quella di indice minore.

Esempio 1 (continua). Applichiamo tale regola al problema

 +

max 2x x

1 2

 −x ≤

+ 2x 6

 1 2

 ≤

+ x 6

x

 1 2

− ≤

x x 4

1 2

 ≤

x 4

 1

 ≥

, x 0

x

 dsm

1 2

Marco Castellani (L’Aquila) Ricerca Operativa La programmazione lineare 93 / 122

L’algoritmo del simplesso

Soluzione ottima degenere

Iniziamo a risolvere il problema geometricamente

6 D ◦ {3,

Si parte da A con base 4, 5, 6}

s

@

@

AAU

◦ → {1,

A B con base 3, 4, 6}

A

@

E x

3

s x @ A ◦ → {1,

B B con base 2, 3, 4}

4 @

A ◦ → {1,

C B C con base 2, 3, 5}

*

@

A

s

A

x

-

1 A

x

6

A A

x x

6

* *

5

2 B

I

@

A A

-

A s s

A A

A A dsm

Marco Castellani (L’Aquila) Ricerca Operativa La programmazione lineare 94 / 122

L’algoritmo del simplesso

Soluzione ottima degenere

Vediamo cosa succede dal punto di vista algebrico. La tabella iniziale è

2 1 0 0 0 0 {3,

−1 =

B 4, 5, 6}

2 1 0 0 0 6 1

1 1 0 1 0 0 6 1

−1 = (0,

1 0 0 1 0 4 0, 6, 6, 4, 4)

x

1 0 0 0 0 1 4

Entra in base x ed esce x ottenendo

5

1 −2

0 3 0 0 0 {1,

=

B 3, 4, 6}

0 1 1 0 1 0 10 2

−1

0 2 0 1 0 2 2

−1 = (4,

x

1 0 0 1 0 4 0, 10, 2, 0, 0) degenere

−1

0 1 0 0 1 0 dsm

Marco Castellani (L’Aquila) Ricerca Operativa La programmazione lineare 95 / 122

L’algoritmo del simplesso

Soluzione ottima degenere

Entra in base x ed esce x ottenendo

2 6

−3

0 0 0 0 1 {1,

−1 =

B 2, 3, 4}

0 0 1 0 2 10 3

−2

0 0 0 1 1 2 3 = (4,

1 0 0 0 0 1 4 x 0, 10, 2, 0, 0) degenere

−1

0 1 0 0 1 0

Entra in base x ed esce x ottenendo

5 4

−1 −1

0 0 0 0

−2 {1,

=

0 0 1 0 3 6 B 2, 3, 5}

4

−2

0 0 0 1 1 2 4 = (4,

1 0 0 0 0 1 4 x 2, 6, 0, 2, 0) ottima!

−1

0 1 0 1 0 2 dsm

Marco Castellani (L’Aquila) Ricerca Operativa La programmazione lineare 96 / 122

L’algoritmo del simplesso

Soluzione ottima degenere

Domanda: cosa succede se il vertice ottimo è degenere?

Risposta: potrebbe accadere di giungere in quel vertice ma che la

condizione sufficiente di ottimalità non sia verificata. In tal caso si

prosegue l’algoritmo cambiando le basi ma rimanendo in quel vertice

fin quando non si ottiene la condizione di ottimalità.

Esempio 6. Consideriamo il seguente problema di PL in forma

canonica  +

max x x

1 2

 ≤

x 2

 1

 ≤

+

2x x 6

1 2

x 2

 2

 ≥

,

x x 0

 1 2 dsm

Marco Castellani (L’Aquila) Ricerca Operativa La programmazione lineare 97 / 122

L’algoritmo del simplesso

Soluzione ottima degenere

1 1 0 0 0 {3,

=

B 4, 5}

1

1 0 1 0 0 2

2 1 0 1 0 6 1 = (0, 0, 2, 6, 2)

x

0 1 0 0 1 2

Entra in base x ed esce x ottenendo

1 3

−1

0 1 0 0 {1,

=

B 4, 5}

2

1 0 1 0 0 2

−2

0 1 1 0 2 2 = (2, 0, 0, 2, 2)

x

0 1 0 0 1 2

Entra in base x ed esce x ottenendo

2 4

−1

0 0 1 0 {1,

=

B 2, 5}

3

1 0 1 0 0 2

−2

0 1 1 0 2 3 = (2,

x 2, 0, 0, 0)

−1 dsm

0 0 2 1 0

Marco Castellani (L’Aquila) Ricerca Operativa La programmazione lineare 98 / 122

L’algoritmo del simplesso

Soluzione ottima degenere 3

La soluzione di base x è degenere e non è ottima; tuttavia, facendo

entrare in base x ed uscire x si ottiene la seguente tabella ottima

3 4

−1/2 −1/2

0 0 0 {1,

=

B 2, 3}

4

−1/2

1 0 0 1/2 2

0 1 0 0 1 2 4 = (2, 2, 0, 0, 0)

x

−1/2

0 0 1 1/2 0

6 A

@

A

@

{1, {1,

Base 2, 5} Base 2, 3}

s s

A

x ? @

5 x A

4

@

A @

x

- @

A @

4 s s

@ A

@

x x x ?

5

1 3 A

x 6

2 x x

- 3 4 dsm

s s

Marco Castellani (L’Aquila) Ricerca Operativa La programmazione lineare 99 / 122

L’algoritmo del simplesso

Regola dell’anticiclo di Bland

Consideriamo il seguente problema di PL in forma standard pubblicato

da E.M.L. Beale in Naval Res. Logistic Quart., 2 nel 1955.

34 1

 − −

+

max x 150x x 6x

1 2 3 4

50

 1 1

 − − + + =

x 60x x 9x x 0

 5

1 2 3 4

 4 25

 1 1

− − + + =

x 90x x 3x x 0

1 2 3 4 6

2 50

+ =

x 1

x

 7

3

 ≥

 , , , , , ,

x x x x x x x 0

5 7

1 2 3 4 6

che produce la seguente tabella simpliciale

−150 −6

3/4 1/50 0 0 0

−60 −1/25

1/4 9 1 0 0 0

−90 −1/50

1/2 3 0 1 0 0

0 0 1 0 0 0 1 1 dsm

Marco Castellani (L’Aquila) Ricerca Operativa La programmazione lineare 100 / 122

L’algoritmo del simplesso

Regola dell’anticiclo di Bland

{5,

=

La base B 6, 7} e la soluzione di base ammissibile è

0

= (0,

x 0, 0, 0, 0, 0, 1) (degenere). Per l’individuazione di soluzioni di

basi adiacenti utilizziamo la regola di massima salita.

Per la variabile entrante in base si sceglie quella la cui

componente del gradiente ridotto risulta maggiore ed in caso di

più componenti con lo stesso tasso di salita si sceglie quella di

indice inferiore.

Per la variabile uscente nel caso in cui esistano più righe avente lo

stesso rapporto non negativo minimo si sceglie la riga di indice

inferiore. dsm

Marco Castellani (L’Aquila) Ricerca Operativa La programmazione lineare 101 / 122

L’algoritmo del simplesso

Regola dell’anticiclo di Bland {1,

=

Primo passo. Entra in base x , esce x e si ha B 6, 7}

5

1 1

−33 −3

0 30 7/50 0 0

−240 −4/25

1 36 4 0 0 0

−15 −2

0 30 3/50 1 0 0

0 0 1 0 0 0 1 1

{1,

=

Secondo passo. Entra x , esce x e si ha B 2, 7}

2 6 2

−18 −1 −1

0 0 2/25 0

−84 −12

1 0 8/25 8 0 0

−1/2 −1/15

0 1 1/500 1/30 0 0

0 0 1 0 0 0 1 1 dsm

Marco Castellani (L’Aquila) Ricerca Operativa La programmazione lineare 102 / 122

L’algoritmo del simplesso

Regola dell’anticiclo di Bland {2,

=

Terzo passo. Entra x , esce x e si ha B 3, 7}

3 1 3

−1/4 −3

0 0 3 2 0

−525/2 −75/2

25/8 0 1 25 0 0

−1/160 −1/60

1 0 1/40 1/120 0 0

−25/8 −25

0 0 525/2 75/2 1 1

{3,

=

Quarto passo. Entra x , esce x e si ha B 4, 7}

4 2 4

−120 −1

1/2 0 0 1 0

−125/2 −150

10500 1 0 50 0 0

−1/4 −2/3

40 0 1 1/3 0 0

−10500 −50

125/2 0 0 150 1 1 dsm

Marco Castellani (L’Aquila) Ricerca Operativa La programmazione lineare 103 / 122

L’algoritmo del simplesso

Regola dell’anticiclo di Bland {4,

=

Quinto passo. Entra x , esce x e si ha B 5, 7}

5 5

3

−330 −1/50

7/4 0 0 2 0

−5/4 −3

210 1/50 0 1 0 0

−30 −1/150

1/6 1 0 1/3 0 0

0 0 1 0 0 0 1 1

{5,

= =

Sesto passo. La base ritorna B 6, 7} B ed anche la tabella

6 0

è quella iniziale

−150 −6

3/4 1/50 0 0 0

−60 −1/25

1/4 9 1 0 0 0

−90 −1/50

1/2 3 0 1 0 0

0 0 1 0 0 0 1 1 dsm

Marco Castellani (L’Aquila) Ricerca Operativa La programmazione lineare 104 / 122

L’algoritmo del simplesso

Regola dell’anticiclo di Bland

Se l’algoritmo del simplesso cicla allora vuol dire che siamo in

presenza di un vertice degenere: purtroppo, nella pratica, la presenza

di vertice degeneri è altamente probabile ma, per fortuna, la possibilità

che l’algoritmo cicli è bassissima. In ogni caso esistono delle regole

che permettono di evitare il ciclo (anche se, per sottolineare

nuovamente l’estrema rarità della presenza di un ciclo, nelle

implementazioni tali regole non vengono quasi mai seguite). La regola

più famosa, pubblicata da R.G. Bland nel 1977 su Math. Oper. Res., 2,

afferma quanto segue:

tra tutte le possibili variabili entranti si selezioni quella con indice

minore;

tra tutte le possibili variabili uscenti si selezioni quella con indice

minore. dsm

Marco Castellani (L’Aquila) Ricerca Operativa La programmazione lineare 105 / 122

L’algoritmo del simplesso

Regola dell’anticiclo di Bland

Teorema (Regola dell’anticiclo di Bland)

Il metodo del simplesso con la regola dell’anticiclo di Bland non

ammette cicli.

La regola di Bland permette di evitare cicli ma degrada le prestazioni

dell’algoritmo del simplesso. Applichiamola al precedente esempio.

Dopo il quarto passo avevamo la tabella

−120 −1

1/2 0 0 1 0

−125/2 −150

10500 1 0 50 0 0

−1/4 −2/3

40 0 1 1/3 0 0

−10500 −50

125/2 0 0 150 1 1

ed abbiamo fatto entrare in base x in quanto direzione di massima

5

crescita. Utilizzando la regola di Bland facciamo entrare x

1 dsm

Marco Castellani (L’Aquila) Ricerca Operativa La programmazione lineare 106 / 122

L’algoritmo del simplesso

Regola dell’anticiclo di Bland {1,

=

Entra x , esce x e si ha B 3, 4}

1 3

−36 −11/5 −1/125

0 0 0 7/5

0 0 1 0 0 0 1 1

−2 −1/15

0 0 1 2/15 1/250 1/250

−168 −4/5

1 0 0 12/5 2/125 2/125

Siamo usciti dal ciclo! La nuova soluzione di base ammissibile è

2 1

, ,

0, 1, 0, 0, 0

125 250

Facendo entrare x ed uscire x otteniamo la tabella ottima

5 4

−15 −21/2 −3/2 −1/20

0 0 0

0 0 1 0 0 0 1 1

−15 −1/2

0 0 15/2 1 3/100 3/100

−180

1 0 6 0 2 1/25 1/25 dsm

Marco Castellani (L’Aquila) Ricerca Operativa La programmazione lineare 107 / 122

L’algoritmo del simplesso

Regola dell’anticiclo di Bland

Esercizio

Il seguente esempio fu introdotto da Yudin e Gol’shtein (1965)

 − −

+

max x x x x

5

3 4 6

 − −

+ + =

x x 2x 3x 4x 0

 5

1 3 4 6

 − −

+ + =

x 4x 3x 2x x 0

5

2 3 4 6

+ + + + =

x x x x x 1

 5 7

3 4 6

 ≥

, , , , , ,

x x x x x x x 0

 5 7

1 2 3 4 6

Mostrare che

utilizzando il criterio di massima salita l’algoritmo compie un ciclo

1 di lunghezza 6;

utilizzando la regola dell’anticiclo di Bland l’algoritmo converge

2 = (3,

alla soluzione ottima x 2, 0, 0, 1, 0, 0). dsm

Marco Castellani (L’Aquila) Ricerca Operativa La programmazione lineare 108 / 122

L’algoritmo del simplesso

Il problema ausiliario

Esempio 7. Consideriamo il seguente problema

 +

max x x

1 2

 − + + =

x x x 2x 20

 1 2 3 4

+ + =

x x x 4

2x

1 2 3 4

 ≥

, , ,

x x x x 0

 1 2 3 4

Dalla tabella del simplesso associata

1 1 0 0

−1

1 1 2 20

−1

2 1 1 4

si vede che non siamo in grado di determinare immediatamente una

matrice di base ammissibile; addirittura non sappiamo neppure se tale

matrice esiste oppure no. dsm

Marco Castellani (L’Aquila) Ricerca Operativa La programmazione lineare 109 / 122

L’algoritmo del simplesso

Il problema ausiliario

Per risolvere questo problema introduciamo due nuove variabili y e y

1 2

non negative, dette variabili artificiali, e consideriamo il seguente

nuovo problema, detto problema ausiliario,

 +

min y y

1 2

 − + + + =

x x x 2x y 20

 1 2 3 4 1

+ + + =

2x x x x y 4

1 2 3 4 2

 ≥

, , , , ,

x x x x y y 0

 1 2 3 4 1 2

Dalla tabella simpliciale associata

0 0 0 0 1 1

−1

1 1 2 1 0 20

−1

2 1 1 0 1 4

1 = (0,

si ricava una soluzione di base ammissibile z 0, 0, 0, 20, 4). dsm

Marco Castellani (L’Aquila) Ricerca Operativa La programmazione lineare 110 / 122

L’algoritmo del simplesso

Il problema ausiliario

Risolviamo il nuovo problema di minimo. Innanzitutto

−3 −3 {y }

= ,

0 0 0 0 B y

1 1 2

−1

1 1 2 1 0 20 1

−1 = (0,

2 1 1 0 1 4 z 0, 0, 0, 20, 4)

Entra in base x ed esce y

1 2

−3/2 −3/2 {x }

= ,

0 3/2 0 3/2 B y

2 1 1

−3/2 −1/2

0 3/2 3/2 1 18 2

−1/2 = (2,

1 1/2 1/2 0 1/2 2 z 0, 0, 0, 18, 0)

ed esce y

Entra in base x

3 1 {x }

0 0 0 0 1 1 = ,

B x

3 1 3

−1 −1/3

0 1 1 2/3 12 3 = (8,

1 0 0 1 1/3 1/3 8 z 0, 12, 0, 0, 0) dsm

Marco Castellani (L’Aquila) Ricerca Operativa La programmazione lineare 111 / 122

L’algoritmo del simplesso

Il problema ausiliario (8,

La soluzione ottima del problema ausiliario è 0, 12, 0, 0, 0) ed il

valore ottimo è 0.

(8,

Osserviamo che 0, 12, 0) è una soluzione di base ammissibile (con

{1,

=

base B 3}) anche per il problema iniziale!

Quindi possiamo risolvere il problema iniziale partendo dalla seguente

tabella 1 1 0 0

−1

0 1 1 12

1 0 0 1 8

Continuate! Invece ora vediamo qual è il trucco che ci sta sotto. dsm

Marco Castellani (L’Aquila) Ricerca Operativa La programmazione lineare 112 / 122


PAGINE

122

PESO

1.28 MB

AUTORE

Atreyu

PUBBLICATO

+1 anno fa


DESCRIZIONE DISPENSA

In questo materiale didattico vengono trattati i seguenti argomenti. Programmazione lineare: ottimizzazione, funzioni obiettivo, funzioni vincolari, problemi in forma canonica, problemi in forma standard. Teoria della PL: insiemi convessi, involucro convesso; insiemi conici, involucro conico; iperpiani e vettori direzione; poliedro, direzione di recessione, direzione di linearità, vertice, spigolo, teorema sulla rappresentazione dei poliedri, teorema sulla localizzazione delle soluzioni. Algoritmo del simplesso: definizioni ed esempi; soluzioni di base ammissibili; criterio per l'ottimalità; metodo del simplesso (geometrico e algebrico); casi particolari: infinite soluzioni, funzione obiettivo non limitata, soluzione degenere, regola dell'anticiclo di Bland, uso del problema ausiliario; formulazione analitica dell'algoritmo; complessità computazionale.


DETTAGLI
Corso di laurea: Corso di laurea in economia e amministrazione delle imprese
SSD:
Università: L'Aquila - Univaq
A.A.: 2011-2012

I contenuti di questa pagina costituiscono rielaborazioni personali del Publisher Atreyu di informazioni apprese con la frequenza delle lezioni di Ricerca Operativa e studio autonomo di eventuali libri di riferimento in preparazione dell'esame finale o della tesi. Non devono intendersi come materiale ufficiale dell'università L'Aquila - Univaq o del prof Castellani Marco.

Acquista con carta o conto PayPal

Scarica il file tutte le volte che vuoi

Paga con un conto PayPal per usufruire della garanzia Soddisfatto o rimborsato

Recensioni
Ti è piaciuto questo appunto? Valutalo!

Altri appunti di Ricerca operativa

Programmazione Lineare Intera
Dispensa
Algoritmi su grafi - Prima parte
Dispensa
Modelli
Dispensa
Analisi numerica - Metodo delle secanti
Dispensa