Ricerca Operativa, Ottimizzazione per il problem solving - Esercizi commentati

RICERCA OPERATIVA

ESEMPI COMMENTATI

• Metodo del simplesso
• Dualità
• Analisi sensibilità
• Problema dei trasporti
• Algoritmi:
  • Dijkstra
  • Bellman Ford
  • Kruskal
• Flusso costo minimo
• Massimo matching
• Critical Path Method
• Flusso massimo - Ford Fulkerson
• Branch & Bound

ALGORITMI - TEORIA

METODO SIMPLESSO (rivoluzionato)

1. Calcolo z_B=c_B x_B
2. Calcolo i moltiplicatori del simplesso π^T = c_B B^-1
3. Calcolo costi ridotti delle var. fuori base r_D = e_D^T - π^T a_g

Se tutti gli r_j ≥0 STOP, x_B è ottima.

Altrimenti: passo 2: Scegliere r_g negativo ➔ il vettore a_g entra in base.

Calcolare ^y_j = B^-1 a_g e dividere i valori ottenuti rispettivamente per quelli di x_B = B^-1 b. Scegliere il minimo valore ➔ la var. rispettiva esce in base.

Passo 3: Se y_j ≤0 = STOP, problema illimitato

Passo 4: Sostituire in B il vettore che esce dalla base con il vettore che entra.

Calcola la nuova sol. di base x_B

Torna al passo 1.

SIMPLESSO DUALE

Passo 0: Data sol. no amm. primale, assum. duali che soddisfa le condizioni:

• ∀_j ∈ B v_j = 0
• ∀_i ∉ B π_i = e_i - z_i ≥ 0
• e ∃a_i ∈ B | x_i < 0 (no amm. primale!)

Passo 1: Se x_j ≥ 0, v_j STOP: la s.a.b. è corretta e OTTIMA.

Passo 2: Scegliere una r_j tale che b_p <0 per det. le var. che esce di base (1⩽p⩽m)

Passo 3: Calcola i rapporti ^k_j = \(\frac{c_j}{b_pj}\) con y_fj <0, j= 1,…,m

Se y_fj ≥ 0 STOP : non esiste s.a. primale

Altrimenti scegliere q=indice j con il rapporto ^c_j |minimo (q è la var che entra in base.

Passo 4: (p,q) è il PIVOT. Aggiorna il Tableau con le operazioni di pivot. Ritornare al passo 1.

ALGORITMO DEI TRASPORTI (o di Dantzig)

Passo 1: Trovare sol. amm. di base con il metodo dell'angolo N-O.ò

Passo 2: Calcolare i moltiplicatori del simplesso U_i, V_j e i coeff. di costi relativi \(\tag{r\_{ij}}\) = C_ij- U_i - V_j

Se \(\tag{r\_{ij}}\) ≥ 0 V_ij → STOP. Soluzione OTTIMA.

Passo 3: Considerare var non di base con \(\tag{r\_{ij}}\) < 0. ➔ Questa entra in base.

Individuare il ciclo “t”.

Pone θ uguale alla più piccola var. di base con segno -, aggiustare soluzione aggiungendo o sottraendo θ.

Dualità

Tabella Corrispondenze

• Primale
• Duale
• min z = c^Tx
• max v = b^Tλ
• R >=
• R = 0
• vincolo