Metodi di ottimizzazione della ricerca operativa

E

· A

F

>

6 Y

· ·

· Y

6 ⑧

&

&

1 1

1

L ↓

L

soluzioni

aggiungo

>

-

⑳ · ⑳

soluzione vircolo ridondante

-

C C C

degenere E

E (tre ·

basi)

· base

cambia

stessa

M >

Muoug M M -

ma

E base

ottimo [F su3

R

Str 3 , ,

H

· · ⑧

H ↑

P P P

Y

6 · Y

6 Y

· ·

range in cui la base non cambia: 33< b < 136/3

- M-

Cosa non cambia quando resto nel range: - non cambia la base B (le variabili) noncabia

- cambia la soluzione di base (le coordinate) x M yacubia

+

B

XB

B =

~ cambia (in genere) l’ottimo z

agli estremi del range: ↳

soluzioni ottimali degeneri quando vincolo ridondante

il (fuoridal

diventa range

vincolo attivo

quando carbio un non

basil

[piv

max c x Condizione di ammissibilità

: ≥ 0

B,

ottimale

base

la

conosco I

-

XB O

= >

Condizione di ottimalità

b,0)

=(B

x

ottimale

soluzione

la

s.a. Ax < b : = − ≤ 0′

I

- I

′ ′ ′

-

B

z*.

ottimo

valore

il

e

x > 0

-

Variazioni nel vettore dei coefficienti della funzione obiettivo possono compromettere le condizioni di ottimalità, ma non hanno

alcun effetto sulle condizioni di ammissibilità. (nor nell'equazione la

c'e cambial

cambio anissimile

regione

2

se non

,

Variazioni nel vettore dei termini noti possono compromettere le condizioni di ammissibilità, ma non hanno alcun effetto sulle

condizioni di ottimalità.

Cambiano i coefficienti della funzione obbiettivo (anche più di uno)

c= c + Δd

s ↓ ↳ moltiplicativo

parautro

- (numero

vettone &

iniziale direzione di (vettore)

perturbazione d

+

r ‘ =

Condizione di ottimalità : < 0’

= r’ + Δ (d’ - d’ B A)

( I

d)' -

1 - ( (B) +

BBA B A

= + +

- B

Δd < -r -r

-r j

j

Δ = max { — se d <0} < Δ < min { — se d >0 } = Δ

Range: min

min j j max 30 -1

d d

j j Vjc0

in cui la base ottima B che sto considerando non cambia rj

-

+ max

- - -

J

* (c)

z = z* (c) + Δd’ x

z* (c )

Valore ottimo: XB

~ AdBB"b

CB "b

'B

((B 1dB) b

= +

= + = B B

Cambiano i termini noti dei vincoli (anche più di uno)

b= b + Δd

- ↓ ↳ moltiplicativo

parautro

- (numero

vettone &

iniziale direzione di (vettore)

perturbazione d

XB

x = = x + ΔB d < 0

Condizione di ammissibilità: I

"5 -

~ B " B "b AB d

(b

B 10)

+ +

=

=

Δd > -x B -(x )

-(x ) i

i

Range: Δ = max { — se d >0} < Δ < min { — se d <0 } = Δ

min i i max

B

B

d d

i i

in cui la base ottima B che sto considerando non cambia -vettone

λ’

* (b)

z

z* (b ) = z* (d) - Δλ’d

Valore ottimo: ~ ABB"d

CB b

*

c (B"(b 10)

=

= +

+ =

B 5 J b

adesso

b

*

Cambio di NOTAZIONE us

caso monodimensione

b = b + Δu sol

i vova

B"5 Bob

* originale)

(sol XB =

=

B .

z* (b ) Δλ

+

)

(b

z*

=

* <'BB"

.. Bb

(5 (5 +(B)

(5

+ 1) * ) +

= z

+

z = = ;

i : :

= ↳ i i

:

λ è il tasso di variazione della funzione obbiettivo rispetto a variazioni del termine noto

Per Δ=1 : prezzo ombra

λ = z* ( b + 1) - z* (b )

variazione marginale della funzione obbiettivo : i

i

1

L moto

termine 45 33

3 3 - 4 0 5

va r i a z i o n e =

:

1) 8 76

2 18R

24F ,

+ = ,

2) 940

18R

24F =

+

· funz obb 64

940-876

va r i a z i o n e : =

.

C E 12 d

= PREZZO OMBRA

=

· M)F R140

+

M Un ora aggiuntiva (di macinazione) vale per l’impresa 12€

↓

↓ R 45 33

=

F + , Valore marginale della risorsa.

.

0 >

6 ⑧ Nel range: base ott. non cambia, prezzo ombra

* (b)

12 cami

quandoX at non cambia, x cambia

a

↑ B

Agli estremi:

RANGE cambia base ott., sol ott. degeneri,

o

I estrai sol de

Cagli

940 - prezzo ombra ???

8 76 - &

& pendenza solor multiple

ottimali

dualita duale ho

nel

92

7 * ↑

- : ,

"Is "lavono

ne

do as 33 Problema di max

Problema di min decrescente

crescente Vincolo >=

C o nve ss a c o n c ave

Vincolo >= marginali

[costi crescentil Problema di max

Problema di min decrescente crescelte

Vincolo <=

Vincolo <= C o n c a rd

C o nve s s a mescentil

(x

Problema di max

Problema di min C o nve s s a c o n c ava

Vincolo =

Vincolo =

+ Per i coefficienti di costo Problema di max

Problema di min c o n c ava C o nve s s a

soluzioi

punti multiple

angolsi ottimali

nei

>

- :

Coefficienti di costo ridotto r = c - A’ λ

Σ coefficiente di costo di una variabile

r = c - a λ

m

j j ij i

1

i = ↳ vincoli

variabile

coeff la ha nei

↳ che va r i -Xi

le variabili scorto

di Usi

Jeff per =

:

mella z

. di

le surplus Xi

variabili Usi

: =

per

Dualità

max c’ x min b’ λ

s.a. Ax < b s.a. A’λ> c

(λ) (x)

x > 0 λ > 0

- [dieta)

(mix)

massimizzazione —> minimizzazione

I vincoli del primale corrispondono in modo biunivoco alle variabili del duale, mentre i vincoli del duale corrispondono in

modo biunivoco alle variabili del primale.

I coefficienti della funzione obiettivo del primale si trasformano nei termini noti del duale.

I termini noti del primale si trasformano nei coefficienti della funzione obiettivo del duale.

La matrice tecnologica del primale viene trasposta per ottenere quella duale.

Metodi:

1. min b’ λ

min b’ λ max c’ x Duale

MIX D

D s.a. A’λ> c

s.a. A’λ ? c s.a. Ax < b λ > 0

λ ? 0 x > 0

-

? qualsices ;

= vincoli

cambiana da voltiplicare

· 1

1

per > per -

a ,

2. tabella

3. prezzi ombra

max c’ x Stabilire il segno della variabile del duale:

min b’ λ

s.a. A’λ> c (x)

s.a. Ax < b λ è il prezzo ombra del vincolo del primale

(λ) λ > 0

x > 0 • b -> b+1 (incremento di uno il termine noto del vincolo

- • ho più (meglio) o meno (peggio) soluzioni?

Stabilire il segno del vincolo nel duale: • la fun.obb. cresce o diminuisce? (max o min del primale)

x è il prezzo ombra del vincolo —> questo è il segno

• z*(b+1) - z*(b) </> 0 della variabile nel duale

• metto un segno a caso (< o >)

( deve venire concorde con la variabile nel primale)

• ha senso il prezzo ombra? valite

D

rem

EO H

-

&

Ottimizzazione intera 2/11

Classificazione:

-Ottimizzazione lineare intera mista -Ottimizzazione lineare intera pura

max c’x + d’y max c’x

s.a. Ax + Ey = b s.a. Ax = b

Mista perché ha sia variabili intere (x)

sia variabili continue (y)

x c Z , y>0 x c Z

~ -

I

-

-Ottimizzazione lineare binaria o booleana

Le variabili intere del modello possono assumere solamente i valori 0 o 1

diventa

Z

c

x x c {0,1}

M

- D -

Esempio: Problema dello zaino

n oggetti 1 se l’oggetto j viene scelto

• E

p : valore dell’oggetto j (importanza) x = 0 altrimenti

• j j

w : ingombro/peso dell’oggetto j

• variabili

j M

av r e vo

>

b : capacità del contenitore

• n p x

max j j

j=1 n w x < b

s.a. j j

j=1

x c {0, 1} j=1…n

-

Pianificazione produttiva con lotti minimi Pjt produce

quanto

produzione

costi di

Cit :

:

Σ Σ

min (c P + h I )

Es "I Ijt

hit vanterimento

it di

it tengo

it costo scorta

It scorta

quarto

: : a

a

s.a. P + I - I = d V j ; V t bilancio djt

di

vincolo finale

scorta

jt

it ↑

t - 1

j

jt :

,

Σ a P < b V i ; V t

R vincoli di capacita sulle

it risorse

↑

it

it

i 1

= V j ; V t

P > l Y Cotto

di Cj

vinc produzione

dimensione del lotto di

. minima

it it

j :

P < γ Y V j ; V t produrra l

voglio

allora

pro almo S

jt

jt se sepjt

I o

P , I > 0 Y c {0,1} Yit

grande

volto P

costarte

V

↑

it jt jt =

- : altriveti

O

forzo Y 1

a

Pianificazione produttiva con costi fissi (set-up) produce

mod

attrezzaggio -n

Σ Σ

min (c P + h I + f Y )

T n fit costifissi

it

it it j t

jt Yit

it producendo

sto

1

t j

1 : -e se

con

= = o nuo

s.a. P + I - I = d jt

it

t1

j

it ,

Σ &

a P < b

R Fit CtPjt

(Pjt) P

;

it

it =

it

i 1 se

=

P < γ Y quando forzo

Pso Pit

jt 1

Y

jt ~ O

=

se

=

,

P , I > 0 Y c {0,1} la funzione obbiettivo

it jt jt E

che

n i assicura

- se Pic

se

Miririzy

(Perche e

↑ Y

allora anche 0

0 Yst

= = altrimuti

Localizzazione di impianti Quali impianti attivo?

m località in cui è possibile attivare un impianto

n destinazioni da rifornire So attivato

l'impianto Xij

viewe

se > 0

-

y

capacità massima dell’impianto attivato nella località i :

: altricti Xi 0

e =

: livello della richiesta da parte della destinazione j