"CONCEPTOS BÁSICOS DE PROGRAMACIÓN NO LINEAL"

°°°°   Programación no Lineal   °°°°

La programación lineal ha demostrado ser una herramienta sumamente poderosa, tanto en la modelización de problemas de la vida real como en la teoría matemática de amplia aplicación. Sin embargo, muchos problemas interesantes de optimización son no lineales. El estudio de estos problemas implica una mezcla diversa de álgebra lineal, cálculo multivariado, análisis numérico y técnicas de computación. Entre las áreas especiales importantes se encuentra el diseño de algoritmos de computación (incluidas las técnicas de puntos interiores para programación lineal), la geometría y el análisis de conjuntos convexos y funciones, y el estudio de problemas especialmente estructurados, tales como la programación cuadrática. La optimización no lineal proporciona información fundamental para el análisis matemático, y se usa extensamente en las ciencias aplicadas (en campos tales como el diseño de ingeniería, el análisis de regresión, el control de inventario y en la exploración geofísica).

programacion no lineal intro

 

 

****  Conceptos básicos de problemas de programación no lineal.

 

•     Programación no lineal: 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 una función objetivo a maximizar, cuando alguna de las restricciones o la función objetivo no son lineales.

•     Qué es una función: una función es una cosa que hace algo. Por ejemplo, una máquina de moler café es una función que transforma los granos de café en polvo. La función (objetivo) traza, traduce el dominio de entrada (denominado región factible) en un rango de salida con dos valores finales denominados valores máximo y mínimo.

•     El método Simplex es un algoritmo de solución muy utilizado para resolver programas lineales. Es la solución algorítmica inicial para resolver problemas de Programación Lineal (PL). Este es una implementación eficiente para resolver una serie de sistemas de ecuaciones lineales. Mediante el uso de una estrategia ambiciosa mientras se salta desde un vértice factible hacia el próximo vértice adyacente, el algoritmo termina en una solución óptima.

• Un algoritmo es una serie de pasos para cumplir con una tarea determinada.

• Región de Factibilidad Ilimitada: Tal y como se mencionó anteriormente, aprenda que una solución ilimitada requiere una región de factibilidad cerrada ilimitada. La situación inversa de este enunciado podría no ocurrir. Por ejemplo, el siguiente problema de PL tiene una región de factibilidad cerrada ilimitada, sin embargo, la solución es limitada.

• Redundancia Entre las Restricciones: Redundancia significa que algunas de las restricciones no son necesarias dado que existen otras más severas.

 

CONCEPTOS BÁSICOS DE PROBLEMAS DE PROGRAMACIÓN NO LINEAL. 

  

****  Ilustración grafica de problemas de programación no lineal.

Cuando un problema de programación no lineal tiene solo una o dos variables, se puede representar gráficamente de forma muy parecida a algún ejemplo anterior de programación lineal. Se verán unos cuantos ejemplos, ya que una representación grafica de este tipo proporciona una visión global de las propiedades  de las soluciones optimas de programación lineal y no lineal. Con el fin de hacer hincapié en las diferencias entre programación lineal y no lineal, se usaran algunas variaciones no lineales del problema anterior. 

 

ILUSTRACIÓN GRAFICA DE PROBLEMAS DE PROGRAMACIÓN NO LINEAL. 

****  Tipos de problemas de programación no lineal.

 
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 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.
   Optimización no restringida.
Optimización linealmente restringida.
Programacion separable.
Entre otras
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 una función objetivo a maximizar, cuando alguna de las restricciones o la función objetivo no son lineales.

Una suposición importante de programación lineal es que todas sus funciones (función objetivo y funciones de restricción) son lineales. Aunque, en esencia, esta suposición se cumple para muchos problemas prácticos, con frecuencia no es así. De hecho muchos economistas han encontrado que cierto grado de no linealidad es la regla, y no la excepción, en los problemas de planeación económica, por lo cual, muchas veces es necesario manejar problemas de programación no lineal, lo cual  vamos a analizar enseguida.

De la manera general el problema de programación no lineal consiste en encontrar:

X=(X₁, X₂, X₃, X₄, X_N) para

Maximizar f(X), sujeta a

G_i(X)<= b_i  para i=1,2…..m,

Y    X=>0,

Donde  f(X) y g_i(x) son funciones dadas de n variables de decisión.

  

DEFINICIÓN

Se puede expresar un problema de programación no lineal (PNL)de la siguiente manera:

Encuentre los valores de las variables  que

Como en la programación lineal z es el funcional del problema de programación no lineal y

son las restricciones del problema de programación no lineal.

Un problema de programación no lineal es un problema de programación no lineal no restringido.

El conjunto de puntos , tal que  es un número real, es, entonces, es el conjunto de los números reales.

Los siguientes subconjuntos de  (llamados intervalos) serán de particular interés:

Y en forma análoga a las definiciones de la programación lineal.

  

DEFINICIÓN

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

  

DEFINICIÓN

 

Por supuesto, si  son funciones lineales, entonces (1) será un problema de programa­ción lineal y puede resolverse mediante el algoritmo simplex