Modelado con Programación Lineal
Índice:
• Modelado de Programación Lineal.
• Ejercicios prácticos de PL.
2
Objetivo
Analizar la programación lineal, con el objetivo de
optimizar la toma de decisiones.
3
EL ARTE DEL MODELADO
4
FASES DE UN ESTUDIO DE IO
Para implementar la IO en la práctica, las fases principales son:
1. Definición del problema.
2. Construcción del modelo.
3. Solución del modelo.
4. Validación del modelo.
5. Implementación de la solución.
5
FASES DE UN ESTUDIO DE IO
La definición del problema implica definir el alcance del problema
investigado.
El objetivo es identificar tres elementos principales del problema de
decisión:
1) descripción de las alternativas de decisión
2) determinación del objetivo del estudio
3) especificación de las limitaciones bajo las cuales funciona el sistema
modelado.
6
FASES DE UN ESTUDIO DE IO
La construcción del modelo implica un intento de transformar la definición
del problema en relaciones matemáticas.
• Si el modelo resultante se ajusta a uno de los modelos matemáticos
estándar, como la programación lineal, se suele obtener una solución
utilizando los algoritmos disponibles.
• Por otra parte, si las relaciones matemáticas son demasiado complejas
como para permitir la determinación de una solución analítica, se puede
optar por simplificar el modelo y utilizar un método heurístico, o bien
considerar la simulación, si es lo apropiado.
7
FASES DE UN ESTUDIO DE IO
La solución del modelo es por mucho la más sencilla de todas las fases
de IO porque implica el uso de algoritmos de optimización bien
definidos.
• Un aspecto importante de la fase de solución del modelo es el análisis
de sensibilidad.
• En estos casos es importante estudiar el comportamiento de la
solución óptima en el entorno de los parámetros estimados.
8
FASES DE UN ESTUDIO DE IO
La validez del modelo comprueba si el modelo propuesto hace en realidad lo que
dice que hace, es decir, ¿predice adecuadamente el comportamiento del sistema
que se estudia?
Se debe estar convencido de que el resultado del modelo no contenga “sorpresas”,
o sea:
• ¿tiene sentido la solución?
• ¿Los resultados sin intuitivamente aceptables?
Un método común de comprobar la validez de un modelo es comparar su resultado
con resultados históricos. El modelo es válido si, en condiciones de datos de
entrada iguales, reproduce de forma razonable el desempeño pasado
9
FASES DE UN ESTUDIO DE IO
La implementación de la solución de un modelo validado
implica la transformación de los resultados en instrucciones
de operación comprensibles que se emitirán a las personas
que administrarán el sistema recomendado.
10
FORMA ESTÁNDAR DEL MODELO
* Se tiene el mismo modelo para el caso de Minimizar.
11
Ejemplo P.L. 1
MODELO DE PL CON DOS VARIABLES (MAXIMIZACIÓN)
Reddy Mikks produce pinturas para interiores y exteriores con dos materias primas, M1 y M2.
• El consumo diario para exteriores es de 6 toneladas por tonelada de pintura y el consumo diario para interiores es
de 4 toneladas por tonelada de pintura, para la materia prima M1.
• El consumo diario para exteriores es de 1 tonelada por tonelada de pintura y el consumo diario para interiores es
de 2 toneladas por tonelada de pintura, para la materia prima M2.
• Las disponibilidades diarias de las materias primas M1 y M2 son de 24 y 6 toneladas, respectivamente.
• La demanda del producto estipula que la producción diaria de pintura para interiores no debe exceder a la de
pintura para exteriores en más de 1 tonelada.
• Se limita la demanda diaria de pintura para interiores a 2 toneladas.
Ejemplo P.L. 1
𝑥𝑥1 : 𝑇𝑇𝑇𝑇𝑇𝑇𝑇𝑇𝑇𝑇𝑇𝑇𝑇𝑇𝑇𝑇𝑇𝑇 𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝 𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑 𝑑𝑑𝑑𝑑 𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝 𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝 𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒.
𝑥𝑥2 : 𝑇𝑇𝑇𝑇𝑇𝑇𝑇𝑇𝑇𝑇𝑇𝑇𝑇𝑇𝑇𝑇𝑇𝑇 𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝 𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑 𝑑𝑑𝑑𝑑 𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝 𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝 𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖.
La tabla siguiente proporciona los datos básicos del problema:
Ejemplo P.L. 1
𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀 𝑍𝑍 = 5𝑥𝑥1 + 4𝑥𝑥2
𝑹𝑹𝑹𝑹𝑹𝑹𝑹𝑹𝑹𝑹𝑹𝑹𝑹𝑹𝑹𝑹𝑹𝑹𝑹𝑹𝑹𝑹𝑹𝑹𝑹𝑹:
6𝑥𝑥1 + 4𝑥𝑥2 ≤ 24
𝑥𝑥1 + 2𝑥𝑥2 ≤ 6
−𝑥𝑥1 + 𝑥𝑥2 ≤ 1
𝑥𝑥2 ≤ 2
𝑥𝑥1 , 𝑥𝑥2 ≥ 0
𝑥𝑥1 : 𝑇𝑇𝑇𝑇𝑇𝑇𝑇𝑇𝑇𝑇𝑇𝑇𝑇𝑇𝑇𝑇𝑇𝑇 𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝 𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑 𝑑𝑑𝑑𝑑 𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝 𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝 𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒.
𝑥𝑥2 : 𝑇𝑇𝑇𝑇𝑇𝑇𝑇𝑇𝑇𝑇𝑇𝑇𝑇𝑇𝑇𝑇𝑇𝑇 𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝 𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑 𝑑𝑑𝑑𝑑 𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝 𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝 𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖.
Ejemplo P.L. 1
Ejemplo P.L. 1
Ejemplo P.L. 1
Ejemplo P.L. 2
MODELO DE PL CON DOS VARIABLES (MINIMIZAR)
Ozark Farms consume diariamente un mínimo de 800 lb de un alimento especial, el cual es una mezcla de maíz y soya con
las siguientes composiciones:
• Las necesidades dietéticas del alimento especial son un mínimo de 30% de proteína y un máximo de 5% de fibra.
• El objetivo es determinar la mezcla diaria de alimento a un costo mínimo.
• Las variables de decisión del modelo son:
𝑥𝑥1 : 𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙 𝑑𝑑𝑑𝑑 𝑚𝑚𝑚𝑚𝑚𝑚𝑚 𝑒𝑒𝑒𝑒 𝑙𝑙𝑙𝑙 𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚 𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑 𝑥𝑥2 : 𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙 𝑑𝑑𝑑𝑑 𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠 𝑒𝑒𝑒𝑒 𝑙𝑙𝑙𝑙 𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚 𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑
• El objetivo es minimizar el costo diario total (en dólares) de la mezcla de alimento, es decir:
Ejemplo P.L. 2
Las restricciones representan la cantidad diaria de la mezcla y las necesidades dietéticas. Ozark Farms requiere un
mínimo de 800 lb de alimento al día, es decir:
20
Ejemplo P.L. 2
𝑹𝑹𝑹𝑹𝑹𝑹𝑹𝑹𝑹𝑹𝑹𝑹𝑹𝑹𝑹𝑹𝑹𝑹𝑹𝑹𝑹𝑹𝑹𝑹𝑹𝑹:
𝑥𝑥1 : 𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙 𝑑𝑑𝑑𝑑 𝑚𝑚𝑚𝑚𝑚𝑚𝑚 𝑒𝑒𝑒𝑒 𝑙𝑙𝑙𝑙 𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚 𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑
𝑥𝑥2 : 𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙 𝑑𝑑𝑑𝑑 𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠 𝑒𝑒𝑒𝑒 𝑙𝑙𝑙𝑙 𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚 𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑
Ejemplo P.L. 2
Ejemplo P.L. 2
23
Ejemplo P.L. 3
Un herrero con 80 kg de acero y 120 kg de aluminio quiere hacer bicicletas de paseo y de
montaña que quiere vender, respectivamente a 20.000 y 15.000 pesos cada una para sacar el
máximo beneficio. Para la de paseo empleará 1 kg de acero y 3 kg de aluminio, y para la de
montaña 2 kg de ambos metales. ¿Cuántas bicicletas de paseo y de montaña deberá fabricar
para maximizar las utilidades?
Requerimiento de materiales
Precio de Venta
Acero Aluminio
Bicicletas de paseo 1 kg 3 kg 20 000 $
Bicicletas de montaña 2 kg 2 kg 15 000 $
Disponibilidad 80 kg 120 kg
25
Ejemplo P.L. 3
Requerimiento de materiales
Precio de Venta
Acero Aluminio
Bicicletas de paseo 1 kg 3 kg 20 000 $
Bicicletas de montaña 2 kg 2 kg 15 000 $
Disponibilidad 80 kg 120 kg
26
Ejemplo P.L. 3
27
Ejemplo P.L. 4
Un autobús que hace el recorrido Cali-Buga, ofrece asientos para fumadores al precio de 10 000 pesos y a
no fumadores al precio de 6 000 pesos.
Al no fumador se le deja llevar 50 kg de peso y al fumador 20 kg.
Si el autobús tiene 90 asientos y admite un equipaje de hasta 3 000 kg.
¿Cuál ha de ser la oferta de asientos de la compañía para cada tipo de pasajeros, con la finalidad de
optimizar el beneficio?
Además, debe considerarse que por políticas de la empresa, deben ofrecerse cómo mínimo 10 asientos
para pasajeros no fumadores.
Peso Precio de Venta
Fumadores 20 Kg 10 000 $
No Fumadores 50 Kg 6 000 $
DISPONIBILIDAD 3000 Kg
29
Ejemplo P.L. 5
Un comerciante acude al mercado popular a comprar naranjas con 50 000 pesos.
Le ofrecen dos tipos de naranjas: las de tipo A a 50 pesos el kg y las de tipo B a 80 pesos el kg.
Sabiendo que sólo dispone de su camioneta con espacio para transportar 700 kg de naranjas como máximo y que
piensa vender el kg de naranjas tipo A a 58 pesos y el kg de tipo B a 90 pesos.
Plantee un modelo de programación lineal que permita resolver la situación anterior.
Precio de
Costo Peso Utilidad
venta
Naranjas tipo A 50 $/kg 1 kg 58 $/kg 8 $/kg
Naranjas tipo B 80 $/kg 1 kg 90 $/kg 10 $/kg
Disponibilidad 50 000 $ 700 kg
32
Ejemplo P.L. 6
Un vendedor de frutas necesita 16 cajas de naranjas, 5 de plátanos y 20 de manzanas. Dos
mayoristas están en condiciones de satisfacer sus necesidades, pero solo venden la fruta en
contenedores completos. El mayorista A envía en cada contenedor 8 cajas de naranjas, 1 de
plátanos y 2 de manzanas. El mayorista B envía en cada contenedor 2 cajas de naranjas, 1 de
plátanos y 7 de manzanas. Sabiendo que el mayorista A se encuentra a 150 km de distancia y
el mayorista B a 300 km, calcular cuántos contenedores habrá de comprar a cada mayorista,
con el objeto de ahorrar tiempo y dinero, reduciendo al mínimo la distancia.
Contenido de cada contenedor
Cajas de Cajas de Cajas de Distancia del
naranjas plátanos manzanas mayorista
Contenedor
8 1 2 150 km
mayorista A
Contenedor
2 1 7 300 km
mayorista B
Requerimientos
16 5 20
mínimos
35
Ejemplo P.L. 7
Como gerente de una asociación de empresas para el reciclaje en la región, ha sido asignado para tomar la
decisión de a quien debe venderse unos desperdicios de metal que fueron recolectados.
Dos empresas: Metales Ltda. y Hierros Unidos, están interesados en la compra de los desperdicios.
La primera empresa, que paga la tonelada de metal a: $500 no esta interesada en comprar mas de 500 toneladas,
en cambio la segunda, que esta dispuesta a pagar $400 por tonelada de metal, ofrece comprar un límite máximo
de 600 toneladas.
Sin embargo la financiación local ha limitado las compras formulando la siguiente condición: La cantidad de
desperdicio vendida a la empresa Metales Ltda. no puede superar el doble de la cantidad vendida a Hierros
Unidos.
Conociendo que la asociación de empresas dispone de 1.000 toneladas de desperdicios metálicos, formule un
modelo de programación lineal que permita alcanzar la mejor decisión para el gerente.
Demanda Precio de compra
Metales Ltda. 500 ton 500 $
Hierros Unidos 600 ton 400 $
Disponibilidad 1000 ton
38
Ejemplo P.L. 8
SUCAFÉ, produce y distribuye dos tipos de café a los supermercados de la ciudad: normal y procesado.
Para éste mes SUCAFÉ tiene 180 toneladas de grano de café en inventario y tiene programadas hasta 50 horas de
tiempo de procesamiento para el tostado.
Cada tonelada de café normal necesita una tonelada de grano, dos horas de tostado y produce una ganancia de
$8 000.
Cada tonelada de café procesado necesita también una tonelada de grano pero necesita cuatro horas de tostado
y produce una ganancia de $9 000.
Plantee un modelo de programación lineal que le permita a SUCAFÉ planear su producción para este mes.
Grano Tiempo de
Utilidad
requerido Tostado
Café normal
Café procesado
Disponibilidad
40
Ejemplo P.L. 9
La fábrica de Hilados y Tejidos «SALAZAR» requiere fabricar dos tejidos de calidad diferente
T y S; se dispone de 500 Kg de hilo a, 300 Kg de hilo b y 108 Kg de hilo c.
Para obtener un metro de T diariamente se necesitan 125 gr de a, 150 gr de b y 72 gr de c;
para producir un metro de S por día se necesitan 200 gr de a, 100 gr de b y 27 gr de c.
El T se vende a $4 000 el metro y el S se vende a $5 000 el metro.
Si se debe obtener el máximo beneficio, ¿cuántos metros de T y S se deben fabricar?
Precio de
Hilo a Hilo b Hilo c
Venta
Tela Tipo T
Tela Tipo S
DISPONIBILIDAD
44
Ejemplo P.L. 10
Una empresa de confecciones puede producir 1000 pantalones o 3000 blusas (o una combinación de ambos)
diariamente.
El departamento de acabado puede trabajar sobre 1500 pantalones o sobre 2000 blusas (o una combinación de
ambos) cada día; el departamento de mercadeo requiere que se produzcan diariamente al menos 400
pantalones.
Si el beneficio de un pantalón es de $ 4000 y el de una blusa es de $ 3000.
¿Cuántas unidades se deben producir de cada uno para maximizar las utilidades?
Producción Acabado Beneficio
Pantalones
Blusas
47
Ejemplo P.L. 11
Un empresario pretende fabricar dos tipos de congeladores denominados A y B.
Cada uno de ellos debe pasar por tres operaciones antes de su comercialización: Ensamblaje, pintura y control de calidad. Los
congeladores requieren, respectivamente, 2.5 y 3 horas de ensamblaje, 3 y 6 kg de esmalte para su pintura y 14 y 10 horas de
control de calidad.
Los costos totales de fabricación por unidad son, respectivamente, 30 y 28, y los precios de venta 52 y 48, todos ellos en miles
de pesos.
El empresario dispone semanalmente de máximo, 4500 horas para ensamblaje, de máximo 8400 kg de esmalte y 20000 horas
máximo, para control de calidad.
Los estudios de mercado muestran que la demanda semanal de congeladores no supera las 1700 unidades y que, en
particular, la de tipo A es de, al menos 600 unidades.
Ensamblaje Pintura Calidad Precio de
Costo Utilidad
Venta
Congeladores tipo A
Congeladores tipo A
Congeladores tipo B
Congeladores tipo B
Disponibilidad
51
Ejemplo P.L. 12
El granjero Leary cultiva trigo y maíz en su granja con un terreno cultivable de 45 acres.
El puede vender a lo más 140 bultos de trigo y 120 bultos de maíz.
Cada acre que él planta con trigo produce 5 bultos, mientras que cada acre plantado con maíz produce 4 bultos.
El trigo se vende a 30 dólares el bulto, mientras que el maíz a 50 dólares el bulto.
Para cosechar un acre de trigo requiere 6 horas de labor; cosechar un acre de maíz requiere 10 horas.
Se pueden contratar hasta 350 horas de labor a 10 dólares la hora.
Para maximizar las ganancias, el granjero formuló y resolvió un modelo lineal.
Acres Tiempo de cosechar Precio
Bultos de trigo a producir 1/5 acres 6 horas/acre 30 $/bulto
Bultos de maíz a producir 1/4 acres 10 horas/acre 50 $/bulto
Disponibilidad 45 acres 350 horas
...
…
…
52
Referencias Bibliográficas
• Hamdy A. Taha. Investigación de operaciones. Novena edición.
• Frederick S. Hillier & Gerald J. Lieberman. Introducción a la investigación de
operaciones. Novena edición.
55
56