Simplesso
Trattiamo problemi di PL della forma:
min cTxA = bx ≥ 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 problemainiziale, 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 cTxx ≥ 0
e possiamo ricondurre ogni problema nella sua forma standard:
min 3x1 - 2x2 + 4x3Sx1 - x2 - 2x3 + xu = Sx1 + x2 + 2x3 = 1
x ≥ 0xu ≥ 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.infx̄ sol. ottima → x̄ soluz. ott
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
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
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
