Ricerca Operativa - Esercizi d'esame

Esercizio 5: Il sig. Mario Rossi, di professione ambulante, deve predispore la propria bancarella

in vista di una fiera. Il furgoncino del sig. Rossi ha una portata massima di 400 kg di merce ed è stato quasi completamente riempito. Rimangono solo gli ultimi 12 kg di carico da decidere e i prodotti ancora a disposizione nel magazzino sono riportati nella tabella, con le caratteristiche di prezzo di vendita, peso e disponibilità. Formulare il problema della scelta delle confezioni di merce da caricare sul furgone che massimizza il valore delle possibili vendite in termini di disponibilità. Formulare il problema della scelta delle confezioni di merce da caricare sul furgone che massimizza il valore delle possibili vendite in termini di ottima.

• max 8x₁ + x₂ + 3x₃ + 7x₄ + 5x₅
• s. a.
  • k + x₁ + x₂ + 4x₄ + x₉ ≤t
  • 0 ≤ x₁ ≤8
  • 0 ≤ x₂ ≤7
  • 0 ≤ x₉ ≤6
  • 0 ≤ x₉ ≤10

z_i(u, i) = max ∑_i=0^u x_itag di (Ks - xi u_i -t)

[408]

Esercizio 1:

Si risolva il seguente problema di programmazione lineare intera con la tecnica del Branch and Bound.

max 4x₁ + 32x₂ + 48x₃ + 36x₄ + 20x₅ + 2x₆

4x₁ + 16x₂ + 12x₃ + 12x₄ + 10x₅ + 2x₆ ≤18

x₁, x₂, x₃, x₄, x₅ ∈ {0,1}

max 8y₄ + 36 y₇ + 12 y₈ + 7 y₅ + 7 y₆

y₁ + 2 y₂ + 15 y₃ + y₂ + y₄ + y₅ ≤ 3

y₃ ∈ {0,1}

y₁-4y₃

P₀

P₁

P₂

P₃

P₄

P₅

Ottimalità

Esercizio 2:

Si verifichi se il grafo disegnato in figura è bipartito, in caso affermativo si determini su di esso un matching di cardinalità massima.

B e D e L e G

V₁ A B A L

B

G

E

D

L

A

E

G A D I

M_B = {(B, F), (D, E), (A, L), (C, G)}

Ricerca di cammini aumentarti: m = ∅

Un cammino aumentante da v₅

Un cammino aumentante da v₃

*Ogni cammino aumentante deve aumentare la cardinalitá del matching di 1, altrimenti c’é un errore.

Esercizio 2:

Si consideri il grafo dell’esercizio precedente. Si verifichi se tale grafo è euleriano. In caso affermativo, determinare un ciclo euleriano. In caso negativo identificare, quali archi aggiunti al grafo lo rendono euleriano e determinare su questo nuovo grafo un ciclo euleriano.

Il grafo non è euleriano se v₆e v₈hanno grado dispari. Un grafo euleriano ha solo nodi di grado pari. Diventa euleriano aggiungendo l’arco (v₇, v₈).

C₁: v₁ - v₂ - v₅ - v₄ - v₁

C₂: v₃- v₂ - v₄ - v₃

C₁, C₂: v₁ - v₂ - v₇ - v₉ - v₃ - v₇ - v₁

C ₂, a₃ è un ciclo euleriano attraverso tutti gli archi del grafo una ed una sola volta.

Esercizio 3:

Si consideri il grafo dell’esercizio 2. Si verifichi se tale grafo è euleriano. In caso affermativo, determinare un ciclo euleriano. In caso negativo identificare, quali archi aggiunti al grafo lo renderebbero euleriano e determinare su questo nuovo grafo un ciclo euleriano.

Non è euleriano, i nodi E, L, S, C hanno grado dispari. Diventa euleriano aggiungendo gli archi (E-S) e (L-C)

• E-L-S-E-A
• L-S-M-R-Q-E-L-S-E-A
• C-M-L

• A-C-S-M-R-Q-E-L
• A-C-S-U-M-Q-E-Z-C-M-L-S-E-A

Esercizio 1:

Si risolva il seguente problema di programmazione lineare intera con la tecnica del Branch and Bound.

max

1. x₁ + 32x₂ + 48x₃ + 36x₄ + 10x₅
2. 16x₂ + 12x₃ + 12x₄ + 6x₅ ≤ 19
3. x₁,x₂,x₃, x₄, x₅ ∈ {0,1}

max

• x₁, x₂, x₃ , x₄ , x₅ ∈ {0,1}

1. xi = 0 , y⁰¹
2. xi = 1

1. zi = 59
2. y ^(1,0,0,0,1)

1. bound :
2. max

1. y^*(1,0,1,1,0,1)

1. Lx^*((1,0,1,1,0)) = (1,0,1,1)
2. zi* :

1. * i
2. max

Esercizio 4:

Dare una definizione di matrici unimodulari, totalmente unimodulari e fornire delle condizioni per verificare se una matrice è TUM. Dimostrare tali condizioni.

• Una matrice A di dimensioni n m (m s) si dice unimodulare se per ogni sottomatrice Q di A di ordine massimo (m) si ha det(A) ε {0, ±1}
• Una matrice A si dice totalmente unimodulare se per ogni sottomatrice quadrata Q, qualsiasi ordine si ha det(Q) ε {0, ±1 , ±1,1 ±3}
• Sia A tale che:
• Ogni colonna A a più di 2 elementi non u n

12 elementi non nulli che si tovano in I1, I2 diversi se la colonna ha 2