Tema 5: Modelos de
Optimización
Programación Lineal
Desarrollada por Dantzig al final de los 40
Metodo matematico para asignar recursos
escasos y lograr un objetivo predeterminado
El objetivo puede ser un beneficio, un costo,
una inversión, ventas, cuotas de mercado,
espacio, tiempo, …
PL se usa para la planificacion de capital, de
mano de obra, mezcla de gasolina, …por
todas las compañias del mundo
Programación Lineal
Variables de Decision
z Los simbolos se usan para representar un
item que puede tomar algun valor (e.g.,
x1=horas de trabajo, x2=# de trabajadores)
Parametros
z Valores constantes conocidos que se definen
con cada problema (e.g., precio de la unidad,
capacidad productiva)
Variables de Decision y Parametros se
definen de modo unico en cada problema
Programación Lineal
Es un metodo para resolver modelos
matematicos lineales
Funciones lineales
f(x) = 5x + 1
g(x1, x2) = x1 + x2
Funciones non-lineales
f(x) = 5x2 + 1
g(x1, x2) = x1x2 + x2
Formulacion de un PL
Definir las variables de decision
z Identificar las variables clave cuyos valores
queremos conocer
Determinar la funcion objetivo
z Concretar lo que estamos intentando hacer
z Maximizar beneficio, Minimizar el costo total
Formular las restricciones
z Determinar las limitaciones de las variables
de decision
Partes de un Programa Lineal
Cualquier PL considera siempre tres
aspectos
Funcion Objetivo
Restricciones
Hipotesis de no-negatividad
Partes de un Programa Lineal
Funcion Objetivo
z Relaciones lineales de las variables de
decision que describen el objetivo de los
problemas
z Siempre suponen maximizar o miniizar
algun valor
z Por ejemplo
z maximizar Z = beneficio,
z minimizar Z = costo
Partes de un Programa Lineal
Restricciones
z Relaciones lineales de las variables de
decision que representan condiciones o
reglas
z e.g., recursos limitados como trabajo o
capital
Hipotesis de no-negatividad
z Restringen las variables de decision a
tomar solo valores mayores o iguales a
cero
Funcion Objetivo
Siempre se presenta para Max o Min
z Maximizar un Beneficio
z Minimizar un Costo
Es una funcion lineal de las variables
de decision
z Maximizar Beneficio = Z = 3x1 + 5x2
z Minimizar Costo = Z = 6x1 - 15x2
Restricciones
Las restricciones son las condiciones del
problema
z Total de horas de trabajo menor o igual que 50
z x1 debe usar menos de 20 litros de aditivos
Se definen como relaciones lineales
z total de horas de trabajo menor o igual que 50
z x1 + x2 ≤ 50
z x1 debe usar menos de 20 litros de aditivos
z x1 < 20
Hipotesis de no-negatividad
Las variables de decision negativas son
inconcebibles en muchos problemas de
PL
Menos 10 unidades de produccion o un
consumo negativo no tiene sentido
Estas restricciones se escriben como
z x1, x2 > 0
PL en Forma Estandar
Cada PL tiene que contener las 3 partes
Una forma estandar de un PL es
Maximizar Z = c1x1 + c2x2 + ... + cnxn
sujeto a a11x1 + a12x2 + ... + a1nxn < b1
…………………..……...
am1x1 + am2x2 + ... + amnxn < bm
x1, x2, xn > 0
Metodos para resolver
Problemas de PL
Existen dos enfoques basicos de solucion
El metodo grafico
z simple, pero limitado a dos variables de
decision
El metodo Simplex
z Mas complejo, pero resuelve problemas de
multiples variables.
z Es el numero 1 del Top-10
Metodo Grafico
1. Construir un plano en coordenadas x-y
2. Pintar todas las restricciones en el plano
3. Identificar la region factible descrita por las
restricciones
4. Identificar la solucion optima pintando una
serie de funciones objetivo sobre la region
factible
5. Determinar el valor exacto de las variables
solucion y el valor optimo para la funcion
objetivo
Ejemplo del metodo grafico
Max 3 P1 + 5 P2
s.a. P1 + < 4 (Planta 1)
P2
2 P2 < 12 (Planta 2)
3 P1 + 2 P2 < 18 (Planta 3)
P1, P2 >0 (no negatividad)
Cualquier punto en este cuadrante no negativo se
Asocia a una alternativa de produccion especifica
( punto = decision = solucion )
P1
0
Ejemplo del metodo grafico
Max 3 P1 + 5 P2
P2
s.a. P1 + < 4 (Planta 1)
2 P2 < 12 (Planta 2)
3 P1 + 2 P2 < 18 (Planta 3)
P1, P2 >0 (no negatividad)
P1
(0,0) (4,0)
Ejemplo del metodo grafico
P2 Max 3 P1 + 5 P2
s.a. P1 + < 4 (Planta 1)
(0,6)
2 P2 < 12 (Planta 2)
3 P1 + 2 P2 < 18 (Planta 3)
P1, P2 >0 (no negatividad)
P1
(0,0) (4,0)
Ejemplo del metodo grafico
Max 3 P1 + 5 P2
s.a. P1 + < 4 (Planta 1)
P2
2 P2 < 12 (Planta 2)
(0,6) (2,6)
3 P1 + 2 P2 < 18 (Planta 3)
P1, P2 >0 (no negatividad)
(4,3)
(9,0)
P1
(0,0) (4,0)
Ejemplo del metodo grafico
Max 3 P1 + 5 P2
s.a. P1 + < 4 (Planta 1)
P2
2 P2 < 12 (Planta 2)
(0,6) (2,6)
3 P1 + 2 P2 < 18 (Planta 3)
P1, P2 >0 (no negatividad)
(4,3)
(9,0)
P1
(0,0) (4,0)
Max 3 P1 + 5 P2
P2 En la Region Factible
(0,6) (2,6)
La Region Factible es el conjunto de
puntos (soluciones) que satisfacen a la
vez todas las restricciones. Hay
infinitos puntos factibles (soluciones).
(4,3)
(9,0)
P1
(0,0) (4,0)
Ejemplo del metodo grafico
P2 Max 3 P1 + 5 P2
(0,6) (2,6)
Perfil de la funcion objetivo
(linea iso-beneficio)
(4,3)
(9,0)
P1
(0,0) (4,0) 3 P1 + 5 P2 = 12
Ejemplo del metodo grafico
3 P1 + 5 P2 = 36
P2 Max 3 P1 + 5 P2
(0,6) (2,6) s.a. P1 + < 4 (Planta 1)
2 P2 < 12 (Planta 2)
3 P1 + 2 P2 < 18 (Planta 3)
P1, P2 >0 (no negatividad)
(4,3)
Solucion Optimal: la solucion
simultanea en la frontera de
las dos restricciones activas
(9,0)
P1
(0,0) (4,0)
Algoritmo para el Metodo Grafico
Dibujar la region factible.
Si la region es vacia, parar: el problema es infactible; debe
haber restricciones contradictorias en el modelo.
Dibujar el perfil de la funcion objetivo y elegir la direccion de
optimizacion.
Determinar si el valor del objetivo sera acotado o no. Si no
lo es, parar: el problema es no acotado; debe haber errores
en la formulacion del modelo.
Determinar un punto esquina optimal.
Identificar las restricciones activas en esa esquina.
Resolver el sistema de ecuaciones simultaneas que definen
la solucion optimal.
Calcular la funcion objetivo en la solucion optimal para
obtener el programa optimal del problema.
El Problema del Cervecero
Una pequeña cerveceria produce ale y pilsen.
z La produccio, esta limitada por los recursos: maiz, lupulo y malta.
z Las recetas de ale y pilsen requieren diferentes cantidades de los
ingredientes.
Maiz Lupulo Malta Beneficio
Bebida
(kilos) (kilos) (kilos)
Ale 5 4 35 13
Pilsen 15 4 20 23
Cantidad 480 160 1190
Como puede maximizar su beneficio el cervecero?
z Dedicar todos los recursos a pilsen: 32 barriles de pilsen ⇒ 736.
z Dedicar todos los recursos a ale: 34 barriles de ale ⇒ 442.
z 7½ barriles de ale, 29½ barriles de pilsen ⇒ 776.
z 12 barriles de ale, 28 barriles de pilsen ⇒ 800.
El Problema del Cervecero
max 13 A + 23B
s. t. 5 A + 15B ≤ 480
4A + 4 B ≤ 160
35 A + 20 B ≤ 1190
A , B ≥ 0
La Region Factible
Lupulo Malta
4A + 4B ≤ 160 35A + 20B ≤ 1190
(0, 32)
(12, 28)
(26, 14) Maiz
5A + 15B ≤ 480
Pilsen
(0, 0) Ale (34, 0)
La Funcion Objetivo
Be
ne
fic
(0, 32) io
(12, 28)
13A + 23B = 1600
(26, 14)
Pilsen 13A + 23B = 800
(0, 0) Ale (34, 0)
13A + 23B = 442
