Che materia stai cercando?

Anteprima

ESTRATTO DOCUMENTO

Cos’è la Ricerca Operativa

Tratto dal sito del MiUR (d.m. del 04/10/2000)

I problemi oggetto di studio comprendono i sistemi di produzione,

trasporto, distribuzione e supporto logistico di beni e servizi, la

pianificazione, organizzazione e gestione di attività, progetti e sistemi,

in tutte le diverse fasi che caratterizzano il processo decisionale:

definizione del problema,

sua formalizzazione matematica,

formulazione di vincoli, obiettivi e alternative di azione,

sviluppo di algoritmi di soluzione,

valutazione, implementazione e certificazione delle procedure e

delle soluzioni trovate.

Le competenze didattiche di questo settore riguardano anche tutti gli

aspetti istituzionali della matematica di base. dsm

Marco Castellani (L’Aquila) Ricerca Operativa Alcuni modelli lineari 7 / 51

Modelli

Problema di produzione

Produciamo due tipi di tessuto A e B; per ottenere 100Kg di

A necessitiamo di 28kg di lana, 7kg di cotone, 3h di lavoro

B necessitiamo di 7kg di lana, 14kg di cotone, 3h di lavoro.

Settimanalmente abbiamo a disposizione di 168Kg di lana, 84kg di

cotone, 42h di lavoro. Sul tessuto A guadagniamo 200 Euro/quintale e

su B guadagniamo 100 Euro/quintale.

Come massimizzare il profitto settimanale rispettando i vincoli di

produzione? dsm

Marco Castellani (L’Aquila) Ricerca Operativa Alcuni modelli lineari 8 / 51

Modelli

Problema di produzione

Indichiamo con

x la quantità espressa in quintali di tessuto A prodotto,

1

x la quantità espressa in quintali di tessuto B prodotto.

2 ≥

Ovviamente x x 0. Il profitto settimanale sarà

,

1 2 (x ) = +

f x 200x 100x

,

1 2 1 2

che cercheremo di massimizzare. Analizziamo i vincoli di produzione.

dsm

Marco Castellani (L’Aquila) Ricerca Operativa Alcuni modelli lineari 9 / 51

Modelli

Problema di produzione +

Quanti Kg di lana consumiamo? 28x 7x e quindi dobbiamo

1 2

sottostare al vincolo + ≤

28x 7x 168.

1 2 +

Quanti Kg di cotone consumiamo? 7x 14x e quindi dobbiamo

1 2

sottostare al vincolo + ≤

7x 14x 84.

1 2

+

Quante ore utilizziamo? 3x 3x e quindi dobbiamo sottostare al

1 2

vincolo + ≤

3x 3x 42.

1 2 dsm

Marco Castellani (L’Aquila) Ricerca Operativa Alcuni modelli lineari 10 / 51

Modelli

Problema di produzione

Il problema assume la seguente forma

 +

max 200x 100x

1 2

 + ≤

28x 7x 168

 1 2

 + ≤

7x 14x 84

1 2

+ ≤

3x 42

3x

 1 2

 ≥

x x 0

,

 1 2

e risulta un problema di PL in forma standard. La soluzione del

36 24

problema è con un guadagno complessivo di 1371 euro.

,

7 7 dsm

Marco Castellani (L’Aquila) Ricerca Operativa Alcuni modelli lineari 11 / 51

Modelli

Problema di produzione

Se la produzione consisteva in rotoli di tessuto dal peso di un quintale

l’uno (e quindi il bene da produrre non era divisibile) la soluzione

precedente non era ammissibile. Il problema avrebbe assunto la

seguente forma  +

max 200x 100x

1 2

 + ≤

28x 7x 168

 1 2

 + ≤

7x 14x 84

1 2

+ ≤

3x 3x 42

 1 2

 ∈

x x

, N

 1 2 (5,

e sarebbe stato un prolema PLI. La soluzione di tale problema è 3)

con guadagno complessivo di 1300 euro. dsm

Marco Castellani (L’Aquila) Ricerca Operativa Alcuni modelli lineari 12 / 51

