Teoria ricerca operativa

Forma standard

Min c₁x₁ + ... + c_nx_n

s.v. a₁₁x₁ + ... + a_1nx_n = b₁

...a_m1x₁ + ... + a_mnx_n = b_m

x₁, ..., x_n ≥ 0

c = [ c₁ ... c_n ]

A = [ a₁₁ ... a_1n ]

b = [ b₁ ]

Min C^Tx

s.v. Ax = b

x = 0

Regione ammissibile

Regione ammissibile: ... sono insiemi convessi. L'intersezione di insiemi convessi è ancora un ...insieme convesso. ... otteniamo la regione ammissibile come intersezione tra insiemi convessi ...

Curve di livello

Curve di livello

Fascia di rette (parallele) che rappresenta la funzione obiettivo ...... Sono perpendicolari al vettore dei costi (retta)

Teorema fondamentale della PL

Con riferimento ad un problema di PL in forma standard con m×n e rango (A) = m, valgono le seguenti proposizioni:

1. Se esiste una soluzione ammissibile allora esiste una soluzione ammissibile di base.
2. Se esiste una soluzione ottima, allora esiste una soluzione ottima di base.

Forma standard

Min _{c1x1 + ... + cnxn}

s.v. a₁₁x₁ + ... + a_1nx_n = b₁

...a_m1x₁ + ... + a_mnx_n = b_m

x₁, ..., x_n ≥ 0

c = [c₁ ... c_n]

x = [x₁ ... x_n]

A = [a₁₁ ... a_1n...a_m1 ... a_mn]

b = [b₁...b_m]

Min Σ_j=1ⁿ c_jx_j

s.v. Σ_j=1ⁿ a_ijx_j = b_i ∀ i = 1, ..., n

x_j ≥ 0 ∀ j = 1, ..., m

Min c^Tx

s.v. Ax = b

x = 0

H

Regione ammissibile

Regione ammissibile:

Le rette e gli iperpiani avversi e anche i semipiani formati dalla retta sono insiemi convessi. L’intersezione di insiemi convessi è ancora un insieme convesso→ otteniamo la regione ammissibile come intersezione tra insiemi convessi (insieme nel quale si trova la soluzione ottima).

Curve di livello

Curve di livello

Fascia di rette (parallele) che rappresenta le funzioni obiettivo al variare di z. → sono perpendicolari al vettore dei costi (centro).

Teorema fondamentale della PL

Con riferimento ad un problema di PL in forma standard con m×n e rango (A) = m, valgono le seguenti proposizioni:

1. Se esiste una soluzione ammissibile allora esiste una soluzione ammissibile di base.
2. Se esiste una soluzione ottima, allora esiste una soluzione ottima di base.

(_n/^m) = n! / m!(n-m)! = 3! / 2! 1! = 3 ·2 ·1 / 2·1 = 3

max numero di soluzioni di base

Forma canonica

max _j=1^t c_jx_j

s.n. _j=1^t a_ijx_j + x_t+1 = b_i con i=1,...,m x≥0 t=n+m

⇒ max c₁x₁ + … + c_tx_t

s.n. a₁₁ x₁ + … + a_1t x_t + x_t+1 = b₁

a₂₁ x₁ + … + a_2t x_t + x_t+2 = b₂

.....

a_m1 x₁ + … + a_mt x_t + x_tm = b_m

x₁,...,x_m≥0

Infinite soluzioni ottime

→ Nella risoluzione grafica troveremo l’ottimo su una retta (che formerà un angolo zero con il vettore c)

→ Nel simplesso, se tra i coefficienti di costo (relativo all’ottimo) (riga 0) in corrispondenza di qualche variabile di base ci sono coeff di costo=0 allora abbiamo infinite soluzioni ottime.

Regola di Bland

Nell’interazione sul pivoting si sceglie la variabile uscente/entrante con l’indice più basso.

Metodo delle 2 fasi

P → Ps → Pc → Pfc

Simplesso 2 fasi

Fasi:

1. Attuazione → Si prova a costruire una prima soluzione ammissibile di base (tecnica delle variabili artificiali).
2. Se l'intersezione è guidata a buon fine si applica il metodo del simplesso per ottenere le prossime.
3. Se l'esito della fase è non è negativo la fase 2 non c'è.
4. A partire da Ps si costruisce il problema artificiale pad e si introducono le variabili artificiali_d1, ..., _dm, una in ciascun vincolo con coeff. 1.
5. Problema artificiale: _d1,...T_Art = ∑_d1 ... E_d1...

1. AX+bd=b x ≥ 0, d ≥ 0

il nuovo problema coincidente

Se pad=0 → conclude la fase 2

Se pad ≠ 0 → non c'è la fase 2, è completo dicendo che Ps è ammissibile e dei corrispettivi anche le p ottimizzano.

Teoria della dualità

Min c^x

1. cre

x∈IRⁿ=>Dual...w∈ Rⁿ...

Proprietà del duale

1. Il duale del duale è il problema di partenza

Teorema di dualità debole

Min c^Tx s.v. Ax = b x ≥ 0 (Ps) Max b^Tw s.v. A^Tw ≤ c (Ds)

Data x una soluzione ammissibile per Ps e w una soluzione ammissibile per Ds, vale la seguente relazione: b^Tw ≤ c^Tx

Dimostrazione: x ammissibile per Ps → Ax = b, x ≥ 0 w ammissibile per Ds → A^Tw ≤ c

In generale... b^Tw = c^Tx

