Teoria fondamenti di ricerca operativa

Teoria LP: Forma standard

Vincoli di uguaglianza

Condizioni di non negatività sulle variabili. Funzione obiettivo di minimo. Se vogliamo portare il problema in forma standard:

• Se ho vincolo di >, tolgo una var. di scarto
• Se ho vincolo di ≤, aggiungo una var. di surplus
• Se non ho vincolo di ≥ sulle var., lo impongo

Forma canonica

Se voglio passare dalla F.S. alla canonica:

• Ax = b ⇒ Ax ≥ b ⇒ Ax > b ⇒ x ≥ 0

Definizioni

Soluzione: x ∈ R^m è soluzione se x verifica tutti i vincoli.

Soluzione ammissibile: x ∈ R^m è soluzione ammissibile se x verifica.

Soluzione ottima: x ∈ R^m è soluzione ottima se il costo di una.

Soluzione di base

Hp. Tengo (A): m = k = m Det (A_B) ≠ 0 A_B è quindi matrice di base.

Teoria LP: Forma standard (ripetizione)

Vincoli di uguaglianza. Condizioni di non negatività sulle variabili. Funzione obiettivo di minimo. Se vogliamo portare il problema in forma standard:

• Se ho vincolo di >=, tolgo una var. di slack -> -s = -
• Se ho vincolo di +s = -
• Se non ho vincolo di >= sulle var., lo impongo es. x₁ = x₁⁺ + x₁^-, x₊, x_- >= 0

Forma canonica (ripetizione)

Se voglio passare dalla F.S. alla canonica:

• min cX
• Ax = b
• Ax >= b
• X >= 0

Definizioni di soluzione

Definizione soluzione → X ∈ R^m è soluzione se X ∈ Tc verifica i vincoli Ax = b.

Soluzione ammissibile → X ∈ R^m = soluzione ammissibile se X ∈ Tc verifica Ax = b X ≥ 0.

Soluzione ottima → X ∈ R^m = soluzione ottima se il costo di una qualsiasi soluzione X è ∃ ∑yⱼAᵢ=0p⊂[0,m]∑x̄ᵢ+ εψᵢ = b Ψ (x̄ᵢ + εyᵢ <= x̄ᵢ/ᵢ) ⊆ R₊ Amm.

Dimostrazioni e casi

Dim 21 ∃ ℤ t.c. _A = b x ≥ 0 ℝ CASO 1 Vettori L.I. Si opera come nella dim. dell'ammissibilità.

CASO 2 Vettori L.D. A₁... A_p Quello che abbiamo fatto per ammissibilità era: = + ℤ soluzione ↔ ∀ ∈ [_ε, ℝ] Ammissibile. Per l’ottimalità occorre studiare il costo di una nuova soluzione: = rispetto alla vecchia. Questo differenzio anche con costo. c^t( + ) = c^t + c^t → c^t Conclusione: poiché ottimamo dove .. c = 0 e vecchio s.e. Se c^t t = (-); il che sarebbe un assurdo poiché è già se ottimo. Se c^t 0 e quindi otterrei il costo c^t = -; il che è di nuovo un assurdo Affermando quindi che c^t sono L.I., e dunque il loro prodotto scalare farà zero c^t = 0 Quindi → c^t( + ) = c^t

Geometria della S.L.

Def - Sottospazio - ℜ è un qualunque S ⊆ ℂ siamo chiuso rispetto a Somma vettoriale Prodotto vettore scalare S = { x(y) t.c. A℧ = 0 } Dimensione sotto spazio → coincide con il max num. di vettori L.I. Contenuti in S. THM - da S ⇔ { ∈ ℜ^m t.c. A℧ = 0 } → dim(S) = m - rango(A) Sottospazio affine → ottenuta per traslazione di un sottospazio S = { ∈ ℜ^m t.c. A℧ - b } DIM. sottospazio affine → coincide con dim del sottospazio Iperpiano -> È un sottospazio affine di dimensione m-1 H = {x ∈ ℝ^m T.C. α^T x = β}α^T (x̅ + εe) = α^T x̅ + ε α^T x= β NORMA > 0 Poliedro = intersezione di un numero finito di semispazi affini È una regione convessa Disequazione valida: α^T x ≤ β - D.V. per poliedro P quando P ⊆ { x ∈ ℝ^m : α^T x ≤ β}

