2. Programación lineal :
Formulación matemática del problema
Jorge Eduardo Ortiz Triviño
[email protected]
Objetivos del Capítulo
 Fijar los requerimientos para establecer un modelo de
programación lineal.
 Representación gráfica de un modelo de programación
lineal.
 Ventajas del modelo de programación lineal:
*
*
*
*
.
Obtención de una solución óptima única.
Obtención de soluciones alternativas
Modelos no acotados.
Modelo no factibles.
 Conceptos de análisis de sensibilidad:
* Reducción de costos.
* Rango de optimalidad.
* Precios sombra.
* Rango de factibilidad.
* Holgura complementaria.
* Agregar restricciones/variables.
 Obtención de una solución por métodos computacionales:
Introducción a la Programación Lineal
 Un modelo de programación lineal busca maximizar o
minimizar una función lineal, sujeta a un conjunto de
restricciones lineales.
 Un modelo de programación lineal esta compuesto de lo
siguiente:
* Un conjunto de variables de decisión
* Una función objetivo
* Un conjunto de restricciones
PROGRAMACIÓN LINEAL
Es un método matemático que se emplea para resolver problemas
de optimización. En palabras simples la P.L. busca asignar recursos
limitados, entre actividades que compiten, de la forma mas óptima
posible.
Supuestos de la P.L.
•Proporcionalidad
•Aditividad
•Divisibilidad
•Certidumbre
•Objetivo único
•No negatividad
PROGRAMACIÓN LINEAL
P R O G R AM AC IO N LIN E AL
FO R M U LAC IO N M ATE M ATIC A
P R O B LE M A G E N E R AL
M E TO D O G R AFIC O
M E TO D O ALG E B R AIC O
(S IM P LE X )
P R O B LE M AS E S P E C IALE S
P R O B LE M AS D E TR AN S P O R TE
P R O B LE M AS D E AS IG N AC IÓ N
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”.
Formulación matemática básica en un
problema de I.O. (PL)
Ejemplo: Una multinacional minera extrae un tipo de mineral de dos minas
diferentes, el cuales es sometido a un proceso de trituración, con tres grados:
alto , medio y bajo. La compañía han firmado un contrato para proveer de
mineral a una planta de fundición, cada semana, 12 toneladas de mineral de
grado alto, 8 toneladas de grado medio y 24 toneladas de grado bajo. Cada
una de las minas tiene diferentes procesos de fabricación.
Mina
Costo por día (miles de Euros)
Producción(toneladas/día)
Alto
Medio Bajo
X
180
6
3
4
Y
160
1
1
6
¿Cuántos días a la semana debería operar cada mina para cumplir el contrato
con la planta de fundición con el que se comprometió la multinacional?
Formulación matemática básica en un
problema de I.O.
Es necesario buscar una solución que minimice el costo de
producción global de la empresa, sujeta a las restricciones
impuestas por los proceso productivos asociados a cada mina
así como el contrato con la planta de fundición.
Traducción del problema en términos matemáticos
1. definir las variables
2. las restricciones
3. el objetivo
Formulación matemática básica en un
Restricciones
problema de I.O.
Variables
Representan las decisiones que puede
tomar la empresa:
Dx = número de días a la semana que
la mina X produce
Dy= número de días a la semana que
la mina Y produce
Notar que Dx0 y Dy0
Objetivo
Como objetivo buscamos minimizar
el costo
180Dx+160Dy
Se recomienda primero plantear las
restricciones con palabras antes de
pasar a su formulación matemática.
Restricción 1. refleja el balance entre
las limitaciones productivas de la
fábrica y el contrato con la plante de
fundición
Grado
Alto
6Dx+1Dy12
Medio
3Dx+1Dy8
Bajo
4Dx+6Dy24
Restricción 2. días
disponibles a la semana
Dx5 y Dy5
de
trabajo
Formulación matemática básica en un
problema de I.O.
La representación completa del problema tomaría la siguiente
forma:
Minimizar 180Dx+160Dy
s.a.
6Dx+1Dy12
3Dx+1Dy8
4Dx+6Dy24
Dx5, Dy5
Dx0, Dy0
PROGRAMACIÓN LINEAL
Construcción de modelos
PROBLEMA DE LA MEZCLA DE PRODUCTOS
Una compañía fabrica dos tipos de componentes electrónicos: transistores
y bobinas.
Cada transistor requiere un minuto de tiempo en el departamento de
ensamble, dos minutos de tiempo en el departamento de Control de
Calidad y un minuto de tiempo en empaque.
Cada bobina requiere dos minutos de tiempo en ensamble, un minuto de
tiempo en Control de Calidad y dos minutos en empaque.
Existe un total de 300 minutos en Ensamble, 400 minutos en C. Calidad y
400 minutos en Empaque disponibles cada día.
Tanto los transistores como las bobinas contribuyen en un dólar a la
utilidad.
La compañía desea determinar la mezcla de productos optima que
maximice la utilidad total.
PROGRAMACIÓN LINEAL
Construcción de modelos
Solución:
Formulación
Paso 1: Identificar el objetivo (meta) a optimizar
Maximizar las utilidades de la compañía (U).{dólares/día}
Paso 2: Identificar las variables de decisión que se desea determinar
X….Cantidad de transistores a fabricar por día {unds./día}
Y….Cantidad de bobinas a fabricar por día {unds./día}
Paso 3: Identificar las restricciones del modelo
R1) Tiempo disponible en el depto. de Ensamble por día 300 min.
R2) Tiempo disponible en el depto. de C. Calidad por día de 400 min.
R3) Tiempo disponible en el depto. de Empaque por día de 400 min.
R4) No Negatividad.
PROGRAMACIÓN LINEAL
Construcción de modelos
Paso 4: Construcción del modelo matemático
F.Objetivo
MAX { U = X + Y }
Sujeto a :
R1) X + 2Y  300
R2) 2X + Y  400
R3) X + 2Y  400
R4) X , Y  0
Métodos de Resolución
Método Gráfico
Empleado principalmente para PPL con dos variables de decisión.
Este método se basa en la idea de obtener regiones de soluciones
factibles (RSF), en las cuales se encontraría la combinación de
variables de decisión que optimizan el modelo.
Método Algebraico (SIMPLEX)
Empleado principalmente para PPL con más de dos variables de
decisión. Este método se desarrollo con base en el método gráfico y
corresponde a un sistema heurístico, por lo cual requiere de una
solución inicial factible para empezar a funcionar.
8
Problemas típicos
•
•
•
•
•
•
•
•
•
•
•
Problema del transporte
Problema de flujo con coste mínimo en red
Problema de asignación
Problema de la mochila (knapsack)
Problema del emparejamiento (matching)
Problema del recubrimiento (set-covering)
Problema del empaquetado (set-packing)
Problema de partición (set-partitioning)
Problema del coste fijo (fixed-charge)
Problema del viajante (TSP)
Problema de rutas óptimas
Problema del transporte
Minimizar el coste total de transporte entre los centros de
origen y los de destino, satisfaciendo la demanda, y sin
superarm lan oferta
Min
c
ij
x ij
i1 j 1
s .a .
m
x
ij
 b j , j  1 .. n
