simplex 2003 2

Fundamentos de Investigaci´on de Operaciones
Investigaci´on de Operaciones 1
M´etodo Simplex
1 de agosto de 2003

1.

Estandarizaci´
on

Cuando se plantea un modelo de LP pueden existir igualdades y desigualdades. De la misma forma pueden existir variables que deben ser no negativas o bien sin restricci´on de signo (srs). Antes de
emplear el m´etodo Simplex para resolver un LP, el problema debeser convertido en uno equivalente
en el cual todas las restricciones son ecuaciones y todas las variables son no negativas. Esta versi´on
equivalente se denomina forma est´
andar del LP.
Para convertir un LP en su forma est´andar cada desigualdad debe ser transformada en una igualdad. Para ilustrar la t´ecnica consideremos el siguiente ejemplo:
Ejemplo 1 Una f´
abrica de zapatos de cuero producedos l´ıneas: modelos de lujo y modelos regulares.
Cada tipo modelo requiere un pie cuadrado de cuero. Un modelo regular necesita 1 hora de mano de
obra, mientras que un modelo de lujo requiere 2 horas de mano de obra. Cada semana se dispone de
40 pies cuadrados de cuero y de 60 horas de mano de obra. Cada zapato regular genera una utilidad
de 30 mil y cada modelo de lujo representa una utilidad de40 mil.
Para plantear el modelo se emplear´an las variables:
x1 : n´
umero de zapatos de lujo producidos a la semana
x2 : n´
umero de zapatos regulares producidos a la semana

(1.1)

Luego, el modelo de LP queda (escribiendo la funci´on objetivo en decenas de miles):
Max
s.t.

z = 4x1 + 3x2 (Funci´on Objetivo)
x1 + x2 ≤ 40
2x1 + x2 ≤ 60
x1 , x2
≥ 0

(a) Restricci´on de cuero
(b) Restricci´on demano de obra
(c) Restricci´on de signo

(1.2)

Para convertir cada desigualdad de tipo ≤ en una igualdad introduciremos una variable de holgura
si . Cada variable si (una por cada desigualdad de tipo ≤) representa la cantidad de recurso no empleado
de esa restricci´on. Luego, en la restricci´on (a) se tiene:
s1 = 40 − x1 − x2

´o

x1 + x2 + s1 = 40

(1.3)

´o

2x1 + x2 + s2 = 60

(1.4)

Similarmente,para la restricci´on (b) se tiene:
s2 = 60 − 2x1 − x2

1

Segundo Semestre 2003

M´etodo Simplex

Luego, cualquier combinaci´on (x1 , x2 ) satisface la restricci´on i s´olo si al reemplazar los valores se
obtiene si ≥ 0. Finalmente, la versi´on estandarizada del problema (1.2) queda:
Max
s.t.

z = 4x1 + 3x2

(Funci´on Objetivo)

x1 + x2 + s1 = 40 (a) Restricci´on de cuero
2x1 + x2 + s2 = 60 (b)Restricci´on de mano de obra

(1.5)

Para ilustrar como estandarizar desigualdades de tipo ≥ consideremos el siguiente ejemplo:
Ejemplo 2
Min
s.t.

z = 50x1 + 20x2 + 30x3 + 80x4
400x1 + 200x2 + 150x3 + 500x4
3x1 + 2x2
2x1 + 2x2 + 4x3 + 4x4
2x1 + 4x2 + x3 + 5x4
x1 , x2 , x3 , x4

≥
≥
≥
≥
≥

(Funci´
on Objetivo)
500
6
10
8
0

(a)
(b)
(c)
(d)
(e)

(1.6)

Para convertir una restricci´on de tipo ≥ enuna restricci´on de igualdad, se definen las variables de
exceso ei . La variable de exceso ei representa la cantidad de sobresatisfacci´on de la restricci´on i,
as´ı para la restricci´on (a) se tiene:
e1 = 400x1 + 200x2 + 150x3 + 500x4 − 500

´o

400x1 + 200x2 + 150x3 + 500x4 − e1 = 500 (1.7)

Similarmente:
e2 = 3x1 + 2x2 − 6
´o 3x1 + 2x2 − e2 = 6
e3 = 2x1 + 2x2 + 4x3 + 4x4 − 10 ´o 2x1 + 2x2 + 4x3+ 4x4 − e3 = 10
e4 = 2x1 + 4x2 + x3 + 5x4 − 8
´o 2x1 + 4x2 + x3 + 5x4 − e4 = 8

(1.8)

Luego, cualquier combinaci´on (x1 , x2 , x3 , x4 ) satisface la restricci´on i s´olo si al reemplazar los valores
se obtiene ei ≥ 0. Finalmente, la versi´on estandarizada del problema (1.6) queda:
Ejemplo 3
Min
s.t.

z = 50x1 + 20x2 + 30x3 + 80x4
400x1 + 200x2 + 150x3 + 500x4 − e1
3x1 + 2x2 − e2
2x1 + 2x2 + 4x3+ 4x4 − e3
2x1 + 4x2 + x3 + 5x4 − e4

(Funci´
on Objetivo)
=
=
=
=

500
6
10
8

(a)
(b)
(c)
(d)

(1.9)

Evidentemente, para modelos de LP que incluyan desigualdades de tipo ≤ y ≥, habr´a que agregar las
variables de holgura y exceso que sean necesarias seg´
un el tipo de restricci´on.
Si en un problema de LP existen variables sin restricci´on de signo (sea por ejemplo y), transformaremos esa...