Programación No Lineal
Antonio H. Escobar Z.
2015
Universidad Tecnológica de Pereira – Colombia
Posgrado en Ingeniería IndustrialMaestría en Investigación Operativa y
Estadística
Qué es Optimizar?
• Es modificar un proceso, un sistema o la forma de realizar una actividad para mejorar su eficiencia.
• Es hacer más con los mismos recursos.
• Es hacer lo mismo con menos recursos.
• Es cambiar recursos ineficientes por recursos eficientes.
• Es eliminar recursos existentes que afectan negativamente el sistema.
• Es involucrar cambios tecnológicos, productivos y organizacionales.
Porque Optimizar?
• Porque existen recursos en las organizaciones que no están siendo aprovechados adecuadamente.
• Porque no se alcanzan los resultados deseados.
• Porque se requiere aumentar la competividad a costos eficientes de inversión, operación y mantenimiento.
• Porque se tienen recursos ineficientes o que no se necesitan.
• Porque debe adecuarse el sistema existente para que responda a las exigencias futuras.
Los procesos de optimización tratan de responder los siguientes interrogantes:
• Puede obtenerse un diseño más económico?
• Se están utilizando eficientemente recursos que son escasos o limitados o no renovables?
• Puede obtenerse una operación más económica?
• Se están utilizando eficientemente recursos que son costosos?
La optimización está asociada a:
• Nivel de conocimiento científico acumulado en los grupos de desarrollo.
• Nivel de tecnología que los miembros del grupo dominan.
• Avance del conocimiento existente a nivel de modelamiento de sistemas reales.
• Nivel de exigencia de las tareas o procesos.
• Variabilidad de los aspectos que se pueden resolver.
• Desarrollo actual de los métodos de solución de los modelos matemáticos resultantes.
La optimización está asociada a:
• Adecuada valoración de resultados.
• Flujo de ideas entre los miembros del grupo.
• Costos encallados resultantes.
• Calidad de los insumos (información de entrada).
• Estrategias utilizadas.
• Desarrollo de la infraestructura tecnológica que se usa.
Abarca un conjunto de métodos científicos que apoyan la toma de decisiones y que permiten determinar la mejor forma de diseñar y operar un sistema bajo condiciones que exigen el uso de recursos escasos o costosos.
Provee un conjunto de algoritmos que pueden ser implementados en sistemas de cómputo y que se constituyen en herramientas efectivas para resolver problemas con soluciones alternativas y tomar decisiones.
Se aplica en todas las disciplinas.
Investigación de Operaciones
Herramientas:
Problema de la Vida real
Modelo
Matemático de
la parte que
deseo controlar
Solución
Matemática
Técnicas demodelamiento
Técnicas desolución
Realimentación o ajustes para la implementación
El modelo puede no existir
SIMULACIONSIMULACION
IDENTIFICACION IDENTIFICACION
Evaluacióndel
Funcionamientodel
Sistema
Información
OPTIMIZACIONOPTIMIZACION
Funciones de Respuesta
Parámetros
Caracterización
Planes de InversiónPolíticas Estratégicas
Planes OperativosDiseños
SIMULACIONSIMULACION
Verificaciónde la
Bondadde las
Decisiones
Encadenamiento de modelos
Definición de Objetivos y adición de
metas
Modelo de operación
Modelo de optimización
Mínimos y máximos globales y locales, puntos de inflexión:
• Función Objetivo: Medida de la efectividad buscada expresada en función de las variables de decisión. Es lo que se minimiza o se maximiza.
• Variables de decisión: Decisiones Cuantificables sobre las que se ejerce control. Por ejemplo: ruta que debe seguir un vehículo de transporte masivo, localización y número de paradas, número de vehículos, precio de pasaje.• Restricciones: Factores que limitan los valores que pueden asumir las variables de decisión. Por ejemplo: capacidad máxima de cada vehículo.
• Parámetros: Datos o recursos que asumen valores constantes y que forman los coeficientes de las variables. Por ejemplo, velocidad de desplazamiento, costo de operación por kilómetro.
Componentes de un problema de Optimización:
Métodos de solución
Métodos de solución
Métodos de solución
Métodos de solución
Complejidad Descriptiva: cantidad de información que debe suministrarse para tener una descripción adecuada del sistema.
Complejidad Generativa: cantidad de instrucciones que se deben dar para construir el sistema bajo estudio.
Complejidad Computacional: cantidad de tiempo y esfuerzo implicado en la solución del problema. En PL esta asociada con el tamaño del problema (n y m).
Complejidad Organizacional: variedad de formas de ordenamiento de los componentes del sistema.
Complejidad Operativa: variedad de modos de operación de los componentes del sistema y del propio sistema.
Problema de Programación No Lineal complejidad
• Un modelo matemático representa el desempeño y comportamiento de un sistema, en términos de ecuaciones matemáticas, ofreciendo resultados cuantitativos
• Un modelo matemático pueden elaborarse a partir del entendimiento físico de un sistema ó a partir de curvas o datos experimentales.
• El modelo puede estar constituido por ecuaciones algebraicas, ecuaciones diferenciales ordinarias y/o parciales, ecuaciones integrales ó por la combinación de ellas.
Modelo matemático
Mundo Real
Mundo Real
Mundo Real
Mundo Real
Min t j h CTt(GTjth)
sujeto a:
GDzth - uTN(z) LDuzth = 0
GDzth + GHAzth + DEFzth = DEMzth
ENuth - jL1(u) GTEjuth
- vL2(u) LLvuth = 0
Min t j h CTt(GTjth)
sujeto a:
GDzth - uTN(z) LDuzth = 0
GDzth + GHAzth + DEFzth = DEMzth
ENuth - jL1(u) GTEjuth
- vL2(u) LLvuth = 0
Mundo Virtual
Min t j h CTt(GTjth)
sujeto a:
GDzth - uTN(z) LDuzth = 0
GDzth + GHAzth + DEFzth = DEMzth
ENuth - jL1(u) GTEjuth
- vL2(u) LLvuth = 0
Min t j h CTt(GTjth)
sujeto a:
GDzth - uTN(z) LDuzth = 0
GDzth + GHAzth + DEFzth = DEMzth
ENuth - jL1(u) GTEjuth
- vL2(u) LLvuth = 0
PIB 5.2%
Costo de combustibles
Hidrología
Inflación = 10%
Devaluación 12%
Costo de
transporte
Min t j h CTt(GTjth)
sujeto a:
GDzth - uTN(z) LDuzth = 0
GDzth + GHAzth + DEFzth = DEMzth
ENuth - jL1(u) GTEjuth
- vL2(u) LLvuth = 0
Min t j h CTt(GTjth)
sujeto a:
GDzth - uTN(z) LDuzth = 0
GDzth + GHAzth + DEFzth = DEMzth
ENuth - jL1(u) GTEjuth
- vL2(u) LLvuth = 0
Mundo Virtual
Costo de oportunidad
* Una fábrica produce mesas metálicas con superficie de vidrio.
* La cantidad de mesas fabricadas semanalmente está limitada por la cantidad máxima disponible de tubos metálicos y de láminas de vidrio que puede adquirir en el mercado:
50 tubos/semana 75 láminas/semana
Ejemplo:
Con el propósito de maximizar las ganancias, la fábrica diversifica sus productos. Para esto se diseñan cuatro tipos de mesas y se evalúa la ganancia neta que cada una produce y sus requerimientos de tubos y vidrio.
Ejemplo:
Tipo de mesa que se fabrica en la
actualidad
Ejemplo:
150 500 200
1 4 1
1 1 2
400
3
1
Lucro
:
hierr
o:50
75 vidrio:
cantidad disponible
Que modelos debe fabricar y en que cantidad para obtener el máximo lucro?
Ejemplo:
150 500 200
1 4 1
1 1 2
400
3
1
Lucro
:
hierr
o:50
75 vidrio:
cantidad máxima disponible
variables de decisión:
x2x1 x3
x4
150 500 200 400
Lucro:
variables de decisión:
x2x1 x3
x4
Modelamiento:
x1 x2 x4150 + 500 + 200max x3+ 400
Función Objetivo
Ejemplo:
1 4 1 3
hierro:
50
variables de decisión:
x2x1 x3
x4
x1 x2 x41 + 4 + 1x3+ 3 ≤ 50 : hierro
Restricción asociada a la cantidad de hierro disponible
Ejemplo:
1 1 2 1 75 vidrio:
variables de decisión:
x2x1 x3
x4
x1 x2 x41 + 1 + 2x3+ 1 ≤ 75 : vidrio
Restricción asociada a la cantidad de vidrio disponible
x1 x2 x4150 + 500 + 200
x1 x2 x4+ 4 +
x1 x2 x4+ + 2
max x3+ 400
x3+ 3
x3+
≤ 50
≤ 75
Modelo resultante:
: hierro
: vidrio
x1 x2 x4150 + 500 + 200
x1 x2 x4+ 4 +
x1 x2 x4+ + 2
max x3+ 400
x3+ 3
x3+
= 50
= 75
Modelamiento:
: hierro
: vidrio
+
+
x5
x6
Variables de holgura
x1 x2 x4150 + 500 + 200
x1 x2 x41 + 4 + 1
x1 x2 x41 + 1 + 2
max x3+ 400
x3+ 3
x3+ 1
= 50
= 75
Caso de estudio: la empresa fabrica únicamente mesas tipo 1 y evalúa la posibilidad de fabricar otro tipo de mesa.
: hierro
: vidrio
+
+
x5
x6
x1 x2 x4150 + 500 + 200
x1 x2 x41 + 4 + 1
x1 x2 x41 + 1 + 2
max x3+ 400
x3+ 3
x3+ 1
= 50
= 75
: hierro
: vidrio
+
+
x5
x6
0
0
0
0
0
0
Solución básica: Lucro = 7500 ; x1 = 50 ; x6 = 25 ;
La cantidad de mesas tipo 1 construidas son limitadas por el recurso que primero se agota: cantidad de tubos de hierro disponibles (recurso1). Con 50 tubos puedo hacer 50 mesas tipo 1 (se requiere 1 tubo por mesa). Del recurso 2 (m2 de vidrio) se usan 50 m2 y quedan 25 m2 sobrantes.
La restricción 1 se activa y la restricción 2 queda con holgura: x6 = 25 m2
0
Solución básica:
x1 x2 x4150 + 500 + 200
x1 x2 x41 + 4 + 1
x1 x2 x41 + 1 + 2
max x3+ 400
x3+ 3
x3+ 1
= 50
= 75
+
+
x5
x6
0
0
0
0
• Una mesa tipo 2 (que requiere 4 tubos de hierro) desplaza 4 mesas tipo 1 (que requieren 1 tubo de hierro cada una). Esto porque esta restricción está en su límite.
• Respecto al recurso: m2 de vidrio, no hay afectación de mesas tipo 1 porque esta restricción tiene holgura.
• En consecuencia, el beneficio neto de fabricar una mesa tipo 2 en lugar de una mesa tipo 1 es: 500 – 4(150) = -100. (no es conveniente).
0
Es conveniente fabricar mesas tipo 2 en lugar de mesas tipo 1 ?
: hierro
: vidrio
x1 x2 x4150 + 500 + 200
x1 x2 x41 + 4 + 1
x1 x2 x41 + 1 + 2
max x3+ 400
x3+ 3
x3+ 1
= 50
= 75
+
+
x5
x6
0
0
0
0
• Una mesa tipo 3 (que requiere 3 tubos de hierro) desplaza 3 mesas tipo 1 (que requiere 1 tubo de hierro cada una). Esto porque esta restricción está en su límite.
• Respecto al recurso: m2 de vidrio, no hay afectación de mesas tipo 1 porque esta restricción tiene holgura.
• En consecuencia, el beneficio neto de fabricar una mesa tipo 3 en lugar de una mesa tipo 1 es: 400 – 3(150) = - 50. (no es conveniente).
0
Es conveniente fabricar mesas tipo 3 en lugar de mesas tipo 1 ?
: hierro
: vidrio
x1 x2 x4150 + 500 + 200
x1 x2 x41 + 4 + 1
x1 x2 x41 + 1 + 2
max x3+ 400
x3+ 3
x3+ 1
= 50
= 75
+
+
x5
x6
0
0
0
0
• Una mesa tipo 4 (que requiere 1 tubo de hierro) desplaza 1 mesa tipo 1 (que requiere 1 tubo de hierro cada una). Esto porque esta restricción está en su límite.
• Respecto al recurso: m2 de vidrio, no hay afectación de mesas tipo 1 porque esta restricción tiene holgura.
• En consecuencia, el beneficio neto de fabricar una mesa tipo 4 en lugar de una mesa tipo 1 es: 200 – 1*(150) = + 50. (si es conveniente).
0
Es conveniente fabricar mesas tipo 4 en lugar de mesas tipo 1 ?
: hierro
: vidrio
Solución óptima:
5 35
Lucro: 9000