UNIDAD 3

INSTITUTO TECNOLÓGICO SUPERIOR DE LA MONTAÑA

EXTENSIÓN  ACADÉMICA ILIATENCO

GENIERÍA EN SISTEMAS COMPUTACIONALES

ASIGNATURA: INVESTIGACIÓN DE OPERACIONES

UNIDAD  3: PROGRAMACIÓN NO LINEAL

 TRABAJO:

INVESTIGACIÓN

DOCENTE:

MTI. Adrián Nava Sánchez

ALUMNO:

TEÓDULO ZACARÍAS CANTÚ

NUMERO DE CONTROL:

S14122013

Programación no lineal (PNL)

Es una parte de la Investigación Operativa cuya misión es proporcionar una serie de resultados y técnicas tendentes a la determinación de puntos óptimos para una función (función objetivo) en un determinado conjunto (conjunto de oportunidades), donde tanto la función objetivo, como las que intervienen en las restricciones que determinan el conjunto de oportunidades pueden ser no lineales.

3.1 Conceptos Básicos de Problemas de Programación No Lineal

El problema general de Programación no Lineal es de siguiente forma:

donde:

x = (x1, x2, xn) ∈ Rn es la variable instrumental o de decisión.

  F: D ⊂ Rn  .→ R es la función objetivo, es decir, aquella que se desea optimizar (en este caso, maximizar), y D su dominio.

g : D ⊂ Rn  → Rm  es una función vectorial g = (g1, g2,  gm) compuesta por  las funciones de restricción.

 b ∈ Rm  es el vector de términos independientes, o recursos. Cada expresión gi(x) ≤ bidetermina una restricción sobre las variables instrumentales.

 Se  denomina  conjunto  de  oportunidades  del  problema,  o  conjunto  factible  al conjunto de puntos de D que satisfacen las restricciones del problema, es decir,

 X = {x ∈ D / g(x) ≤ b}

 Una combinación de variables instrumentales x se dice que es factible para el problema (PNL) si pertenece a X.

La región factible para el problema de programación no lineal es el conjunto de puntos  que satisfacen las m restricciones.

3.2 Ilustración Gráfica de Problemas de Programacion No Lineal

Cuando un problema de programación no lineal tiene sólo una o dos variables, se puede representar gráficamente de forma muy parecida al ejemplo de la Wyndor Glass Co. de programación lineal

La figura 13.5 muestra lo que ocurre con este problema si los únicos cambios que se hacen al modelo de la sección  son que la segunda y tercera restricciones funcionales se sustituyen por la restricción no lineal 9x{ + 5x2 < 216. Compare las figuras 13.5 y La solución óptima sigue siendo (a^  x2) = (2,6). Todavía se encuentra sobre la frontera de la región factible, pero no es una solución factible

en un vértice (FEV). La solución óptima pudo haber sido una solución FEV con una función objetivo diferente (verifique Z = 3xx + x2), pero que no necesite serlo significa que ya no se puede aprovechar la gran simplificación utilizada en programación lineal que permite limitar la búsqueda de una solución óptima para las soluciones FEV

Ahora suponga que las restricciones lineales de la sección 3.1 se conservan sin cambio, pero que la función objetivo se hace no lineal. Por ejemplo, si.

entonces la figura 13.7 ilustra que la solución óptima es (*l5 x2 ) = (3,3), que se encuentra dentro de la frontera de la región factible. (Se puede comprobar que esta solución es óptima si se usa cálculo para derivarla como un máximo global no restringido; como también satisface las restricciones, debe ser óptima para el problema restringido.) Por lo tanto, es necesario que un algoritmo general para resolver problemas de este tipo tome en cuenta todas las soluciones en la región factible, y no sólo aquellas que están sobre la frontera.

3.3 Tipos de problemas de programación no lineal

Los problemas de programación no lineal se presentan de muchas formas distintas. Al contrario del método simplex para programación lineal, no se dispone de un algoritmo que resuelva todos estos tipos especiales de problemas. En su lugar, se han desarrollado algoritmos para algunas clases (tipos especiales) de problemas de programación no lineal. Se introducirán las clases más importantes y después se describirá cómo se pueden resolver algunos de estos problemas.

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 utilizando alguno 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 formulaciones especiales 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 las soluciones 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 estimada en un grado de fiabilidad apropiado.

Las condiciones de Karush-Kuhn-Tucker proporcionan las condiciones necesarias para que una solución sea óptima.

Los tipos de problemas de programación no lineal son:

Optimización no restringida.

Optimización linealmente restringida.

 Programación cuadrática

 Programación convexa.

3.4 Optimización clásica

Si la restricción no existe, o es una restricción de igualdad, con menor o igual número de variables que la función objetivo entonces, el cálculo diferencial, da la respuesta, ya que solo se trata de buscar los valores extremos de una función.

3.4.1 Puntos de inflexión

Un punto de inflexión es un punto donde cambia la curvatura de la función.

Si x=a es un punto de inflexión → f”(a)=0

En el problema nos dan 2 datos:

f(x) pasa por el punto (3,1), es decir f(3)=1

x=3 es un punto de inflexión, es decir, f”(3)=0

Con esta información, obtenemos b y d

f(3)=1 → 1=33+b32+2.3+d → 1=27+9b+6+d → 9b+d=-32

f’(x)=3x2+2bx+2

f”(x)=6x+2b

f”(3)=0 → 6.3+2b=0 → 18+2b=0 → 2b=-18 → b=-18/2=-9

9b+d=-32; 9.(-9)+d=-32; -81+d=-32; d=-32+81; d=49

Solución: b=-9 y d=49

3.4.2 Máximos y mínimos

Puntos minimax.

El punto minimax de la función lagrangiana es otro concepto relacionado con la solución de un problema de optimización. Si bien su definición no le hace útil a la hora de la resolución directa del problema, sí constituye un paso intermedio muy importante en la obtención del problema dual, que estudiaremos más adelante. En esta sección definimos dicho punto y estudiamos su relación con otro concepto, el punto de silla de la lagrangiana.

La relación del punto minimax con la solución del problema de programación no lineal se obtiene de forma inmediata sin mas que tener en cuenta que:

Min L (x, ë ) = f (x) − Max ët [g(x) − b]R m+R m+

Si gi (x) – bi ≤ 0, entonces ëi [gi(x) - bi] ≤ 0, luego

Max ëi ( gi (x) − bi ) = 0R m+ (se alcanza en ë = 0). Por tanto, si x ∈ X, Min L (x, ë ) = f (x) .R m+ Si gi (x) – bi > 0, entonces Sup ëi [gi(x) - bi] = ∞, por lo que en este caso no se alcanza el R m+ mínimo de la Lagrangiana.

Por tanto,

Max Min L (x, ë ) = Max f (x) D R m+ X

Así pues, si (x0, ë0) es un punto minimax, x0 es una solución óptima del problema original.

Programación separable.

Programación no convexa.

Programación geométrica.

Programación fraccional.

Problema de complementariedad.

BIBLIOGRAFÍA

Baumol, W., Teoría Económica y Análisis de Operaciones, N.J, Prentice may, 1980,.; .

Dantzing, Linear Programming and Extensions, Edit. Princenton University Press, 1963

Dorfman, Samuelson y Salow, Programación Lineal y Análisis Económico, Madrid, España, Edit. Aguilar, 1964