Ricerca operativa

C C D C E

*3, 3 F 12 ; , , , F , F , F 1 0

;

C Œ C D E Œ

Naturalmente , e sono le variabili strutturali, , ed sono di slack. Sono mostrati di seguito il tableau

x x x s s s

1 2 3 4 5 6

iniziale, e il tableau finale; per ottenere quello finale si è reiterato il processo di ricerca dell’ottimo facendo

prima entrare in base al posto di e poi al posto di . Come si vede l’ottimo si ha per =[0 1 3 0 0 2], e

T

x*

x s x s

3 5 2 4

si ottiene Nel tableau iniziale sono stati messi in evidenza la matrice all’ottimo (nei

B

z*=7. due riquadri rossi), costituita dalle colonne delle variabili in

base relative a la matrice (nel riquadro tratteggiato in

N

x*,

verde) e il vettore colonna (cerchiato in blu). Nel tableau

b

finale sono invece evidenziati la matrice (nel riquadro

-1

B

(cerchiato in verde), lo scalare

blu), il vettore BT

-1 -1

b B b

B z*=C

(cerchiato in rosso) e le colonne della matrice (in

-1

B N

tratteggiato). Le matrici di cui parliamo sono naturalmente

riferite alla scrittura finale del problema. Infine i tre numeri evidenziati dal riquadro, cioè i coefficienti della

funzione delle variabili non in base, sono detti e il vettore dei prezzi ombra

z prezzi ombra,

,π ,…,π ]=C . Il significato algebrico ed economico è presto

può ottenersi come: BT -1

B

π=[π

1 2 n

dedotto. Il vettore è composto dai valori dei coefficienti

BT

C

iniziali della funzione obiettivo relativi alle variabili che nel

tableau ottimo sono in base (quindi nulli nel caso di slack);

= [–2 3 0]. All’ottimo, il vettore delle

nell’esempio BT

C x N

variabili fuori base è nullo; per un aumento unitario della i–

esima variabile fuori base, il profitto decresce di una quantità

pari a . Una variabile fuori base di scarto che assume valore unitario negativo fisicamente corrisponde ad un

π

i

aumento unitario della risorsa corrispondente (cioè il termine noto della equazione del vincolo in cui compare

quella variabile), e algebricamente vediamo come, se lo facesse, il profitto aumenterebbe di . Allora è

π π

i i

proprio il prezzo massimo che sono disposto a pagare per acquistare un’unità in più di quella risorsa. I prezzi

ombra si riferiscono solo a vincoli stringenti: infatti per le risorse espresse dai vincoli corrispondenti a slack

positive (e quindi in base) non avrebbe senso considerare l’acquisto di ulteriori unità, avendo di esse quantità

in esubero. Se si scegliesse di operare in tal senso bisogna ricordarsi che deve valere la condizione -1

B b≥0.

0

Dunque per la variazione di unità Δb dell’i-esima risorsa possiamo determinare un campo di ammissibilità:

• a

i ? B

? B

⋮ ,.

• “ •

> A

> A a

1 c ; N 1 0 ⟺ • 1 7N

N •

> A

Ž ’ > A

a a a

,.

⋮

.

.

> A > A

⋮ •

= @ = @

0 a

• ‘ k,.

Dalla precedente si ottengono relazioni e ognuna di essa impone un vincolo di disuguaglianza: i vincoli su

k

Δb saranno i più stretti tra questi. Se la risorsa subisce una variazione Δb esterna all’intervallo consentito,

i

i i

possiamo al più dire che Δz ≤ Δb π . Passiamo alle variabili strutturali fuori base. Nell’esempio, come si vede,

i i

è fuori base: ciò significa che all’ottimo non converrà produrne (x =0). Ci si può chiedere dunque di quanto

x 1 1

debba aumentare il profitto unitario (al momento uguale a 2) affinché convenga che >0. Algebricamente

c x

1 1

– 7 • — 0 ⟺ • p –

ciò che deve accadere è che si perda l’ottimalità, e che convenga che entri in base: in altre parole deve

x π

1 1

essere negativo, e dunque la variazione del profitto unitario dovrebbe essere: . Nel

caso limite in cui Δc =π si ha una situazione d’indifferenza: l’ottimalità si avrebbe ancora poiché risulterebbe

1 1

=0 nel tableau ottimo, e fisicamente saremmo nella condizione in cui l’aumento di profitto derivante dalla

c 1 eguaglierebbe il decremento derivante dalla diminuzione della produzione di

vendita di unità del prodotto x 1

alcuni degli altri, cioè si avrebbe Δz=0.

6

Capitolo 2. max , , 1 c

&

Riproponiamo il problema del mix di produzione in forma canonica: . Definiamo

P tale problema. Supponiamo che oltre ad utilizzare le risorse per produrre le quantità , queste si

˜ 9– , – , … , – :

primale x i

il vettore dei relativi prezzi. Possiamo formulare allora

possano anche vendere e chiamiamo ∑

min – min ˜

. . .

un nuovo problema che ha come obiettivo: , al fine di capire se non convenga vendere in

∑ – 1 *∀3,, ˜ 1

blocco le risorse anziché utilizzarle. I vincoli devono allora assicurare che, nel caso in esame, non sia più

. 0. . . che in forma compatta si scrivono come .

conveniente produrre, cioè devono essere:

min ˜ ˜1

Possiamo allora scrivere la forma canonica di questo nuovo problema, detto D:

˜1c duale

, ,

Ogni soluzione ammissibile per il duale permette di realizzare un guadagno non inferiore al profitto massimo

ottenibile dal problema primale (ovverosia producendo). Ad ogni problema P è associato un problema D, e

tra questi vi sono numerose analogie. Il numero di

vincoli di P è uguale al numero di variabili di D, e

viceversa. Tutte le altre sono evidenziate in figura.

Ragionando allo stesso modo si può intuire come

formulando il problema duale del duale D si ottenga

nuovamente il primale P di partenza. Ogni variabile

duale è associata ad un vincolo del primale ed è non

negativa fintantoché il vincolo è con

congruente

. Per evitare di confondersi conviene orientare

l’obiettivo

5

le disuguaglianze dei vincoli del primale congruentemente con il tipo di problema (max o così da avere

min),

nel duale unicamente variabili non negative. Enunciamo i teoremi di dualità:

Teorema della dualità debole: Data una coppia di problemi primale – duale, per convenzione

˜ max min,

&

per ogni coppia di soluzioni (X, ammissibili vale la relazione: .

π)

Teorema della dualità forte: Data una coppia di problemi primale – duale, per convenzione ˜

max min,

& ∗ ∗

una coppia di soluzioni (X*, ammissibili è ottima se e solo se vale la relazione: . Questo

π*)

teorema ha come corollario che gli (prezzi ombra) del primale coincidono con π*.

shadow price

Supponiamo di avere un problema P ed il suo duale D, e di conoscere le soluzioni ottime rispettive X*e π*.

L’algoritmo del simplesso duale consente di trovare nuovamente la soluzione ottima dopo l’aggiunta di un

nuovo vincolo a P, senza che sia necessario risolvere il problema dall’inizio. Si consideri l’esempio a fianco. La

prima immagine mostra il tableau ottimo di un certo

problema iniziale P, e le soluzioni Il secondo

X*e π*.

raffigura come si modifica il tableau dopo l’aggiunta di un

nuovo vincolo ≤3, che in forma standard diventa: +s =3.

x x

1 1 5

La prima cosa da fare è annullare l’elemento di posto 5x1

con operazioni di pivoting affinché il nuovo vincolo sia

espresso nella base corrente. Una volta completato questo

passaggio l’ultima riga del tableau è quella mostrata in

figura: siamo ancora fuori dal poliedro. A questo punto

dell’algoritmo bisogna scegliere una variabile in base

uscente a cui corrisponde un valore negativo. Nel nostro

y r0 7

5 Se il problema è di max un vincolo è congruente se è del tipo “minore o uguale” (vincolo di tipo risorsa). Viceversa se

l’obiettivo è un min vincoli congruenti saranno del tipo “maggiore o uguale” (vincolo di tipo necessità).

caso è , a cui corrisponde -1/3, cerchiato in rosso nell’ultima

s

5

figura, mentre in generale si sceglie il più grande in modulo.

Per decidere quale fare entrare in base si sceglie, tra le

min i /i <0, quella per cui si verifica

variabili a cui corrisponde un y rk

jk [k , con negativo. Dunque deve uscire ed

y s

5

0k

entrare . Reiterando il processo si giunge all’ottimo.

s

2

Si può dimostrare che inserire una nuova variabile

strutturale (senza inserire nuovi vincoli) o non modifica la soluzione ottima oppure la rende semplicemente

X*

primale ammissibile e quindi andranno eseguiti dei passi di simplesso primale per determinare la nuova

soluzione ottima. Dunque si abbia il tableau finale di un dato problema. Inserire una nuova variabile vuol

x k

dire definire il coefficiente per ogni vincolo e il coefficiente della funzione obiettivo. Naturalmente in

y y 0k

rk quello che era il tableau finale non possiamo inserire questi

coefficienti, ma dobbiamo invece calcolarli rispetto alla base corrente.

Essendo la matrice inversa di estraibile dal tableau finale,

-1

B B,

possiamo calcolare i nuovi coefficienti come = , dove è un

-1

Y B N. N.

.k k k

vettore costituito dai coefficienti sopracitati, e inserire nel

Y

y .k

rk

tableau. Se chiamiamo il vettore costituito dai coefficienti *

y* y 0j

corrispondenti alle colonne che costituiscono , possiamo calcolare il

-1

B

costo ridotto di come: *= – . Per chiarire, mostriamo un

y*N.

x y y

k 0k k 0k

esempio. Il problema iniziale è mostrato in figura, con l’aggiunta della

variabile , evidenziata in rosso. È mostrato il tableau all’ottimo

x 6

(naturalmente con esclusa), dai quali può ricavarsi la matrice -1

B

x 6

(colonne delle variabili che nel tableau iniziale sono in base) e il vettore

3/2 0 71/4 1

1 1

Calcoliamo la colonna relativa ad da aggiungere al tableau finale:

y*. x 1 1

6

72 1 1/2

š N R ; i › R 7 i œ • 7 3 72 *— 0,

2 1 2

0

a ∗ ∗ 2 4

.Œ .Œ .Œ jŒ

jŒ

71/2 0 1/4 2 0 2

Si noti come il valore di non subisca alcuna variazione, dato che la nuova variabile si inserisce come variabile

z

fuori base, e quindi si pone con valore nullo. Giunti a questo punto, o si è già all’ottimo, oppure bisogna

trovarlo nuovamente con processi di simplesso primale. Nel nostro caso non siamo all’ottimo perch&eac