Unidad 5

Unidad 5 Programación no lineal

• Objetivos

– Proponer en forma cuantitativa acciones o decisiones a

tomar para optimizar sistemas donde existan recursos

escasos y se presenten relaciones no lineales simples,

mediante la teoría y práctica de la Técnica de

Programación no Lineal.

– Resolver los problemas de programación no lineal

adecuadamente:

• Saber detectar cada tipo de problema

• Modelarlo

• Realizar consultas bibliográficas

• Realizar investigaciones

• Interpretar los datos en la realidad

Unidad 5 Programación no lineal Contenido

• Conceptos de óptimo local y global. Forma cuadrática. Matriz positiva

definida o semidefinida. Función convexa. Región factible convexa.

Enunciado de las condiciones necesarias y suficientes de óptimo local

no–condicionado. Algoritmos para problemas no–lineales sin

restricciones: métodos de búsqueda directa; método del gradiente.

Ejemplos. Derivación gráfica de las condiciones necesarias de óptimo

local de problemas no–lineales restringidos por igualdades. Enunciado de

las condiciones necesarias y suficientes de óptimo local para problemas

no–lineales con restricciones de igualdad. Conceptos de óptimo local

restringido. Derivación de las condiciones necesarias y suficientes de

óptimo local para problemas no–lineales restringidos por desigualdades

(condiciones de Kuhn–Tucker). Enunciado de las condiciones suficientes

de óptimo global para problemas no–lineales con restricciones de

desigualdad. Algoritmos para problemas no–lineales con restricciones:

Programación convexa; Programación cuadrática; Programación

geométrica; Programación estocástica; método de combinaciones

lineales.

Teoría clásica de la optimización

En la teoría clásica de la optimización se usa

el cálculo diferencial para determinar puntos

extremos, o de máximo o de mínimo, para

funciones sin restricciones y restringidas.

Se establecerán las condiciones necesarias

y suficientes para determinar los puntos

extremos no restringidos, mediante los

métodos jacobiano y lagrangiano para

problemas con restricciones de igualdad, y

las condiciones de Kuhn-Tucker para

problemas con restricciones de desigualdad

Teoría clásica de la optimización Problemas sin Restricciones

Problemas sin Restricciones

Problemas sin Restricciones Aunque x1 (en la figura anterior) es un punto máximo, se

diferencia de los otros máximos locales porque el valor de f

correspondiente a al menos un punto en la proximidad de x1 es

igual a f(x1). A este respecto, es un máximo débil, mientras

que x3 y x4 son máximos fuertes.

En general, X0 es un máximo débil si f(X0 + h) < f(X0), y es un

máximo fuerte si f(X0 + h) > f(X0), donde h es como se definió

arriba.

En la figura, la primera derivada o pendiente de f es igual a

cero en todos los puntos extremos. Esta propiedad también se

satisface en puntos de inflexión y de silla, como x5.

Si un punto con pendiente (gradiente) cero no es un extremo

(máximo o mínimo), debe ser un punto de inflexión o un punto

de silla.

Condiciones necesarias y

suficientes

Condiciones necesarias y

suficientes

Condiciones necesarias y

suficientes

Condiciones necesarias y

suficientes

Método Newton Raphson

Una dificultad del método es que no siempre se garantiza la convergencia, a

menos que la función f tenga buen comportamiento. En la figura, si el punto

inicial es a, el método diverge. No hay manera fácil para ubicar un “buen” punto

inicial

Restricciones de igualdad

Se presentan dos métodos:

- el jacobiano o de Jacobi

- el lagrangiano o de Lagrange.

El método lagrangiano se puede deducir en forma

lógica a partir del método jacobiano.

Esta relación proporciona una interesante

interpretación económica del método lagrangiano

Las funciones f (X) y gi(X), i 1, 2, ..., m son doble y

continuamente diferenciables.

La idea de usar derivadas restringidas es desarrollar una