Modelli

Problema della dieta

Dobbiamo preparare una dieta che garatisca giornalmente almeno

600cal calorie, 50g di proteine e 700mg di calcio. Abbiamo a

disposizione 3 ingredienti.

Pane, 10 cent/Hg, col seguente apporto nutritivo: calorie 30

cal/Hg, proteine 5 g/Hg, calcio 20 mg/Hg;

Carne, 90 cent/Hg, col seguente apporto nutritivo: calorie 180

cal/Hg, proteine 90 g/Hg, calcio 80 mg/Hg;

Uova, 12 cent/Hg, col seguente apporto nutritivo: calorie 50

cal/Hg, proteine 30 g/Hg, calcio 50 mg/Hg.

Come costruire una dieta che soddisfi il fabbisogno minimo richiesto e

minimizzi il costo? dsm

Marco Castellani (L’Aquila) Ricerca Operativa Alcuni modelli lineari 13 / 51

Modelli

Problema della dieta

Indichiamo con

x la quantità espressa in Hg di pane utilizzata,

1

x la quantità espressa in Hg di carne utilizzata,

2

x la quantità espressa in Hg di uova utilizzata.

3 ≥

Ovviamente x x x 0. Il costo giornaliero sarà

, ,

1 2 3

(x ) = + +

f x x 10x 90x 12x

, ,

1 2 3 1 2 3

che cercheremo di minimizzare. Analizziamo i vincoli nutrizionali. dsm

Marco Castellani (L’Aquila) Ricerca Operativa Alcuni modelli lineari 14 / 51

Modelli

Problema della dieta + +

Quante calorie somministriamo? 30x 180x 50x e quindi

1 2 3

dobbiamo sottostare al vincolo

+ + ≥

30x 180x 50x 600.

1 2 3 + +

Quanti g di proteine somministriamo? 5x 90x 30x e quindi

1 2 3

dobbiamo sottostare al vincolo

+ + ≥

5x 90x 30x 50.

1 2 3 + +

Quanti mg di calcio somministriamo? 20x 80x 50x e quindi

1 2 3

dobbiamo sottostare al vincolo

+ + ≥

80x 50x 700.

20x

1 2 3 dsm

Marco Castellani (L’Aquila) Ricerca Operativa Alcuni modelli lineari 15 / 51

Modelli

Problema della dieta

Il problema assume la seguente forma

 + +

min 10x 90x 12x

1 2 3

 + + ≥

30x 180x 50x 600

 1 2 3

 + + ≥

5x 90x 30x 50

1 2 3

+ + ≥

20x 80x 50x 700

 1 2 3

 ≥

x x x 0

, ,

 1 2 3

ed è un problema di PL in forma standard. dsm

Marco Castellani (L’Aquila) Ricerca Operativa Alcuni modelli lineari 16 / 51

Modelli

Problema di turnazione

Un supermercato aperto 24 ore ha i seguenti fabbisogni minimi di

cassieri

Periodo 1 2 3 4 5 6

: : : : : :

Ore 03 07 07 11 11 15 15 19 19 23 23 03

Cassieri 7 20 14 20 10 5

Ogni cassiere lavora 8 ore consecutive cominciando all’inizio di uno

dei sei periodi.

Qual è il numero minimo di dipendenti necessari per soddisfare il

fabbisogno del supermercato? dsm

Marco Castellani (L’Aquila) Ricerca Operativa Alcuni modelli lineari 17 / 51

Modelli

Problema di turnazione

Indichiamo con x il numero di cassieri che cominciamo a lavorare

i =

all’inizio del periodo i (con i 1, 6). Dobbiamo minimizzare la

. . . ,

funzione obiettivo 6

X

(x ) = + + + + + =

f x x x x x x x x x x x x

, , , , ,

5 5

1 2 3 4 6 1 2 3 4 6 i

i=1

Per quanto riguarda i vincoli osserviamo che durante il periodo i

+

lavorano x x cassieri e quindi deve essere

i−1 i + ≥

x b

x

i−1 i i

dove b indica il numero minimo di cassieri necessari.

i dsm

