3 Simplex

Introducci´
on
Forma Est´
andar
Direcciones B´
asicas Factibles
M´
etodo Simplex

El M´etodo Simplex
Nelson Devia C.
IN3701 - Modelamiento y Optimizaci´
on
Departamento de Ingenier´ıa Industrial
Universidad de Chile

2011
Basado en Bertsimas, D., Tsitsiklis, J. (1997)
“Introduction to Linear Optimization”
Cap´ıtulo 3

Nelson Devia C.

El M´
etodo Simplex

Introducci´
on
Forma Est´
andarDirecciones B´
asicas Factibles
M´
etodo Simplex

Contenidos

1

Introducci´on

2

Forma Est´andar

3

Direcciones B´asicas Factibles

4

M´etodo Simplex

Nelson Devia C.

El M´
etodo Simplex

Introducci´
on
Forma Est´
andar
Direcciones B´
asicas Factibles
M´
etodo Simplex

Introducci´on
Se sabe que si un problema de programaci´
on lineal admite soluci´
on
o
´ptima, entonces existe una soluci´
on b´asica factible (sbf) que es soluci´
on
o
´ptima de ´este.
Esto implica que:

Si el problema tiene soluci´
on ´
optima u
´nica, ´esta es una
soluci´
on b´asica factible1
Si el problema tiene infinitas soluciones ´
optimas, al menos una
de ellas es una soluci´
on b´asica factible1
El m´etodo Simplex aprovecha esto y busca la soluci´
on ´
optima movi´endose
de una sbf a otra, a trav´es de las aristas delpoliedro factible, en alguna
direcci´
on que reduzca los costos.
En este cap´ıtulo se considerar´
a un problema en forma est´
andar, es decir:
m´ın

cx
Ax = b
x ≥0

1

sbf = v´ertice o punto extremo del poliedro factible
Nelson Devia C.

El M´
etodo Simplex

Introducci´
on
Forma Est´
andar
Direcciones B´
asicas Factibles
M´
etodo Simplex

Condiciones de Optimalidad
Como todo problema deprogramaci´
on lineal es representado
por un poliedro, basta con buscar ´
optimos locales, ya que en
un conjunto convexo todo ´
optimo local es un ´optimo global.
´
Optimo
Local: Un punto x ∗ es un ´
optimo local si ning´
un
punto factible cercano a ´el lleva a una mejora en la funci´on
objetivo.
Formalmente, x ∗ es un ´
optimo local de P si y s´olo si:
∃ε > 0,

∀x ∈ B(x ∗ , ε) ∩ P,

c x ≥ c x∗

Donde B(x∗ , ε) es una bola de radio ε centrada en x ∗

Nelson Devia C.

El M´
etodo Simplex

Introducci´
on
Forma Est´
andar
Direcciones B´
asicas Factibles
M´
etodo Simplex

Propiedades de la Forma Est´andar
Recordemos que el problema en forma est´
andar de la primera l´
amina es
una representaci´
on matricial del siguiente problema:
n

m´ın

ci xi
i=1
n

Ai xi = b
i=1

xi ≥ 0

i = 1, . . . , n

SeanB(1), . . . , B(m) los ´ındices de las variables b´
asicas para una sbf del
poliedro factible.

Recordar que en una sbf se tiene que
xi = 0, ∀i ∈
/ B = {B(1), . . . , B(m)}
El problema se puede escribir ahora separando las variables b´
asicas de las
no b´
asicas...
Nelson Devia C.

El M´
etodo Simplex

Introducci´
on
Forma Est´
andar
Direcciones B´
asicas Factibles
M´
etodo Simplex

Propiedades dela Forma Est´andar
m

n

m´ın

ci xi
i=1
n

Ai xi = b

m´ın

⇔

ci xi
i ∈B
/

m

AB(i) xB(i) +
i=1

i=1

xi ≥ 0

cB(i) xB(i) +
i=1

i = 1, . . . , n

Ai xi = b
i ∈B
/

xi ≥ 0 i = 1, . . . , n
En t´erminos matriciales, lo que se hizo fue reordenar las columnas de la
matriz A y las componentes de los vectores c y x, de manera que se
obtenga el mismo resultado:

⇒
Nelson Devia C.

El M´
etodoSimplex

Introducci´
on
Forma Est´
andar
Direcciones B´
asicas Factibles
M´
etodo Simplex

Propiedades de la Forma Est´andar

⇒
⇒

Nelson Devia C.

El M´
etodo Simplex

Introducci´
on
Forma Est´
andar
Direcciones B´
asicas Factibles
M´
etodo Simplex

Propiedades de la Forma Est´andar
Ahora el problema se puede escribir matricialmente de la
siguiente forma:
m´ın

cB xB + cN xN

(1)

AB xB + AN xN = b(2)

x ≥0

(3)

Sabemos que en una sbf, la matriz AB es de rango completo y,
por lo tanto, es invertible. Luego, de la ecuaci´on (2) se tiene:
−1
xB = A−1
B b − AB AN xN

Sean b = A−1
B b,

AN = A−1
B AN , por lo tanto:
xB = b − AN xN

En las sbf’s se tiene que xN = 0, luego xB = b
Nelson Devia C.

El M´
etodo Simplex

(4)

Introducci´
on
Forma Est´
andar
Direcciones B´
asicas Factibles
M´...