ecuación de forma cerrada para las primeras derivadas

parciales de f (X) en todos los puntos que satisfacen las

restricciones g(X) = 0. Los puntos estacionarios

correspondientes se identifican como aquellos en los que

se anulan esas derivadas parciales. Se pueden usar las

condiciones de suficiencia para comprobar la identidad de los

puntos estacionarios.

Para aclarar el concepto propuesto, considérese a f (x1, x2), que

se ve en la figura.

Esta función se va a minimizar, sujeta a la restricción

en donde b es una constante. De acuerdo con la figura, la curva definida

por los tres puntos A, B y C representa los valores de f(x1, x2) para los

cuales siempre se satisface la restricción.

El método de derivadas restringidas define al gradiente de f(x1, x2) en

cualquier punto de la curva ABC. El punto B en el que se anula la

derivada restringida es un punto estacionario del problema con

restricción.

Análisis de sensibilidad en el método jacobiano.

Con el método jacobiano se puede estudiar el efecto que

tienen cambios pequeños en el lado derecho de las

restricciones, sobre el valor óptimo de f. En forma específica,

¿cuál es el efecto de cambiar de gi(X) = 0 a gi(X) = en

el valor óptimo de f? A este tipo de investigación se le llama

análisis de sensibilidad y es similar al que se lleva a cabo

en la programación lineal. Sin embargo, el análisis de

sensibilidad en la programación no lineal sólo es válido en la

proximidad (o cercanía) inmediata del punto extremo. El

desarrollo es útil en el estudio del método lagrangiano.

Aplicación del método jacobiano a un problema

de programación lineal.

Se tiene el problema de programación lineal:

Maximizar Z= 2x1 + 3x2

sujeta a

x1 + x2 + x3 + x4 = 5

x1 - x2 + x4 = 3

x1 , x2, x3, x4 > 0

Para tener en cuenta las restricciones de no negatividad xj > 0, se hace

la sustitución xj = wj 2.

Con esta sustitución, las condiciones de no negatividad se vuelven

implícitas, y el problema original se transforma en

FIGURA

Puntos extremos del espacio de soluciones del

programa lineal

Se pueden sacar algunas conclusiones generales de la

aplicación del método jacobiano al problema de

programación lineal. De acuerdo con el ejemplo numérico,

las condiciones necesarias requieren que las variables

independientes sean igual a cero. También, las condiciones

de suficiencia indican que la hessiana es una matriz

diagonal. Entonces, todos sus elementos diagonales deben

ser positivos para que haya mínimo, y negativos para que

haya máximo. Las observaciones demuestran que la

condición necesaria equivale a especificar que sólo se

necesitan las soluciones básicas (factibles) para ubicar la

solución óptima. En este caso, las variables independientes

equivalen a las variables no básicas del problema de

programación lineal. También, la condición de suficiencia

demuestra la fuerte relación entre los elementos diagonales

de la matriz hessiana y el indicador de optimalidad zj – cj en

el método símplex.

En el método de Jacobi, sea que el vector l represente los coeficientes de

sensibilidad; esto es

Método lagrangiano.

Estas condiciones son suficientes, pero no necesarias, para identificar un

punto extremo. Esto quiere decir que un punto estacionario puede ser un

punto extremo sin satisfacer esas condiciones.

Existen otras condiciones que son necesarias y suficientes al mismo tiempo,

para identificar puntos extremos. Sin embargo, el procedimiento puede ser

computacionalmente inmanejable. Se define la siguiente matriz en el

punto estacionario (X0, l0):

Restricciones de desigualdad

Se amplía el método de Lagrange para

manejar restricciones de desigualdad.

La contribución principal en este caso es el

desarrollo de las condiciones generales de

Karush-Kuhn-Tucker (KKT) que

proporcionan la teoría básica de la

programación no lineal.

Extensión del método de Lagrange.

Se tiene el problema

Maximizar z = f (X)

