Investigacion de Operaciones 3 Ambos Archivos

8/6/2019 Investigacion de Operaciones 3 Ambos Archivos

1/26

INTRODUCCION

La Programacin no Lineal (PNL) es una parte de la Investigacin Operativacuya misin es proporcionar una serie de resultados y tcnicas tendentes a ladeterminacin de puntos ptimos para una funcin (funcin objetivo) en undeterminado conjunto (conjunto de oportunidades), donde tanto la funcinobjetivo, como las que intervienen en las restricciones que determinan elconjunto de oportunidades pueden ser no lineales. Evidentemente, la estructuradel problema puede ser muy variada, segn las funciones que en lintervengan (a diferencia de la Programacin Lineal (PL) donde la formaespecial del conjunto de oportunidades y de la funcin objetivo permitenobtener resultados generales sobre las posibles soluciones y facilitan lostratamientos algortmicos de los problemas). Ello ocasiona una mayor dificultaden la obtencin de resultados, que se refleja tambin en la dificultad de laobtencin numrica de las soluciones. En este sentido, hay que distinguir entrelas diversas caracterizaciones de ptimo, que slo se emplean como tcnicasde resolucin en problemas sencillos, y los mtodos numricos iterativos, cuyofuncionamiento se basa en estas caracterizaciones, para la resolucin deproblemas ms generales.

Los mtodos de solucin de la programacin no lineal se pueden clasificar, demanera general, en algoritmos directos e indirectos. Como ejemplo de losmtodos directos estn los algoritmos de gradiente, donde se buscan elmximo (el mnimo) de un problema siguiendo la mayor tasa de aumento(disminucin) de la funcin objetivo. En los mtodos indirectos, el problemaoriginal se sustituye por otro del cual se determina el ptimo. Como ejemplosde estos casos estn la programacin cuadrtica, la programacin separable yla programacin estocstica (TAHA, 2004).

El problema general de la Programacin no Lineal toma la siguiente forma:

donde: x = (x1, x2, xn) Rn es la variable instrumental o de decisin.

f: D Rn R es la funcin objetivo, es decir, aquella que se deseaoptimizar (en este caso, maximizar), y D su dominio.

g : D Rn Rm es una funcin vectorial g = (g1, g2, , gm) compuestapor las funciones de restriccin.

b Rm es el vector de trminos independientes, o recursos. Cada expresingi(x) bidetermina una restriccin sobre las variables instrumentales.Se denomina conjunto de oportunidades del problema, o conjunto factibleal conjunto de puntos de D que satisfacen las restricciones del problema, esdecir, X = {x D / g(x) b}.

Una combinacin de variables instrumentales x se dice que es factible para elproblema (PNL) si pertenece a X. As pues, el problema (PNL) consiste enencontrar las variables de decisin factibles para el problema para las cuales la


2/26

funcin objetivo tome el mayor valor posible. Si para un punto, la funcinobjetivo toma el valor mximo de todos los puntos situados en algn entornosuyo, se dice que el mximo es local. Si se encuentra un punto que produce elvalor mximo de f en todo el conjunto de oportunidades, el mximo es global:

Definicin 1: Un punto x* X se dice que es un mximo local de (PNL) si existeun entorno de x*, E(x*) tal que x E(x*) X, se verifica f(x*) f(x).Definicin 2: Un punto x* X se dice que es un mximo global de (PNL) si x

X, se verifica f(x*) f(x).

Es importante tener en cuenta que esta formulacin del problema no suponeprdida de generalidad, ya que si el objetivo fuese minimizar la funcinobjetivo, se puede maximizar su opuesta. Por otro lado, cualquier restriccincon se puede convertir en una de sin ms que cambiar de signo, y lasrestricciones de igualdad se pueden descomponer en dos, con las dosdesigualdades. No obstante, tambin enunciaremos los resultados msimportantes para el problema de mnimo.

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 estnorientados a poder asegurar la globalidad de los ptimos obtenidos. En efecto,veremos que la casi totalidad de los mtodos y caracterizaciones empleados enla resolucin de problemas no lineales slo nos garantizan la obtencin deptimos locales. El primero de los teoremas que enunciamos (Teorema deWeierstrass) nos da las condiciones bajo las cuales podemos asegurar laexistencia de ptimos globales en un problema. El segundo (Teorema Local Global) nos proporciona las condiciones que nos permiten afirmar que unptimo local es global.

Teorema 1. Teorema de Weierstrass.

Dado el problema (PNL), si el conjunto de oportunidades X es compacto y novaco, y la funcin objetivo f es continua en X, entonces el problema (PNL)posee mximo y mnimo globales.

Teorema 2. Teorema Local Global.

Dado el problema (PNL), si el conjunto de oportunidades X es convexo, y lafuncin objetivo f es continua y cncava (resp. convexa) en X, entoncescualquier mximo (resp. mnimo) local de (PNL) es global. Un problema de

