Metodi e modelli di ottimizzazione - Appunti

∈X,

*

Output: x vertice ottimo di P

INIZIO

t:=0

t 0

x :=x t t

Δx(h)

Finchè esistono direzioni basiche del simplesso nel vertice corrente x , h∈I(x ) tali che

c

i INIZIO

Selezionare una di queste Δx(h)

c Δx (h) ≥

l Se 0

i

o STOP: Ottimo illimitato

Altrimenti

w INIZIO Δx

h Calcolare = min { : (h) < 0 }

i

t+1 t + λΔx(h)

i x := x Calcolo del passo

t+1 t

l x entra nella base: I(x ) = I(x )-{h}

h t+1 e avanzamento

e (il vincolo h non è più attivo in x )

t+1 t

x esce nella base: I(x ) = I(x ) {k}

k t+1

(il vincolo k diventa attivo in x )

t: t+1

FINE

FINE

* t

x =x

FINE (correttezza dell’algoritmo del simplesso)

Teorema *

Ax=b, x≥0}.

Consideriamo il problema min cTx, x∈P={x∈Rn: Un vertice x di P è ottimo se e solo

* T

se non esistono in x direzioni basiche di discesa per c x.

Dimostrazione (solo se):

*

Ipotesi: il vertice x di P è ottimo

* T

Tesi: in x non esistono direzioni basiche di discesa per c x.

* *

Se vertice x di P è ottimo, necessariamente in x non possono esistere direzioni basiche di discesa

T *

per c x, perché altrimenti si potrebbe trovare una soluzione ammissibile migliore di x

(contraddizione). CVD 38

Dimostrazione (se):

* T

Ipotesi: in x non esistono direzioni basiche di discesa per c x.

*

Tesi: il vertice x di P è ottimo

* T

Supponiamo che nel vertice x di P non esistano direzioni basiche di discesa per c x.

*

Facciamo vedere che ciò implica la condizione più forte che in x non esistono proprio direzioni

T

ammissibili di discesa per c x (basiche e non basiche).

Per vederlo dimostriamo che ogni direzione ammissibile che non è una direzione basica è sempre

ottenibile come combinazione lineare delle direzioni basiche con pesi non negativi.

Consideriamo in x* una possibile direzione ammissibile d (non

basica), si ha: Δx(v2)+ δ Δx(v3)

d=δ

2 3

δ 0

2

δ 0

3

E’ sempre possibile identificare d come combinazione lineare delle n

*

direzioni basiche in x con pesi non negativi

Solo le direzioni basiche sono rilevanti.

Ogni altra direzione ammissibile è combinazione lineare delle direzioni basiche con pesi non

negativi. * T

Quindi se nel vertice x di P non esistono direzioni basiche di discesa per c x allora ogni altra

δ Δx(v1)+δ Δx(v2)+ δ Δx(v3), δ δ δ ≥0

direzione ammissibile d= NON può essere di discesa

1 2 3 1, 2, 3

* T

in x per c x.

Infatti, nessuna combinazione lineare di direzioni del simplesso con pesi non negativi può essere

* T

di discesa in x (c d<0) senza che lo sia almeno una delle direzioni basiche da cui si ottiene la

combinazione (e, per ipotesi, in x* non ve ne sono).

* T *

Dunque in assoluto in x non esistono direzioni ammissibili di discesa per c x e qundi x è

*

OTTIMO LOCALE. (Tattandosi di un problema di PL si può anche concludere che x è

OTTIMO GLOBALE) CVD

Individuazione di una soluzione iniziale Ax=b, x≥0}.

Dato un problema in forma standard la cui regione ammissibile è P={x∈Rn:

∈P.

0

Assumiamo P non vuoto e supponiamo di conoscere una soluzione x

Per poter inizializzare l’algoritmo del simplesso come algoritmo di ricerca locale ci dobbiamo

occupare di:

 verificare se esiste almeno un vertice (SBA) iniziale

 se esiste, individuarne uno.

Si tratta della I fase del metodo del Simplesso attraverso la quale si può capire se il problema in

forma standard è ammissibile e, quindi, esiste la forma canonica ammissibile equivalente e

calcolare la SBA corrispondente. 39

Consideriamo il problema …..(P)

generale di PL in FS (non

necessariamente FCA):

Consideriamo un esteso (x,y),

con ym ≥ 0, e

definiamo il seguente

Problema Ausiliario

(spazio aumentato):

T

=(1,…,1)

dove e

! 0 0

Nota: Nello spazio aumentato il problema ausiliario è in FCA e (x ,y )=(0,b) è una SBA

………..(vertice) Il problema ausiliario è sempre ammissibile (per costruzione).

Si dimostra che: 0

1) (P) è ammissibile se e solo se w = 0

0

2) Se w = 0 allora la soluzione ottima (x*,y*) di (PA) è tale che

 y* = 0

 x* è una SBA (vertice) per il problema (P)

Una volta impostato e risolto il problema ausiliario

0

 se w > 0 non esiste alcuna soluzione ammissibile per (P)

0

 Simplesso

se w = 0, x* è un vertice ammissibile per (P) RL

METODO DELLE DUE FASI metodo della “Multa M” (“Metodo del

In alternativa al Metodo delle due fasi, si può adottare il

Big M”).

In questo caso si imposta un unico problema (PM) di PL in FS:

con M costante positiva molto elevata che corrisponde a una multa o penalità da pagare per la ”non

