Problemas resueltos investigacion de operaciones

Fundamentos de Investigaci´n de Operaciones o Investigaci´n de Operaciones 1 o
Formulaci´n de Modelos de Programac´n Lineal o o
25 de julio de 2003

La Programaci´n Lineal (LP) es una herramienta para resolver problemas de optimizaci´n que se o o caracterizan por tener como funci´n objetivo y restricciones combinaciones lineales de las variables de o decisi´n. La principal ventaja radica enque existe un algoritmo eficiente (SIMPLEX) para resolver o este tipo de modelos.

1.

Conceptos B´sicos a
Consideremos el siguiente ejemplo para describir los t´rminos presentes en todo problema de LP. e

Ejemplo 1. Una muebler´ produce mesas y sillas de madera. Cada mesa es vendida en $27000 y requiere $10000 ıa en materiales, adem´s, el costo de unitario por mano de obra se estima en$14000. En el caso de a las sillas, su precio de venta es de $21000 y los costos son de $9000 y $10000, en materiales y mano de obra respectivamente. La fabricaci´n de cada producto requiere de dos tipos de labores: carpinter´ o ıa y terminaciones. Una mesa requiere de 1 hora de carpinter´ y 2 horas de terminaciones. Una silla ıa requiere de 1 hora de carpinter´ y 1 hora de terminaciones. ıa Cadasemana, la muebler´ puede obtener todos los materiales que desee, sin embargo, se pueden ıa dedicar hasta 100 horas a las terminaciones y hasta 80 horas a la carpinter´ La demanda por mesas ıa. no est´ limitada, mientras que la demanda semanal m´xima por sillas es de 40. a a ıa a La muebler´ desea maximizar sus utilidades (ingresos - costos). Formule un modelo matem´tico que permita maximizar lasutilidades.

1.1.

Variables de Decisi´n o

Se debe comenzar definiendo las variables de decisi´n relevantes. En un modelo de programaci´n o o lineal las variables de decisi´n deben ser capaces de describir completamente las decisiones que puedan o ser tomadas y todas las variantes que existan. Antes de definir las variables de decisi´n es importante definir las unidades involucradas en el problema.o En este caso, se habla de unidades de sillas y mesas, de horas de trabajo por unidad y de demanda o o semanal. De acuerdo a ello, una buena opci´n para definir las variables de decisi´n consiste en asociar las variables al n´mero de unidades de sillas y mesas a producir por semana. Por lo tanto, podemos u definir: x1 = n´mero de mesas producidas por semana. u (1.1) x2 = n´mero de sillasproducidas por semana. u

1

Segundo Semestre 2003

Programaci´n Lineal o

1.2.

Funci´n Objetivo o

En un problema de LP, se debe tomar la decisi´n de maximizar (usualmente las utilidades) o o de minimizar (usualmente los costos) cierta funci´n de las variables de decisi´n. La funci´n a o o o maximizar o minimizar se denomina funci´n objetivo. Antes de formular el modelo matem´tico o aconviene resumir los datos del problema (Cuadro 1.1). Venta Mesa Silla Disponibilidad un. 27000 21000 –
$

Materiales un. 10000 9000 –
$

Mano de Obra un. 14000 10000 –
$

Carpinter´ ıa hr. un. 1 1 80

Terminaciones hr. un. 2 1 100

Dda. M´xima a un. sem. – 40 –

Cuadro 1.1: Resumen Ejemplo 1 En el ejemplo, los costos e ingresos no dependen del valor de x1 o de x2 , por lo tanto bastaconcentrarse en maximizar la diferencia entre: ingresos semanales − costos de materiales − costos por mano de obra (1.2)

Luego, se debe expresar los t´rminos anteriores en funci´n de las variables de decisi´n x 1 y x2 . e o o Supondremos que todas las sillas y mesas fabricadas son vendidas (respentando las condiciones de mercado del enunciado). As´ ı: ingresos semanales = = = Similarmente: costospor materiales costos por mano de obra = 10000x1 + 9000x2 (1.4) = 14000x1 + 10000x2 ingresos por mesas $ mesa mesas semana + + + $ silla ingresos por sillas sillas semana 21000x2 (1.3)

27000x1

Por lo tanto la funci´n a maximizar queda (en miles): o (27x1 + 21x2 ) − (10x1 + 9x2 ) − (14x1 + 10x2 ) = 3x1 + 2x2 (1.5)

Otra opci´n para construir la funci´n objetivo consiste en calcular...