Marco Castellani (L’Aquila) Ricerca Operativa Alcuni modelli lineari 18 / 51

Modelli

Problema di turnazione

Il problema assume la seguente forma

+ + + + +

 min x x x x x x

5

1 2 3 4 6

 + ≥

x x 7

 6 1

 + ≥

x 20

x

 1 2

 + ≥

x x 14

 2 3

+ ≥

x x 20

3 4

 + ≥

x x 10

 5

4

 + ≥

x x 5

 5 6

 ∈

 x x x x x x

, , , , , N

5

1 2 3 4 6

ed è un problema di PLI in forma standard. La soluzione del problema

(2,

è 18, 0, 20, 0, 5) corrispondente a 45 cassieri. dsm

Marco Castellani (L’Aquila) Ricerca Operativa Alcuni modelli lineari 19 / 51

Modelli

Problema dello zaino

Partiamo per un campeggio e dobbiamo preparare lo zaino. Ci sono 5

oggetti che vogliamo portare ma il peso totale supera i 12kg che

abbiamo deciso di sopportare. Per facilitare il processo di scelta

abbiamo assegnato a ciascun oggetto un valore (funzione utilità

cardinale): Oggetto 1 2 3 4 5

Peso 10, 4 4, 6 7, 0 3, 0 1, 4

Valore 100 60 70 15 15

Quali oggetti ci portiamo dietro massimizzando l’utilità ma rispettando

il vincolo di peso? dsm

Marco Castellani (L’Aquila) Ricerca Operativa Alcuni modelli lineari 20 / 51

Modelli

Problema dello zaino =

Indichiamo con x la quantità dell’oggetto i (con i 1, 5) che

. . . ,

i

portiamo: poiché un oggetto sarà preso oppure lasciato a casa la

variabile x assumerà i valori

i 1 se l’oggetto i viene portato

=

x

i 0 se l’oggetto i viene lasciato a casa

Dobbiamo massimizzare la funzione obiettivo

(x ) = + + + +

f x x x x 100x 60x 70x 15x 15x

, , , , 5 5

1 2 3 4 1 2 3 4

L’unico vincolo presente riguarda il peso totale dello zaino

+ + + + ≤

10, 4x 4, 6x 7x 3x 1, 4x 12.

5

1 2 3 4 dsm

Marco Castellani (L’Aquila) Ricerca Operativa Alcuni modelli lineari 21 / 51

Modelli

Problema dello zaino

Il problema assume la seguente forma

 + + + +

max 100x 60x 70x 15x 15x

5

1 2 3 4

 + + + + ≤

10, 4x 4, 6x 7x 3x 1, 4x 12

5

1 2 3 4

 ∈ {0,

x x x x x 1}

, , , ,

 5

1 2 3 4

ed è un particolare tipo di problema PLI detto probema booleano. La

(0,

soluzione del problema è 1, 1, 0, 0) corrispondente ad una

soddisfazione pari a 130. dsm

Marco Castellani (L’Aquila) Ricerca Operativa Alcuni modelli lineari 22 / 51

Modelli

La programmazione lineare

Tutti i problemi presentati si risolveranno con i seguenti strumenti:

i problemi di PL utilizzando l’algoritmo del simplesso in forma

primale oppure duale,

i problemi di PLI utilizzando

l’algoritmo del simplesso assieme al metodo di branch and bound,

◮ l’algortimo del simplesso assieme al metodo dei tagli di Gomory.

Sebbene i successivi problemi si possano risolvere con il metodo del

simplesso, data la loro particolare struttura, esistono algoritmi

opportuni migliori. dsm

Marco Castellani (L’Aquila) Ricerca Operativa Alcuni modelli lineari 23 / 51

Modelli

Problema del trasporto

Un’azienda elettrica ha 3 stabilimenti a, b, c che devono soddisfare le

esigenze di 4 città Ogni stabilimento fornisce il seguente

α, β, γ, δ.

quantitativo di kWh di elettricità:

35 milioni lo stabilimento a,

50 milioni lo stabilimento b,

40 milioni lo stabilimento c.

