Riassunto esame Ricerca, prof. Pacifici, libro consigliato Lezioni di Ricerca Operativa, Fischetti

Name: Riassunto esame Ricerca, prof. Pacifici, libro consigliato Lezioni di Ricerca Operativa, Fischetti
Brand: Skuola.net
Price: 7.99 EUR
Availability: InStock
Rating: 4.0 (2 reviews)
Author: Betta_1991

Revisionato il 15/04/2026

di Betta_1991

Publisher

Vota 4,0/5 (2)

Contenuto verificato e approvato dal Team di Esperti di Skuola.net

Riassunto per l'esame di Ricerca operativa, basato su rielaborazione di appunti personali e studio del libro adottato dal docente Pacifici, Lezioni di Ricerca Operativa, Fischetti. Gli argomenti …

Esame Ricerca operativa

Facoltà Ingegneria

Dal corso del Prof. Pacifici Andrea

Università Università degli Studi di Roma Tor Vergata

A.A. 2012-2013

110 pagine

1 download

Appunto

Scarica

Estratto del documento

Ricerca Operativa

Alloc. Risorse Scarse

Disponendo di alcuni dati, ci viene detto di “massimizzare” il risultato, ovvero, il nostro obiettivo. Ad esempio:

Prodotti

A venduto a 2,5 €/l
B a 1,8 €/l

Risorse (D)

mix frutta 350 kg
l’heliceno 420 kg
il uomo 80 h

MATERIE ^{DISPONIBILITÀ}

MATERIE PRIME (M):

A (1l) 3 kg
C (1l) 22 kg

Occorre poi introdurre delle variabili di decisione per indicare quanto di A e quanto di B viene prodotto. I valori delle variabili rappresentano i punti ammissibili di Ω:

X = (^X_A/_{X_B}) > 0

Z f.o. => max 2,5 X_A + 1,8 X_B

vincoli PER RISORSE

3 X_A + 2,2 X_B < 350
0,2 X_A + 0,3 X_B < 420
0,03 X_A + 0,01 X_B < 80

Tutto ciò si può anche utilizzare:

max p^Tx

H ⋅ x < D

x > 0_n

M = # di variabili di decisione che si devono introdurre

Ricerca Operativa

Alloc. Risorse Scarse

Disponendo di alcuni dati, ci viene chiesto di "massimizzare" il risultato, ovvero, il nostro obiettivo.

Ad esempio:

Prodotti (P)
- A venduto a 2,5 €/l
- B 2 1,8 €/l

Disponibilità di alcune risorse (D)
- Mix frutta 350 kg
- Il cereale 420 kg
- Il uomo 80 h

Occorre poi introdurre delle variabili di decisione per indicare quanto di A e quanto di B viene prodotto. I valori delle variabili rappresentano i punti ammissibili di Ω.

x = ( xA xB ) > 0

Le f.o. -> max 2,5 x_A + 1,8 x_B

vincoli ->

3x_A + 2,2 x_B ≤ 350
0,2 x_A + 0,3 x_B ≤ 420
0,03 x_A + 0,01 x_B ≤ 80

Tutto ciò si può anche risolvere!

max . p T x H ≤ D x > 0 oppure min . ( - pT x ) H x ≥ D x > 0

M è il numero di variabili di decisione che si devono introdurre.

Il problema è illimitato se esiste un punto ammissibile x* ε Ω f.c. per ogni punto ammissibile f(x*) ≤ f(x)

→ Se Ω = ∅ il problema è vuoto

→ Se ∃ xε Ω f(x_x) ≤ k il problema è limitato

R' = ≥ {x>0} min (f-k)

Problema di KNAPSACK

max (_j=1³Σ c_j x_j)

Detti:

b ε R
oggetti j=1,2,3,..., m
ingombro a₁, a₂, a₃... a_m
valore c₁, c₂, c₃... c_m

Quale è la migliore combinazione ingombro/valore di oggetti per minimizzare l'ingombro e massimizzare il valore degli oggetti che inserisco?

Occorre vare delle variabili di decisione binarie

x_j ε {0,1}
1 = "Inserisco l'oggetto j"
0 = "Non inserisco l'oggetto j"
j=1...m

le variabili sono tante quante sono gli oggetti.

oggetti che inserisco → _j=1³Σ a_j x_j ≤ b

[=0 se x_j=0; =a_j se x_j=1]

es. b= 10 a_j → 5 2 2

c_j → 10 6 8

=3 { { } { } { } }

1_2α

→ 2³ sottoinsiemi possibili tra cui trovo la combin. Non ottimale!

1 prendo perché ingombrano poco

2 perché le var. di dec. è binaria {0,1}

Handshaking lemma

Avendo un grafo

Si definisce grado di un vertice il # di lati che hanno come suo dai due estremi quel vertice

Σ:u∈Vdu

Anteprima

Vedrai una selezione di 23 pagine su 110