Programación Lineal, Modelos
varios
PROFESOR:
FELIPE CASELLI
INGENIERO CIVIL INDUSTRIAL
MASTER EN INGENIERÍA DE NEGOCIOS
DOCTOR © GESTIÓN AVANZADA DE EMPRESAS EN UNA
ECONOMÍA GLOBALIZADA
Objetivos
• Fijar los requerimientos para establecer un modelo de
programación lineal.
• Comprender la formulación de diversos modelos de PL
2 COI 401 -FCB
Programación Lineal
• Un modelo de programación lineal busca
maximizar o minimizar una función lineal,
sujeta a un conjunto de restricciones lineales.
3 COI 401 -FCB
Programación Lineal
• La importancia de la programación lineal:
– Ciertos problemas se describen fácilmente a través
de la programación lineal.
– Muchos problemas pueden aproximarse a modelos
lineales.
– La salida generada por el programa que resuelve el
modelo de programación lineal entrega información
útil para responder nuevas condiciones sobre el
“qué pasa si” (análisis de sensibilidad).
4 COI 401 -FCB
Programación Lineal
• Lo anterior quiere decir que el modelo debe cumplir
con dos propiedades:
– Proporcionalidad: La contribución de cada variable de
decisión a la Función Objetivo (FO) y sus requerimientos en
las restricciones debe ser directamente proporcional al valor
de la variable (ej. Con el descuentos por volumen no se
cumple la proporcionalidad)
– Aditividad: La contribución total de todas las variables en la
FO y sus requerimientos en las restricciones, debe ser la suma
directa de las contribuciones o requerimientos individuales de
cada variable (si el aporte de una variable depende del valor
de otra variable, la aditividad no se cumple)
5 COI 401 -FCB
Programación Lineal
• Como ya se ha definido, un modelo de programación
lineal esta compuesto de lo siguiente:
– Un conjunto de variables de decisión
– Una función objetivo (con una condición de optimización)
– Un conjunto de restricciones
– Conjunto de parámetros o datos
• Asimismo, la solución óptima del modelo de PL
pertenecerá a un:
– Espacio factible: conjunto de soluciones posibles que
cumplen con las restricciones dadas por el modelo
– Vértice factible: punto de intersección de las rectas que
delimitan el espacio factible de soluciones
6 COI 401 -FCB
PROBLEMA GENERAL DE LA IO
7
Encontrar x para
Maximizar o Minimizar f(x1,….,x
n)
s.a
Restricciones gi(x
1,….,x
n) ≤ r
i i=1,….,m
Variables de Decisión
Medida de desempeño
Función Objetivo
=
≥
≤
Condición de
optimización
COI 401 -FCB
METODOLOGÍA DE LA Investigación de
Operaciones: Definición del Sistema
(Identificación del Problema)
8
• Objetivo
• Ámbitos
Alternativas de solución
Dimensión espacial
Dimensión temporal
Nivel de las decisiones
Separabilidad de las decisiones
Tiempo, tecnología y recurso
humano disponible
Grado de precisión numérica
Esencial:
Objetivo del modelo
Comprensión del sistema
En ocasiones será mejor utilizar métodos heurísticos COI 401 -FCB
Planificación de la Producción
• La planificación de la producción es uno de los
ejemplos más concurrentes de programación lineal en
la gestión de empresas. Se desea determinar la
cantidad de los diferentes productos de la empresa
que se han de producir considerando los recursos
disponibles.
• El criterio que orienta la selección de alternativas está
generalmente asociado a minimizar los costos de
producción o a maximizar los ingresos o los beneficios
obtenidos de la explotación.
9 COI 401 -FCB
Eje
mp
lo
p
lan
ificació
n d
e la p
ro
du
cció
n
• La empresa ABRAX Ltda. Fabrica puertas y ventanas de madera. Existen dos
modelos de puertas y ventanas: dobles y simples. El insumo más importante es la
madera.
• El proceso de corte de las partes se realiza en dos sierras eléctricas de precisión y el
barnizado lo efectúa personal experimentado. Las cantidades de madera y los
tiempos de corte y barnizado que requiere cada producto se muestran en la tabla 1.
10
• Los proveedores de madera pueden entregar hasta 900 m2 en un mes. Además se
pueden utilizar hasta 400 horas de sierra para el proceso de corte y 300 horas-hombre
para el barnizado. La empresa está comprometida con una constructora para
entregar 20 puertas simples y 12 ventanas dobles en el mes. Los precios de venta
unitarios y costos unitarios de producción, en miles de pesos (M$), se muestran en la
tabla 2.
• Se desea determinar un plan de producción para el mes que maximice el beneficio
total y cumpla con los compromisos de entrega, suponiendo que todo lo que se
produce se vende.
Producto Madera (m2) Corte (horas-
máquina)
Barnizado (horas-
hombre)
Puertas dobles 4 1,5 2
Puertas Simples 2,5 1 1,2
Ventanas Dobles 3 2 1,5
Ventanas Simples 1,8 0,8 0,8
Producto Precio (M$) Costo unitario (M$)
Puertas dobles 120 80
Puertas Simples 80 50
Ventanas Dobles 100 75
Ventanas Simples 60 30
COI 401 -FCB
Mezcla de alimentos
• El administrador de un plantel cunícola (crianza de conejos) desea determinar la
composición de 1.000 kg de alimento que cumpla con los requerimientos nutritivos
establecidos para el normal crecimiento de los conejos q que tenga el menor costo
posible. En la elaboración del alimento pueden utilizarse los ingredientes cuyas
características nutritivas y costo se señalan en la tabla 2.
• La dieta debe tener las siguientes características:
14
Elemento Requisito
Proteína 15%
Fibra Mínimo 25%
Hidratos de carbono Mínimo 20% y máximo 40%
Calorías Mínimo 800/kg y máximo 1800/kg
Harina de pescado Máximo 10%
Ingredientes Proteínas
(%) Fibra (%)
Hidratos de
carbono (%)
Calorías
(calorías/kg) Costo ($/kg)
Harina de soya 9 12 50 1000 45
Harina de pescado 55 - 4 1950 100
Trigo 7 6 66 1750 70
Alfalfa 12 25 35 450 45
Avena 8,5 11 58 1700 80
Tabla 2 – ingredientes disponibles
COI 401 -FCB
Mezcla de componentes
• La empresa GASOL Ltda.., produce y vende dos tipos de gasolina: corriente y especial. Para ello
utiliza dos tipos de petróleo crudo: liviano y pesado, que tienen un costo de US$15 y US$20 por
barril, respectivamente. Las características de los dos tipos de petróleo se señalan en la tabla 1.
• Las especificaciones exigidas para los productos finales: gasolina corriente y especial, y los
precios de venta se muestran en la tabla 2.
• Cada barril puede contener 40 kg de petróleo liviano, o 50 kg de petróleo pesado o 60 lt de
gasolina. El octanaje de los combustibles corresponde a la media de los octanajes de sus
componentes ponderada por su volumen.
• El encargado de la producción de combustibles necesita determinar qué tipos de mezclas utilizar
para cada combustible y cuál debe ser el nivel de producción de manera que se obtenga la mayor
utilidad posible.
18
Petróleo liviano Petróleo pesado
Densidad 0,65 0,85
Octanaje 70 102
Disponibilidad (barriles) 800 600
Costo (US$/barril) 15 20
Combustible Densidad (kg/lt) Octanaje Precio
(US$/barril)
Gasolina
corriente
Min = 0,70
Max = 0,75 85 25
Gasolina especial Min = 0,70
Max = 0,75 94 30
COI 401 -FCB
PROBLEMA DE TRANSPORTE
• El ministerio de salud distribuye leche desde 2 centros
de distribución c/u de ellos tiene una capacidad de 90
toneladas al mes y la leche se distribuye en 3
consultorios distintos, la siguiente tabla muestra los
costos unitarios del envío de una tonelada de leche
desde cada centro a cada consultorio. El ministro
desea enviar el mismo número de toneladas a cada
consultorio y minimizar el costo total.
22
Consultorio 1 Consultorio 2 Consultorio 3
CD1 1 3 5
CD2 2 5 4
COI 401 -FCB
Definición del problema
23
1
2
1
2
3
a1
a2
b1
b2
bm
Centros de
Distribución
Consultorios
Un
idad
es
de
Ofe
rta
Un
idad
es d
e
De
man
da
COI 401 -FCB