Ejercicio de Programación Lineal: Fábrica de Juguetes de Madera

En Iquique, se está instalando una fábrica de juguetes que produce cuatro tipos de juguetes de madera. El proceso de fabricación está compuesto de tres etapas: corte, pintado y pulido. Dentro del próximo mes se dispone de 800 horas de máquina para corte; 1,000 horas de máquina para pintado y 340 horas-hombre para el pulido.

Los precios según tipo de juguete son los siguientes: $8, $14, $30 y $50 respectivamente. El camión de juguete ocupa 1 hora de corte, 1.5 horas de pintado y 30 minutos de pulido. El auto de juguete ocupa 2 horas de corte, 2 horas de pintado y 0.6 horas de pulido. El avión de madera ocupa 10 horas de corte, 4 horas de pintado y 60 minutos de pulido. El tren de madera ocupa 16 horas de corte, 5 horas de pintado y 2 horas de pulido.

La fábrica desea maximizar las utilidades dentro de este período.

Resultados del Modelo: Celda de Variables

Resultados del Modelo: Restricciones

Variables y Restricciones del Modelo

• X1: Cantidad de camiones de juguete producidos por mes
• X2: Cantidad de autos de juguete producidos por mes
• X3: Cantidad de aviones de juguete producidos por mes
• X4: Cantidad de trenes de juguete producidos por mes

Función Objetivo:

Maximizar Z: 8X1 + 14X2 + 30X3 + 50X4

Sujeto a:

1. 1X1 + 2X2 + 10X3 + 16X4 ≤ 800 (Horas disponibles de máquina de corte)
2. 1.5X1 + 2X2 + 4X3 + 5X4 ≤ 1000 (Horas disponibles de máquina de pintado)
3. 0.5X1 + 0.6X2 + 1X3 + 2X4 ≤ 340 (Horas-hombre disponibles para pulido)
4. X1, X2, X3, X4 ≥ 0 (No negatividad)

Ejercicio de Programación Lineal: Desarrollo de Software

Un Ingeniero Civil Informático desarrolló 3 tipos de programas que quiere vender para generar dinero extra (A, B y C). Estos programas son diferentes tanto en capacidad, diseño y complejidad. Se ha conseguido un programador, un diseñador y un Ingeniero en Sistemas para la generación de estos. Cada programa debe ser programado, diseñado y debe tener su propio sistema de información. Los tiempos en horas que requiere en cada proceso son los siguientes:

Los tiempos disponibles del programador, diseñador e Ingeniero en Sistemas son 15,000, 20,000 y 20,000 horas respectivamente. Los precios de cada programa son $1,000 para A y B y $2,000 para C.

No se podrán vender más de 1,000 programas de C.

Modelo de Programación Lineal

• X1: Cantidad de programas A
• X2: Cantidad de programas B
• X3: Cantidad de programas C

Función Objetivo:

Maximizar Z: 1000X1 + 1000X2 + 2000X3

Sujeto a:

1. 1X1 + 2X2 + 3X3 ≤ 15000 (Horas disponibles del programador)
2. 2X1 + 4X2 + 1X3 ≤ 20000 (Horas disponibles del diseñador)
3. 3X1 + 2X2 + 5X3 ≤ 20000 (Horas disponibles del Ingeniero en Sistemas)
4. X3 ≤ 1000
5. X1, X2, X3 ≥ 0 (No negatividad)

Ejercicio de Programación Lineal: Fruity Snacks

La compañía “Fruity Snacks” está decidiendo qué producir el próximo mes. De acuerdo a su inventario, poseen 500 kg de avellanas, 1,000 kg de maní y 500 kg de chocolate. Actualmente venden tres tipos de productos:

• “Sporty Mix”, que contiene 1 kg de cada ingrediente.
• “Crunchy Mix”, que contiene 2 kg de maní y 1 kg de avellanas.
• “Choco Crunch”, que contiene 2 kg de chocolate y 1 kg de maní.

Pueden vender cantidades ilimitadas de estos productos, a excepción de “Choco Crunch”, del que solo pueden vender hasta 100 unidades. Los precios de venta de cada producto son $2, $3 y $4 respectivamente.

Modelo de Programación Lineal

• X1: Cantidad (unidades) de Sporty Mix a producir.
• X2: Cantidad (unidades) de Crunchy Mix a producir.
• X3: Cantidad (unidades) de Choco Crunch a producir.

Función Objetivo:

Maximizar Z: 2X1 + 3X2 + 4X3

Sujeto a:

1. 1X1 + 1X2 + 0X3 ≤ 500 kg (Avellanas)
2. 1X1 + 2X2 + 1X3 ≤ 1000 kg (Maní)
3. 1X1 + 0X2 + 2X3 ≤ 500 kg (Chocolate)
4. X3 ≤ 100
5. X1, X2, X3 ≥ 0 (No negatividad)

Ejercicio de Programación Lineal: Actividades Diarias

Haz un listado de cinco actividades que realizas generalmente durante tu día. Elige las dos que más realizas. Las horas que las realices en el día serán tus variables. Crea cuatro restricciones asociadas a las variables anteriores. Por ejemplo, el tiempo mínimo de cada una, haz varias diferentes (incluir al menos 1 restricción con <= y otra con >=).

Además, indica cuál de las actividades prefieres más, y genérale una ponderación del 1 al 10.

1. Plantea el problema como un PL, describiendo variables, función objetivo y restricciones.

Lista de Actividades y Preferencia

Modelo de Programación Lineal

• X1: Cantidad de horas para jugar videojuegos por día
• X2: Cantidad de horas para escuchar música por día

Función Objetivo:

Maximizar Z (Preferencias): 10X1 + 9X2

Restricciones:

• X1 ≤ 5 horas (Máximo de horas para jugar videojuegos)
• X1 ≥ 1 hora (Mínimo de horas para jugar videojuegos)
• X2 ≤ 3 horas (Máximo de horas para escuchar música)
• X2 ≥ 1 hora (Mínimo de horas para escuchar música)
• X1, X2 ≥ 0 (No negatividad)

Ejercicio de Asignación: El Juego de Supervivencia

Comienza el juego, este consiste en agruparse, según el número que indique el anfitrión del juego. Hasta ahora, has logrado formar dos grupos de amigos. Para sobrevivir, idean una estrategia que les permita reagruparse entre ustedes sin levantar sospechas. Sin embargo, hay una condición clave: no pueden unirse compañeros del mismo grupo.

Por eso, deciden basarse en las distancias entre cada uno para planear cómo moverse lo menos posible y así formar los equipos rápidamente antes de que sea demasiado tarde.

A continuación, se presentan las distancias entre los jugadores en metros.

Tu misión es ayudar a los personajes a reagruparse con el menor esfuerzo posible y evitar que mueran en el intento. Usa la siguiente nomenclatura:

• i → Grupo 1: A = Jugador 388; B = Jugador 007
• j → Grupo 2: 1 = Jugador 456; 2 = Jugador 333; 3 = Jugador 246; 4 = Jugador 120

a) Crea un modelo de PL, tomando en cuenta que en el primer turno se pide hacer grupos de 2 personas, por lo que 1 integrante del grupo 1 se agrupará con otro jugador del grupo 2 y así sucesivamente.

Sean:

Xij =
{ 1 si el jugador i del Grupo 1 se empareja con el jugador j del Grupo 2
{ 0 si no

Donde: i ∈ {A, B} y j ∈ {1, 2, 3, 4}

Función Objetivo:

Minimizar Z = 1XA1 + 3XA2 + 2XA3 + 1.5XA4 + 2.5XB1 + 4XB2 + 3.5XB3 + 6XB4

Restricciones:

1. XA1 + XA2 + XA3 + XA4 = 1 (Cada jugador del Grupo 1 debe emparejarse con exactamente uno del Grupo 2)
2. XB1 + XB2 + XB3 + XB4 = 1 (Cada jugador del Grupo 1 debe emparejarse con exactamente uno del Grupo 2)
3. XA1 + XB1 ≤ 1 (Cada jugador del Grupo 2 debe emparejarse con a lo sumo uno del Grupo 1)
4. XA2 + XB2 ≤ 1 (Cada jugador del Grupo 2 debe emparejarse con a lo sumo uno del Grupo 1)
5. XA3 + XB3 ≤ 1 (Cada jugador del Grupo 2 debe emparejarse con a lo sumo uno del Grupo 1)
6. XA4 + XB4 ≤ 1 (Cada jugador del Grupo 2 debe emparejarse con a lo sumo uno del Grupo 1)
7. Xij ∈ {0, 1} (Variables binarias)

Ejercicio de Elección: Laberinto

3.- LABERINTO (15 PTS)

Bienvenido al juego final. Has sobrevivido… hasta ahora. Los jugadores restantes se dividirán en dos bandos: Rojos y Azules.

Tú, como líder del equipo Rojo, diseñas una estrategia implacable. El equipo Rojo debe asignar un jugador rojo a vigilar cada sala del laberinto.

Por ejemplo, si colocas un jugador Rojo en la puerta entre la Sala A y B, es capaz de vigilar ambas salas. Las puertas entre las salas son rutas de escape, y deben estar cubiertas.

Sin rutas de escape, los Azules no podrán huir. Hoy, nadie saldrá con vida. Sin segundas oportunidades.

Crea un modelo de PL para minimizar la cantidad de compañeros del equipo rojo a utilizar.

a) Xi =
{ 1 si se elige o coloca un jugador Rojo en la puerta i
{ 0 si no

Donde: i ∈ {1, 2, 3, 4, 5, 6, 7, 8, 9}

Función Objetivo:

Minimizar Z = X1 + X2 + X3 + X4 + X5 + X6 + X7 + X8 + X9

Xi ∈ {0, 1} (Variables binarias)

Ejercicio de Programación Lineal: Sastrería Falabella

La sastrería Falabella, en su afán por aumentar su cuota de mercado, ha decidido fabricar camisas formales y camisas casuales para hombres y venderlas a la tienda de retail Almacenes Suizos.

El proceso de producción se compone de: Corte, Confección y Empaque.

Se cuenta con 35 trabajadores en el área de confección, 25 trabajadores en el área de corte y 5 en empaque, quienes trabajan 8 horas al día. Con los datos entregados en la tabla:

Modelo de Programación Lineal

• X1: Cantidad de camisas casuales a fabricar
• X2: Cantidad de camisas formales a fabricar

Función Objetivo:

Maximizar Z: 8X1 + 12X2

Sujeto a:

1. 20X1 + 60X2 ≤ 12000 (Corte: 25 trabajadores * 8 horas/día * 60 min/hora)
2. 70X1 + 60X2 ≤ 16800 (Confección: 35 trabajadores * 8 horas/día * 60 min/hora)
3. 12X1 + 4X2 ≤ 2400 (Empaque: 5 trabajadores * 8 horas/día * 60 min/hora)
4. X1, X2 ≥ 0 (No negatividad)

Ejercicio de Transbordo: Operación Juegos del Calamar

En el año 2033, la hija del Jugador 456 decide poner fin a los Juegos del Calamar a nivel mundial. Como parte de su estrategia, planea destruir los dos principales centros donde se llevan a cabo: Corea del Sur y Estados Unidos. Para ello, propone desplegar soldados en ambas ubicaciones con el objetivo de ejecutar un ataque sorpresa, el cual debe llevarse a cabo con la mayor rapidez posible.

Para llevar a cabo su plan, ha identificado tres islas cercanas que pueden ser utilizadas como puntos de infiltración. A través de estas, se puede avanzar discretamente utilizando barcos mercantiles, lo que permite moverse de una isla a otra sin levantar sospechas y, finalmente, acceder a las bases enemigas en Corea del Sur y Estados Unidos.

La operación se coordinará desde dos bases de origen: la Base 1, con una dotación de 1,000 soldados, y la Base 2, con 1,500 soldados. Las velocidades de transporte (en horas) entre los distintos puntos se detallan a continuación.

Sabemos también que las islas son muy pequeñas, por lo que no se podrán enviar más de 900 soldados a la Isla Norte ni más de 1,300 a la Isla Sur. Además, la cantidad de soldados enviados desde la Base 1 a la Isla Sur debe ser menor que los enviados desde la Base 1 a la Isla Norte. Finalmente, se deben arribar al menos 900 soldados a Corea y 600 a EE. UU.

a) Realizar PL para minimizar el tiempo de la estrategia. Para el ejercicio usar las siguientes nomenclaturas:

• 1 = Base 1
• 2 = Base 2
• 3 = Corea del Sur
• 4 = EE. UU.
• A = Isla Norte
• B = Isla Sur
• C = Isla Central

b) Representa el resultado a través de un diagrama, indica el valor del objetivo (sin importar si está incorrecto).

c) ¿Se encuentra correcto el resultado? ¿Qué restricción(es) está incorrecto?

