Simplesso
Trattiamo problemi di PL della forma:
min cTx
A = bx
x ≥ 0
e possiamo ricondurre ogni problema nella sua forma standard:
min 3x1 - 2x2 + ωx3
f(x) = g(x1)
5x1 - x2 - 2x3 + xu = S
x1 + x2 + 2x3 = 1
x ≥ 0
xu ≥ 0
dove ad ogni punto ammissibile del problema iniziale, faccio corrispondere il punto ammissib. x̄(x1, x2, x3, S-(5x1+x2-2x3)),T dove xi (i=1...3) è la coordinata i-esima del punto ammiss. del primo problema x̄:
xu = S-(5x1+x2-2x3) ≥ 0
Dove xu è la variabile di slack.
Notiamo che:
f(x̄) = g(x̄)
Pg = ∅ <=> Pℓ = ∅
g ill. inf. <=> ℓ ill. inf.
x̄ sol ottima => x̄ solu. ott
Simplesso
Trattiamo problemi di PL della forma:
min cTx
x ≥ 0
e possiamo ricondurre ogni problema nella sua forma standard:
min 3x1 - 2x2 + 4x3
Sx1 - x2 - 2x3 + xu = S
x1 + x2 + 2x3 = 1
x ≥ 0
xu ≥ 0
dove ad ogni punto ammissibile del problema iniziale, faccio corrispondere il punto ammissibile:
x̄(x1, x2, x3, S-(Sx1 + x2 - 2x3)T) dove xi, (i=1...3) è la coordinata i-esima del punto ammissibile del primo problema x̄:
xu = S - (Sx1 + x2 - 2x3) ≥ 0
Dove xu è la variabile di slack.
Notiamo che:
Pg = ∅ ↔ Pe = ∅
gill.inf ↔ fill.inf
x̄ sol. ottima → x̄ soluz. ott
Variabili di slack e surplus
Osserva che ho un numero di variabili di slack e di surplus è pari al numero di disuguaglianze:
min 3x1-2x2+u3
5x1+x2-2x3≤5
x1+x2+2x3≥1
x ≥ 0
min 3x1-2x2+u3
5x1+x2-2x3+xu=5
x1+x2+2x3-xs=1
x ≥ 0
xu, xs ≥ 0
Variabili non positive
Se invece avessi un caso in cui x1 ≤ 0 introduco una nuova variabile:
x1*= - x1
min 3x1-2x2+u3
x1+x2+2x3≥1
x1, x3 ≥ 0
x1 ≤ 0
min -3x1*-2x2+u3
-5x1*+x2+2x3 ≤ 1
x ≥ 0
x1* ≥ 0
Variabili libere
Se invece una variabile xs è libera posso esprimerle come differenza di due numeri positivi:
xs = xs+-xs- con xs+, xs- ≥ 0:
min 3x1-2x2+u3
5x1-x2-2x3 ≤ 5
x1+x2+2x3 ≥ 1
x1 ≥ 0
x2 ≥ 0
min 3x1-2x2+u(x3+-x3-)
5x1-x2-2(x3+-x3-)=5
x ≥ 0
x3+, x3- ≥ 0
Nota che ora la corrispondenza non è biunivoca ma a noi interessa da destra a sinistra.
Es
min -3xλ+5xz-x3+xu
xλ+xz+x3+xu≤1
-5xλ-2xz+7x3≥u
6xλ+xz+x3-xu=1
5xz+2x3≤8
xλ≤0
x3≥0
xu≥0
Introduco xλ1=xλ, due variabili di slack e una di surplus e xz=xz1-xz2 con xz1, xz2 ≥0:
min 3xλ1+5(xz1-xz2)-x3+xu
-xλ1+(xz1-xz2)+x3+xu+xs=1
5xλ-2(xz
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Recensioni
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo
