Programación Lineal Paso a Paso Grupo HETUES ® INVESTIGACIÓN DE OPERACIONES I PROGRAMACIÓN LINEAL PASO A PASO Henry E.
Views 10 Downloads 0 File size 47KB
Programación Lineal Paso a Paso
Grupo HETUES ®
INVESTIGACIÓN DE OPERACIONES I PROGRAMACIÓN LINEAL PASO A PASO Henry E. Tucto Espinoza1 ([email protected]) Ejemplo de Aplicación Nº 01 Un sastre hace un pedido a la empresa textil “Textiles TyC” 700 rollos de tela Poliseda, de 42 centímetros de ancho, 480 rollos de 50 centímetros de ancho y 1200 rollos de 70 centímetros de ancho. Si “Textiles TyC” sólo tiene rollos de tela de 1.45 metros de ancho. Expresar en un modelo de programación lineal para indicar de cómo debe cortarse la tela para cubrir el pedido con el mínimo desperdicio posible, sabiendo que el máximo desperdicio de tela que se puede aceptar es de 25 centímetros (las telas deben ser cortadas en 5 tipos). Solución. Construyendo una tabla con todos los datos para facilitar la solución. TC CR 42 50 70 Desperdicio
X1
X2
X3
X4
X5
3 0 0 19
0 1 1 25
2 1 0 11
1 2 0 3
0 0 2 5
Cantidad Pedido 700 480 1200
I. PLANTEO DE MODELO MATEMÁTICO 1. Identificación de Variables: El primer paso a seguir en el desarrollo de problemas de Programación Lineal (PL) es identificar las variables existentes en el enunciado. X1: Cantidad de rollo del corte de tipo 1. X2: Cantidad de rollo del corte de tipo 2. X3: Cantidad de rollo del corte de tipo 3. X4: Cantidad de rollo del corte de tipo 4. X5: Cantidad de rollo del corte de tipo 5. 2. Función Objetivo: Por lo común la función objetivo (FO) en la PL busca maximizar o minimizar: costos, utilidades, cantidad de producción, ventas, unidades, etc. Para el caso se busca Minimizar el desperdicio de corte de tela en función de los tipos de corte en metros de la tela de 1.35 metros. Min : C = 19 X 1 + 25 X 2 + 11X 3 + 3 X 4 + 5 X 5 © Copyright: Henry E. Tucto Espinoza (HETUES)
Programación Lineal Paso a Paso
Grupo HETUES ®
3. Restricciones: Como tercer paso debemos detallar o especificar las restricciones al cual esta inmerso el problema o enunciado, de acuerdo a los datos o condiciones que muestra en problema. Restricción de pedidos de rollos de tela de 42 centímetros: 3X1 + 2X3 + X 4 ≤ 700 Restricción de pedidos de rollos de tela de 50 centímetros: X 2 + X 3 + 2 X 4 ≤ 480 Restricción de pedidos de rollos de tela de 70 centímetros: X 2 + 2 X 5 ≤ 1200 Condiciones de no negatividad: X 1 ≥ 0; X 2 ≥ 0; X 3 ≥ 0; X 4 ≥ 0; X 5 ≥ 0 4. Modelo Matemático: Finalmente se realiza el modelo matemático del problema, este paso es el más importante puesto que involucra todo los demás pasos y si esta bien planteado nos facilita para determinar la solución optima por los diferentes métodos: Método gráfico, Método Simples, etc. Min : C = 19 X 1 + 25 X 2 + 11X 3 + 3 X 4 + 5 X 5 S. A. 3 X 1 + 2 X 3 + X 4 ≤ 700 X 2 + X 3 + 2 X 4 ≤ 480 X 2 + 2 X 5 ≤ 1200 X1 ; X 2 ; X 3 ; X 4 ; X 5 ≥ 0 II. SOLUCIÓN POR MÉTODO GRÁFICO Ejemplo de Aplicación Nº 02 Mediante la solución por el método gráfico encontrar la solución optima del siguiente modelo matemático: Max : Z = 129 X 1 + 186 X 2 S . A. 8 X 1 + 7 X 2 ≤ 840 10 X 1 + 17 X 2 ≤ 1700 X 2 ≤ 40 X1 ≥ 0 ; X 2 ≥ 0 Solución: Este método es muy sencillo, puesto que sólo consiste en graficar el modelo matemático considerándolo las variables (X1=X, X2=Y), es decir es como graficar inecuaciones de primer grado. Creo que la forma más simple de graficar rectas es identificando las intersecciones con el eje X (X1) y el eje Y (X2). © Copyright: Henry E. Tucto Espinoza (HETUES)
Programación Lineal Paso a Paso
Grupo HETUES ®
Entonces, los puntos por donde pasan cada una de las restricciones: Restricciones (1) 8 X 1 + 7 X 2 ≤ 840 (2) 10 X 1 + 17 X 2 ≤ 1700 (3) X 2 ≤ 40
Puntos X1 X2 0 120 105 0 0 104 136 0 IR
40
Luego, la gráfica que se obtiene es el siguiente:
En el gráfico, las líneas azules son las restricciones dadas, la recta morada (la inferior) es la grafica de la función objetivo y el de la parte superior no es mas que la prolongación del mismo (en forma paralela) hasta alcanzar el punto donde se encuentra ubicado la Solución Óptima (SO). En el gráfico observamos que la solución óptima (SO) es el punto de intersección de las restricciones (1) y (2), entonces considerando como un sistema de cauciones determinamos los valores de las variables. S . O. = (1) ∩ ( 2 ) 8 X 1 + 7 X 2 ≤ 840 10 X 1 + 17 X 2 ≤ 1700
⇒
X 1 = 36.06µ
∧ X 2 = 78.79µ
Por lo tanto obtenemos que: S. O. = (36.06; 78.79) unidades. Z = 129 × 36.06 + 186 × 78.79 = 19 306.68 [ Unidades monetarias ]
Donde Z es la función objetivo. © Copyright: Henry E. Tucto Espinoza (HETUES)
Programación Lineal Paso a Paso
Grupo HETUES ®
Ejemplo de Aplicación Nº 03 Una empresa fabrica los productos A, B y C y puede comercializar todo lo que produce a un precio de: 120, 350 y 680 dólares, respectivamente. El cuadro adjunto muestra los requerimientos de horas de trabajo, horas de acabado y materia prima por producto. Producto Trabajo A 5 Horas B 2 Horas C 3 Horas Disponibilidad 100 Horas
Acabado 2 Horas 3 Horas 1 Hora 200 Horas
Materia Prima 3 Unidades 7 Unidades 4 Unidades 500 Unidades
Basándose en los datos proporcionados Formule y construya el modelo de Programación Lineal, de manera que maximice los ingresos por ventas de la empresa. Solución 1. Identificación de Variables: Lo primero que debemos hacer es identificar y definir las variables de decisión y expresarlas simbólicamente. X1: Unidades a producir de producto A X2: Unidades a producir de producto B X3: Unidades a producir de producto C 2. Función Objetivo: Como ya sabemos que la FO sólo pude ser maximizar o minimizar, para el caso se trata de maximizar, la FO debe estar expresada como una función lineal. Objetivo: Maximizar ingresos de ventas de los productos A, B y C. Max : Z = 120 X 1 + 350 X 2 + 680 X 3 Escribir el objetivo de esta forma es expresar en unidades físicas uno de sus términos. Este término presenta la información específica de lo que contiene y permite confirmar la esencia física de lo que se está sumando y también que ello es consecuente con lo que se está obteniendo en el total de la ecuación; en este caso, ingreso en dólares. 3. Restricciones: En este punto deben definirse las restricciones y también expresarlas como funciones lineales. R1: Disponibilidad limitada de horas de trabajo; 5 X 1 + 2 X 2 + 3 X 3 ≤ 100 R2: Horas de acabado disponibles en este período; 2 X 1 + 3 X 2 + X 3 ≤ 200 R3: Disponibilidad limitada de unidades de materia prima; 3 X 1 + 7 X 2 + 4 X 3 ≤ 500 © Copyright: Henry E. Tucto Espinoza (HETUES)
Programación Lineal Paso a Paso
Grupo HETUES ®
De esta manera las restricciones están expresadas en unidades físicas. Se destaca en cada una de ellas alguno de sus términos, con indicación de lo que representa. Esto confirma que lo que se está sumando es consecuente con lo que se está obteniendo del lado derecho de la ecuación. 4. Modelo Matemático: Por último, incorporando las restricciones y las condiciones de no negatividad de las variables de decisión, se resume así el modelo matemático: Max : Z = 120 X 1 + 350 X 2 + 680 X 3 S . A. 5 X 1 + 2 X 2 + 3 X 3 ≤ 100 2 X 1 + 3 X 2 + X 3 ≤ 200 3 X 1 + 7 X 2 + 4 X 3 ≤ 500 X1, X 2 , X 3 ≥ 0 Ejemplo de Aplicación Nº 04 La Cámara de Industria del Perú promueve periódicamente servicios públicos, seminarios y programas de especialización. Actualmente los planes de promoción para este año están en marcha. Los medios alternativos para realizar la publicidad así como los costos y la audiencia estimados por unidad de publicidad, además de la cantidad máxima de unidades de publicidad en que puede ser usado cada medio se muestran en el cuadro siguiente. Restricciones Audiencia por unidad de publicidad Costo por unidad de publicidad Uso máximo del medio
Televisión
Radio
Prensa
10 000 2 000 $ 15
1 800 350 $ 20
4000 620 $ 10
Para lograr un uso balanceado de los medios, la publicidad en radio no debe exceder el 60% del total de unidades de publicidad autorizados. Además la cantidad de unidades solicitadas en televisión debe ser al menos 15% del total autorizado. El presupuesto total para promociones se ha limitado a 12.500 dólares. Solución 1. Identificación de Variables: Lo primero que debemos hacer es identificar y definir las variables de decisión y expresarlas simbólicamente. X1: Unidades de publicidad a contratar en televisión. X2: Unidades de publicidad a contratar en radio. X3: Unidades de publicidad a contratar en prensa. 2. Función Objetivo: Objetivo: Maximizar la audiencia total o cantidad de personas que ven la publicidad. © Copyright: Henry E. Tucto Espinoza (HETUES)
Programación Lineal Paso a Paso
Grupo HETUES ®
Max : Z = 1000 X 1 + 1800 X 2 + 4000 X 3 3. Restricciones: R1: Disponibilidad limitada de presupuesto para la publicidad: 2000 X 1 + 350 X 2 + 620 X 3 ≤ 12500 R2: Uso máximo de medios para la publicidad: X1 ≤ 15 R3: Uso máximo de medios para la publicidad: X 2 ≤ 20 R4: Uso máximo de medios para la publicidad: X 3 ≤ 10 R5: Publicidad limitada a un máximo de 60% en radio, con relación al total de unidades a contratar: X 2 ≤ 0.6 ( X 1 + X 2 + X 3 ) R6: La cantidad de unidades solicitadas en televisión debe ser al menos 15% del total autorizado. X 1 ≥ 0.15 ( X 1 + X 2 + X 3 ) 4. Modelo Matemático: Por último, incorporando las restricciones y las condiciones de no negatividad de las variables de decisión, se resume así el modelo matemático: Max : Z = 1000 X 1 + 1800 X 2 + 4000 X 3 S . A. 2000 X 1 + 350 X 2 + 620 X 3 ≤ 12500 X 1 ≤ 15 X 2 ≤ 20 X 3 ≤ 10
X 2 ≤ 0.6 ( X1 + X 2 + X 3 )
X 1 ≥ 0.15 ( X 1 + X 2 + X 3 ) X1, X 2 , X 3 ≥ 0 Ejemplo de Aplicación Nº 05 El Banco Azteca atiende de lunes a viernes de 8 a.m. a 4p.m. De experiencias pasadas sabe que va a necesitar la cantidad de cajeros señalados en la tabla dada. Hay dos tipos de cajeros: los que trabajan tiempo completo de 8 am a 4 pm, los cinco días, excepto la hora que utilizan para almorzar. Periodo de tiempo Cajeros requeridos
8-9am 9-10am 10-11am 11-12m 12-1pm 1-2pm 4
3
4
6
5
6
2-3pm
3-4pm
8
8
El Banco determina cuándo debe almorzar cada cajero, pero debe ser entre las 12m y la 1 p.m. o entre la 1 p.m. y las 2 p.m. A los empleados a tiempo completo se les paga 180 $ la hora (incluida la hora de almorzar). También hay trabajadores a tiempo parcial que deben trabajar exactamente 3 horas consecutivas cada día y se le paga 110 $ la hora, sin ningún otro pago. A fin de mantener la calidad del servicio el Banco desea tener un © Copyright: Henry E. Tucto Espinoza (HETUES)
Programación Lineal Paso a Paso
Grupo HETUES ®
máximo de 5 cajeros contratados a tiempo parcial, es decir, se desea minimizar los costos de empleados contratados. Bueno, este problemita lo dejo para ti, si me entendiste sé que lo harás.
==========================================================================
1
-
Henry E. Tucto Espinoza
Egresado de la EAP de Ingeniería de Sistemas e Informática de la Universidad de Huánuco. Analista y diseñador de aplicaciones en plataforma Microsoft. Asesoría y Consultoría en Proyectos de Investigación. http://henry-eduard-tucto-espinoza.neurona.com
==========================================================================
© Copyright: Henry E. Tucto Espinoza (HETUES)