Investigacion de operaciones 1 unidad

INSTITUTO TECNOLÓGICO
del Istmo


MATERIA:
INVESTIGACION DE OPERACIONES
PROFESOR:
MIGUEL ANGEL NUÑEZ BIELMA

ALUMNO:
MANUEL VALDIVIESO MIJANGOS

ESPECIALIDAD:
ING. SISTEMAS COMPUTACIONALES

HEROICA CD. JUCHITAN DE ZARAGOZA OAX

Heroica Ciudad Juchitán de Zaragoza, Oax., Agosto 2010.Programación no lineal
En matemáticas, Programación no lineal (PNL) es el proceso de resolución de un sistema de igualdades y desigualdades sujetas a un conjunto de restricciones sobre un conjunto de variables reales desconocidas, con un función objetivo a maximizar (o minimizar), cuando alguna de las restricciones o la función objetivo noson lineales
Formulación matemática del problema
El problema de programación no lineal puede enunciarse de una forma muy simple:
maximizar una función objetivo
o
minimizar una función objetivo (de coste)
donde

Métodos de resolución del problema
Si la función objetivo f es lineal y el espacio restringido es un politopo, el problema es de Programación lineal y puede resolverse utilizandoalguno de los bien conocidos algoritmos de programación lineal.
Si la función objetivo es cóncava (problema de maximización), o convexa (problema de minimización) y el conjunto de restricciones es convexo, entonces se puede utilizar el método general de Optimización convexa
Existe una variedad de métodos para resolver problemas no convexos. Uno de ellos consiste en utilizar formulacionesespeciales de problemas de programación lineal. Otro método implica el uso de técnicas de Ramificación y poda, cuando el problema se divide en subdivisiones a resolver mediante aproximaciones que forman un límite inferior del coste total en cada subdivisión. Mediante subdivisiones sucesivas, se obtendrá una solución cuyo coste es igual o inferior que el mejor límite inferior obtenido por alguna de lassoluciones aproximadas. Esta solución es óptima, aunque posiblemente no sea única. El algoritmo puede ser parado antes, con la garantía de que la mejor solución será mejor que la solución encontrada en un porcentaje acotado. Ello se utiliza en concreto en problemas importantes y especialmente difíciles y cuando el problema cuenta con costes inciertos o valores donde la incertidumbre puede ser estimadaen un grado de fiabilidad apropiado.
Las condiciones de Karush-Kuhn-Tucker proporcionan las condiciones necesarias para que una solución sea óptima.
Ejemplos bidimensional

La intersección de la línea con el espacio de restricciones representa la solución.
Un problema sencillo puede definirse por las restricciones:
x1 ≥ 0
x2 ≥ 0
x12 + x22 ≥ 1
x12 + x22 ≤ 2
con una función objetivo aser maximizada
f(x) = x1 + x2
donde x = (x1, x2)
Ejemplo tridimensional

La intersección de la superficie superior con el espacio de restricciones en el centro representa la solución.
Otro problema simple se define por la restricciones:x12 − x22 + x32 ≤ 2
x12 + x22 + x32 ≤ 10
con una función objetivo a ser maximizada
f(x) = x1x2 + x2x3
donde x = (x1, x2, x3)

Ilustración grafica deproblemas de programación no lineal
Ilustración grafica de problemas de PLN.
Procurando mejorar la búsqueda de soluciones a este tipo de problemas se han
empleado, en los últimos tiempos, técnicas heurísticas y técnicas inteligentes como
Colonia de Hormigas, Recocido Simulado, Búsqueda Tabú, Algoritmos Genéticos,
Partículas Swarm, entre otras. En general, están basados en la aleatoriedad y enalgunos
criterios obtenidos de la experiencia del diseñador para encontrar una buena solución.
Estas técnicas usan la función objetivo solo para evaluar la calidad de las soluciones, en
muchas ocasiones ignorando la información matemática (gradiente) del problema que se
encuentra en esta función.

La Programación No Lineal (PNL) provee una serie de herramientas que manipulan en
forma...