Ottimizzazione lineare e Ricerca operativa

CSC

Mi da (P) → max z: -----vincoli (si)

• se mi da x dell (P)
• se non ho x₁ e variabilifreccio grafico → x₂vedo e trovo la S0 x

(…) (P) ILL. → (D) INAMM. √(P) INAMM. → (D) ha S0 F(P) INAMM → (D) INAMM F(P) AMM → (D) AMM. F

verifico se SA (sostituisco in (P) vedo chiuso/μ)traccio il (D) — SE VUOLE FAI GRAFICOSC I, SC II

sostituisco x nelle SCdove ε = 0,0 √ gli altri prendo se μ^* μ^*faccio sistema (basta moltiplicare per x)e trovo γ = y_{i j}← y^m

sostituisco γ in (D), verifico se SA (D)verifica: w(γ) ≟ z(x)per Teorema CSC ≟ Ξ so (P)Ξ so (D)

Grafi → RICHIESTE

1. (a) MAX FLUSSO CAMMINI AUMENTANTI → f_(x)
2. (b) TAGLIO DI CAPACITA MINIMA → C(W₀,W₀)

testo: flusso entranti = flusso uscentecammino aumentante se:AVANTI : x_ij < c_ijINDIETRO : x_ij > 0C_ij : CAPACITÀX_ij : FLUSSO

inizialmente considero tutti i flussi ≠ 0 (se sono dati convalora quelli)vedo i percorsifacciof₁ = min { c_ij - x_ij } (cammini AVANTI)f₂ = min { x_ij } (cammini INDIETRO)f₃ = min {Δi , f₁ , f₂ }

aggiungo (cammini AVANTI) o sottraggo (cammini indietro) il f sugli architrovato f_(x) = f_(x) + f₃ se l^∗ direzione ≠ o

quando non ho più cammini, ottieno f_(x) e il flusso MAX. (b) C(W₀, W₀) dove trovo quell'foliso a cui capacità ha lo stesso valore del FLUSSO MAX (che serve anche per flusso dell TAGLIO)

CSC

Mi da il (P) → max z: --- vincoli ( i )

• se mi da x̄ dell (P)
• se non ho x̄
• verifico se SA (sostituisco in (c), vedo che n[j/i])
• scairo il (D) ^{se vuole fai grafico}
• SC I, SC II
• sostituisco x̄ nelle SC

• (P) ILL→(D) INAMM. V
• (P) INAMM→(D) ha SO F
• (P) INAMM→(D) INAMM. F
• (P) AMM→(D) AMM. F

Grafi

→ RICHIESTE

• (a) MAX FLUSSO CAMMINI AUMENTANTI → f(x)
• (b) TAGLIO DI CAPACITA MINIMA

forw.:

• flusso entrante = flusso uscente
• cammino aumentante se AVANTI: x̄j < c̄j
• indietro: x̄j > 0

Inizialmente considero tutti i flussi = 0 ( se sono dati considero quelli )

• vedo i percorsi
• faccio f - = min {c̄j - x̄j} (cammini AVANTI)
• f - = min {x̄j} (cammini INDIETRO)

aggiungo (cammini AVANTI) o sottraggo (cammini indietro) il f̄ f sui flussi ARCHI

trovo f(x̄) = f(x̄) + d̄

quando non ho piu cammini, ottimo f(x̄) e il flusso MAX.

(b) dove trovo quel taglio a cui capacita ha lo stesso valore del flusso MAX (che serve anche il flusso del TAGLIO)

PREZZO OMBRA E INTERVALLO DI VALIDITÀ

Avrò un

max z :

(I)

• vincoli

• faccio grafico

x∗ = ^ls

x∗ è tanα S.O. - x∗∗

V.O.

sono intersezione di due vincoli (con +, )

(un vincolo sono sistematicamente VINCOLO (M))

(a) RICHIESTA: prezzo ombra VINCOLO (M)

a quel VINCOLO (M) aggiunjo "+ Δ" delle parte dei termini noti

P.O.

max z :

(I)

vincoli:

VINCOLO (M)^(n)

2x₁ + 3x₂ ≤ 10 + Δ

Andrò a fare la stessa intersezione da cui ho ricavato x∗

ma adesso considerando VINCOLO (M) diventà VINCOLO (M)

^fueltu con Δ^

< VINCOLO (N)^(n) >

etere vincolo

trovo x∗ = (x₁∗, x₂∗)

sono mi