programacin no lineal es un problema de programacin no lineal norestringido. Los siguientes subconjuntos de (llamados intervalos) sern departicular inters:


3/26

Supngase que (1) es un problema de maximizacin.

Por supuesto, si son funciones lineales, entonces (1) ser un problema deprogramacin lineal y puede resolverse mediante el algoritmo simplex.

UNIDAD 3: PROBLEMAS DE PROGRAMACIN NO LINEAL

PLANTEAMIENTO DEL PROBLEMA DE PROGRAMACIN NO LINEAL.

El objeto de las siguientes secciones es definir una serie de conceptosrelacionados con el problema general de programacin no lineal, as como elestudio de las relaciones existentes entre cada uno de ellos y la solucin dedicho problema.

Los conceptos que estudiaremos sern los siguientes:

Punto estacionario.

Punto minimax, ntimamente relacionado con el concepto de dualidad .

Veremos que, en general, ser ms directa la demostracin de la suficiencia deestas condiciones para asegurar que tenemos una solucin del problema que

la de la necesariedad de las mismas, para las que habr que imponer condiciones de regularidad sobre la s restricciones del problema, quellamaremos cualificaciones de restricciones. En esta seccin se enuncianvarias cualificaciones de restricciones y se estudia la relacin entre ellas. Engeneral, los resultados que se obtienen generalizan los dados en la seccinanterior para los problemas con restricciones de igualdad, en el sentido de laexistencia de condiciones de primer orden que implican a las primerasparciales de la funcin de Lagrange asociada al problema y condiciones desegundo orden que suponen convexidad de ciertas funciones.


4/26

Un problema general de programacin no lineal consiste en encontrar losvalores de ciertas variables que maximizan o minimizan una funcin dada,dentro de un conjunto definido por una serie de restricciones de desigualdad,de forma que no hay aseguradas condiciones de linealidad ni sobre la funcin aoptimizar ni sobre las funciones que definen el conjunto dentro del cualbuscamos dicho ptimo.

donde:

y son ambas al menos de clase dos en todo su dominio.

El conjunto de oportunidades X es el conjunto en el cual maximizamos lafuncin, es decir, la interseccin entre el dominio de las funciones del problemay el conjunto determinado por las restricciones. As, donde: X = { x D / g(x) b }, b = (b1 ,, bm).

Este tipo de problemas es muy representativo de las circunstancias en las quese desenvuelve la actividad econmica. Normalmente, se dispone decantidades limitadas de recursos, pero sin la obligacin de emplearlas en sutotalidad, si ello no resultase adecuado. Por c onsiguiente, es posible pensar ensoluciones factibles y ptimas que no saturen necesariamente todas lasrestricciones, dejando un excedente inutilizado del recurso cuya disponibilidadlimitan.

Se debe tener en cuenta sin embargo, en relacin con el proble ma formulado,que el sentido de las desigualdades ( ) es nicamente cuestin de convenio.

1). Por otra parte, una restriccin de igualdad puede reemplazarse por dos dedesigualdad, por ejemplo, g(x) = b se convierte en g(x) b y -g(x) -b. O bienpuede ser tratada directamente, sin restringir el signo del multiplicador correspondiente. En ocasiones, para que el problema sea econmicamentesignificativo, es necesario que las variables instrumentales sean no negativas,es decir, x 0. Ms adelante en este captulo, daremos un tratamiento


5/26

especfico a estas restricciones. Asociadas al problema de maximizacin,podemos definir la siguiente funcin, muy importantes en lo que sigue:

Funcin de Lagrange L:

L : D Rm+ R L(x, ) = f(x) t[g(x) - b] 1, donde Rm+ es el vector demultiplicadores asociado al bloque de restricciones del problema, tambindenominados multiplicadores de Kuhn Tucker.

Dado un vector b Rm, si llamamos x0(b) a la correspondiente solucindel problema de programacin no lineal, se puede demostrar, anlogamente alo que vimos en el caso con restricciones de igualdad, que, para cada j = 1, ,m, anterior, una disminucin del valor de bj originara un aumento del valor dela funcin objetivo en el mximo, para un conjunto de oportunidades que es unsubconjunto del de partida, lo que estara en contradiccin con que x0 fuera elmximo del problema original.

Al objeto de analizar en profundidad las propiedades del problema deprogramacin no lineal, ser necesario en algunos casos distinguir entre lasrestricciones que se verifican con igualdad en el ptimo y las que se verificancon desigualdad estricta. As, diremos que la restriccin gi(x) bi es activa enun punto factible x0 (o que x0 satura dicha restriccin), si verifica gi(x0)= bi.

Ejemplos de Programacin No Lineal

Ejemplo N 1