sujeta a gi (X) < 0, i = 1, 2, ..., m

• Las restricciones de no negatividad X > 0, si las hay, se

incluyen en las m restricciones.

• Si el óptimo no restringido de f (X) no satisface a todas las

restricciones, el óptimo restringido debe ser un punto

limiten la frontera del espacio de soluciones. Esto quiere

decir que al menos una restricción se debe satisfacer en

forma de ecuación. Por consiguiente, el método implica los

siguientes pasos.

Pasos Paso 1. Resolver el problema sin restricciones:

Maximizar z = f (X)

Si el óptimo resultante satisface todas las restricciones,

detenerse, porque todas las restricciones son redundantes.

En caso contrario hacer k = 1 y seguir en el paso 2.

• Paso 2. Activar todas las k restricciones (es decir,

convertirlas en igualdades) y optimizar a f (X) sujeta a las k

restricciones activas, con el método de Lagrange. Si la

solución obtenida es factible con respecto a las demás

restricciones, detenerse; se tiene un óptimo local.2 En caso

contrario, activar otro conjunto de k restricciones y repetir el

paso. Si se han considerado todos los conjuntos de

restricciones activas, tomadas de k en k, sin encontrar una

solución factible, proceder al paso 3.

Pasos Paso 3. Si k = m, detenerse. No existe solución factible. En

caso contrario, poner k = k + 1 y seguir en el paso 2.

Un punto importante que con frecuencia se pasa por alto al

presentar el procedimiento es que no garantiza una

optimalidad global, aun cuando el problema tenga buen

comportamiento (es decir, que posea un óptimo único). Otro

punto importante es la idea errónea implícita que para p < q,

el óptimo de f (X) sujeta a p restricciones de igualdad

siempre es mejor que su óptimo sujeto a q restricciones de

igualdad. Eso es cierto, en general, sólo si las q restricciones

forman un subconjunto de las p restricciones.

El procedimiento que acabamos de describir ilustra que lo

mejor que cabe esperar usando el método de Lagrange es

una (posiblemente) buena solución factible. Esto es

especialmente cierto si la función objetivo no es unimodal.

Si las funciones del problema tienen buen comportamiento

(es decir, el problema posee un solo óptimo restringido), se

puede rectificar el procedimiento para localizar al óptimo

global. En forma específica, considérense el óptimo no

restringido y los óptimos restringidos sujetos a todos los

conjuntos de una restricción activa, después a dos

restricciones activas, y así sucesivamente, hasta que se

activen todas las m restricciones. El mejor de todos los

óptimos factibles es el óptimo global.

Esto indica que el uso del método para resolver problemas

de cualquier tamaño práctico es limitado

Las condiciones de Karush-

Kuhn-Tucker (KKT). Se presentan las condiciones necesarias

KKT para identificar puntos estacionarios

de un problema no lineal restringido sujeto

a restricciones de desigualdad. El

desarrollo se basa en el método de

Lagrange. Esas condiciones también son

suficientes, bajo ciertas reglas que se

enunciarán después.

Se tiene el problema

Maximizar z = f (X)

sujeta a gi (X) < 0, i = 1, 2, ..., m

Estas condiciones se aplican también al caso de minimización, con la

excepción de que debe ser no positiva . Tanto en la maximización como en

la minimización, los multiplicadores de Lagrange que corresponden a las

restricciones de igualdad deben ser libres en signo.

Suficiencia de las condiciones KKT.

Las condiciones necesarias de Kuhn-Tucker también son suficientes, si la

función objetivo y el espacio de soluciones satisfacen las condiciones de

la tabla

Es más fácil comprobar que una función es convexa o cóncava que

demostrar que un espacio de soluciones es un conjunto convexo. Por esta

razón se presenta una lista de condiciones que son más fáciles de aplicar en

la práctica, en el sentido que se puede establecer la convexidad del espacio

de soluciones comprobando la convexidad o la concavidad de las funciones