Il fabbisogno di kWh di elettricità delle quattro città è il seguente:

45 milioni la città α,

20 milioni la città β,

30 milioni la città γ,

30 milioni la città δ. dsm

Marco Castellani (L’Aquila) Ricerca Operativa Alcuni modelli lineari 24 / 51

Modelli

Problema del trasporto

Supponiamo che il costo (in milioni di euro) per mandare 1 milione di

kWh dipende dalla distanza che l’elettricità deve percorrere ed è

indicato nella seguente tabella

α β δ γ

a 8 6 10 9

b 9 12 13 7

c 14 9 16 5

Come soddisfare le esigenze di elettricità delle quattro città

minimizzando i costi di distribuzione? dsm

Marco Castellani (L’Aquila) Ricerca Operativa Alcuni modelli lineari 25 / 51

Modelli

Problema del trasporto

Il problema può essere sintetizzato attraverso la seguente tabella

costi–domanda–offerta Offerta

α β γ δ

a 8 6 10 9 35

b 9 12 13 7 50

c 14 9 16 5 40

Domanda 45 20 30 30 dsm

Marco Castellani (L’Aquila) Ricerca Operativa Alcuni modelli lineari 26 / 51

Modelli

Problema del trasporto

Il problema del trasporto è un particolare problema di flusso di costo

minimo su rete visualizzandolo attraverso un grafo:

HIJK

ONML

GFED

@ABC @ABC

GFED

a c

b

35 40

50

O

I

O o

>

I

/ u

O o

/

I O > o u

I

/ O / o u

I >

O

o

uu

O

o

O 5

16

8 6 10 9 13 9

9 7 14

12 >

/ I /

O u

oooo

O

I >

/ u

/

O

I > u

O

/ I /

O u

>

o

I O

/ u

/ oo

>

I O u

O

I

/ >

/

ooooo uuuu

O

I >

/ O /

I O >

I

/ /

O

>

I O

o

/ uu

/

O

I o >

O

o

I

/ / >

O

u

o

I O

o

/ u >

/

I O

oo u >

O

I

/ /

u O

o I >

/ O

u

o /

I O >

o u I

/ O

o /

u >

I O

ooo

/ u O

/

I >

uu O

I

/ >

/ O

o I O

ooo >

/ uuuu I / O >

I O

/ /

ooo O

I >

O

I

 O

z

@ABC

GFED HIJK

ONML @ABC

GFED @ABC

GFED

$

u

w '

o

α γ

β δ

45 30

20 30 dsm

Marco Castellani (L’Aquila) Ricerca Operativa Alcuni modelli lineari 27 / 51

Modelli

Problema del trasporto

Indichiamo con x la quantità di elettricità che inviamo dalla centrale i

ij

= =

(con i 1, 2, 3) alla città j (con j 1, 2, 3, 4); dobbiamo minimizzare la

funzione obiettivo

(x ) = + + + + + +

f 8x 6x 10x 9x 9x 12x

ij 11 12 13 14 21 22

+13x + + + + +

7x 14x 9x 16x 5x

23 24 31 32 33 34

I vincoli sono di produzione (non si può superare il livello di produzione

di ogni centrale) e di fabbisogno (si deve soddisfare la richiesta delle

città). dsm

Marco Castellani (L’Aquila) Ricerca Operativa Alcuni modelli lineari 28 / 51


PAGINE

51

PESO

555.94 KB

AUTORE

Atreyu

PUBBLICATO

+1 anno fa


DESCRIZIONE DISPENSA

In questo materiale didattico vengono trattati i seguenti argomenti. Introduzione alla Ricerca Operativa. Modelli ed esempi: problema di produzione; problema della dieta; un problema di turnazione; problema dello zaino. Programmazione lineare: definizione; problema del trasporto; problema di assegnamento; problema dell'albero ricoprente di costo minimo; problema del cammino minimo; problema di flusso massimo; problema del portafoglio.


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
Programmazione lineare
Dispensa
Algoritmi su grafi - Prima parte
Dispensa
Analisi numerica - Metodo delle secanti
Dispensa