A una compaa le cuesta c UM por unidad fabricar un producto. Si lacompaa cobra p UM por unidad de producto, los clientes pedirn unidades.

Para maximizar las ganancias, qu precio tendra que poner la compaa?Solucin

La variable de decisin de la empresa es p y la empresa querr resolver elsiguiente problema de maximizacin sin restriccin:


6/26

Ejemplo N 2

Si se utilizan K unidades de capital y L unidades de trabajo, una compaapuede producir KL unidades de un bien manufacturado. Se puede conseguir elcapital a 4 UM/unidad y el trabajo a 1 UM/unidad. Se dispone de un total de 8UM para contratar capital y trabajo. Cmo puede la compaa maximizar lacantidad de bienes que se pueden fabricar?Solucin

Sea

K = unidades de capital contratadas y L = unidades de trabajocompradas entonces K y L deben satisfacer.

Por lo tanto, la compaa quiere resolver el si guiente problema demaximizacin restringido:

Problemas de programacin no lineal.

Solucin:

En general en la resolucin de un problema de programacin no linealseguiremos una serie de pasos:

En primer lugar intentaremos representar grficamente nuestro conjunto de

oportunidades y las curvas de nivel de la funcin objetivo.El segundo paso consistir en comprobar la aplicabilidad de los Teoremas deWeierstrass y Local Global, de tal forma que podamos tener seguridad de laexistencia de solucin global a nuestro problema, y si dichas soluciones queobtengamos con las tcnicas aplicadas son las soluciones globales.

En tercer lugar obtendremos las soluciones a nuestro problema mediante lascondiciones de punto estacionario, aunque en este caso podemos seguir dos


7/26

vas para la resolucin del sistema que se genera. Una, corresponde a laresolucin de dicho sistema teniendo en cuenta las distintas ramas que sepresenten y otra, basada en la determinacin, con la ayuda de larepresentacin grfica, de las restricciones activas en el ptimo y reducir deesa manera las distintas posibilidades del caso anterior.

Posteriormente deben analizarse las condiciones de segundo orden tantonecesaria como suficientes, para poder afirmar si dichos puntos estacionariosson ptimos, y si lo son, si son locales o globales.

Las condiciones de punto estacionario vienen dadas por:

El conjunto de oportunidades, como podemos observar en la grfica, es unconjunto cerrado, acotado, convexo y no vaco, mientras que la funcinobjetivo es continua y convexa, luego por el Teorema de Weierstrasspodemos asegurar que existe un mnimo global y por el Teorema Local Global, todo mnimo local es global.

En consecuencia, nos bastara con determinar los mnimos locales ydirectamente obtendremos los globales pero, como se verifican lascondiciones suficientes para que un punto estacionario sea mnimo global,slo necesitamos encontrar los puntos estacionarios. Para ello, podemoshacerlo de dos formas posibles, directamente a travs de las condiciones depunto estacionario, o bien, a travs de la grfica analizando las restriccionesactivas en el mnimo. Veamos los dos procedimientos comenzando por el de

punto estacionario. Para resolver el problema a travs de las condiciones depunto estacionario, para construir la funcin de Lagrange deberemosmodificar nuestra funcin objetivo de acuerdo con la relacin: Min (x 3)2 +(y 1)2 = Max (x 3)2 - (y 1)2 Y entonces, la funcin deLagrange vendr dada por L ( x, y, 1 , 2 ) ( x 3) ( y 1) 2 1 ( xy2 9) 2 ( 5 y).


8/26

Las condiciones de punto estacionario vienen dadas por:

Para resolver ese sistema que contiene ecuaciones e inecuacionescomenzaremos resolviendo las ecuaciones y posteriormente, comprobaremos

el cumplimiento de las inecuaciones. As, determinaremos los puntos queverifican (1), (2), (5) y (6). Para ello, pueden formarse cuatro sistemas quevienen dados por las ecuaciones (1), (2), (5a) o (5b) y (6a) o (6b).Posteriormente, comprobaremos si las soluciones verifican las inecuaciones(3), (4), (7) y (8) y dichos puntos sern los puntos estacionarios para nuestroproblema de mnimo.

Pasamos a estudiar cada una de las cuatro posibilidades que surgen alcombinar las distintas ramas.

a) 1 = 2 = 0-2(x-3) = 0 x = 3-2(y-1) = 0 y = 1 Punto que no verifica laprimera restriccin luego no sera factible.

b) 1 = 0 5 x + y = - 2( x 3)-2(x-3) + 5 2 = 0 2 = 5-2(y-1) 2 = 0 2= 2( y 1) Igualando las dos expresiones que surgen para 2 ydespejando la variable x obtenemos que:


9/26


10/26


11/26