Teorema di dualità forte

Se il problema primale ammette una soluzione ottima x', allora anche il problema duale ammette una soluzione ottima w' e vale la seguente relazione: b^Tw' = c^Tx'

Teorema

Se il problema primale è illimitato le corrispondente duale è inammissibile

Dimostrazione x₁, x₂, ... (successione di soluzioni) lim c^Tx_k = ∞ (k → ∞) problema di un illimitato b^Tw ≤ -∞ per il teorema di dualità debole Allora non può esistere una soluzione w** Se il problema primale è ammissibile, il corrispondente duale può essere illimitato o inammissibile.

Teorema degli scarti complementari

Min c^Tx      Max b^Tw

sv. _aix = b_i i = 1,...,m      =>      sv. w^TA_j ≤ c_j j = 1,...,n

x ≥ 0

Primale       Duale

* Due soluzioni ammissibili rispettivamente per P e Ds indicate con x e w sono ottime se e solo se valgono le seguenti relazioni:

(c_j - w^TA_j)x_j = 0      ∀ j = 1,...,n

Dimostrazione:

c^Tx = b^Tw      x teorema del duale forte

c^Tx - w^Tb = 0

c^Tx - w^TA x = w^T(Ax - b) = 0     (Ax = b)

=>(c^T- w^TA)x + w^T(Ax - b) = 0

(c^T- w^TA) x = 0      (A^Tw ≤ c => w^TA ≤ c^T => c^T - w^TA ≥ 0_n)

≥ 0_n      ≥ 0

Affinché il prodotto di 2 vettori non negativi, devono essere i prodotti delle singole componenti

(c_j- w^TA_j) x_j = 0      ∀ j = 1,...,n * CVD

Teorema degli scarti complementari per la coppia

Min c^Tx      Max b^Tw

sv. _aix ≥ b_i i = 1,...,m      =>      sv. w^TA_j ≤ c_j j = 1,...,m

x > 0_m         D

x e w sono ottime per P e D rispettivamente se e solo se

(c_j - w^TA_j) x_j = 0      ∀ j = 1,...,n

w_i (a_i x - b_i) = 0      ∀ i = 1,...,m

Metodo del simplesso duale

Il metodo del simplesso duale varia solamente le condizioni duali (se attiva alla prima iterazione raggiunge l’ottimo).

Se b_i ≥ 0 allora si è all'ottimo.

Altrimenti basta b_h > 0.

Se a_nk ≥ 0 va scelto di calcolare decidendo che è perturbata l'inammissibile.

Altrimenti tra le colonne l con a_hj si sceglie k tale che:          c_k/a_hk { Max } c_j/a_hy          a_nk ≤ 0

Significato del duale

"Avendo scelto di vendere tutte le proprie risorse prodotte, il manager aziendale deve stabilire il prezzo di vendita. /Le azienda deve fare in modo che la vendita delle e risorse risulti non meno conveniente della vendita dei beni prodotti mediante le loro risorse."

Analisi di sensitività

O_M^T   C_N^T = C_N^T - C_B^T A_B^-1 A_N   d_- = -C_B^T A_B^-1 b I     A_N = A_B^-1 A_N   B̅ = A_B^-1 b Se A_B è la matrice di base attiva, quota matrice resta ottima se e solo se resterà ammissibile per le primule. b_- intervallo b₁^' = b + d_eⁱ.

_b11 ⟶ _A12 ⟶ _O ⟶ _{b b¹ bⁱ b²}  ⟶  _{p perturbazione} ⟶ A_B^-1 b ≥ 0_m

A_B^-1 (b + d_eⁱ) ≥ 0_m A_B^-1 b + A_B^-1 d_eⁱ ≥ 0_m b + A_B^-1 (d_eⁱ) ≥ 0_m   ⟶ con questo arriviamo nel tollera b al posto A_B

Introduzione di un vincolo

P ⟶ Ω(P) ⟶ Ω(P) ⊇ Ω(P¹) ⟶ La regione a. di P¹ è contenuta in quella di P. P¹ ⟶ Ω(P¹)  ⟶⟶ x^* è l’ottimo di P ⟶ x^* ∈ Ω(P¹) ⟶⟶ x^* è l’ottimo di P¹

Se aggiungiamo vincoli quello che aggiungiamo è m+4. Che è: a_m+1 ≤ 5m+1

Prezzi ombra

Min ctx

s.v. Ax = b

x ≥ 0

⇒Max b^Tw

s.v. A^-Tw ≤ c

x = ( x_B ) = ( A_B^-1b )( x_N ) ( 0_m,n )

ε = c_B A_B^-1 b

w^T = c_B A_B^-1

Perturbiamo il elemento b_i della quantità b:

x^' = ( x_B^' ) = ( A_B^-1 b^' )( x_N^' ) ( 0_m,n )

ε^' = c_B^T A_B^-1 b^' = c_T b_N ( b + Δei )

Δε = ε^' - ε = c_B^T A_B^-1 b + c_B A_B^-1 Δei - c^T A_B^-1 Δei

Se i^th tale da una modifica alla base ottima posso semplificare la forma precedente Δε = c_B A_B^-1 (Δei) = w^T (Δei)

( w₁ w₂ ... w₄ w_n ... ) 0 = w_i Δ

Δ = w_i Δ ⇒ w_i = ΔεΔ

a_i x = b_i → vincolo che fa riferimento alla dipendibilità della risorsa :

→ valore marginale di una risorsa

Prezzi ombra