Vertice

Consideriamo un poliedro P = { x | A x ≤ b} Dato x̅ ∈ P. Ã = vincoli T.C. Ã x̃ = b. Se il rango (Ã) = m, allora x̃ è vertice. Ogni soluzione di base è un vertice del poliedro. Non è vero l’inverso se abbiamo la degenerazione questa corrispondenza non è bionivoca.

Simplex

Il simplesso parte da una soluzione che sia di base e ammissibile e mantiene l’ammissibilità. Il simplesso si sposta sui vertici adiacenti. Condizione sufficiente di ottimalità: Il simplesso lavora in forma standard:

• min c^T x
• Hp. m ≤ m Ax = b
• Rango (A) = m
• X ≥ 0

Soluzione di base

Dobbiamo costruire una soluzione di base avendo A come matrice posso prendendo AB con AB ∈ ℝ^m e det (AB) ≠ 0, quindi invertibile, la soluzione associata a tale base è x̅ = Vogliamo valutare il costo di questa soluzione: c^T x̅ = = = c^T x̅_B Dobbiamo confrontarlo con una soluzione ammissi.

Valutazione del costo

[A_B A_N]

|X_B| = |b|

|X_N| |0|

A_BX_B+A_NX_N=b

X_B=|b-A_NX_B|

X_B=A_B^-1b-A_B^-1A_NX_NX=|X_B| |X_N|

Costo della soluzione X

Quindi possiamo valutare il costo di X e lo confrontarlo con X se ε una sol. ottima.

cⁿx=|c_B c_N| [A_B^-1 b-A_N X_B^-1 ]=c_BA_B^-1b-c_BA_B^-1A_NX_N+c_NX_N=c^ⁿX_B+[C_N^{-C_BA_B-1A_N]X_N=CⁿX_Bⁿ+C_NX_N}

_{Costo vecchia}

_{CN coefficienti}

_{Costo Nodo} Per le soluzioni ammissibili X_N≥0. Se C_N>0 il costo della nuova soluzione ≥ di quella vecchia. Quindi se C_N>0 possiamo concludere che la X bar ε ε ε ottima

Dizionario del Simplex

ζ=C′X+C_NX_NX_E=Condizione necessaria e sufficiente di ottimalità C_N>0 e non degenerazione_{direzione di crescita ammissibile è decrescita}

Condizione sufficiente di ottimalità

Cosa succede se J ∌ IN (fuori base) t.c. δ_j<0? La condizione sufficiente di ottimalità ci suggerisce quale variabile sarebbe opportuno ridurre ad aumentare il valore, quindi potenzia rimase per πρµζιωνρωµευνεπιων.

X+δ_i γ_jε|X_B| |X_B| X_BX_B+A_NX_N=b|X_N||X_N|X=AB^-1b-AB^-1A_NX_N

Scegliamo un X_j di X_NX_B(δi)=δ_jγ_jε|δε_i|X=AB^-1b-S_j AB^-1A_Nsubs|δε_i|

Nuova soluzione x^e

Quindi la nuova x^e è soluzione di Ax=b, ma è ammissibile? Devo vedere se tutte le componenti sono y_j ≥ 0. Considerando y = A_B^-1 A_N:

