Ricerca Operativa - Simplesso

Simplesso

Trattiamo problemi di PL della forma:

min c^Tx

Ax = b

x ≥ 0

e possiamo ricondurre ogni problema nella sua forma standard:

min 3x₁ - 2x₁ + 4x₃

S_x + x₂ - 2x₃ + x_u = S

x₁ + x₂ + 2x₃ = 7

x ≥ 0

x_u ≥ 0

dove ad ogni punto ammissibile del problema iniziale, faccio corrispondere il punto ammiss.

x̅(x₁, x₂, x₃, S-(Sx₁+x₂-2x₃))^T dove x_i (i=1...3)

e' la coordinata i-esima del punto ammiss.

del primo problema x̅:

x_u = S-(Sx₁+x₂-2x₃) ≥ 0 corrisp. biumu

Dove x_u e' la variabile di slack

Notiamo che:

f(x̅) = g(x̅)

P_g = ∅ <=> P_e = ∅

g il. inf <=> f il. inf

x̅ sol ottima => x̅ soluz. ott

Osserva che ho un numero di variabili di slack e di surplus è pari al numero di disuguaglianze:

Se invece avessi un caso in cui x₁ ≤ 0 introdico una nuova variabile x^*₁= - X₁:

Se invece una variabile x_i è libera posso esprimere come differenza di due numeri positivi x_i = x⁺_i - x^-_i con x⁺_i,x^-_i ≥ 0 :

Nota che ora la corrispondenta non è bihumuca ma a voi interessa da destra a sinistra

Semplifichiamo la matrice dei vincoli attivi, notando che le righe l e m+1 sono opposte:

* se ho tutti i vincoli linearmente indip.,

allora vale la definizione:

x ammissibile è vertice

⇐>

le colonne della matrice A relative alle variabili positive sono linearmente indip.

Nota: se ho m vincoli e l variabili positive

la matrice delle colonne dei vincoli attivi per x è mxl con l>m allora

x non è sicuramente un vertice

=>

un vertice ha al più m variabili positive

Es

min -3x₁ + 5x₂ - x₃ + x_u

x₁ + x₂ + x₃ + x_u ≤ 1

-5x₁ -2x₂ + x₃ ≥ u

6x₁ + x₂ + x₃ - x_u = -1

5x_u + 2x₃ ≤ 8

x₁ ≤ 0

x₃ ≥ 0

x_u ≥ 0

Introduco x'₁ = -x₁, due variabili di slack e una di surplus e x'₂ = x₁-x₂ con x'₂, x'₂ ≥ 0:

min 3x'₁ + 5(x'₂ - x'₂) - x₃ + x_u

- x'₁ + (x'₁ - x'₂) + x₃ + x_u + x_s = 1

5x₁ - 2((x'₁ - x'₂) + x₃ - x₆ = u

-6x₁ + (x'₁ - x'₂) + x₃ - x_u = -4

5(x'₁ - x'₂) + 2x₃ + x₃ = 8

x'₁ ≥ 0

x'₂ ≥ 0

x₁ ≥ 0

x_u ≥ 0

x₃ ≥ 0

x₆ ≥ 0

x₂ ≥ 0

definizie il sistema

A x = (B; N) _{(XB) (Xn)} = _{(B Xe + N Xn = b)}

che ha soluzione

x = (_{(B^-1b ; 0)})^T

esempio. Sempre sul sistema di prima

→ ²(X_A) + ^-2(X_u = 3) _{1 1} = ₂2 (X_B) = _{1 2}

ha soluzione x = (1,1,0,0)

→ ¹(X_u) + ²(X_B = 3) _{2 1} = ₂2 (X_u) = _{1 2}

ha soluzione x = (0,0,0,1)

Def Una soluzione di base è ammissibile nel poliedro

A x = b, x ≥ 0

se (B^-1b ≥ 0)

Teorema

x̅ è un vertice

↓ ↑

x̅ è una soluzione di base ammissibile (SBA)

Dim : meglio che la vedi sul libro!

1° Test: Ottimalità

Ho la base che mi ha permesso di arrivare a

min c_B^TB^-1b + γ^Tx_N

con γ = c_N^T - c_B^TB^-1N

e il vertice alla base corrente è:

x̄ =

( B^-1b )

( 0 )

Il valore di x̄ è nel problema ridotto:

f_rid(x̄) = c_B^TB^-1b

• se γ ≥ 0, allora f_rid(x̄) è valore ottimo;
• se γ < 0, allora potrebbe esistere un'altra x̄∈P soluzione ottima per cui f_rid(x̄) < f_rid(x̄).

es

min x_A + 2x₂ + x₃ + x₄ + x₅ + x₆

x₁ + 2x₂ + 3x₃ + x_A = 3

2x_A - x₂ - 5x₃ + x₅ = 2

y₄ + 2x₂ - x₃ + x₆ = 1

x ≥ 0

Con base iniziale ammissibile B = {1,3,4}:

B = (

1 3 1

2 -5 0

1 -1 0

)

B^-1 = 1/3 (

0 -5 1

0 -1 2

3 1 -1

)

γ^T = c_N^T - c_B^TB^-1N = (10/3 -1/3 7/3)

con soluzione di base associato x_B = B^-1b

x_B = (1, 0, 0, 2, 0, 0)

Il valore nel problema ridotto e'

C_BB^-1b + y_jp̅

Posso scegliere un p̅ fino a che non incontro un altro vincolo dato da Πx_s ≤ B^-1b:

Per rimanere ammissibile devo prendere il piu' grande p̅ tra i π_ij ≤ (B^-1b)_j con π_ij > 0:

p̅ = min_j|πij>0 (B^-1b)_j / (Π_ij)

es

• 2p ≤ 1
• 3p ≤ 2 → p ≤ ¹/₃ => scelgo p̅ = ²/₃ per restare base
• a p ≤ 3 → p ≤ ³/_a ammiss. e per stare sul vin. accanto (mi sto spost.)

Considero dunque nel problema ridotto il punto (0...0,p̅,0...0) che nel problema iniziale e'

(B^-1b-Π_ip̅, 0...0, p̅, 0...0)^T

Questa e' una selezione di base con un cambiam. dove entra l'i-esima (che ha y_i < 0, la dimin. p piu' velocemente) ed esce la j-esima (quella che soddisfa p̅ = min...)