de restricción.

Para suministrar estas condiciones se definirán los problemas no lineales

generalizados como sigue:

Maximizar z = f (X)

sujeta a gi (X) < 0, i = 1, 2, ..., r

gi (X) > 0, i = 1, 2, ..., p

gi (X) = 0, i = 1, 2, ..., m

donde li es el multiplicador de Lagrange correspondiente a la restricción

i. Las condiciones para establecer la suficiencia de las condiciones KKT

se resumen en la tabla

Las condiciones de la tabla sólo representan un subconjunto de las condiciones de la

tabla. La razón es que un espacio de soluciones puede ser convexo y no satisfacer las

condiciones de la tabla

La tabla es válida, porque las condiciones dadas producen una función lagrangiana

cóncava L(X, S, l ) en el caso de maximización, y una L(X, S, l ) convexa en el caso

de minimización. Este resultado se comprueba al notar que si gi(x) es convexa,

entonces li gi(x) es convexa si li > 0, y es cóncava si li < 0. Se pueden establecer

interpretaciones parecidas para todas las condiciones restantes. Observe que una

función lineal es convexa y cóncava al mismo tiempo. También, si una función f es

cóncava, entonces (–f) es convexa, y viceversa.

Los métodos de solución de la programación no lineal se

pueden clasificar, de manera general, en:

• Algoritmos directos:

• Método del gradiente : busca el máximo (el

mínimo) de un problema siguiendo la mayor tasa

de aumento (disminución) de la función objetivo

•Algoritmos indirectos: el problema original se sustituye por

otro en el cual se determina el óptimo:

• Programación cuadrática

• Programación convexa separable

• Programación estocástica

Algoritmos sin restricciones

• Método de búsqueda directa

• Método del gradiente

Método de búsqueda directa

Los métodos de búsqueda directa se aplican principalmente a funciones unimodales de una variable.

La idea de los métodos de búsqueda directa es identificar el intervalo de incertidumbre que comprende al punto de solución optima. El procedimiento localiza el óptimo estrechando en forma progresiva el intervalo de incertidumbre hasta cualquier grado de incertidumbre que se desee.

Método de búsqueda directa

Existen dos algoritmos estrechamente

relacionados:

- método de búsqueda dicotómico

- método de la sección dorada

Ambos buscan la maximización de una función

unimodal f(x) en el intervalo a < x < b, que se

sabe incluye el punto x*. Los dos métodos

comienzan con Io =(a,b) que representa el

intervalo inicial de incertidumbre.

En el método dicótomo los valores x1 y x2 se encuentran

simétricos respecto del punto medio del actual intervalo de

incertidumbre. Esto significa que

Ii = 0.5(Ii-1 + D) La aplicación repetida del algoritmo garantiza que la

longitud del intervalo de incertidumbre se acercará al nivel

de exactitud deseado, D.

En el método de la sección dorada la idea es de mayor

involucramiento. Se puede apreciar que cada iteración del

método dicótomo requiere calcular los dos valores f(x1) y

f(x2), pero termina por descartar alguno de ellos. Lo que

propone el método de la sección dorada es ahorrar

cálculos mediante el reuso del valor descartado en la

iteración inmediata siguiente.

Comparado con el método dicótomo, el método de

la sección dorada converge más rápidamente

hacia el nivel deseado de exactitud.

Adicionalmente, cada iteración en el método de la

sección dorada requiere la mitad de los cálculos,

en virtud de que recicla siempre un conjunto de

los cálculos correspondientes a la iteración

inmediata anterior

Método del Gradiente Es un método para optimizar funciones que son

doble continuamente diferenciables. La idea es generar puntos sucesivos en la dirección del gradiente de la función. Esta técnica también es llamada método del ascenso (o descenso) mas pronunciado, o de la pendiente mas inclinada.

El final del método del gradiente se encuentra ene l punto donde el vector gradiente se anula. Esta solo es condición necesaria para la optimalidad. La optimalidad no se puede comprobar a menos que a priori se conozca que f(x) es cóncava o convexa

Algoritmos con restricciones El problema general de programación no

lineal con restricciones se define como:

Z = f(x) Max o Min

Sujeta a:

g(x) < 0

Las condiciones de no negatividad forman parte de las restricciones. Tambien al menos una de las funciones f(x) o g(x) es no lineal, y todas las funciones son continuamente diferenciables.

No existe algoritmo general para manejar modelos de no lineal, por el comportamiento errático de las funciones no lineales. Quizá el resultado más general aplicable al problema es el de las condiciones KKT.

Se presentan varios algoritmos que se pueden clasificar en general como métodos indirectos o directos. Con los primeros se resuelve el problema no lineal manejando uno o dos programas lineales derivados del problema original. Los métodos directos manejan el problema en su forma original.

Entre los métodos indirectos se estudiaran: programación separable, cuadrática, geométrica y estocástica. Entre los directos se verán las combinaciones lineales y una breve descripción de la técnica de maximización secuencial sin restricciones.

Programación separable

Entres los ejemplos de otras funciones que se pueden hacer

separables mediante sustituciones están e (x1 + x2) y x1x2. Se puede

aplicar una variante del procedimiento presentado, para lllegar a

la separabilidad.

La programación separable maneja los problemas no lineales

en lo que la función objetivo y las restricciones son separables.

En esta sección veremos como se puede obtener una solución

de cualquier problema separable, mediante aproximación lineal

y el método simplex de la programación lineal.

La función f(x) de una sola variable se puede aproximar

mediante una función lineal en intervalos, con programación

entera mixta. Supongamos que se puede aproximar f(x) en un

intervalo [a,b]. Se define ak k= 1,2,…,k como el k-esimo punto de

quiebre (o de discontinuidad) en el eje x tal que a1 < a2<…<ak

Los puntos a1 y ak coinciden con los extremos a y b del intervalo

que se investiga.

Asi, f(x) se aproxima como sigue

Programación Cuadrática

La función XTDX define una forma cuadrática. Se supone que la

matriz D es simétrica y negativa definida. Eso quiere decir que

el Z es estrictamente cóncava. Las restricciones lineales, lo que

garantiza que el espacio de soluciones es convexo.

La solución a este problema se basa en las condiciones KKT

necesarias. Como z es estrictamente cóncava y el espacio de

soluciones es convexo, estas condiciones son suficientes para

tener un óptimo global .

Se describirá el problema de programación cuadrática para el

caso de la maximización . Es trivial cambiar la formulación para

el caso de la minimización.

El problema se puede planear como sigue:

Convexa separable

Trabajaremos el caso de programación geométrica sin restricciones

Programación geométrica

La programación geométrica tiene que ver con problemas en los que

las funciones objetivo y de restricción son del siguiente tipo:

donde

La programación estocástica tiene que ver con situaciones en las que

algunos o todos los parámetros del problema son variables aleatorias. Esos

casos son típicos en los problemas de la vida real, donde puede ser difícil

determinar con certidumbre los valores de los parámetros.

La idea de la programación estocástica es convertir el problema

probabilístico en un caso determinístico equivalente. En esta sección se

explicará la programación restringida por el azar, que se define como

Programación estocástica

Esta restricción se puede llevar a la forma de programación separable

mediante la sustitución

Así la restricción original equivale a

Caso 2. Sólo bi es normal con media E{bi} y varianza var{bi}. El análisis

se parece al del caso 1. Considere la restricción estocástica:

Este método tiene que ver con el siguiente problema, en el

que todas las restricciones son lineales:

Maximizar Z = f (X)

sujeta a

AX < b, X > 0

El procedimiento se basa en el método de la pendiente más

inclinada (del gradiente). Sin embargo, la dirección

especificada por el vector gradiente podrá no resultar en

una solución factible para el problema con restricciones.