x = | _{XB + δj y} | | _{δj ej} |{ δ_j ≥ 0 Se questo è vero ho X_B + δ_j y ≥ 0 Se y_i ≥ 0 ho ammissibilità gratuita X_B + δ_j y_i ≥ 0 Se y_i < 0 devo scegliere δ_j ← ^X_Bi / _yi> 0 per ammissibilità Scelgo il passo δ_j ≤ min_{i.tc. yi < 0} ^X_Bi / _yi Valutando i costi, e quindi max miglioramento:

c^t x = c^t x + c_N X_N = c^t x + Ĉ_j δ_j δ_j essendo > 0 e essendo contenuto in un range m conviene prendere δ_j max, per minimizzare i costi Chiaramente se entra in base una nuova variabile, qualche altro esce dalla base ed è quello che ha la condizione del passo più stringente.

Correttezza dell'operazione di pivot

PIVOT

B = { ...^l ... (*)} N = { ... (_) ...} La variabile che entra in base garantisce i vettori lini L'operazione di pivot preserva l'indipendenza lineare dei vettori selezionati A_B = [A₁ | ... | A_ω] matrice di base x_j va entrante (j ∈ N) x_θ v un uscente (j ∈ B) A_B = [A₁ A₊₊ A_j A_j⁺ A_m]

Vogliamo quindi assicurare che A_B^-1 è una matrice di base N = Σ_i A_{j+i (in iter simplicesso coincide con Aj)} N può essere sommato con Aⁱ se e solo se λⁱ ≠ 0 Condizione sufficiente → se λⁱ = 0 allora A_B è una base Dati i moltiplicatori μ_i l'unica combinazione lineare che annulla mΣ_i μ_i a_i = 0 e μ_i ≠ 0 ∀ i.1/m Σ_i=1ⁱ⁼⁷Σ_i=1^i=m μ_i A_i = μ_i A_i + μ_i A_i = 0

Σ_i=1^i=m μ_i x_α A^α = 0 μ₁*μ_t*V = λ = 0 Per μ_i = 0 ∀ i ≠ i^* μ₂*λ^*= 0 0 Pen Hp λ_i^* ≠ 0 -> Quindi μ_i^* = 0 Quando μ sono tutti nulli e λ_n di Ab formano una base Condizione necessaria 1. Se ab^-1 è una base allora λ^* ≠ 0...m/en...[1, Â…], = A_m... La funzione di pivot quindi parte di una base e arriva a una base...0. δ* < 0 costo diminuisce - δ* = 0 riasciclo ciclo infinito

Algoritmo del Simplesso

1. Ab det (Ab) ≠ 0 Xb = Ab^-1 b > 0...
2. Se č_n ≥ 0 allora stop (costo ottimo), altrimenti vado al 4
3. Scelgo un indice j ϵ N.C. č_j < 0...
4. Se y > 0 allora stop (problema illimitato), altrimenti vado al 7
5. Determinato x^* = arg min Pivot mi v^* = e_j^*

Algoritmo del Simplesso a parole

Calcolo i costi ridotti Control costi ridotti... Sceglio la v. entrante Vedo se problema è illimitato (passo) Sceglio la var uscente Faccio il pivot

Scelta delle variabile entrante

1. Regola anticao di buon (si basa solo sull'indice della variabile)... 1. Scelgo il v.a.r. con costo ridotto più negativoⁱ arg min _j∈T con ^{c_j - z_j} || _{zj < 0} [dove controlliamo tutti] 3) Complesso di scelta del coefficiente di costo ridotto non tra [1, kk negativo] 4) Costruirlo c_j* e prendilo il più grande di questo prodotto tra i j per ottenere il max miglioramento

Scelta della variabile uscente

Dobbiamo migliorare la condizione più stringente sul passo: min ^X_bi/_{yi < 0} Se avessimo più variabili che ci danno lo stesso passo minimo posso usare la regola anticiclo disegna A⁺ = min t.c. { min ^X_bi/_{yj < 0} }

Simplex 2 Fasi

Applico un simplex a 2 fasi quando per un problema di PL in FS non ho una soluzione di base di partenza min c^tx(P) A^tx <= d X >= 0 Moltiplico per -1 Posso poi associare delle variabili ausiliarie una per vincolo del problema P, generando così: il problema ausiliario P.A. vado a risolvere il P.A. in cui si minimizza la somma delle variabili ausiliarie min Σx₀ di X = 0| var origine | var ausiliarie Essendo un funzione obiettivo che minimizza variabile > 0 non posso ottenere che il problema ausiliario sia illimitato, poiché il valore minimo che posso ottenere è 0. Il simplex lo face a 2 esiti:

1. Functione obiettivo P.A. > 0 Per P vuoto per assurdo supponiamo che

∃x' Ax' <= b DM= [1^nx'0] assumendo questa soluzione dev P.A.e f.o. sarebbe >= 0 che va contro il testo f.o. > 0 Functione obiettivo f.o. = 0 Per davvero i 3 casi:

A) Sol. di base ottima del problema, non ci sono X_m in base Quindi è soluzione di base ammissibile per P.