Programación No Lineal Antonio H. Escobar Z. 2015 Universidad Tecnológica de Pereira – Colombia...

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