Fundamentos De La Programacion No Lineal

FUNDAMENTOS DE LA PROGRAMACIÓN NO LINEAL.

La Programación no Lineal es parte de la Investigación Operativa, su objetivo 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 determinado conjunto (conjunto de oportunidades), donde tanto la función objetivo, como las que intervienen en las restricciones quedeterminan el conjunto de oportunidades pueden ser no lineales.
La estructura del problema es variada, debido a las funciones que en él intervengan (a diferencia de la Programación Lineal donde la forma especial del conjunto de oportunidades y de la función objetivo permite obtener resultados generales sobre las posibles soluciones y facilitan los tratamientos algorítmicos de los problemas). Estoocasiona 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 laresolución de problemas más generales.

CONDICIONES DE KARUSH – KUHN – TUCKER

Dado que las condiciones KKT son el resultado analítico más importante en programación no lineal, se desarrollaran estas condiciones en dos pasos por conveniencia de exposición. En primer lugar se analizan las condiciones de no negatividad, para en el paso posterior desarrollar un problema con las condiciones dedesigualdad tanto para maximización como para minimización.

1. Condiciones de no negatividad:
Como primer paso se considera un problema simple de optimización de la función z = f(x1) sujeta a la restricción que la variable de elección sea no negativa, es decir, x1 ≥ 0.
Naturalmente esta condición es equivalente a – x1 ≤ 0, entonces incorporando una variable de holgura s ≥ 0 y llamando µ almultiplicador de lagrange, la función lagrangiana resulta:
F(x1, µ, s) = f(x1) + µ (- x1 + s) = 0
Las condiciones necesarias son:
∂F/∂x1 = df/dx1 – µ = 0
∂F/∂µ = - x1 + s = 0
∂F/∂s = µs = 0
De la primera se desprende que µ = df/dx1. Entonces se pueden dar solamente tres tipos de extremos:
a. Extremo local interno lo que implica que x1 óptimo (x1*) es positivo y su derivada es nula, es decir queµ = 0.
b. Extremo local de frontera lo que implica que x1* es igual a cero y su derivada es nula
c. Punto de frontera lo que implica que x1* = 0 y su derivada es positiva si es un problema de minimización, o negativa si es un problema de maximización.
Estas condiciones se pueden resumir de la siguiente manera:
df/dx1 ≤ 0 x1 ≥ 0 x1 df/dx1 = 0 [Maximización]
df/dx1 ≥ 0 x1 ≥ 0 x1 df/dx1= 0 [Minimización]
Ampliando el problema para casos en que existen n variables de elección, es decir:
Extremar z = f(x1, x2,..., xn)
Sujeto a xj ≥ 0 j: 1, 2,..., n
Las condiciones de primer orden para un óptimo son
df/dxj ≤ 0 xj ≥ 0 xj
df/dxj = 0 j: 1, 2,..., n [Maximización]
df/dxj ≥ 0 xj ≥ 0 xj
df/dxj = 0 j: 1, 2,..., n [Minimización]

2. Condiciones de desigualdad:En este segundo paso se reconsidera el problema con la incorporación de una restricción de desigualdad y otra variable de elección. Además, dado que tradicionalmente los problemas de maximización se presentan con desigualdades del signo contrario a las de los problemas de minimización, se determinarán las condiciones para máximo y para mínimo a partir de problemas distintos.
Maximizar z = f(x1,x2) Minimizar z = f(x1, x2)
sujeto a g1(x1, x2) ≤ r1 sujeto a g1(x1, x2) ≥ r1
xj ≥ 0 j:1, 2 xj ≥ 0 j:1, 2
La restricción de desigualdad puede transformarse en una igualdad incorporando una variable de holgura o de excedente apropiada. Para este caso, la condición para máximo queda satisfecha sumando a g(x1, x2) ≤ r1 una variable de holgura no negativa s1; asimismo para el problema de...