La siguiente pregunta que debemos contestar para finalizar la resolucin deeste problema es si este punto estacionario es un mnimo global. La respuestasera s, ya que, como ya hemos visto, se verifican las condiciones suficientespara que un punto estacionario sea mnimo global.

3.2 OPTIMIZACIN CLSICA.

Si la restriccin no existe, o es una restriccin de igualdad, con menor o igualnmero de variables que la funcin objetivo entonces, el cl culo diferencial, dala respuesta, ya que solo se trata de buscar los valores extremos de unafuncin.

3.2.1 PUNTOS DE INFLEXIN PROGRAMACIN NO LINEAL

Puntos estacionarios.

Procedemos entonces, tras haber establecido ciertos conceptos bsicos en laseccin anterior, a resolver el problema

Maximizar sujeta a :f (x)g(x) b(PRD)


12/26

donde suponemos que se dan condiciones de diferenciabilidad sobre f y g yque el conjunto D es abierto. En esta situacin, tenemos aseguradas ciertascondiciones de diferenciabilidad sobre la funcin de Lagrange L. Empezaremosdefiniendo el concepto de punto estacionario de Kuhn -Tucker a partir de L. Trasello, estudiaremos su relacin con las soluciones del problema (PRD). Comoveremos, sern necesarias condiciones de convexidad en los teoremas desuficiencia, y no as en los de necesariedad (donde, eso s, har falta incluir cualificaciones de restricciones).

As pues, definimos:

supuesto que x0 es un punto factible:

Una vez definido este concepto, veamos seguidamente los teoremas quelo relacionan con las soluciones del problema (PRD). Empezaremos dando elteorema de condiciones necesarias, es decir, el teorema en el que seestablecen qu condiciones necesariamente deben verificar los ptimos de(PRD).


13/26

Como se observa, gracias a la formulacin de punto estacionario de Kuhn-Tucker (4), este teorema afirma que, si se verifica la cualificacin derestricciones de independencia lineal en x0, entonces necesariamente todoptimo local del problema es un punto estacionario de Kuhn-Tucker.Existe otro concepto de punto estacionario (punto estacionario de Fritz-John) ms general que el de Kuhn-Tucker, que no necesita de la cualificacinde restricciones para que se establezca esta condicin neces aria.

Este teorema admite exactamente la misma formulacin para elproblema de mnimo, teniendo simplemente en cuenta las definiciones depunto estacionario para mnimo. As, por ejemplo, la condicin quedara:

f (x ) + i gi (x ) = 0 .00i I

Pasamos ahora a dar el teorema de condiciones suficientes, es decir, elteorema que afirma bajo qu condiciones un punto estacionario de KuhnTucker es mximo del problema. Ya se ha comentado que hace falta en estecaso exigir condiciones de convexidad sobre las funciones del problema.Realmente, basta con unas suposiciones un poco ms suaves que laconvexidad global, si bien aqu no vamos a especificarlas: 24 sobre lasfunciones del problema. Realmente, basta con unas suposicio nes un poco mssuaves que la convexidad global, si bien aqu no vamos a especificarlas

Este teorema admite una formulacin similar para el problema de mnimo, conlas correspondientes definiciones de los puntos estacionarios, y suponiendoque la funcin f sea convexa. Si observamos con detenimiento las condicionesde punto estacionario que hemos desarrollado en esta seccin, podremosver su analoga con el caso en el que existan restricciones de igualdad. Enconcreto, desde un punto de vista intuitivo, el proceso se podra interpretar de


14/26

la siguiente forma: en primer lugar, se identifican las restricciones activas en elpunto en cuestin. Posteriormente, se toman las condiciones de primer ordenpara problemas con restricciones de igualdad, teniendo en cuenta slo lasmencionadas restricciones activas (que, en el punto bajo estudio, se puedenconsiderar de igualdad). Finalmente, se aade la condicin adicional de nonegatividad sobre los multiplicadores ptimos, que, segn vimos previamente,garantizan que la funcin objetivo no mejora al moverse hacia el interior relativode las restricciones activas.

3.2.1 MXIMOS Y MNIMOS PROGRAMACIN NO LINEAL

Una funcin puede contener varios mximos y mnimos, identificados por lospuntos extremos de la funcin. En la figura se puede observar esto, los puntosx1, x3 y x6 son mximos, de la figura notamos que f(x6) es el mayor que f(x1) y

f(x3), a este punto se le conoce como mximo global de la funcin y a losrestantes como mximos locales. Lo mismo se puede ver para los mnimos, enlos que tambin existe un mnimo global f(x2) y un mnimo local f(x4). Como esde lgico, solo puede existir un solo global y posiblemente varios locales.

Puntos minimax.

El punto minimax de la funcin lagrangiana es otro conc epto relacionado con lasolucin de un problema de optimizacin. Si bien su definicin no le hace til ala hora de la resolucin directa del problema, s constituye un paso intermediomuy importante en la obtencin del problema dual. En esta seccin definimosdicho punto y estudiamos su relacin con otro concepto, el punto de silla de lalagrangiana.

