Programación no lineal

Programación no lineal

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, cuando alguna de las restricciones o la función objetivo no son lineales.

Contenido

Formulación matemática del problema

El problema de programación no lineal puede enunciarse de una forma muy simple:

\max_{x \in X}f(x) maximizar una función objetivo

o

\min_{x \in X}f(x) minimizar una función objetivo (de coste)

donde

f: R^n \to R
X \subseteq R^n.

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 utilizando alguno de los bien conocidos algoritmos de programación lineal.

Si la función objetivo es concava (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 limite 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.

Ejemplos

Ejemplo 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 a ser maximizada

f(x) = x1 + x2

donde x = (x1, x2)

Ejemplo tridimensional

La intersección de la superfie superior con el espacio de restricciones en el centro representa la solución

Otro problema simple se define por la restricciones:x12x22 + x32 ≤ 2

x12 + x22 + x32 ≤ 10

con una función objetivo a ser maximizada

f(x) = x1x2 + x2x3

donde x = (x1, x2, x3)

Véase también

Referencias

  • Avriel, Mordecai (2003). Nonlinear Programming: Analysis and Methods. Dover Publishing. ISBN 0-486-43227-0.
  • Bazaraa, Mokhtar S. and Shetty, C. M. (1979). Nonlinear programming. Theory and algorithms. John Wiley & Sons. ISBN 0-471-78610-1.
  • Nocedal, Jorge and Wright, Stephen J. (1999). Numerical Optimization. Springer. ISBN 0-387-98793-2.
  • Bertsekas, Dimitri P. (1999). Nonlinear Programming: 2nd Edition. Athena Scientific. ISBN 1-886529-00-0.

Enlaces externos

Software

Obtenido de "Programaci%C3%B3n no lineal"

Wikimedia foundation. 2010.

Игры ⚽ Поможем сделать НИР

Mira otros diccionarios:

  • programación matemática — Aplicación de técnicas de programación matemática y computacional a la construcción de modelos determinísticos, principalmente en los negocios y en la economía. En el caso de los modelos que sólo requieren ecuaciones algebraicas lineales, la… …   Enciclopedia Universal

  • Programación lineal — Saltar a navegación, búsqueda La Programación Lineal es un procedimiento o algoritmo matemático mediante el cual se resuelve un problema indeterminado, formulado a través de ecuaciones lineales, optimizando la función objetivo, también lineal.… …   Wikipedia Español

  • Programación dirigida por eventos — Saltar a navegación, búsqueda La programación dirigida por eventos es un paradigma de programación en el que tanto la estructura como la ejecución de los programas van determinados por los sucesos que ocurran en el sistema o que ellos mismos… …   Wikipedia Español

  • Programación dinámica (informática) — Saltar a navegación, búsqueda En informática, la programación dinámica es un método para reducir el tiempo de ejecución de un algoritmo mediante la utilización de subproblemas superpuestos y subestructuras óptimas, como se describe a continuación …   Wikipedia Español

  • Programación — ► sustantivo femenino 1 Elaboración de un plan o proyecto, o distribución y ordenación de las partes que componen alguna actividad: ■ la programación del viaje resultó un desastre; realizó una plantilla en la que figuraba la programación de las… …   Enciclopedia Universal

  • Programación lineal — INTRODUCCIÓN A LA PROGRAMACIÓN LINEAL introducción modelo de programación lineal forma estandar limitaciones suposiciones * * * Técnica matemática para modelar, útil para guiar decisiones cuantitativas en los negocios, en ingeniería industrial y …   Enciclopedia Universal

  • lineal — ► adjetivo 1 De la línea: ■ los trazos lineales representan las calles; tiene una asignatura de dibujo lineal. 2 BOTÁNICA, ZOOLOGÍA Que tiene forma larga y estrecha: ■ los pinos tienen hojas lineales. 3 Que es proporcional: ■ se ha producido un… …   Enciclopedia Universal

  • lineal — Ver: función lineal Ver: programación lineal …   Diccionario de Economía Alkona

  • lineal — Ver: función lineal Ver: programación lineal …   Diccionario de Economía

  • programación lineal — Informática. Técnica matemática que se aplica cuando la función objetivo, que es lo que se pretende maximizar o minimizar, y las restricciones, que es lo que impone las condiciones, son funciones lineales …   Diccionario de Economía Alkona

Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”