Esercizi e guide Ricerca Operativa 2

esercizi svolti e spiegati di ricerca operativa 2 comprendenti i temi:
- branch and bound d'esame
- programmazione dinamica svolta passo passo
- piani di taglio
- algoritmo ungherese con guida step by step per impararlo
- algoritmo del matrimonio stabile
- matching d'esame
- esercizi sui grafi
- matrici unimodulari e totalmente unimodulari

Esame Ricerca operativa

Facoltà Ingegneria

Dal corso del Prof. Nicosia Gaia

Università Università degli Studi Roma Tre

Publisher -valeriap

A.A. 2020-2021

48 pagine

Appunto

Vota 3,0 / 5 (1)

Scarica

Estratto del documento

BRANCH & BOUND KNAPSACK [0,1]

max {5x₁ + 40x₂ + 38x₃ + 9x₄ + 1x₅}

{17x₁ + 5x₂ + 13x₃ + 3x₄ + 1x₅} ≤ 20

xᵢ ∈ [0, 1]

= B

È LA CAPACITÀ

DEL KNAPSACK DA NON SUPERARE!

il valore nella funzione obiettivo è il profitto
il valore nel vincolo è il peso dell’oggetto

PASO 1

ORDINOO GLI OGGETTI IN BASE AL PROFITTO (P/I)\ PER INSERIRE PRIMA GLI OGGETTI CON RAPPORTO MAGGIORE.

P₁: 5/17 = 0.29 → (5)
P₂: 40/5 = 8 → (3)
P₃: 38/13 = 2.92
P₄: 9/3 = 3
P₅: 1/1 = 1

quello appena scritto sarà il pila da usare per il branching

P_L0

RISOLVO IL PÙ RILASSATO PER INIZIARE IL BRANCHING ED INIZIALIZARE L'ALBERO INDIVIDUO L’OGGETTO CRITICO PER FARE BRANCHING.

u₁ = 5
u₂ = 3
u₃ = 13
u₄ = 3
u₅ = 0

B = 20 - 5 = 15

B = 15 - 3 = 12

B = 12 - 13 = 12

OGGETTO CRITICO

x^*: (1, 1, 12/13, 0, 0)

z = 40 + 9 + (38 * 12/13) = 84,07

P_L1

PONGO A UNO: L’OGGETTO U₃ COME PRIMO VINCOLO

u₁ = 5
u₂ = 3
u₃ = 13
u₄ = 3
u₅ = 0

B = 7 - 5 = 2

B = 2 - 3 = 1

OGGETTO CRITICO INSENSO 2/3

x = (1, 2/3, 1, 0, 0) z = 40 + (2/3 * 9) + 38 = 84

P_L2

u₁ = 5
u₂ = 3
u₃ = 13
u₄ = 9
u₅ = 0

B = 20 - 5 = 15

B = 15 - 3 = 12

B = 12 - 1 = 11

B = 11 - 6 = 6

x^* = (1, 1, 0, 1, 11/17)

z = 40 + 9 + 1 + (11/17 * 5) = 53,23

ALBERO PARZIALE

PL0 x*=(1, 11/13, 0, 0) z=84,07

PL1 x*=(1, 2/3, 1, 0, 0) z=84 U₂=1 U₃=1

PL3 x=(4/5, 1, 1, 0, 0) z=79
PL4 x=(1, 0, 1, 1/17) z=79,29
PL5 x=(1, 0, 1, 1, 0) z=79,1

PL2 x*=(1, 1, 1/17) z=53
PL6 INAMMISSIBILE

PL3 (5x)

FIGLIO DI PL1 PER CRITERIO BEST FIRST IMPOSTO U₂=1 OLTRA U₃=1

U₁=5 B=7-5=2 U₂=3 U₃=13 U₄=0 U₅=0 CRITICO! 5

Anteprima

Vedrai una selezione di 11 pagine su 48