Ottimizzazione lineare e Ricerca operativa

CSC

Mi dà il (P)

se mi dà x dall'ill (P)

• se non ho l'ammissibilità
• faccio gráfico

verifico se SA (sostituisco in P, vedo che vale y)

SCRIVO il (dual) ← SE VUOI FAI GRAFICO polo trovato X0, 2 (X)

SC I, SC II

sostituisco x nelle SC

• dove o = 0: ✔
• gli altri procedo per in
• faccio yizione (parte molteplica per x)
• tovo ÿ = y(1, ..., m)

sostituisco y in (o), verifico se SA (o)

verifica w(yi) ≡ z(x)

per Teorema CSC postfix x so (yi)

(P) ILL. = (o) INAMM. ✔

(P) INAMM. = (o) ha SO ✔

(P) INAMM. = (o) AMM. ✘

(P) AMM. = (o) AMM. ✘

Grafi - RICHIESTE

(c) MAX FLUSSO CAMMINI AUMENTATI -> ß(x)

(b) TAGLIÓ NI CAPACITÀ MINIMA -> C(W0, W0)

flusso entrati = flusso uscente

cammino aumentato se

• AVANTI: xij < cij
• INDIETRO: xij > 0

Inzialmente considero tutti i flussi = Θ (e se sono diet controllo quelli)

vedo i percorsi

• faccio fd = min { cij - xij }
• f_ = min { xij }

aggiungo (cammini avanti) o tolgo (cammini indietro) il fd ei flusi anche

tovo f(x) - fs(x) + fd

quedo non ho piu cammini, metuno f(x) e il fluso MAX

(b) C(W0, W0) - dove trovo quel tolgo la cui capacita ha lo fluso role se del FLUSSO MAX. (ch serve anche il fluso dell TAGLIO)

PREZZO OMBRA E INTERVALLO VALIDITÀ

Avvio un _{P. d'I.} max Z

• vincoli

faccio grafico

x₁

x = tasso SO.

*= sono intersezione di due vincoli (con *)(un vincolo serve staccamente vincolo (m))

(a) RICHIESTA: prezzo ombra vincolo (m)

a quel vincolo (m) aggiungi "+ Δ" delle parti dei termini not

_{P. d'I.} max Z:(1) vincoli

V INCOLO (N): 2x₁ + 3x₂ ≤ 10 + Δ

Andrà a fare la stessa intersezione che mi ha ricercato x *ma adesso considerendo VINCOLO (N) estirla VINCOLO (m)

V incolo (N)

altro vincolo trovo x * _{(x1, x2)}

sono in carlo Δ

Ora calcolo V.O. del P.d'I. (I) sostituendo alle F.O. i coeff. di x *_{(x1, x2)} → trovo Z' (Δ)Avrò già calcolato V.O. P.d'I (I) con x * = Z'

Ora farò Z'(Δ) - Z' _{(noto so rinter)} = numero . Δ

2n = PREZZO OMBRA VINCOLO (N)

(b) RICHIESTA: intervallo di realtà

preso x *_{(x1, x2)}

e sostitui ai VINCOLI iniziali del P.d'I.(sostituisco valori x₁ e x₂ (quesiti cioè) ai generici x₁, x₂ cioè vari vincoli)

troverò per ogni vincolo degli intervelli di Δmetto e potrire i vari intervelli di Δ e trovero ni A compreso tra due numeri

... < Δ < ...

sara intervello di veritàdel prezzo ombrerelaciono el VINCOLO (N)

Triangolarità matrici di base

ho M:

è triang.?

1. Scelgo riga con un solo coeff. non nullo
2. Cancello riga e colonna in corrispondenza di quel coeff.minore di (a)...minori perstqj (_{I, II, ...})
3. Riscrivo righe da _{I, II, ...}
4. Riscrivo colonne

traso M

Ogni matrice del prob del trasporto è triangulari dei base

mass z = x₁

(P)

• -x₁ + x₂ ≤ 2
• x₁ ≤ 8
• x₁ + x₂ ≤ 4
• x₁, x₂ ≥ 0

Supponiamo di sostituire F.O. z con z* = Cx₁ + Cx₂. Calcolare i valori di c per i quali la S.O. e il punto (4) rimane ottimo

^S₃S₂ = 0

S₃ = 0

S₀(6, 2)

max z = x₁

• -x₁ + x₂ + S₄ = 2
• x₁ + x₂ + S₂ = 8
• x₁ = + S₃ = 4
• x₁, x₂, S₄, S₃, S₂ ≥ 0

1° trovo graficamente S0

a_x1 + b_x2 + c = 0

Coef. Angolare -a/b

• 2° vedo quali sono le più rese realistiche
• 3° faccio m nelle inìnterelati
• 4° faccio m F.O. z* (con c)
• 5° vedo l'intervallo

VB = x₁, x₂, S₁

VNB = S₂, S₃

B = [A₁, A₂, A₃] = -1 1 1 1 0 0 1 -1 0

N = [A₄, A₅] = 0 0 1 0 0 1

B^-1 = 0 1/2 1/2 0 1/2 -1/2 1 0 1

C_N = 0

C_B = 1/c

Formule C_N^T - C_B^TB^-1N = (1/2 + 1/2/2 1/2_c) ≤ 0

Per via grafica: coeff. angolare z* = 1/c

1. m = +1
2. -1/c ≤ -1

-1 < c < 1

ES (Dualità - Trasporto)

a: ORIGINI: (30, 80, 40, 60)

b: DESTIN.: (10, 50, 20, 80, 20)

c: COSTI

matrice coeff. f.o.

INIZIO da ANG. NORD OVEST

SBA trovata con 8 componenti ≠ 0

SBA NON DEGENERATA (non ha cellelle = b-1)

ha solo cellelle vuote

9 eq. in 8 variabili

8 LIN. IND. 1 RIDOND.

rg = 8

UNICA SOL.

matrice INVERT. → t. matrice di BASE

1) soddisfatta → metto φ

0 = dx o sotto = cambio deprima

SBA generica (ho eliminato uno φ)

f* = 22

TAGLIO (W;W^)

• W = (1,3,4)
• W^ = (2,5,6,7)

capacità C (W;W^) = c₁₂ + c₄₆ + c₃₅ = 10 + 5 + 7 = 22

altro — TAGLIO W = (1,2)

W^ = (3,4,5,6,7)

C(W;W^) = c₂₆ + c₁₄ + c₁₃ = 15 + 40 + 10 = 35

flusso attraverso il taglio F(W;W^) = Σ x_ij - Σ x_ji

f(x) = F (W;W^) < C (W;W^)

essendo x flusso om....., (W₀,W^) TAGLIO t.c f(x) = C(W₀;W^)

allora x è flusso di valore max

e (W₀,W^) TAGLIO di CAPACITÀ MINIMA