i1
ai: unidades de oferta en el punto origen i
bj: unidades de demanda en el punto destino j
Se supone oferta total igual a demanda total
n
x
xij: unidades a enviar de origen i a destino j
cij: coste unitario de transporte de i a j
ij
 a i , i  1 .. m
j 1
x ij  0 , x ij  Z
Algunas reflexiones
•
Hemos pasado de la definición del problema a su
formulación matemática.
•
Error de especificación, el error más frecuente consiste en
descuidar las limitaciones (restricciones, características de
las variables, etc,)
En el ejemplo anterior:
a) Todas las variables son continuas (admitimos fracciones de
día)
b) Existe un único objetivo (minimizar los costes)
c) El objetivo y las restricciones son lineales
Las tres consideraciones anteriores nos llevan a lo que
denominamos un problema de Programación Lineal PL
Algunas reflexiones
El ejercicio anterior plantea un PROBLEMA DE DECISIÓN
Se ha tomado una situación real y se ha construido su equivalente
matemático MODELO MATEMÁTICO
Durante la formulación del modelo matemático se considera el
método cuantitativo que (esperanzadamente) nos permitirá resolver
el modelo numéricamente ALGORITMO
El algoritmo es un conjunto de instrucciones que siguiendo de
manera gradual producen una solución numérica
Otra definición de I.O.
Ciencia para la representación de problemas reales mediante
modelos matemáticos que junto con métodos cuantitativos nos
permiten obtener una solución numérica a los mismos
Dificultades
Dificultades de este tipo de enfoques:
•Identificación del problema (debemos ignorar partes o tratar el
problema entero).
•Elección del modelo matemático adecuado así como el
algoritmo adecuado para resolverlo (validación del algoritmo).
•Dificultades en la implementación.
•Velocidad (costes) que supone llegar a una solución.
•Calidad de la solución.
•Consistencia de la solución.