Investigación de operaciones - método simplex

Fundamentos de Investigaci´n de Operaciones o Investigaci´n de Operaciones 1 o M´todo Simplex e
1 de agosto de 2004

1.

Estandarizaci´n o

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´n de signo (srs). Antes de o emplear el m´todo Simplex para resolver un LP, elproblema debe ser convertido en uno equivalente e en el cual todas las restricciones son ecuaciones y todas las variables son no negativas. Esta versi´n o equivalente se denomina forma est´ndar del LP. a Para convertir un LP en su forma est´ndar cada desigualdad debe ser transformada en una iguala dad. Para ilustrar la t´cnica consideremos el siguiente ejemplo: e a ıneas: modelos de lujo y modelosregulares. Ejemplo 1 Una f´brica de zapatos de cuero produce dos l´ 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´n las variables: a x1 : n´mero de zapatos de lujo producidos a la semana u x2 : n´mero de zapatos regulares producidos a la semana u Luego, el modelo de LP queda (escribiendo la funci´n objetivo en decenas de miles): o Max s.t. z = 4x1 + 3x2 (Funci´n Objetivo) o x1 + x2 ≤ 40 2x1 + x2 ≤ 60 x1 , x2 ≥ 0 (a) Restricci´n de cuero o (b)Restricci´n de mano de obra o (c) Restricci´n de signo o (1.2) (1.1)

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´n. Luego, en la restricci´n (a) se tiene: o o s1 = 40 − x1 − x2 Similarmente, para la restricci´n (b) se tiene: o s2 =60 − 2x1 − x2 ´ o 1 2x1 + x2 + s2 = 60 (1.4) ´ o x1 + x2 + s1 = 40 (1.3)

Segundo Semestre 2004

M´todo Simplex e

Luego, cualquier combinaci´n (x1 , x2 ) satisface la restricci´n i s´lo si al reemplazar los valores se o o o obtiene si ≥ 0. Finalmente, la versi´n estandarizada del problema (1.2) queda: o Max s.t. z = 4x1 + 3x2 (Funci´n Objetivo) o (1.5)

x1 + x2 + s1 = 40 (a) Restricci´nde cuero o 2x1 + x2 + s2 = 60 (b) Restricci´n de mano de obra o 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 ≥ ≥ ≥ ≥ ≥ 500 6 10 8 0 (Funci´n Objetivo) o (a) (b) (c) (d) (e)

(1.6)

Para convertir unarestricci´n de tipo ≥ en una restricci´n de igualdad, se definen las variables de o o exceso ei . La variable de exceso ei representa la cantidad de sobresatisfacci´n de la restricci´n i, o o as´ para la restricci´n (a) se tiene: ı o e1 = 400x1 + 200x2 + 150x3 + 500x4 − 500 Similarmente: e2 = 3x1 + 2x2 − 6 ´ 3x1 + 2x2 − e2 = 6 o e3 = 2x1 + 2x2 + 4x3 + 4x4 − 10 ´ 2x1 + 2x2 + 4x3 + 4x4 − e3 = 10 o e4= 2x1 + 4x2 + x3 + 5x4 − 8 ´ 2x1 + 4x2 + x3 + 5x4 − e4 = 8 o (1.8) ´ o 400x1 + 200x2 + 150x3 + 500x4 − e1 = 500 (1.7)

Luego, cualquier combinaci´n (x1 , x2 , x3 , x4 ) satisface la restricci´n i s´lo si al reemplazar los valores o o o se obtiene ei ≥ 0. Finalmente, la versi´n estandarizada del problema (1.6) queda: o 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 = = = = 500 6 10 8 (Funci´n Objetivo) o (a) (b) (c) (d) (1.9)

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