SIMPLEX

Introducci´n
o
Ejemplo Simplex
Ejemplo Fase I

Ejemplos de Simplex
Nelson Devia C.
IN3701 - Modelamiento y Optimizaci´n
o
Departamento de Ingenier´ Industrial
ıa
Universidad de Chile

2011

Nelson Devia C.

Ejemplos de Simplex

Introducci´n
o
Ejemplo Simplex
Ejemplo Fase I

Contenidos

1

Introducci´n
o

2

Ejemplo Simplex

3

Ejemplo Fase I

Nelson DeviaC.

Ejemplos de Simplex

Introducci´n
o
Ejemplo Simplex
Ejemplo Fase I

Introducci´n
o
Consideremos el siguiente problema de optimizaci´n en R2 :
o
(P) m´x
a

x1 + 2x2
x1 + x2

≤4

x2

≤3

−x1 + x2

≤3

x1 , x2

≥0

Lo primero es llevar (P) a su forma est´ndar:
a
m´
ın

z = −x1 − 2x2
x1 + x2 + x3
x2

=4
+ x4

−x1 + x2

=3

(R2 )

+ x5 = 3

(R3 )x1 , x2 , x3 , x4 , x5 ≥ 0
Nelson Devia C.

(R1 )

Ejemplos de Simplex

Introducci´n
o
Ejemplo Simplex
Ejemplo Fase I

Introducci´n
o
Consideremos el siguiente problema de optimizaci´n en R2 :
o
(P) m´x
a

x1 + 2x2
x1 + x2

≤4

x2

≤3

−x1 + x2

≤3

x1 , x2

≥0

Matricialmente:
m´
ın

z = −1


−2

1
0
−1

0

0

1
1
1

1
0
0

x10 · x1 x2 x3 x4
 
x1

 
x2 
4
0 0
 
1 0 · x3  = 3
 
x4 
3
0 1
x5

x2

Nelson Devia C.

x3

x4

x5

≥0

Ejemplos de Simplex

x5

Introducci´n
o
Ejemplo Simplex
Ejemplo Fase I

Introducci´n
o
Consideremos el siguiente problema de optimizaci´n en R2 :
o
(P) m´x
a

x1 + 2x2
x1 + x2

≤4

x2

≤3

−x1 + x2

≤3

x1 , x2

≥0La regi´n factible de (P) es la siguiente:
o

Nelson Devia C.

Ejemplos de Simplex

Introducci´n
o
Ejemplo Simplex
Ejemplo Fase I

Inicializaci´n
o
El algoritmo necesita una base inicial factible (cualquiera) para comenzar
a iterar.
Recordemos que una base cumple que:
xi ≥ 0

∀i ∈ B

xi = 0

∀i ∈ B
/

Lo m´s sencillo es comenzar desde la base asociada al origen:
a
xB =Con esto se tiene

1
A B = 0
0

1
A−1 = 0
B
0
x3

{x3 , x4 , x5 }

xN =

{x1 , x2 }

que:
0
1
0
0
1
0


0
0 ,
1

0
0 ,
1



1
AN =  0
−1

1
AN =  0
−1

x4 Nelson Devia C.
x5


1
1 ,
1

1
1,
1

x1 de
Ejemplos x2 Simplex

 
4 
b = 3

3
 
4 
b = 3

3

R1
R2
R3
R1
R2
R3

Introducci´n
oEjemplo Simplex
Ejemplo Fase I

Inicializaci´n
o
Conociendo los valores de x1 y x2 es f´cil determinar los valores de las
a
otras variables, a partir del sistema:
x1 + x2 + x3
x2

=4
+ x4

−x1 + x2

=3
+ x5

=3

x1 , x2 , x3 , x4 , x5

≥0

Con esto se obtiene que:

x3 = 4
x1 = 0
⇒ x4 = 3
x2 = 0
x5 = 3

Nelson Devia C.

Ejemplos de Simplex

Introducci´n
o
EjemploSimplex
Ejemplo Fase I

Inicializaci´n
o
¿La base actual es ´ptima?
o

Para esto se calculan los costos reducidos, dados
c N = cN − cB AN
En este caso se tiene que:

1
cN
= −1 −2 − 0 0 0 ·  0
−1
x1 x2
x3 x4 x5
x1
c1 c2
= −1 −2
x1

por:


1
1
1
x2

x2

Como existen costos reducidos negativos, la base actual no es optima,
´
luego, se escoge la variable conmenor costo reducido para que entre a la
base:
Criterio de entrada a la base: m´ {c i }
ın
i ∈B
/

En este caso: m´ {c 1 , c 2 } = −2, luego x2 entra a la base.
ın
Nelson Devia C.

Ejemplos de Simplex

Introducci´n
o
Ejemplo Simplex
Ejemplo Fase I

Inicializaci´n
o
¿Qu´ variable sale de la base?
e
Se busca la primera variable b´sica que se anula cuando x2 crece:
a
Criterio desalida de la base:
m´
ın

ais >0

bi
ais

e
donde: ais es la i-´sima componente de la columna de AN = A−1 AN
B
asociada a la columna de la variable que sale (s) y b es la i-´sima
e
componente del vector b = A−1 b.
B
En este caso:
m´
ın

ai2 >0

b1 b2 b3
,
,
a1,2 a2,2 a3,2
x3

x4

x5

4 3 3
, ,
1 1 1

= m´
ın
x3

x4

=3
x5

Como tenemos un empate, da...