Ejercicio de Programación Lineal: El Minero

Usted es un ingeniero en minas y tiene a cargo 3 tipos de camiones (CATERPILLAR, LIEBHERR y KOMATSU), los cuales le generan dinero por cada vuelta realizada en la mina. Para generar una vuelta, debe pasar a través de 3 zonas llamadas FASE 1, FASE 2 y FASE 3. Cada camión tiene diferentes tiempos que demora por cruzar cada una de las fases, según las condiciones de esta.

Los tiempos en horas que requiere cada camión para pasar por cada una de las fases son los siguientes:

Mientras un camión está pasando por una fase, los otros no pueden ingresar a ese sector, y las fases solo estarán abiertas una cantidad de horas (esto debido a las tronaduras).

Los tiempos disponibles en la FASE 1, FASE 2 y FASE 3 son 15,000, 20,000 y 20,000 horas respectivamente.

La utilidad que genera cada camión por una vuelta son $1,000 para CATERPILLAR y LIEBHERR y $2,000 para KOMATSU.

Sin embargo, el camión de KOMATSU podrá dar un máximo de 1,000 vueltas.

Modelo de Programación Lineal

• X1: Cantidad de vueltas de camiones Caterpillar
• X2: Cantidad de vueltas de camiones Liebherr
• X3: Cantidad de vueltas de camiones Komatsu

Función Objetivo:

Maximizar Z: 1000X1 + 1000X2 + 2000X3

Sujeto a:

1. 1X1 + 2X2 + 3X3 ≤ 15000 (Horas disponibles en Fase 1)
2. 2X1 + 4X2 + 1X3 ≤ 20000 (Horas disponibles en Fase 2)
3. 3X1 + 2X2 + 5X3 ≤ 20000 (Horas disponibles en Fase 3)
4. X3 ≤ 1000
5. X1, X2, X3 ≥ 0 (No negatividad)

Ejercicio de Programación: JPMorgan Chase

3.- JPMorgan Chase tiene un problema de programación.

Los operadores trabajan turnos de 8 horas y pueden iniciar sus actividades a medianoche, 4:00 A.M., 8:00 A.M., mediodía, 4:00 P.M. u 8:00 P.M.

Los operadores se necesitan para satisfacer el siguiente patrón de demanda. Formule un modelo de programación lineal para satisfacer los requisitos de demanda con el menor número posible de operadores.

Variables:

• X1: Número de trabajadores que inician en el 1er período (Medianoche – 4 A.M.)
• X2: Número de trabajadores que inician en el 2do período (4 A.M. – 8 A.M.)
• X3: Número de trabajadores que inician en el 3er período (8 A.M. – mediodía)
• X4: Número de trabajadores que inician en el 4to período (Mediodía – 4 P.M.)
• X5: Número de trabajadores que inician en el 5to período (4 P.M. – 8 P.M.)
• X6: Número de trabajadores que inician en el 6to período (8 P.M. – medianoche)

Función Objetivo:

Minimizar Z: X1 + X2 + X3 + X4 + X5 + X6

Restricciones:

• X6 + X1 ≥ 4 (Demanda de Medianoche – 4 A.M.)
• X1 + X2 ≥ 6 (Demanda de 4 A.M. – 8 A.M.)
• X2 + X3 ≥ 90 (Demanda de 8 A.M. – mediodía)
• X3 + X4 ≥ 85 (Demanda de Mediodía – 4 P.M.)
• X4 + X5 ≥ 50 (Demanda de 4 P.M. – 8 P.M.)
• X5 + X6 ≥ 20 (Demanda de 8 P.M. – medianoche)
• X1, X2, X3, X4, X5, X6 ≥ 0 e Enteros (No negatividad y variables enteras)

Ejercicio de Programación Lineal: La Reconstrucción Urbana

3. La Reconstrucción:

Una ciudad al sur del país enfrenta un recorte presupuestario significativo, lo que implica una situación grave para su desarrollo.

Buscando una solución a largo plazo y sustentable, el consejo de la ciudad aprueba la demolición de un área de viviendas dentro de la ciudad y su reemplazo con un moderno desarrollo.

El proyecto implica dos fases:
Demolición de viviendas para así tener el terreno para el nuevo desarrollo, y construcción del nuevo desarrollo.

A continuación, un resumen de la situación:

• Se demolerán 500 viviendas populares. Cada casa ocupa un lote de 200 m².
• Los tamaños de los lotes para construir viviendas básicas, familiares, súper y extra, son de 130 m², 280 m², 320 m² y 330 m², respectivamente.
• Las calles, los espacios abiertos y el área para la instalación de servicios, ocupan el 15% del área total disponible.
• En el nuevo desarrollo, las unidades súper y extra deben representar al menos el 25% del total de viviendas.
• Las unidades básicas deben ser al menos el 20% de todas las unidades, y las unidades familiares deben construirse en un mínimo del 10%.
• El impuesto por unidad aplicado a las viviendas básicas, familiares, súper y extra es de M$1,100, M$1,800, M$2,900 y M$3,500, respectivamente.
• El costo de construcción por unidad de las viviendas básicas, familiares, súper y extra es de M$3,200, M$5,300, M$6,000 y M$7,500, respectivamente.
• El financiamiento a través de una donación local está limitado a M$5,500,000.

Modelo de Programación Lineal

• X1: Número de viviendas básicas a construir
• X2: Número de viviendas familiares a construir
• X3: Número de viviendas súper a construir
• X4: Número de viviendas extra a construir

Función Objetivo:

Maximizar Z: 1100X1 + 1800X2 + 2900X3 + 3500X4

Sujeto a:

1. 130X1 + 280X2 + 320X3 + 330X4 ≤ 85000 (Área disponible: 500 casas * 200 m²/casa * 0.85)
2. 3200X1 + 5300X2 + 6000X3 + 7500X4 ≤ 5500000 (Financiamiento)
3. X3 + X4 ≥ 0.25(X1 + X2 + X3 + X4) (Proporción de viviendas súper y extra)
4. X1 ≥ 0.2(X1 + X2 + X3 + X4) (Proporción de viviendas básicas)
5. X2 ≥ 0.1(X1 + X2 + X3 + X4) (Proporción de viviendas familiares)
6. X1, X2, X3, X4 ≥ 0 (No negatividad)