Esercizi e guide Ricerca Operativa 2

Name: Esercizi e guide Ricerca Operativa 2
Rating: 3.0 (2 reviews)
Author: -valeriap

Revisionato il 31/05/2026

di -valeriap

Publisher

Vota 3,0/5 (2)

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

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 …

Esame Ricerca operativa

Facoltà Ingegneria

Dal corso del Prof. Nicosia Gaia

Università Università degli Studi Roma Tre

A.A. 2020-2021

48 pagine

Appunto

Scarica

Estratto del documento

LUGLIO 2019

BRANCH & BOUND KNAPSACK [0,1]

Max (5x₁ + 40x₂ + 38x₃ + 9x₄ + x₅)

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

B = capacità del knapsack da non superare!

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

PASSO 1

Ordino gli oggetti in base al profitto (P/W), per inserire prima gli oggetti con rapporto maggiore.

P₁: 5/17 = 0,29
P₂: 40/5 = 8
P₃: 38/13 = 2,92
P₄: 9/3 = 3
P₅: 1/1 = 1

Quello appena scritto sarà il pilota usato per il branching

PL0

Risolvo il PL rilassato per iniziare il branching ed inizializzare l'albero.

Individuo l'oggetto critico per fare branching.

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

B = 20 - 5 = 15
B = 15 - 3 = 12
B = 12 - 13 (oggetto critico)

x* = (1, 1, 12/13, 0, 0)

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

PL1

Pongo a uno l'oggetto u₃ come primo vincolo

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

B = 7 - 5 = 2

B = 2 - 3 = -1 (oggetto critico)

x* = (1, 2/3, 1, 0, 0)

z = 40 + (2/3 * 9) + 38 = 84

PL2

B = 20 - 5 = 15

B = 15 - 3 = 12

B = 12 - 1 = 11 (critico!)

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

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

BRANCH & BOUND KNAPSACK [0,1]

Max (5x₁ + 40x₂ + 38x₃ + 9x₄ + 1x₅)

17x₁ + 5x₂ + 13x₃ + 3x₄ + x₅ ≤ 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

ORDINO GLI OGGETTI IN BASE AL PROFITTO (P/N) PER INSERIRE PRIMA GLI OGGETTI CON RAPPORTO MAGGIORE.

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

max (40x₁ + 9x₂ + 38x₃ + 4x₄ + 5x₅)

45 riscrivo il primo con il 42

42 nuovo 43

43 variabile 41

quello appena scritto sarà il PILDA usare per il branching

PLO

RISOLVO IL PIÙ RILASSATO PER INIZIARE IL BRANCHING ED INIZIALIZZARE L'ALBERO. INDIVIDUO L'OGGETTO CRITICO PER FARE BRANCHING.

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

B = 20-5 = 15

B = 15-3 = 12

B = 12-13 OGGETTO CRITICO, ne inserisco 12/13

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

z = 40 + 9 + (38 × 12/13) = 84.07

PL1

PONGO A UNO L'OGGETTO U3 COME PRIMO VINCOLO

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

B = 7-5 = 2

B = 2-3 = 1 OGGETTO CRITICO, inserisco 2/3

x^* = (1,2/3,1,0,0)

z = 40 + (2/3 × 9) + 38 = 84

PL2

u₁ = 5
u₂ = 3
u₃ = 0
u₄ = 6
u₅ = 17

B = 20-5 = 15

B = 15-3 = 12

B = 12-1 = 11

B = 11-6 = 5 CRITICO!

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

z = 40 + 9 + 1 + (11/17 × 5) = 53.23

ALBERO PARZIALE

PL0x^* = (1, 1, 12/13, 0, 0)z = 84,05

PL1x^* = (1, 1, 2/3, 1, 0, 0)z = 84u₂ = 1u₃ = 1

PL2x^* = (1, 1, 0)z = 53

PL3x^* = (4/5, 1, 1, 0, 0)z = 79

PL4x^* = (1, 0, 1, 1, 1/17)z = 79,29

PL5x^* = (1, 0, 1, 0, 1)z = 79,29

PL6 INAMMISSIBILE

PL3 FIGLIO DI PL1 PER CRITERIO BEST FIRSTIMPOSTO u₂ = 1 OLTRE u₃ = 1

y₁ = 5
y₂ = 3
y₃ = 3,6
y₄ = 0
y₅ = 0

CRITICO! 5/4 → 4/5

B = - 7,9 : 3 = 4B = - 20,13 = 7

x^* = (4/5, 1, 1, 0, 0)z = (4/5 . 40) + 9 + 38 = 79

PL4 FIGLIO DX DI PL1 CON u₂ = 0

y₁ = 5
y₂ = 0
y₃ = 13B = 1CRITICO 1/17
y₄ = 0
y₅ = 0

Anteprima

Vedrai una selezione di 11 pagine su 48