jump to navigation

UNIDAD 3

PROGRAMACION NO LINEAL

3.1 Problemas de programación no lineal

3.2 Puntos de inflexión programación no lineal

3.2.1 Máximos y mínimos programación no lineal

3.3 Problemas no restringidos programación no lineal

3.3.1 Multiplicadores de Lagranje Lambda

 

 

 

INTRODUCCION

La 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. Evidentemente, la estructura del problema puede ser muy variada, según las funciones que en él intervengan (a diferencia de la Programación Lineal (PL) donde la forma especial del conjunto de oportunidades y de la función objetivo permiten obtener resultados generales sobre las posibles soluciones y facilitan los tratamientos algorítmicos de los problemas). Ello ocasiona una mayor dificultad en la obtención de resultados, que se refleja también en la dificultad de la obtención numérica de las soluciones. En este sentido, hay que distinguir entre las diversas caracterizaciones de óptimo, que sólo se emplean como técnicas de resolución en problemas sencillos, y los métodos numéricos iterativos, cuyo funcionamiento se basa en estas caracterizaciones, para la resolución de problemas más generales.

 El tema que abordamos está compuesto por los siguientes epígrafes: en la sección 1, aparte de esta introducción, definimos el problema general de Programación no Lineal que estudiamos, y daremos las definiciones y resultados básicos que se emplearán a lo largo de todo el tema. Asimismo, se recuerda el estudio de los problemas irrestrictos (PI) y de los problemas con restricciones de igualdad (PRI). La sección 2 se dedica a establecer y dar los conceptos básicos de los problemas con restricciones de desigualdad (PRD), mientras que la sección 3 estudia la resolución de estos problemas a través de la definición de punto estacionario, y algunas de sus variaciones para casos especiales. Con la utilización del llamado punto minimax, se aborda en la sección 4 el concepto de dualidad en Programación Matemática.

El problema general de Programación no Lineal que estudiaremos a lo largo de todo el tema toma la 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.

Así pues, el problema (PNL) consiste en encontrar las variables de decisión factibles para el problema para las cuales la función objetivo tome el mayor valor posible. Si para un punto, la función objetivo toma el valor máximo de todos los puntos situados en algún entorno suyo, se dice que el máximo es local. Si se encuentra un punto que produce el valor máximo de f en todo el conjunto de oportunidades, el máximo es global:

Definición 1.

 Un punto x* ∈ X se dice que es un máximo local de (PNL) si existe un entorno de

x*, E(x*) tal que ∀ x E(x*) ∩ X, se verifica f(x*) ≥ f(x).

 Definición 2.

Un punto x* ∈ X se dice que es un máximo global de (PNL) si ∀ x X, se verifica

f(x*) ≥ f(x).

 Es importante tener en cuenta que esta formulación del problema no supone pérdida de  generalidad,  ya  que  si  el  objetivo  fuese  minimizar  la  función  objetivo,  se  puede maximizar su opuesta. Por otro lado, cualquier restricción con ≥ se puede convertir en una de ≤ sin más que cambiar de signo, y las restricciones de igualdad se pueden descomponer en dos, con las dos desigualdades. No obstante, también enunciaremos los resultados más importantes para el problema de mínimo.

 Antes de pasar a estudiar los diferentes tipos de problemas, vamos a enunciar dos teoremas cuya utilidad es crucial en el tema que nos ocupa. Ambos están orientados a poder asegurar la globalidad de los óptimos obtenidos. En efecto, veremos que la casi totalidad de los métodos y caracterizaciones empleados en la resolución de problemas no lineales sólo nos garantizan la obtención de óptimos locales. El primero de los teoremas que enunciamos (Teorema de Weierstrass) nos da las condiciones bajo las cuales podemos asegurar la existencia de óptimos globales en un problema. El segundo (Teorema Local – Global) nos proporciona las condiciones que nos permiten afirmar que un óptimo local es global. La demostración de ambos teoremas puede encontrarse en Caballero, González y Triguero (1992):

 Teorema 1. Teorema de Weierstrass.

Dado el problema (PNL), si el conjunto de oportunidades X es compacto y no vacío, y la función objetivo f es continua en X, entonces el problema (PNL) posee máximo y mínimo globales.

Teorema 2. Teorema Local – Global.

Dado el problema (PNL), si el conjunto de oportunidades X es convexo, y la función objetivo f es continua y cóncava (resp. convexa) en X, entonces cualquier máximo (resp. mínimo) local de (PNL) es global.

sujeto a:                                                   

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.

Supóngase que (1) es un problema de maximización.

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

Comentarios»

No comments yet — be the first.

Deja un comentario

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

Seguir

Recibe cada nueva publicación en tu buzón de correo electrónico.

%d personas les gusta esto: