Repblica Bolivariana de Venezuela

Ministerio del Poder Popular para la Educacin Universitaria

Universidad Bicentenaria de Aragua
Turmero Edo. Aragua










Programacin no lineal







Integrantes:
Dayra Blanco
C.I.- 21.131.143
Kristel Rivero
C.I.-



Turmero, mayo de 2014
Introduccin

La programacin no lineal optimiza el problema de una funcin
objetivo, teniendo presente las restricciones de igualdad y/o desigualdad. Por
desgracia no existe un algoritmo matemtico que resuelva cualquier
problema no lineal, ya que depende de la naturaleza que posea el problema,
sea por la funcin objetivo o por las restricciones que puedan existir, para
eso se aplica un mtodo para la solucin del problema. La PNL es una parte
que conforma la investigacin operativa puesto que proporciona ciertos
resultados y tcnicas que tienden a determinar puntos ptimos en una
funcin. Por lo general la programacin lineal es utilizada en varias
aplicaciones industriales de optimizacin, para ello recurren a modelos no
lneas de tamaos grandes, para poder trazas metas y as obtener
respuestas provenientes de un modelo estadstico.

Hasta la fecha los investigadores han desarrollado un mtodo
sistemtico prctico. La PNL se conoce tambin como programacin
cuadrtica, debido a que la mayor parte de los problemas contienen
ecuaciones cuadrticas. En el presente trabajo se dar a conocer ciertos
puntos importantes de la programacin lineal, mediante problemas e
ilustraciones grficas para el fcil entendimiento de dichos problemas
















INDICE

INTRODUCCION..2
DESARROLLO..3


Programacin no lineal

Es un conjunto de mtodos que son usados para la optimizacin de
funciones objetivos, sujeto por ciertas restricciones donde una o ms
variables son no lineales. Su aplicacin es muy frecuentada en aplicaciones
industriales, econmicas, estrategias militares, etc.

Ventajas de la programacin no lineal

En ciertas oportunidades la distribucin optima de un presupuesto
excluye cualquier bien considerado en un presupuesto general,
reflejndose en cualquier restriccin del modelo.
La programacin no lineal brinda una mayor informacin. No solo
define los objetivos, sino que tambin define las orientaciones para
lograr los objetivos.

Formulacin de un problema de programacin no lineal

Cuando los problemas son no lineales se convierten en problemas de
programacin matemtica, donde su funcin objetivo y sus restricciones son
no lineales.

Caractersticas de los problemas no lineales

Se caracterizan por poseer relaciones directas y proporcionales entre
variables que intervengan. Este tipo de problema tambin es conocido como
curvilneos, ya que su rea se delimita en soluciones factibles mediante un
grfico. En la programacin lineal, la funcin objetivo puede ser cncavo
cuando se quiere maximizar, y es convexo cuando se desea minimiza.






Formulacin y resolucin de modelos matemticos con restricciones u
objetivos no lineales


Al igual que en la programacin lineal la funcin f(x1,x2,,xn) es la
funcin objetivo del P.N.L. y gi(x1,x2,,xn) (<,=,>)bi, i=1,,m son sus
restricciones. Suponindose que estas funciones son diferenciales. Los
problemas de programacin no lineal toman en cuenta la funcin objetivo no
lineal y las restricciones no lineales, como en el siguiente ejemplo:


Como se puede ver, la funcin objetivo y la restriccin se presenta en
variables de segundo grado (cuadrtica); son no lineales. Para resolver este
problema no lineal se toma la restriccin representndola en un grfico
utilizando el mismo procedimiento que se emplea en la programacin lineal.

Tomando en consideracin la desigualdad que existe en la restriccin,
se le concede un valor de 0 a la variable Y, para as poder hallar el punto de
X en el grfico. De tal manera se le otorga un valor de 0 a la variable X, para
as encontrar el punto Y. Se despeja la variable X de la siguiente forma:


Y se despeja la variable Y:



Segn el mtodo grafico que es utilizado en la programacin lineal, se
dibuja en un plano cartesiano las restricciones que fueron formuladas
matemticamente, as mismo se representara como se muestra en el
siguiente grfico:



Como se puede visualizar en el grafica anterior, la restriccin es
expresada por una curva convexa, y la funcin objetivo por la cncava.
Luego se grafica la funcin objetivo, asignado cualquier valor a la variable X
y a la contribucin, en este ejemplo, se le otorgo un valor a X=40 y una
contribucin de $1,000, para despus sustituir dichos valores en la funcin
objetivo y as encontrar el valor de la variable Y:



Ya encontrados los valores de X, Y en la funcin objetivo, se procede
a graficar y prolongarse hasta tocar el punto ms apartado del rea de
soluciones factibles, y as poder hallar la solucin ptima.


La solucin ptima de este ejemplo es X=30 y Y=75. Puede calcularse
matemticamente, para realizarlo se deriva la funcin objetivo:

Primero se resuelve la ecuacin de la funcin objetivo.



Ya definida la derivada de la funcin objetivo, se trabaja para hallar la
derivada de la restriccin:



El paso siguiente es igualar los resultados obtenidos de las dos
derivadas; la derivada de la restriccin con la derivada de la funcin objetivo:



Luego se procede a sustituir la ecuacin Y, resultado proveniente de la
ecuacin original de restriccin.



Con el resultado anterior, se le asigna un valor a X. tomando en
cuenta el grafico anteriormente expuesto, la solucin ptima es X=30, por la
cual se sustituir ese valor en la ecuacin resultante:



Ya que el valor de X=30 complace la ecuacin, se considera ese valor
como optimo en el problema. Ese mismo valor se puede sustituir en la
ecuacin de restriccin original y as poder encontrar el valor ptimo de Y.




Despus de adquirir los valores ptimos de X e Y, se decide calcular
la contribucin ptima, sustituyendo los valores hallados en la funcin
objetivo:



Tipos de problemas de programacin no lineal

Sin restricciones: son problemas de variable de decisin no
restringida. Su formulacin es la siguiente:


Aparecen de forma natural, en reas de la ciencia como la estadstica
y econometra. Una caracterstica importante de este tipo, es que en
ciertas oportunidades un P.N.L. con restricciones puede ser resuelta
de uno sin restricciones. Por ejemplo:

Se poseen los siguientes datos sobre una poblacin animal, yi a lo
largo de cinco aos. Se requiere ajustar a un modelo:




Se optimiza la funcin:


En este caso sera:

El metodo de minimos cuadrados corresponde a la formula no lineal
sin restricciones, es decir, la funcion y=ax+b ajustada a los datos
(xi,yi), i)1,, n minimizando la expresion.



Con restricciones: tuvo su comienzo tomando solamente el problema
con restricciones de igualdad, con origen en el siglo XVIII. El problema
con restricciones de desigualdad posee una historia reciente, hasta los
aos cincuenta del pasado siglo, este tipo de problema permite ver la
realidad de forma matemtica mucho mejor que los problemas con
restricciones de igualdad, porque no se limitan en la eleccin de
valores para las variables de decisin. Los problemas con
restricciones de igualdad son poco definidos por causa a lo restrictivo
de su planteamiento. Por ejemplo:

Una compaa planea gastar 10000 euros en publicidad. Se conoce
que un minuto de publicidad en televisin cuenta 3000 euros y 1000
euros en la radio. Si la empresa adquiere x minutos de publicidad en
televisin e y minutos en la radio, su ingreso en euros, est dado por
la ecuacin:


Cmo puede la empresa maximizar sus ingresos?

Las variables de decisin son:
x: minutos que adquiere la empresa en televisin
y: minutos que adquiere la empresa en radio

El objetivo es maximizar los ingresos:

Restricciones del problema:
- Gastar 10000 euros en publicidad en los dos medios,
3000x+1000y=10000. Por lo tanto:


Este es un problema no lineal con restricciones de igualdad.

Programacin cuadrtica: como en la programacin lineal que posee
restricciones lineales, en la R.N.L. ahora se trabaja con la funcin
objetivo de forma cuadrtica o el producto de dos variables.



Programacin convexa: incluye diversas clases de problemas, entre
ellos, cuando f(x) es cncava.

Programacin separable: perteneciente a los casos de programacin
convexa en donde las funciones f(x) y g(x) son separables. La funcin
separable es donde cada trmino contiene una sola variable, por lo
que se puede separar en forma de suma de funciones de variables
individuales. Por ejemplo: si f(x) es una funcin separable, se expresa
de la siguiente manera:



Programacin no convexa: inserta problemas de programa no lnea
que no cumplen con las suposiciones de programacin convexa. Aun
cuando se halle el mximo local, no existe seguridad de que sea un
mximo global. No se posee un algoritmo que pueda encontrar una
solucin ptima para estos problemas, pero si para ciertos algoritmos
para encontrar mximos locales, sobre todo cuando las funciones no
lineales no se desven de suposicin de la programacin convexa.

Programacin geomtrica: cuando se desea emplear la
programacin no lineal a problema de ingeniera, la funcin objetivo y
las funciones de restriccin toman la siguiente forma:



Este tipo de funciones no son cncavas ni convexas, por eso las
tcnicas de programacin convexa no se pueden designar
directamente a problemas de programacin geomtrica. Existe un
caso en el que problema puede transformarse en un problema de
programacin convexa equivalente. Todos los coeficientes de cada
funcin son positivos y la funcin objetivo se debe minimizar y se
obtiene al establecer:


Ahora se puede aplicar un algoritmo de programacin convexa.

Programacin fraccional: supngase que la funcin objetivo es de
tipo fraccin:


Los problemas de programacin fraccional se originan, por ejemplo,
cuando se quiere maximizar la razn de una produccin en horas-
hombre trabajadas, o la ganancia en el capital invertido.


Optimizacin no restringida

Consideremos el caso de maximizar una funcin diferenciable de una
variable cncava (f(x) < 0) no sujeta a ninguna restriccin. Recordemos el
resultado de Anlisis Matemtico que nos dice que x es mximo global si y
solo si:



Si se puede despejar x de modo directo, el problema llega a su n;
pero si f(x) no es una funcin sencilla y su derivada no es una funcin lineal o
cuadrtica, tal vez sea imposible resolver la ecuacin analtica. De ser as,
existe una cantidad de procedimientos de bsqueda para resolver el
problema en forma numrica. El enfoque con cualquiera de estos
procedimientos de bsqueda implica encontrar una serie de ensayos de
solucin que conduzcan hacia una solucin ptima. En cada iteracin se
comienza con la solucin de prueba actual para llevar a cabo una bsqueda
sistemtica, que culmina con la identificacin de una nueva solucin de
prueba mejorada. El procedimiento continua hasta que la solucin de prueba
haya convergido hacia una solucin ptima, en caso de que exista una.
Como el conocido procedimiento intuitivo y directo Mtodo de Biseccin para
resolver:



Cuyo algoritmo viene dado a continuacin.

Paso inicial: Seleccionar una tolerancia 0 Encontrar x y x por
inspeccin, ubicar un valor con derivada positiva y otro con derivada
negativa. Seleccionar una solucin de prueba inicial intermedia:


Paso iterativo: Avanzar i:= i + 1. Evaluar:


Si es positivo, redenir x:= x(i). Si es negativo, redenir:



Seleccionar una nueva solucin intermedia:



Criterio de parada: Si x x 2, parar, x x(i). Sino, ir al Paso
iterativo.

Ejemplos

Aplicacin del mtodo de biseccin

Utiliza el Mtodo de Biseccin con tolerancia = 0.01 para
resolver el problema:



f(x) = 12x 3x^4 2x^6. Como f(x) = 12(3x^2 + 5x^4) 0, f
es cncava por lo que si encontramos un mximo local, ser mximo
global. El mximo x debe satisfacer f(x) = 0, por lo que el problema
de maximizacin se reduce a resolver la ecuacin no lineal 12 12x^3
12x^5 = 0.


Dada dicha tolerancia, el algoritmo parara en la iteracin 7,
ofreciendo un resultado de x (0.828125, 0.84375) y x 0.8359375.

Presentamos a continuacin el esquema algortmico mtodo de
Newton para resolver f(x) = 0, tcnica que juega un papel fundamental
en la PNL:

o Paso inicial: Seleccionar una tolerancia 0 Encontrar por
inspeccin una solucin de prueba inicial, i:= 0.

o Paso iterativo: Evaluar.



Redefinir una nueva solucin:


Aplicacin del Mtodo de Newton

Utiliza el mtodo de Newton con tolerancia = 0.00001 para
resolver el problema del ejercicio anterior:


Dada dicha tolerancia, el algoritmo parara en la iteracin 4,
ofreciendo un resultado de x 0.83762. En solo cuatro iteraciones,
este mtodo ha convergido con un grado muy alto de precisin. Una
comparacin de esta tabla con la Tabla anterior ilustra cuanto ms
rpido converge el mtodo de Newton que el mtodo de biseccin. Si
se aplica este ltimo, se requeriran cerca de 20 iteraciones para
converger con el mismo grado de precisin. Aunque esta
convergencia rpida es muy usual en el mtodo de Newton, su
desempeo vara de problema a problema. Consideremos ahora el
caso de maximizar una funcin diferenciable de varias variables
cncava no sujeta a ninguna restriccin. Recordemos el resultado de
Anlisis Matemtico que nos dice que x es mximo global si y solo si:



Supongamos que el sistema no se puede resolver en forma
analtica, por lo que debe emplearse un procedimiento de bsqueda
numrico. Igual que en el caso de una variable, existen varios
procedimientos de bsqueda para resolver este tipo de problema en
forma numrica. Uno de estos, el mtodo de bsqueda del gradiente,
es muy importante porque identifica y utiliza la direccin de
movimiento, desde la solucin de prueba actual, que maximiza la tasa
a la cual se incrementa f(x). Esta es una de las ideas clave de la
programacin no lineal. Las adaptaciones de esta idea para tomar en
cuenta las restricciones tambin son una caracterstica central de
muchos algoritmos que se utilizan para llevar a cabo una optimizacin
restringida:

o Paso inicial: Seleccionar una tolerancia 0 Encontrar por
inspeccin una solucin de prueba inicial x. Ir al Criterio de
parada.
o Paso iterativo: Consta de 3 fases.

Expresar f(x + tf(x)) como funcin de t al establecer:


y sustituir estas expresiones en f(x).

Utilizar el procedimiento de bsqueda en una dimensin
para encontrar t = t que maximice f(x + tf(x)) para t
0.
Establecer x := x + tf(x). Ir al criterio de parada.

Criterio de parada: Evaluar f(x), si:


j =1, 2, . . . , n, parar, la aproximacin a la solucin
optima es x. Sino, ir al Paso iterativo.

La versin general del mtodo de Newton esta diseada para
resolver problemas de optimizacin restringida con variables mltiples.
La idea bsica es la misma, es decir, se trabaja con una aproximacin
cuadrtica de la funcin objetivo f(x), donde, en este caso, x = (x1, x2,
. . . , xn). Esta funcin cuadrtica de aproximacin se obtiene al
truncar la serie de Taylor alrededor de la solucin de prueba actual
despus del trmino de la segunda derivada. Despus, esta funcin
aproximada se maximiza (o minimiza) exactamente para obtener la
nueva solucin de prueba para iniciar la siguiente iteracin. Cuando la
funcin objetivo es cncava y tanto la solucin de prueba actual x
como su gradiente f(x) se escriben como vectores columna, la
solucin x que maximiza la funcin cuadrtica de aproximacin tiene
la forma:


Donde [2f(x)]1 es la inversa de esta matriz hessiana. Los
algoritmos de programacin no lineal que emplean el mtodo de
Newton (incluso aquellos que lo adaptan para ayudar a tratar con
problemas de optimizacin restringida) por lo general aproximan el
inverso de la funcin hessiana de varias maneras. Estas
aproximaciones del mtodo de Newton son conocidas como mtodos
cuasi-Newton (o mtodos mtricos variables).

Aplicacin del mtodo de bsqueda del gradiente

Utiliza el mtodo de Bsqueda del Gradiente para resolver el
problema:


F es cncava por lo que si encontramos un mximo local, ser
mximo global. Consideremos (0, 0) la solucin inicial de prueba.


En iteraciones sucesivas, se obtienen:



Esta sucesin converge a (1, 1) que es la solucin ptima, ya
que f(1, 1) = (0, 0).


Optimizacin restringida: condiciones KKT

Hemos visto las condiciones de optimalidad para el caso no
restringido, para el caso restringido general, veremos las condiciones de
Karush-Kuhn-Tucker (condiciones KKT), que fueron desarrolladas de manera
independiente por Karush (tesis de master, 1939) y por Kuhn y Tucker
(1951). En la Tabla 2.7 se resumen las condiciones de optimalidad para
problema de PNL restringidos o no.


Teorema de condiciones nesarias: Sean f(x), g1(x), g2(x), . . . ,
gm(x) funciones diferenciables que satisfacen ciertas condiciones de
regularidad. Entonces, x = (x1, x2, . . . , xn) puede ser una
solucin ptima para el problema de PNL (2.1), solo si existen m
nmeros u1, u2, . . . , um que satisfagan las siguientes condiciones
KKT:



Teorema de condiciones suficientes: Sea f(x) cncava y g1(x),
g2(x),. . . , gm(x) convexas (es decir, se trata de un problema de
programacin convexa), donde todas estas funciones satisfacen las
condiciones de regularidad y x satisface las condiciones KKT.
Entonces, x es una solucin ptima.


Programacin cuadrtica

Como se ha mencionado en la clasificacin de problemas de PNL, la
programacin cuadrtica difiere de la programacin lineal nada ms en que
la funcin objetivo es una funcin cuadrtica, es decir, incluye tambin
trminos cuadrados o productos de variables.

Formulacin cuadrtica: Sea f : IRn IR, f es una funcin
cuadrtica si:




Sea f: IRn IR una funcin cuadrtica, se dice que es:

Definida positiva:



Semidefinida positiva:



Definida negativa:



Semidefinida negativa:



Indefinida: si no entra en ninguna de las clasificaciones
anteriores.

Recurdese la caracterizacin de matrices definidas
positivas: todos los autovalores j son positivos, o
equivalentemente, todos los determinantes de los menores
principales son positivos. Por el contrario, la caracterizacin de
matrices definidas negativas: todos los autovalores i son
negativos, o equivalentemente, todos los determinantes de los
menores principales tienen signos alternos, siendo el primero
negativo.



En consecuencia, si se usa la notacin matricial el
problema es encontrar x para:



Donde c IRn es un vector fila y x IRn y b IRn son
vectores columna. Q = (qij) Mnn y A = (aij) Mmn son
matrices y el superndice t denota la transpuesta. Los
elementos qij de Q son constantes dadas tales que qij = qji (es
decir, Q es una matriz simtrica, Qt = Q). As, la funcin objetivo
se expresa en trminos de estas qi, los elementos cj de c y las
variables xj, de la siguiente manera:



Ejemplos


Formulacin de un problema cuadrtico

Consideremos el siguiente problema cuadrtico de dos variables:



Si observamos la funcin objetivo:



Igualando coeficiente a coeficiente con la expresin:



Tenemos:



Se dispone de varios algoritmos para el caso especial de un
problema de programacin cuadrtica donde la funcin objetivo es
una funcin cncavo. La funcin objetivo:



Si x^tQx es Semidefinida negativa. En efecto, recurdese la
caracterizacin de convexidad dada y obsrvese que:


Se describir uno de estos algoritmos, el mtodo simplex
modificado, que es muy aceptado porque se basa en el mtodo
simplex con una pequea modificacin. La clave de este enfoque es
construir las condiciones KKT y despus re expresarlas de una
manera conveniente que se parezca a programacin lineal. Por esto,
antes de describir el algoritmo, se desarrollar esta prctica forma.

Condiciones KKT en programacin cuadrtica

Analicemos las condiciones KKT en el ejemplo anterior.



Para poder re expresar estas condiciones en una forma ms
conveniente, se mueven las constantes de las condiciones 1 y 3 al
lado derecho y despus se introducen variables de holgura no
negativas (denotadas por y1, y2 y v1, respectivamente) para convertir
estas desigualdades en ecuaciones.



Observe que la condicin 2 para j = 1 se puede re expresar
ahora en forma simple como la necesidad de que se cumpla una de
las dos, x1 = 0 o bien y1 = 0; esto es, x1y1 = 0.
Exactamente en la misma forma, las condiciones 2 para j = 2 y
4 se pueden sustituir por x2y2 = 0 y u1v1 = 0.

Para cada uno de estos tres pares (x1, y1), (x2, y2) y (u1, v1),
las dos variables se llaman variables complementarias, porque slo
una de las dos podra ser diferente de cero. Estas nuevas formas de
las condiciones 2 y 4 se pueden combinar en una nica restriccin,
llamada restriccin de complementariedad: x1y1 + x2y2 + u1v1 = 0.

Despus de multiplicar las ecuaciones de las condiciones 1. Por
1 para obtener lados derechos no negativos, se obtiene la forma
deseada del conjunto completo de condiciones:



Esta forma es en especial conveniente puesto que excepto por
la restriccin de complementariedad, estas condiciones son
restricciones de programacin lineal.

En cualquier problema de programacin cuadrtica, sus
condiciones KKT se pueden reducir a la misma forma conveniente que
contiene slo restricciones de programacin lineal y una restriccin de
complementariedad. En notacin matricial, esta forma general es:



Donde los elementos del vector columna u IRm son las ui de
las condiciones KKT y los elementos de los vectores columna y IRn
y v IRm son variables de holgura.

Resolucin del mtodo simplex modificado
Como hemos visto, la matriz:



Es definida negativa, por lo que la funcion objetivo a maximizar
f(x) es cncava. El punto de partida para resolver este ejemplo son las
condiciones KKT en la forma conveniente. Una vez que se introducen
las variables artificiales z necesarias, el problema de programacin
lineal que se resolver en forma explcita por el mtodo simplex
modificado es:



La restriccin de complementariedad adicional:



No se incluye de manera explcita, porque el algoritmo garantiza
que se satisfaga esta restriccin de manera automtica con la regla de
entrada restringida. En particular, en cada uno de los tres pares de
variables complementarias siempre que una de las dos variables sea
ya una variable bsica, la otra se excluye de las candidatas como
variable bsica entrante. Recuerde que slo las variables diferentes
de cero son variables bsicas. Dado que el conjunto inicial de
variables bsicas del problema de programacin lineal (z1, z2 y v1)
proporciona una SBF inicial que satisface la restriccin de
complementariedad, no hay manera de violar esta restriccin con
ninguna de las SBF subsiguientes.

En la iteracin inicial se presenta el sistema de ecuaciones
inicial despus de convertir de minimizacin de z a maximizacin de
z y de eliminar algebraicamente las variables bsicas iniciales de la
ecuacin (0). Las tres iteraciones proceden igual que en el mtodo
simplex normal, excepto por la eliminacin de ciertos candidatos para
la variable bsica entrante, segn la regla de entrada restringida. En la
iteracin 1 se elimina u1 como candidato porque su variable
complementaria v1 es ya una variable bsica (de todas maneras,
habra entrado x2 puesto que | 4| > | 3|). En la iteracin 2 se
elimina tanto u1 como y2 (puesto que sus complementarias v1 y x2
son variables bsicas) y de manera automtica se elige x1 como nico
candidato con coeficientes negativos en la fila (0), mientras que el
mtodo simplex normal habra permitido la entrada de x1 o bien de u1,
porque estn empatadas con el coeficiente ms negativo. En la
iteracin 3 se eliminan y1 y y2 (porque x1 y x2 son variables bsicas).
Esta vez u1 no se elimina, puesto que v1 ya no es una variable
bsica, as que se elige u1 como variable entrante. La solucin
optima que resulta para esta fase del problema es x1 = 12, x2 = 9, u1
= 3, mientras el resto de las variables son nulas. Adems, se
satisfacen las condiciones KKT del problema original, por lo que la
solucin ptima para el problema de programacin cuadrtica es (x1,
x2) = (12, 9) con z = 270.









Optimizacin clsica

Representacin de mximos y mnimos en una funcin con una sola
variable, tcnicas de optimizacin clsica, Mtodo de derivadas restringidas
(Jacobiano), Mtodo de Newton, explicacin del mtodo simplex,
programacin no lineal, mtodos de gradiente. Si la restriccin no existe, o es
una restriccin de igualdad, con menor o igual nmero de variables que la
funcin objetivo entonces, el clculo diferencial, da la respuesta, ya que solo
se trata de buscar los valores extremos de una funcin.




Puntos de inflexin

Un punto de inflexin es un punto donde cambia la curvatura de la
funcin. Si x=a es un punto de inflexin f(a)=0. En el problema nos dan 2
datos: f(x) pasa por el punto (3,1), es decir, f(3)=1, x=3 es un punto de
inflexin, es decir, f(3)=0.

Con esta informacin, obtenemos b y d

f(3)=1 1=33+b32+2.3+d 1=27+9b+6+d 9b+d=-32

f(x)=3x2+2bx+2

f(x)=6x+2b

f(3)=0 6.3+2b=0 18+2b=0 2b=-18 b=-18/2=-9
9b+d=-32; 9.(-9)+d=-32; -81+d=-32; d=-32+81; d=49
Solucin: b=-9 y d=49




Mximos y mnimos en programacin no lineal

El punto minimax de la funcin lagrangiana es otro concepto
relacionado con la solucin de un problema de optimizacin. Si bien su
definicin no le hace til a la hora de la resolucin directa del problema, s
constituye un paso intermedio muy importante en la obtencin del problema
dual, que estudiaremos ms adelante. En esta seccin definimos dicho punto
y estudiamos su relacin con otro concepto, el punto de silla de la
lagrangiana.

La relacin del punto minimax con la solucin del problema de
programacin no lineal se obtiene de forma inmediata sin mas que tener en
cuenta que:

Min L (x, ) = f (x) Max t [g(x) b]R m+R m+

Si gi (x) bi 0, entonces i [gi(x) - bi] 0, luego Max i ( gi (x) bi ) =
0R m+ (se alcanza en = 0). Por tanto, si x X, Min L (x, ) = f (x) .R m+ Si
gi (x) bi > 0, entonces Sup i [gi(x) - bi] = , por lo que en este caso no se
alcanza el R m+ mnimo de la Lagrangiana.

Por tanto, Max Min L (x, ) = Max f (x) D R m+ X

As pues, si (x0, 0) es un punto minimax, x0 es una solucin ptima
del problema original.




Multiplicadores de Lagrange

Teniendo un problema de optimizacin sujeto a ciertas interacciones y
siendo el caso en que estas sean igualdades. La representacin del
problema sea:



Donde; m es el nmero de restricciones y n es el nmero de variables.

El problema consiste en determinar un punto X* en cual produzca un
mnimo relativo para f(x) y tambin satisfaga a las restricciones. Ciertamente
la regin factible es enormemente reducida con la presencia de las
ecuaciones (restricciones con igualdades).

La solucin consiste en formar un nuevo problema sin restricciones a
la funcin objetivo con Multiplicadores de Lagrange i=1,2,..,n. La nueva
funcin objetivo L(X,) es llamada el Lagraciano. Est definida en Em+n, el
cual es un problema multidimensional, ya que existen m+n elementos
desconocidos ( m= is + n variables). El precio pagado por prescindir de las
restricciones es un problema multidimensional. Como el problema es definido
por:



Es ahora sin restricciones, se pueden aplicar las condiciones necesarias para
estacionalidad, que son:



Lo cual produce un conjunto de m+n ecuaciones en m+n elementos
desconocidos (X,) para ser encontrados para los valores ptimos (X*,*).
Ntese que:



Garantiza que las restricciones sean satisfechas en la solucin ptima.
En este caso gi(x)=0 ; i=1,2,....m y el valor ptimo de el Lagraciano es igual
que el retorno ptimo del problema original:



Para la forma cuadrtica se puede resolver este problema (una vez
que se ha probado la convexidad y obteniendo el Lagraciano y derivadas
parciales por Programacin Lineal, utilizando el Mtodo Simplex.

Proceso de aplicacin

Cualquier mnimo o mximo local de la funcin z= f(x,y) sujeto a una
restriccin g(x,y)=0 estar entre esos puntos ( xo, yo) para los que ( xo, yo,
o ) es una solucin a el sistema:


Donde; F(x,y,) = f(x,y) + g(x,y), provee todas las derivadas parciales
que existen.

Pasos claves

Paso 1: Formule el problema en la forma.



Paso 2: De la ecuacin F.



Paso 3: Encuentre los puntos crticos para F; lo que es, resolver el
sistema.



Paso 4: S (xo, yo, o) es el nico punto crtico de F, entonces se
asume que (xo, yo ) siempre producir la solucin a los problemas que
consideremos. S F tiene ms de un punto crtico, entonces evale z =
f(x,y) en (xo, yo) para cada punto crtico (xo, yo, o) de F. Para los
problemas que consideramos, se asume que el ms grande de esos
valores es el mximo valor de f(x,y), sujeto a la restriccin g(x,y) = 0, y
el ms pequeo es el mnimo valor de f(x,y), sujeto a la restriccin
g(x,y) = 0.








Ejemplos

Maximizar.



Tenemos que:



Lo cual produce las condiciones necesarias:



As; x *= 3, x *= 3/2, y = -6. Sin embargo, esta es la solucin al
problema tal que:



Debido a que la solucin al problema de maximizacin es
ilimitada, entonces; x *= , x *= , y f(x *, x *) = .





Minimizar.



Primero se elimina x despejando x = 4 - x. Entonces:



Lo cual produce las condiciones necesarias:



En lugar de las cinco ecuaciones con cinco incgnitas que
resultaran si se escribiera el Lagraciano:



En este caso:




Interpretacin econmica

Considrese el problema siguiente:




Donde los valores numricos de b son considerados como la
cantidad de recursos escasos que estn limitados de acuerdo a las
restricciones. Es intuitivamente claro que si los valores del recurso b
varan, la solucin ptima (x*, *) cambiar.

Como deseamos saber que efectos se tendrn en L(x*, *) con
un cambio en b y como esta es una constante, entonces = = 0.
As:



Debido a que L(x*, *) = f(x*) en el ptimo.

Si pensamos en la funcin objetivo como el retorno en pesos,
entonces * puede ser interpretado como pesos por unidad del ivo.
recurso. Ya que este tiene las dimensiones de un precio, los
Multiplicadores de Lagrange son denominados algunas veces precios
sombra. Otra interpretacin que sigue del anterior resultado es que los
Multiplicadores de Lagrange representan coeficientes de
sensibilidad. Esto significa que el valor marginal de cantidades
adicionales del ivo recurso est dado por -* cuando todos los
recursos son asignados ptimamente. Si convertimos a un problema
de maximizacin cambiando el signo de f(x), tambin cambiamos los
signos de todos los * , i = 1,2,....,m.

Ejemplo:










La sensibilidad:



Implica que para b < 4 un incremento en b tiene un retorno
positivo, mientras que para b > 4 un incremento en b tendr un retorno
negativo o perdida. Si b = 4, entonces * = 0, y las soluciones al
problema con o sin restricciones son idnticas.

Existencia de :

Los Multiplicadores de Lagrange pueden ser usados para
resolver cierto tipo de problemas de toma de decisiones. Por ejemplo,
si una cantidad adicional del algn recurso puede ser comprado por y
pesos por unidad, entonces esta compra deber realizarse si:



Esto es, si el valor marginal de retorno (-*) de la asignacin
ptima de una unidad adicional del recurso es mayor que su costo
marginal y, entonces la compra de cantidades adicionales del recurso
ivo es econmica.


Condiciones de punto de silla

Dos desventajas del estado estacionario Kuhn y Tucker son que
(1) que son condiciones necesarias para funciones no convexas f(x) y
g (x), y (2) se aplican nicamente cuando las funciones f(x) y g (x) son
diferenciables.

El Lagraciano tiene un punto de silla en (x*, *), y las
condiciones estacionarias Kuhn y Tucker pueden tambin ser
establecidas en trminos de las propiedades de los valores del punto
de silla de L(x, ).

Teorema. Un punto (x*, *) con * > 0 es un punto de silla del
Lagraciano L(x*, *) asociado con un problema primo si y solamente si
las siguientes condiciones se cumplen:



El problema primo es definido como:



Donde x= [ x , x ,......,x ], y f(x) y g (x) son funciones de valor
real. No existen requerimientos de no diferenciabilidad o convexidad
sobre estas funciones.

Teorema. Si el punto (x*, *) es un punto de silla para el
Lagraciano asociado con el problema primo, entonces x* resuelve el
problema primo.


Derivacin condiciones de segundo orden

La expansin de Taylor de la funcin objetivo en torno al punto x es:



En la vecindad de x, R2(x) es un orden de magnitud ms
pequeo que el termino de 2do orden podemos ignorarlo para un
anlisis de optimalidad local. En un punto mnimo, el gradiente de la
funcin en el punto debe ser nulo.

Para que f(x) sea menor a la funcin objetivo evaluada en
cualquier x en la vecindad de x, debe suceder que:



Es decir:



Esto equivale a que la matriz D ^2f(x) sea semidenida
positiva:



Si es denida positiva esto se cumple estrictamente:




Ejemplo de programacin no lineal irrestricto

Ejemplo 1:



Las condiciones de primer orden son:









El Hessiano de la funcin objetivo en (1,1):



H es denida positiva en todo D, y en particular en (1,1). El punto
corresponde a un mnimo nico global estricto de P).

Ejemplo 2:




La matriz Hessiana est dada por:



Observamos que 1 = 6x y que 2 = 0.
Existe alguna regin en que f(x,y) sea positiva denida? No.
Existe alguna regin en que f(x,y) sea semidenida positiva? S, x
0.
Existe alguna regin en que f(x,y) sea semidenida positiva? S, x
0.


Ejemplo 3:



Tenemos que:



En x = 0, f*(x) = 0 y f**(x) = 0. El punto cumple con la condicin
necesaria de 2 orden. De esta informacin no se podra inferir nada ms,
pero:



Adems es diferenciable, entonces x = 0 es un punto mnimo local de
P).




As, x = 0 es un punto mnimo global de P), nico, pues x ,= 0 x4
> 0.



Diferencias entre programacin lineal y no lineal






Programacin geomtrica

Cuando se aplica programacin no lineal a problemas de diseo de
ingeniera, muchas veces la funcin objetivo y las funciones de restriccin
toman la forma:



En tales casos, las ci y a ty representan las constantes fsicas y las x}
son las variables de diseo. Estas funciones por lo general no son ni
cncavas ni convexas, por lo que las tcnicas de pro-gramacin convexa no
se pueden aplicar directamente a estos problemas de programacin
geomtrica. Sin embargo, existe un caso importante en el que el problema se
puede transformar en un problema de programacin convexa equivalente.
Este caso es aquel en el que todos los coeficientes c en cada funcin son
estrictamente positivos, es decir, las funciones son polino-mios positivos
generalizados (ahora llamados posinomiales), y la funcin objetivo se tiene
que minimizar. El problema equivalente de programacin convexa con
variables de decisin yx, y2,, yn se obtiene entonces al establecer:



En todo el modelo original. Ahora se puede aplicar un algoritmo de
programacin convexa. Se ha desarrollado otro procedimiento de solucin
para resolver estos problemas de progra-macin posinomial, al igual que
para problemas de programacin geomtrica de otros tipos.


Proporcionalidad

La contribucin de cada actividad al valor de la funcin objetivo Z es
proporcional al nivel de actividad xj, como lo representa el trmino cjxj en la
funcin objetivo. De manera similar, la contribucin de cada actividad al lado
izquierdo de cada restriccin funcional es proporcional al nivel de la actividad
xj, en la forma en que lo representa el trmino aijxj en la restriccin. En
consecuencia, esta suposicin elimina cualquier exponente diferente a 1 para
las variables en cualquier trmino de las funciones (ya sea la funcin objetivo
o la funcin en el lado izquierdo de las restricciones funcionales) en un
modelo de programacin lineal.

Actividad

Establece que la entrada y salida de un recurso en particular al
conjunto de actividades, deben ser la misma cantidad; o sea, que las
actividades transforman los recursos y no los crean o destruyen. Esta
suposicin garantiza que la contribucin total tanto a la funcin objetivo como
a las restricciones, es igual a la suma de las contribuciones individuales.
Cuando en un problema dado no se tenga la aditividad puede recurrirse al
empleo de otras tcnicas de la programacin matemtica, dependiendo de
cada caso en particular.

Aditividad

Cada funcin en un modelo de programacin lineal (ya sea la funcin
objetivo o el lado izquierdo de las restricciones funcionales) es la suma de las
contribuciones individuales de las actividades respectivas.

Divisibilidad

Las variables de decisin en un modelo de programacin lineal
pueden tomar cualquier valor, incluyendo valores no enteros, que satisfagan
las restricciones funcionales y de no negatividad. As, estas variables no
estn restringidas a slo valores enteros. Como cada variable de decisin
representa el nivel de alguna actividad, se supondr que las actividades se
pueden realizar a niveles fraccinales.
Planteamiento de problemas de programacin no lineal y optimizacin

Una suposicin importante de programacin lineal es que todas sus
funciones (Funcin objetivo y funciones de restriccin) son lineales. Aunque,
en esencia, esta suposicin se cumple para muchos problemas prcticos, es
frecuente que no sea as. De hecho, muchos economistas han encontrado
que cierto grado de no linealidad es la regla, y no la excepcin, en los
problemas de planeacin econmica, por lo cual, muchas veces es necesario
manejar problemas de programacin no lineal.

De una manera general, el problema de programacin no lineal
consiste en encontrar x=(x1,x2,,xn) para:

Maximizar (x),

Sujeta a

No se dispone de un algoritmo que resuelva todos los problemas
especficos que se ajustan a este formato. Sin embargo, se han hecho
grandes logros en lo que se refiere a algunos casos especiales, haciendo
algunas suposiciones sobre las funciones, y la investigacin sigue muy
activa.

Programacin convexa

La programacin convexa abarca una amplia clase de problemas,
entre ellos como casos espe-ciales, estn todos los tipos anteriores cuando
/(x) es cncava. Las suposiciones son:

1. f(x) es cncava.
2. Cada una de las g(x) es convexa.





Como resolver un modelo de programacin no lineal con AMPL

La complejidad adicional que representan los modelos de
programacin no lineal en comparacin a los modelos de programacin
lineal, justifica el desarrollo de algoritmos especializados que permitan
abordar de forma ms eficiente la resolucin de este tipo de modelos.

En este contexto, uno de
los lenguajes de programacin
matemtica ms conocidos y
confiable para formular diversos
modelos de optimizacin es
AMPL. Su popularidad ha sido sustentada adicionalmente por el desarrollo
de distintos algoritmos de resolucin (o solvers) que son compatibles con
AMPL y que permiten resolver modelos de programacin lineal,
programacin no lineal, programacin entera, entre otras. Estos solvers han
sido resultado del trabajo de prestigiosas universidades y centros de
investigacin, en algunos casos en conjunto con empresas de software. El
servidor NEOS consolida esta informacin en Internet.
A continuacin mostraremos cmo resolver un modelo de
programacin no lineal sencillo utilizando la versin estudiantil de AMPL y
utilizando el solver de resolucin MINOS versin 5.5. Para ello debemos
descargar el archivo amplcml.zip a nuestro computador, descomprimir ste
y luego ejecutar el archivo de nombre ampl.
Consideremos el siguiente modelo de programacin no lineal:

La sintaxis utilizada por AMPL es bastante intuitiva como se aprecia a
continuacin en la resolucin del ejemplo:

La solucin ptima es X1=1,2 y X2=2,4 con valor ptimo V(P)=3,2.




Bibliografa

Programacin no lineal:
http://es.wikipedia.org/wiki/Programaci%C3%B3n_no_lineal
Programacin no lineal:
http://www.ugr.es/~proman/IO1Grado/PDF/Tema_8.pdf
Tcnicas clsicas de optimizacin:
http://www.ehu.es/mae/html/prof/Maria_archivos/plnlapuntes.pdf
Programacin no lineal:
http://www.angelfire.com/oz/rubincelis/Pnolineal.pdf
Clase 9: Programacin no lineal:
http://intrawww.ing.puc.cl/siding/public/ingcursos/cursos_pub/descarga
.phtml?id_curso_ic=375&id_archivo=12407
Diferencias de programacin lineal y no lineal
http://programacionnolinealsm.wordpress.com/diferencias-entre-
programacion-lineal-y-no-lineal/
Programacin geomtrica
http://programacionnolinealsm.wordpress.com/programacion-
geometrica/
Proporcionalidad:
http://programacionnolinealsm.wordpress.com/proporcionalidad/
Planteamiento de problemas de programacin no lineal y
optimizacin:
http://programacionnolinealsm.wordpress.com/planteamiento-de-
problemas-de-programacion-no-lineal-y-optimizacion/
Programacin convexa:
http://programacionnolinealsm.wordpress.com/programacion-convexa/
Como resolver un modelo de programacin no lineal con AMPL:
http://www.gestiondeoperaciones.net/programacion-no-lineal/como-
resolver-un-modelo-de-programacion-no-lineal-con-ampl/