Metodo sinmplex

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 for-
ma 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 problemadebe ser 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 igual-
dad. Para ilustrar la t¶ecnica consideremos el siguiente ejemplo:
Ejemplo 1 Una f¶abrica de zapatos decuero produce dos 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 representauna utilidad de 40 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 z = 4x1 + 3x2 (Funci¶on Objetivo)
s.t.
x1 + x2 · 40 (a) Restricci¶on de cuero
2x1 + x2 · 60 (b) Restricci¶onde mano de obra
x1; x2 ¸ 0 (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)
Similarmente, para larestricci¶on (b) se tiene:
s2 = 60 ¡ 2x1 ¡ x2 ¶o 2x1 + x2 + s2 = 60 (1.4)
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 z = 4x1 + 3x2 (Funci¶on Objetivo)
s.t.
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 z = 50x1 + 20x2 + 30x3 + 80x4 (Funci¶on Objetivo)
s.t.
400x1 + 200x2 + 150x3 + 500x4 ¸ 500 (a)
3x1 + 2x2 ¸ 6 (b)
2x1 + 2x2 + 4x3 + 4x4 ¸ 10 (c)
2x1 + 4x2 + x3 + 5x4 ¸ 8 (d)
x1; x2; x3; x4 ¸ 0 (e)
(1.6)
Para convertir una restricci¶onde tipo ¸ en una restricci¶on de igualdad, se de¯nen 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 ¶o2x1 + 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 z = 50x1 + 20x2 + 30x3 + 80x4 (Funci¶on Objetivo)
s.t.
400x1 + 200x2 + 150x3 + 500x4¡ e1 = 500 (a)
3x1 + 2x2 ¡ e2 = 6 (b)
2x1 + 2x2 + 4x3 + 4x4 ¡ e3 = 10 (c)
2x1 + 4x2 + x3 + 5x4 ¡ e4 = 8 (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),...