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