La relacin del punto minimax con la solucin del problema de programacin nolineal se obtiene de forma inmediata sin ms 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 laLagrangiana.

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


15/26

As pues, si (x0, 0) es un punto minimax, x0 es una solucin ptima delproblema original. Pasamos ahora a dar los teoremas que relacionan losconceptos de punto de silla de L y punto minimax. Veremos que dicha relacines casi una equivalencia, en el sentido de que todo punto minimax es puntode silla, y todo punto de silla es un punto minimax considerado sobreconjuntos ms restringidos.

Como hemos expuesto anteriormente, para obtener el teorema recproco esnecesario restringir los conjuntos de definicin del punto minimax. Previamente,hemos visto que la primera parte de la igualdad debe ser de la forma

Definimos, por tanto, N = { R m + / Max ( f ( x ) t [g(x) b ])}, NR m+ Entonces, la segunda parte de la igualdad se debe expresar como sigue:

Min Max L (x, ) Por tanto, el punto minimax que buscamos ahora es de laforma:

Para el problema de mnimo, el punto minimax toma la forma:

tomando adems la funcin lagrangiana correspondiente a este problema.Con esta definicin, los teoremas 16 y 17 seran vlidos de forma anloga paraesta formulacin.


16/26

El concepto de dualidad nace estrechamente ligado al de punto minimax quese desarroll en la seccin anterior. As, dado nuestro problema original,recordemos la definicin de punto minimax: se trata de un par (x0, 0) queverifica: L (x0 , 0 ) = Max Min L (x, ) = Min Max L (x, ) , donde L(x, ) =f(x) t[g(x)

Dualidad en Programacin Matemtica.El concepto de dualidad nace estrechamente ligado al de punto minimax quese desarroll en la seccin anterior. As, dado nuestro problema original,recordemos la definicin de punto minimax: se trata de un par (x0, 0) queverifica: L (x0 , 0 ) Max Min L (x, ) Min Max L (x, ) ,L(x, ) = f(x) - t[g(x)

que es, precisamente, el problema de partida, que llamaremos a partir de ahoraProblema.

Solucin de Programacin no Lineal con una Variable

Aqu explicaremos cmo resolver el PNL: mx. (o mn.) (4) sujeto a (Si , laregin factible para el PNL (4) es y si , la regin factible para (4) es ).

Para encontrar la solucin ptima para (4), buscamos todos los mximos (omnimos) locales. Un punto que es un mximo local o un mnimo local para (4)se llama un extremo local. Entonces la solucin ptima para (4) es el mximo(o mnimo) local con el mayor (o menor) valor de Naturalmente, si , (4) nopuede tener una solucin ptima (ver la figura).


17/26

Existen tres tipos de puntos para los cuales (4) puede tener un mximo omnimo local (estos puntos a veces se llaman extremos candidato).

Caso 1. Los puntos en los cuales y (llamado punto estacionario de )

3.3 PROBLEMAS NO RESTRINGIDOS PROGRAMACIN NO LINEAL

Caso con restricciones de igualdad.

Como paso previo al tratamiento del problema general de ProgramacinMatemtica, vamos a estudiar el caso especial en el que todas las restriccionessean de igualdad. Ello nos permitir, cuando abordemos el estudio del casogeneral, distinguir el caso en que el ptimo sea interior al conjunto deoportunidades (anlogo al caso irrestricto), y el caso en que el ptimo est enla frontera (anlogo a este problema con restricciones de igualdad, sise consideran slo aquellas que se satisfacen con igualdad). As pues, los


18/26

resultados obtenidos en este captulo sern un punto de partida para el estudiodel caso general.

El problema que estudiamos en este caso es:

donde se supone que f est definida sobre el conjunto de oportunidadesdeterminado por las restricciones, que son m relaciones de la forma gi(x) = bi, i= 1, , m. Supondremos que tanto la funcin objetivo f como las restriccionesgi son de clase 2 en X.

A lo largo del tratamiento de estos problemas, es de vital importancia ladefinicin de la llamada funcin de Lagrange asociada, que es una funcin que

de alguna forma engloba todo el problema, al aadir a la funcin objetivo lasrestricciones, cada una de ellas acompaada por un multiplicador ( multiplicador de Lagrange):

Definicin 3.

En lo que sigue, veremos que las condiciones de primer y segundo orden eneste caso son anlogas al caso irrestricto, pero exigindolas sobre la funcinde Lagrange en lugar de sobre la funcin objetivo f. Previamente, vamos aestudiar algunas propiedades interesantes de la funcin de Lagrange.

La primera nos asegura que cuando trabajamos con puntos factibles, el valor de la funcin de Lagrange coincide con el de la funcin objetivo. La segundanos permite afirmar que cualquier punto crtico de la funcin de Lagrange esfactible para el problema (PRI):

Teorema 9.


19/26

Demostracin: Si x es un punto arbitrario de X:g(x) b = 0,de donde: L(x, ) =f(x) t 0 = f(x).

Antes de enunciar la siguiente proposicin, expresemos el gradiente de lafuncin de Lagrange de una forma operativa: L(x, ) = f(x) t [g(x) - b]resultando que:

Ahora bien: x L(x, ) = x [f(x) - t (g(x) - b)] =f(x) t [Jg(x)]t Luego, endefinitiva:

Demostracin.

Si (x* ,*) es punto crtico de L, entonces, por la forma de su gradiente,

de donde se deduce que x* D pues existen f(x*) y g(x*), y adems: - (g(x*) b) = 0. Luego x* X, como queramos demostrar.

Segn hemos visto, la funcin de Lagrange incorpora tanto la funcin objetivodel problema original, como las restricciones del mismo. Adems, tambin severifica que todo punto crtico de la funcin de Lagrange es factible para elproblema (PRI), y, en esta situacin, el valor de L coincide con el de f. En estascircunstancias, cabe preguntarse si existir alguna relacin entre los ptimoslocales de (PRI) y los puntos crticos de L. El siguiente teorema demuestra que,en efecto, todo ptimo local de (PRI) produce un punto crtico de lalagrangiana:


20/26

Demostracin.

Supongamos que x* es un ptimo local de (PRI), lo cual implica que x* esfactible, es decir, g(x*) = b, y que existe un entorno de x*, E1(x*), tal que x* esptimo global de f en el conjunto de puntos de E1(x*) que satisfacen lasrestricciones del problema. Por otro lado, por hiptesis, las restriccionesverifican ser de rango completo en x*, es decir,

en cuyo caso x = (x1t, x2t), resulta que lo anterior es suficiente (teorema de lafuncin implcita) para que existan un entorno de x1*, E1(x1*), un entorno dex2*, E2(x2*), y una funcin

h : E2(x2*) E1(x1*), tal que: (i) h(x2*) = x1*(ii)x2 E2(x2*), g(h(x2), x2)= b. Podemos suponer, sin prdida de generalidad, que E (x *) E(x *) E1(x*). es decir, que x* es ptimo global de f en el entorno en el que podemosponer x1 como funcin de x2. Sustituyendo en la funcin objetivo, podemosdefinir una nueva funcin:

F: E 2 (x 2 *) RF (x 2 ) =f (h(x 2 ), x 2 )

funcin en las variables x2 = (xm+1, xm+2, , xn) que no est restringida por ninguna relacin en un entorno del punto x*, pudiendo aplicarle las tcnicasdesarrolladas en el apartado anterior. Como, por hiptesis, x* es ptimo enE1(x*), entonces, x2* lo ser de la nueva funcin F, y por tanto: es decir,

F(x2*) = 0.

Por otro lado, en todo E2(x2*), se verifica que g(h(x2), x2) = b, lo cual implicaque:


21/26

y estas parciales no se pueden anular en (0, 0) para ningn valor delmultiplicador , por lo que (0, 0) no es punto crtico de L.

Al igual que ocurre en el caso irrestricto, tambin en el problema restringidoexisten condiciones de segundo orden que garantizan la optimalidad de lospuntos crticos de la funcin de Lagrange. Esta condicin de segundo orden,tambin supone condiciones sobre la matri z hessiana, pero, en este caso, setomar restringida a una condicin que garantiza que comparamos el ptimoslo con los puntos de su entorno que pertenecen al conjunto de oportunidadesdel problema.

Teorema 12. Si (x*, *) es un punto crtico de la funcin de Lagrange asociadaal problema (PRI), una condicin suficiente para que x* sea un mximo (resp.mnimo) local del problema es que la forma cuadrtica


22/26

3.3.1 MULTIPLICADORES DE LAGRANJE LAMBDA

INTERPRETACIN DE LOS MULTIPLICADORES DE LAGRANGE.

Uno de los resultados ms importantes de la Programacin Matemtica, quedesarrollamos a continuacin, es que la valoracin marginal de los recursos,cuyo uso est fijado por las restricciones, viene dada por los multiplicadores(variables duales) asociados a los mismos.

Sea el problema: Max f(x)s.a g(x) = b.Sea (x*, *) una solucin ptima dedicho problema. Se trata, por tanto, de un punto crtico de la funcin deLagrange asociada al problema:

L(x, ) = f(x) t (g(x) b) es decir, (x*, *) verifican:xL(x*, *) = x f(x*) Jg(x*)* = 0 L(x*, *) = g(x*) + b = 0

Para distintos valores del segundo miembro de las restricciones (vector b), seobtendran, lgicamente, distintas soluciones ptimas del problema anterior.Consideremos entonces la solucin ptima como una funcin del vector b, ysupongamos que esta funcin es diferenciable (lo cual es cierto si se verificanlas condiciones suficientes de optimalidad): x* = x(b) * = (b)

Los valores ptimos de la funcin objetivo pueden considerarse como unafuncin de b, f(x(b)), e igualmente la funcin vectorial de las restricciones,g(x(b)). Derivando, tanto una como otra con respecto a b, obtenemos,respectivamente b f(x(b)) = Jb(x(b)) x f(x(b)) Jb g(x(b)) = Jb(x(b)) Jx g(x(b))

Teniendo en cuenta las condiciones de optimalidad de primer orden x f(x*) Jx g(x*) * = 0 y multiplicndolos por Jb(x(b)): Jb(x(b))x f(x(b)) Jb(x(b)) Jx

g(x(b)) * = 0sustituyendo por las expresiones anteriormente obtenidas, resulta: b f(x(b)) Jb g(x(b)) * = 0

Finalmente, como g(x(b)) = b, derivando esta expresin con respecto a lasvariables bi, obtenemos que Jb g(x(b)) = I(mm), por tanto:

es decir, la variacin del valor ptimo de la funcin objetivo f(x*) producida por variaciones infinitesimales del segundo miembro de una restriccin, estrepresentada por el multiplicador ptimo i asociado a la misma. En otraspalabras, el valor ptimo del multiplicador de Lagrange asociado a unadeterminada restriccin nos proporciona un medida de la sensibilidad del valor ptimo de la funcin objetivo ante cambios en el recurso de dicha restriccin.


23/26

Nota. En los problemas de mnimo, se suele tomar la funcin de Lagrangecomo:L(x, ) = f(x) + t [g(x) - b],

Esta interpretacin general tiene una traduccin econmica concreta segn seala funcin objetivo y la expresin de las restricciones. Si la funcin objetivoconsiste, por ejemplo, en maximizar la funcin de utilidad del consumidor sometido a una restriccin presupuestaria de igualdad, el multiplicador deLagrange se interpreta como la utilidad marginal por unidad monetaria. Si elproblema consiste en determinar el plan de produccin compatible con lafuncin de produccin de la empresa y tal que resulte mnimo el coste deproduccin, el multiplicador de Lagrange se interpretara como el coste marginalde produccin del producto.

Es por ello que los multiplicadores de Lagrange reciben l a denominacin deprecios de clculo por cuanto permiten determinar las consecuencias de unamodificacin marginal de una restriccin.

Pueden considerarse como la medida del pago mximo que podra efectuarsea cambio de un desplazamiento de la restricci n. Por ejemplo, si el problema esmaximizar el beneficio eligiendo los niveles de factores productivos y deproduccin, sujetos a la limitacin impuesta por la cantidad disponible de unfactor, b. En este problema, * mide la rentabilidad marginal del fact or o la tasaa la que aumenta el beneficio mximo como consecuencia de un pequeoincremento en la cantidad fija del factor. Por consiguiente, * mide la cantidadmxima que la empresa estara dispuesta a pagar por el incremento en el

factor, ya que si pagase menos el resultado sera un incremento neto en elbeneficio, y si pagase ms se producira una reduccin neta del mismo. Por esta razn, a * se le puede denominar precio sombra del factor, utilizndosedicho adjetivo para indicar que el precio pued e diferir del precio real delmercado.

Otro aspecto digno de resaltarse es el comportamiento e interpretacin delsigno del multiplicador. As, si la lagrangiana se toma para mximo (es decir,los multiplicadores entran restando), en el supuesto de multipl icador positivo

En el caso en que la funcin de Lagrange se formule para mnimo, estasrelaciones se dan justo a la contra.


24/26

3.3.2 INTERPRETACIN ECONMICA.

Los multiplicadores de Lagrange tienen una interpretacin econmicainteresante e importante. En otras palabras, en el punto ptimo, el valor delmultiplicador de Lagrange es la tasa de cambio instantnea del VO (el valor ptimo de la funcin objetivo), cuando el -simo LD (valor en solucin), biaumenta, permaneciendo iguales todos los dems datos. Otra forma deexpresar este concepto en trminos de economa, es que el i-simomultiplicador de Lagrange refleja el valor marginal del i -simo recurso. Por consiguiente, sus unidades son:

Unidades de la funcin objetivo

-----------------------------------------------

Unidades del LD de la restriccin iPor ejemplo, un fabricante desea minimizar el costo total de un producto, elobjetivo estaba expresado en dlares, bajo la restriccin de que la produccintotal, digamos en toneladas, de dos productos deba ser igual a K. As pues, lasunidades del multiplicador de Lagrange para esta restriccin son dlares por tonelada, y el valor de la misma es el costo marginal instantneo de produccincorrespondiente a la R-sima unidad

Los multiplicadores de Lagrange tienen a menudo una interpretacin comocierta cantidad saliente de inters. Para ver por qu ste pudo ser el caso,observe eso:

As pues, k es el ndice del cambio de la cantidad que es optimizada enfuncin de la variable del constreimiento. Como ejemplos, adentro MecnicosLagrangiana las ecuaciones del movimiento son derivadas encontrando puntosinmviles de la accin, el integral del tiempo de la diferencia entre la energacintica y potencial.

As, la fuerza en una partcula debido a un potencial escalar, puede ser interpretado como multiplicador de Lagrange que determina el cambio en laaccin (transferencia del potencial a la energa cintica) que sigue unavariacin en la trayectoria obligada de la partcula. En la economa, el beneficioptimo a un jugador se calcula conforme a un espacio obligado de acciones,donde est el valor un multiplicador de Lagrange de relajar un constreimientodado (e.g. con soborno u otros medios).

El mtodo de multiplicadores de Lagrange es generalizado por Condiciones deKarush-Kuhn-Tucker. Un ejemplo muy simple

Supngale desear maximizar f(x,y) = x + y conforme al constreimiento x2 + y2= 1. El constreimiento es el crculo de la unidad, y sistemas del nivel de f son


25/26

las lneas diagonales (con la cuesta -1), as que una puede ver grficamenteque el mximo ocurre en (y el mnimo ocurre en Formalmente, sistema g(x,y) =x2 + y2 1, y (x,y, ) = f(x,y) + g(x,y) = x + y + (x2 + y2 1)

Fije el derivado d = 0, que rinde el sistema de ecuaciones: Como siempre, laecuacin es el constreimiento original.

Combinar las primeras dos producciones de las ecuaciones x = y(explcitamente, (si no (i) rinde 1 = 0), as que uno puede solucionar para ,rindiendo = 1/(2x), en que uno puede substituir (ii)).

El substituir en (iii) rinde 2x2 = 1, tan y los puntos inmviles son y . Evaluacinde la funcin objetiva f en estas producciones as el mximo es , en que selogra y el mnimo es , en que se logra .

Ejemplo simple

Suponga que usted desea encontrar los valores mximos para con la condicinque x y y las coordenadas mienten en el crculo alrededor del origen con elradio 3, es decir, Pues hay justo una sola condicin, utilizaremos solamenteun multiplicador, decimos el . Utilice el constreimiento para definir unafuncin g(x, y):

La funcin g es idnticamente cero en el crculo del radio 3. Tan cualquier mltiplo de g(x, y) puede ser agregado a f(x, y) yndose f(x, y) sin cambiar en laregin del inters (sobre el crculo donde nuestro constreimiento original estsatisfecho). Dejado los valores crticos de ocurra cuando su gradiente escero. Los derivados parciales son la ecuacin (iii) es justa el constreimientooriginal. La ecuacin (i) implica x = 0 o = y. En el primer caso, si x = 0entonces debemos tener por (iii) y entonces por (ii) =0. En el segundo caso, si

= y y substituyendo en la ecuacin (ii) tenemos eso, Entonces x2 = 2y2. Elsubstituir en la ecuacin (iii) y el solucionar para y da este valor de y:

As hay seis puntos crticos:

Evaluando el objetivo en estos puntos, encontramos por lo tanto, la funcinobjetiva logra a mximo global (con respecto a los apremios) en y a mnimoglobal en el punto es a mnimo local y es a mximo local.

Ejemplo: entropa

Suponga que deseamos encontrar el discreto distribucin de la probabilidadcon mximo entropa de la informacin. Entonces por supuesto, la suma deestas probabilidades iguala 1, as que nuestro constreimiento es g(p) = 1 .

Podemos utilizar los multiplicadores de Lagrange para encontrar el punto de laentropa mxima (dependiendo de las probabilidades). Para todos k a partir dela 1 a n, requerimos eso cul da realizar la diferenciacin de stos n lasecuaciones, conseguimos. Esto demuestra eso todo pi sea igual (porquedependen de solamente). Usando el del constreimiento pk = 1,


26/26

encontramos. Por lo tanto, la distribucin uniforme es la distribucin con laentropa ms grande.

Economa, la optimizacin obligada desempea un papel central adentroeconoma. Por ejemplo, el problema bien escogido para a consumidor serepresenta como uno de a de maximizacin funcin para uso general conformea constreimiento del presupuesto. El multiplicador de Lagrange tiene unainterpretacin econmica como precio de sombra asociado al constreimiento,en este caso utilidad marginal de renta .

Documents

Investigacion de Operaciones 3 Ambos Archivos