ammissibilità” 40

Anche il problema (PM) può essere risolto con l’algoritmo del Simplesso RL partendo dal punto

0 0

iniziale (x ,y )=(0,b).

Sia (x*,y*) la soluzione ottima di (PM); si dimostra che vale necessariamente una delle seguenti:

Il caso DEGENERE

Consideriamo un problema in forma standard

Definizione

Un vertice corrisponde a una SBA degenere (base degenere) se in esso sono attivi più di n vincoli.

Analogamente, se più di n−m variabili sono uguali a 0 (qualche variabile basica è nulla).

! Nota: le direzioni basiche dipendono dalla base che stiamo considerando

Nel caso di vertice degenere x si hanno più basi associate a x e |I(x)| > n

L’avanzamento dell’algoritmo del simplesso dipende dalla base associata al vertice

degenere x (che corrisponde a una scelta specifica di n vincoli lin. indip. in I(x)). 41

Modelli DEA

Si tratta di modelli per la valutazione della efficienza di unità o strutture produttive/organizzative

come scuole, ospedali, università, uffici pubblici, pattuglie stradali, ecc.

–

Efficienza: caso 1 input 1 output:

EFFICIENZA ASSOLUTA:

EFFICIENZA RELATIVA:

–

Efficienza: caso n input n output:

caso di più input e più output, l’efficienza di ogni unità organizzativa viene misurata mediante

Nel

il rapporto tra un output sintetico e un input sintetico, ottenuti come somme pesate con pesi non

≥ 0)

negativi rispettivamente rispettivamente degli output osservati (pesi u e degli input osservati

r

≥ 0).

(pesi v s

Problema: come devono essere scelti i valori dei pesi degli input e degli output in modo che

l’efficienza venga valutata correttamente, cioè in modo da non favorire o penalizzare nessuna unità

produttiva? Per determinare un sistema di pesi comune a tutte le unità, Charnes, Cooper e

Rhodes (1978) propongono che ogni unità possa scegliere un sistema di pesi che

massimizzi la sua efficienza.

CCR (1978):

 un modello di PM (non lineare, ma linearizzabile) per individuare il

massimizza l’efficienza di una data unità j

sistema dei pesi che ;

0

 il modello si formula e risolve per ciascuna delle unità separatamente

formulato per l’unità j

Nel modello DEA (unità di riferimento):

0

o i pesi degli input v e degli output u sono le incognite;

s r

o la f.o. (da massimizzare) corrisponde alla efficienza E ;

j0

(l’input sintetico di j

o può essere posto pari a 1)

0

o ogni efficienza è vincolata ad assumere valori tra 0 e 1;

o tutti i pesi sono non negativi. 42

(l’input sintetico di j può essere posto pari a 1: vincolo tecnico necessario per normalizzare il

0

sistema dei pesi)

La soluzione del problema fornisce il sistema di pesi che massimizza l’unità presa in considerazione

un’unità produttiva che riesce a

Si definisce efficiente raggiungere un valore di efficienza pari a 1

Se l’efficienza dell’unità A

attraverso una opportuna definizione dei pesi degli input e degli output.

è minore di 1 allora A è inefficiente e deve esistere necessariamente almeno un’altra unità che, con

lo stesso sistema di pesi, ha efficienza maggiore di A ( e uguale a 1)

Modello DEA generale

N insieme delle n unità operative j=1,..,n

r=1,…,p

R insieme degli p output s=1,…,q

S insieme degli q input

per l’unità j

y > 0 output r-esimo

rj l’unità j

x > 0 input s-esimo per

sj ε > 0

Introducendo un molto piccolo, possiamo garantire che tutti i

imponendo direttamente che ogni peso sia ≥ ε.

pesi siano positivi

Modello CCR primale

Linearizzazione del modello CCR primale

Proprietà (invarianza di scala)

L’efficienza E(u,v) è invariante rispetto a una variazione dei pesi degli output e degli input per un

α>0,

fattore di scala positivo cioè si ha: E(αu, αv) = E(u,v) ∈

∈

Il modello DEA può essere sempre riformulato considerando per l’unità di riferimento j una

0

efficienza con denominatore pari a 1. 43

Infatti scegliendo

per j si ha:

0

Adottando i pesi scalati αu e αv:

nel modello con unità di riferimento j si può sempre assumere che il denominatore di E sia

0 j0

pari a 1;

per l’unità di riferimento j coincide con l’output sintetico di j

, E .

0 j0 0

Il problema di Pj0 può essere riformulato in maniera equivalente come modello di PL:

! Nota: Nel modello DEA:

 la f.o. può essere linearizzata grazie al vincolo “tecnico”;

 anche i vincoli non lineari (frazionari) sono facilmente linearizzabili.

Il modello CCR duale

Se l’unità di riferimento non risulta efficiente è possibile formulare un altro modello, strettamente

per individuare l’unità target dell’unità di

legato al modello primale e detto Modello CCR duale

riferimento j .

0

[unità target: unità teorica di riferimento data da una combinazione lineare delle unità del peer set di j (valuta la input

0

.

efficienza)]

Nel problema duale fissato l’output dell’unità di riferimento l’unità

j inefficiente, si individua

0

minimizzando l’input

target di j di cui questa unità ha bisogno per produrre quando produce j .

0 0 44

Consideriamo l’unità B come unità di riferimento, cioè j0=B (inefficiente).

Formuliamo un problema