OPTIMIZACIÓN LINEAL
INGENIERÍA INDUSTRIAL
UNIVERSIDAD MANUELA BELTRÁN
PROGRAMACIÓN LINEAL
La optimización basada
en programación lineal
corresponde a
situaciones reales en las
que se pretende
identificar y resolver
dificultades para
aumentar la
productividad respecto a
los recursos
(principalmente los
limitados y costosos),
aumentando así los
beneficios.
Los resultados y el proceso de optimización se convierten en un
respaldo cuantitativo de las decisiones frente a las situaciones
planteadas. Decisiones en las que sería importante tener en cuenta
diversos criterios administrativos como:
Los hechos La experiencia La intuición La autoridad
¿Qué es la PROGRAMACIÓN
LINEAL?
La programación lineal es una técnica
matemática que se utiliza para la solución de
diferentes tipos de problemas, tanto teóricos
como prácticos, en diversas áreas del
conocimiento.
Jesús y Antonio Arreola Risa en su libro “Programación
Lineal: Una introducción a la toma de decisiones
cuantitativa”
El éxito en su aplicación a problemas reales,
sofisticados y complejos es avalado por una gran
cantidad de instituciones productoras de bienes
y servicios en muchos países del mundo.
La programación lineal consiste básicamente en
la construcción, solución y análisis del modelo
lineal de un problema dado.
Programación Lineal según
Wikipedia…..
Consiste en optimizar (minimizar o
maximizar) una función lineal,
denominada función objetivo, de tal
forma que las variables de dicha
función estén sujetas a una serie de
restricciones que expresamos
mediante un sistema de
inecuaciones lineales.
Programación Lineal según
[Link]ó[Link]
La Programación Lineal (PL) es
una de las principales ramas de la
Investigación Operativa.
En esta categoría se consideran
todos aquellos modelos de
optimización donde las funciones
que lo componen, es decir,
función objetivo y restricciones,
son funciones lineales en las
variables de decisión.
La programación lineal (PL) es una técnica
matemática de optimización, es decir, un
método que trata de maximizar o minimizar
un objetivo.
Su interés principal es tomar decisiones
óptimas.
Dr. Guillermo Martínez
Atilano
Estructura básica de un problema
de programación lineal (PL)
Un problema de PL consta de
una función objetivo (lineal) por
maximizar o minimizar, sujeta a
ciertas restricciones en la forma
de igualdades o desigualdades.
Ejemplo
Gepetto S.L., manufactura muñecos y trenes de madera.
Cada muñeco:
• Produce un beneficio neto de 3 €.
• Requiere 2 horas de trabajo de acabado.
• Requiere 1 hora de trabajo de carpintería.
Cada tren:
• Produce un beneficio neto de 2 €.
• Requiere 1 hora de trabajo de acabado.
• Requiere 1 hora trabajo de carpintería.
Cada semana Gepetto puede disponer de:
• Todo el material que necesite.
• Solamente 100 horas de acabado.
• Solamente 80 horas de carpintería.
También:
• La demanda de trenes puede ser cualquiera (sin límite).
• La demanda de muñecos es como mucho 40.
Gepetto quiere maximizar sus beneficios.
¿Cuántos muñecos y cuántos trenes debe fabricar?
Este problema es un ejemplo típico
de un problema de programación lineal (PPL).
Variables de Decisión Función Objetivo. En cualquier PPL, Restricciones
la decisión a tomar es como Son desigualdades que
x = nº de muñecos maximizar (normalmente el limitan los posibles valores
producidos a la beneficio) o minimizar (el coste) de de las variables de
semana alguna función de las variables de decisión.
y = nº de trenes decisión. Esta función a maximizar o En este problema las
producidos a la minimizar se llama función objetivo. restricciones vienen dadas
semana por la disponibilidad de
horas de acabado y
El objetivo de Gepetto es elegir carpintería y por la
valores de x e y para maximizar 3x demanda de muñecos.
También suele haber
+ 2y. Usaremos la variable z para
restricciones de signo o no
denotar el valor de la función negatividad:
objetivo. La función objetivo de x≥0
Gepetto es: y≥0
Max z = 3x + 2y
Restricciones
Cuando x e y crecen, la función objetivo de Gepetto también crece. Pero
no puede crecer indefinidamente porque, para Gepetto, los valores de x e
y están limitados por las siguientes tres restricciones:
Restricción 1: no más de 100 horas de tiempo de acabado pueden ser usadas.
Restricción 2: no más de 80 horas de tiempo de carpinteria pueden ser usadas.
Restricción 3: limitación de demanda, no deben fabricarse más de 40 muñecos.
Estas tres restricciones pueden expresarse matematicamente por las
siguientes desigualdades:
Restricción 1: 2 x + y ≤ 100
Restricción 2: x + y ≤ 80
Restricción 3: x ≤ 40
Además, tenemos las restricciones de signo: x ≥ 0 e y ≥ 0
Formulación matemática de PL
Variables de Decisión x = nº de muñecos producidos a la semana
y = nº de trenes producidos a la semana
Muñeco Tren
Beneficio 3 2 Max z = 3x + 2y (función objetivo)
Acabado 2 1 ≤ 100 2 x + y ≤ 100 (acabado)
Carpintería 1 1 ≤ 80 x + y ≤ 80 (carpinteria)
Demanda ≤ 40 x ≤ 40 (demanda muñecos)
x ≥0 (restricción de signo)
y ≥0 (restricción de signo)
Formulación matemática del PPL
Para el problema de Gepetto, combinando las restricciones de
signo x ≥ 0 e y ≥ 0 con la función objetivo y las restricciones,
tenemos el siguiente modelo de optimización:
Max z = 3x + 2y (función objetivo)
Sujeto a (s.a:)
2 x + y ≤ 100 (restricción de acabado)
x + y ≤ 80 (restricción de carpinteria)
x ≤ 40 (restricción de demanda de muñecos)
x ≥0 (restricción de signo)
y ≥0 (restricción de signo)
EJERCICIO 1: La ensalada
La naranja cuesta 4 pesos/kilo y tiene 12 gramos de vitamina C y un gramo
de vitamina A. La uva cuesta 60 pesos/kilo y tiene 0 gramos de vitamina C y
26 gramos de vitamina A. La zanahoria cuesta 12 pesos/kilo y tiene 3
gramos de vitamina C y 10 gramos de vitamina A. La lechuga cuesta 4
pesos/kilo y tiene 2 gramos de vitamina C y 4 gramos de vitamina A.
Se desea preparar una ensalada para 10 personas que contenga en total
cuando menos 10 gramos de vitamina C y 12 gramos de vitamina A.
EJERCICIO 2: La felicidad de Pepe
EJERCICIO 3: Casas de muñecas
Una empresa, especializada en la fabricación de mobiliario para
casas de muñecas, produce cierto tipo de minimesas y minisillas
que vende a 2000 unidades monetarias (u.m.) 3000 u.m. por
cada artículo, respectivamente. Desea saber cuántas unidades
de cada artículo debe fabricar diariamente un operario para
maximizar los ingresos, teniendo las siguientes restricciones:
El número total de unidades de los dos tipos no podrá exceder
de cuatro por día y operario.
Cada minimesa requiere dos horas para su fabricación; cada
minisilla, tres horas. La jornada laboral máxima es de diez horas.
El material utilizado en cada minimesa cuesta 400 u.m. El
utilizado en cada minisilla cuesta 200 u.m. Cada operario
dispone de 1200 u.m. diarias para material.
Plantear y resolver el anterior problema como un modelo de
programación lineal.