También, el vector gradiente no necesariamente será nulo

en el punto óptimo (restringido). El método de pendiente

más inclinada se puede modificar entonces para manejar el

caso con restricciones.

Método de combinaciones lineales

Al comparar con el método de la pendiente más inclinada

(Método del gradiente) se ve que el parámetro r representa el

tamaño del paso

Los problemas de programación lineal generados en las

iteraciones sucesivas sólo difieren en los coeficientes de la

función objetivo. Así, se pueden usar los procedimientos de

análisis de sensibilidad presentados en Programación Lineal

(análisis postoptimal) para hacer los cálculos con eficiencia

Algoritmo SUMT

En esta sección se presenta un método de gradiente más general. Se

supone que la función objetivo f (X) es cóncava, y que cada función de

restricción gi(X) es convexa. Además, el espacio de soluciones debe tener

un interior. Esto excluye el uso implícito y explícito de restricciones de

igualdad.

El algoritmo SUMT (de sequential unconstrained maximization technique,

técnica de maximización secuencial no restringida) se basa en transformar

el problema con restricciones en uno equivalente sin restricciones (o no

restringido). El procedimiento se parece al uso del método de los

multiplicadores de Lagrange. Después, el problema transformado se puede

resolver con el método de la pendiente más pronunciada (Método del

gradiente).

Para aclarar el concepto, considérese la nueva función

donde t es un parámetro no negativo. El signo de suma tiene

en cuenta las restricciones de no negatividad, que se deben

poner en la forma –xj < para ser consistentes con las

restricciones originales. Como gi(X) es [1/ gi(X)] convexa, es

cóncava. Eso quiere decir que p(X, t) es cóncava en X. En

consecuencia, p(X, t) posee un máximo único. La

optimización del problema original

restringido equivale a la optimización de p(X, t).

El algoritmo se inicia seleccionando en forma arbitraria un

valor inicial no negativo para t. Se selecciona un punto inicial

X0 como la primera solución de prueba. Debe ser un punto

interior, esto es, no debe estar en las fronteras del espacio

de solución. Dado el valor de t, se aplica el método de la

pendiente más pronunciada para determinar la solución

óptima (el máximo) de p(X, t).

El algoritmo se inicia seleccionando en forma arbitraria un

valor inicial no negativo para t. Se selecciona un punto inicial

X0 como la primera solución de prueba. Debe ser un punto

interior, esto es, no debe estar en las fronteras del espacio de

solución. Dado el valor de t, se aplica el método de la

pendiente más pronunciada para determinar la solución

óptima (el máximo) de p(X, t).

El nuevo punto de solución siempre será un punto interior,

porque si ese punto está cerca de las fronteras, al menos una

de las funciones adquirirá un valor negativo muy

grande.

Como la función objetivo es maximizar p(X, t), esos puntos de

solución se excluyen en forma automática.

El resultado principal es que los puntos de solución sucesivos

siempre serán puntos interiores. En consecuencia, el

problema siempre se puede manejar como un caso sin

restricciones.

Una vez obtenida la solución óptima correspondiente a

determinado valor de t, se genera un nuevo valor de t y se repite

el proceso de optimización (con el método de la pendiente más

pronunciada). Si t' es el valor actual de t, se debe seleccionar el

siguiente valor t" de modo que 0 < t" < t'.

El algoritmo SUMT termina cuando, para dos valores sucesivos

de t, los valores óptimos correspondientes de X, obtenidos

maximizando p(X, t), sean aproximadamente iguales.

En este punto los intentos posteriores producirán poca mejoría.

La implementación real de SUMT tiene más detalles que los que

se presentaron aquí.

En forma específica, un factor importante que puede afectar la

rapidez de convergencia es la selección de un valor inicial de t.

Además, para determinar un punto interior inicial se pueden

necesitar técnicas especiales. Estos detalles se pueden

encontrar en Fiacco y McCormick (1968).