Ottimizzazione lineare e Ricerca operativa

CSCMi

Da (P) → max z: ----- vincoli (si)

Se mi dà x del (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 grafico

SC I, SC II

Sostituisco x nelle SC

Dove ε = 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

• (a) Max flusso cammini aumentanti → f_(x)
• (b) Taglio di capacità minima → C(W₀,W₀)

Testo: flusso entranti = flusso uscente

Cammino aumentante se:

Avanti: x_ij < c_ij

Indietro: x_ij > 0

C_ij: capacità

X_ij: flusso

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

Vedo i percorsi

Faccio

f₁ = 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 archi

Trovato f_(x) = f_(x) + f₃ se l^∗ direzione ≠ o

Quando non ho più cammini, ottengo 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 del taglio)

CSCM

Mi dà il (P) → max z: --- vincoli ( i ) se mi dà x̄ del (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 capacità 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 più cammini, ottimo f(x̄) e il flusso max.

(b) Dove trovo quel taglio a cui capacità 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∗ = ^lsx∗ è 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) aggiungo "+ Δ" 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) diventa vincolo (M)^fueltu con Δ^etere vincolo trovo x∗ = (x₁∗, x₂∗)

Sono mi