Optimización Restringida
(caso n variables de decisión y m
restricciones)
Material complementario
Se deberá acompañar con la siguiente lectura:
Chiang, A. C. & Wainwright, K (2006) Métodos Fundamentales de Economía Matemática, 4º edición. Mc-Graw
Hill Interamericana; capítulo 12
Prof.: Rita Beatriz Morrone
Problemas de optimización
En la formulación de un problema de optimización debe delinearse una función objetivo
en la que la variable dependiente representa el objeto a maximizar o minimizar y en la
que el conjunto de variables independientes indica cuáles son las variables de elección. El
proceso de optimización consiste en hallar el conjunto de valores de las variables de
elección que conducirá al extremo deseado de la función objetivo.
El proceso de optimización empieza con la búsqueda de valores candidatos a
óptimos, es decir aquellos que verifiquen las condiciones necesarias de existencia
de un extremo. El siguiente paso consiste en verificar cuales de esos candidatos
cumplen con las condiciones suficientes para la existencia de un máximo o un
mínimo.
Las condiciones suficientes de segundo orden se relacionan con la forma en la que una
curva, superficie o hipersuperficie se curva alrededor de un punto estacionario. Nos
indican si un punto estacionario es la “cúspide de una colina” o “el fondo de un valle”.
Cuando limitamos la comprobación de la configuración de
colina o valle a una vecindad pequeña del punto estacionario,
podríamos analizar solo los máximos y mínimos relativos
Si la colina o valle pertenece a un subconjunto S del dominio, la función es cóncava o convexa
en S, mientras que, si se da en todo el dominio, la función es cóncava o convexa.
Concavidad/convexidad en todo el dominio → conceptos globales.
Es decir que un extremo de una función cóncava/convexa será un máximo/mínimo absoluto
porque abarcamos todo el dominio. Pero ese extremo absoluto no necesariamente es único,
porque la colina o valle podrían contener una parte superior o inferior horizontal plana. La
última posibilidad se puede descartar solo cuando se especifica concavidad estricta porque solo
entonces la cúspide o valle constará de un solo punto y el extremo absoluto será único.
La formulación del problema comprende las variables de decisión, el conjunto de
factible y la función objetivo.
El problema es tal que se escogen valores para n variables independientes 𝑥1 , 𝑥2 , … , 𝑥𝑛 llamadas de
decisión o de política. Las mismas pueden ser resumidas por el vector columna:
𝒙𝟏
𝒙𝟐
𝑿= … = (𝒙𝟏 , 𝒙𝟐 , … , 𝒙𝒏 )𝒕
𝒙𝒏
llamado vector de decisión. El mismo es un vector en el espacio Euclidiano N-dimensional.
El vector 𝑿 es factible si satisface todas las restricciones del problema.
El conjunto de vectores factibles es el conjunto S de posibles soluciones, un subconjunto de 𝐸 𝑛 .
La función objetivo resume la relación entre la variable dependiente que representa el objeto de
optimización, y las variables independientes:
𝒛 = 𝒇(𝒙𝒊 ) = 𝒇(𝒙𝟏 , 𝒙𝟐 , … , 𝒙𝒏 )
y se supone diferenciable continuamente.
Del problema general de programación matemático pueden distinguirse los
casos de programación clásica, programación no-lineal y programación lineal.
En el problema clásico las restricciones consisten en m igualdades:
g1 (x) = g1 (𝑥1 , 𝑥2 , … , 𝑥𝑛 ) = b1
g 2 (x) = g 2 (𝑥1 , 𝑥2 , … , 𝑥𝑛 ) = b2
…
g 𝑚 (x) = g 𝑚 (𝑥1 , 𝑥2 , … , 𝑥𝑛 ) = b𝑚
donde las funciones g1 (x) , g 2 (x) ,…, g 𝑚 (x) son diferenciables
continuamente y los parámetros b1 , b2 ,…, b𝑚 son constantes reales.
Se asume que el número de variables n y de restricciones m son finitos y
que n>m, donde n-m son los grados de libertad del problema.
Optimización con restricciones de igualdad, el
método de multiplicadores de Lagrange.
En este caso, la elección óptima de los valores de las variables de decisión se
encuentra sujeta a restricciones de igualdad. El conjunto factible es la
intersección de todas ellas. Estas tienen el efecto de reducir el rango de la función
objetivo (aunque siempre la cantidad de variables debe ser mayor a la de
restricciones para posibilitar alguna decisión) y de generar dependencia entre las
variables de elección.
El método de los multiplicadores de Lagrange convierte un problema de extremo
restringido a una forma tal que sea aplicable la condición de primer orden del
problema de extremo libre. Dicho método consiste en el planteo de la función
lagrangiana, que es una versión modificada de la función objetivo que incorpora
las restricciones del problema. Cada restricción se incorpora a la función
lagrangiana con un multiplicador de Lagrange, de forma tal que habrá uno por
cada restricción y serán tratados como variables adicionales del problema.
Método multiplicadores de Lagrange.
Caso de n variables y m restricciones
Para el caso general de n variables y m restricciones, el problema se
formula:
g1 (x) = g1 (𝑥1 , 𝑥2 , … , 𝑥𝑛 ) = b1
2 2
Optimizar 𝑓 𝑥1 , 𝑥2 , … , 𝑥𝑛 𝑠. 𝑎 g (x) = g (𝑥1 , 𝑥 2 , … , 𝑥𝑛 ) = b 2
𝑥1 ,𝑥2 ,…,𝑥𝑛 ⋮
g 𝑚 (x) = g 𝑚 (𝑥1 , 𝑥2 , … , 𝑥𝑛 ) = b𝑚
Variables de decisión
m Restricciones constantes
Con m<n
Función de Lagrange:
𝑚
𝐿(𝑥1 , 𝑥2 , … , 𝑥𝑛 ; 𝜆1 , 𝜆2 , … , 𝜆𝑚 ) = 𝑓(𝑥1 , 𝑥2 , … , 𝑥𝑛 ) + 𝜆𝑖 [𝑏𝑖 − 𝑔𝑖 (𝑥1 , 𝑥2 , … , 𝑥𝑛 )]
𝑖=1
La condición de primer orden consiste en las siguientes (n+m) ecuaciones
simultáneas:
𝜕𝑓 𝑚 𝜕𝑔𝑘
− 𝜆𝑘 =0 𝑖 = 1,2, … , 𝑛
൞ 𝜕𝑥𝑖 𝑘=1 𝜕𝑥𝑖
𝑏𝑖 − 𝑔𝑖 𝑥1 , 𝑥2 , … , 𝑥𝑛 = 0 𝑖 = 1,2, … , 𝑚
para las n + m incógnitas 𝑥1 , 𝑥2 , … , 𝑥𝑛 ; 𝜆1 , 𝜆2 , … , 𝜆𝑚 .
Los puntos críticos son la solución del sistema de n + m ecuaciones simultáneas
SON CANDIDATOS A EXTREMOS
Condición suficiente de segundo orden
La condición suficiente de segundo orden se puede expresar en forma de determinante como en el
caso del extremo libre. Sin embargo, en lugar del determinante hessiano 𝐻 , en el caso del extremo
restringido encontraremos lo que se conoce como hessiano orlado 𝐻 ഥ.
𝑗 𝜕𝑔𝑗
Donde 𝑔𝑖
= son las derivadas
𝜕𝑥𝑖
parciales de las restricciones y
𝜕2 𝐿
𝐿𝑖𝑗 = las derivadas
𝜕𝑥𝑖 𝜕𝑥𝑗
parciales de segundo orden de la
función lagrangiana.
A partir de 𝐻 ഥ pueden formarse diversos menores principales directores orlados. El que
contiene a 𝐿22 como último elemento de la diagonal principal se denomina 𝐻 ഥ2 . Al
incluir una fila y una columna adicionales, de modo de incluir a 𝐿33 , tendremos 𝐻ഥ3 , etc.
Con esta simbología, es posible establecer la condición suficiente de segundo orden en
términos de los signos de los siguientes (n-m) menores principales directores orlados:
𝐻ഥ𝑚+1 , 𝐻ഥ𝑚+2 , … , 𝐻
ഥ𝑛
Condición suficiente para máximo de L: que alternen de signo𝑚+1
los menores principales
ഥ𝑚+1 igual al de (−1)
directores orlados, siendo el signo de 𝐻
Condición suficiente para mínimo
𝑚
de L: que los menores principales directores orlados
tomen todos el signo de (−1) (si el número de restricciones es par, todos los
determinantes deberán ser positivos para un mínimo mientras que, si es impar,
negativos).
Ejemplo:
𝑥 2 + 𝑦 2 = 25
max 𝑧 𝑥, 𝑦, 𝑧 = 𝑥 + 2𝑦 + 2𝑧 𝑠. 𝑎. ቊ
𝑥+𝑦+𝑧 =0
Paso 1 – Armar la función Lagrangeana
𝐿 𝑥, 𝑦, 𝑧, 𝜆1 , 𝜆2 = 𝑥 + 2𝑦 + 2z + 𝜆1 25 − 𝑥 2 − 𝑦 2 + 𝜆2 −𝑥 − 𝑦 − 𝑧
Paso 2 - Plantear las condiciones de primer orden
De (3) Sustituyendo en (1) y (2) 1
𝐿′𝑥 = 1 − 2𝑥𝜆1 − 𝜆2 = 0 𝑥=
(1) 2 = 𝜆2 −2𝑥𝜆1 = 1 −2𝜆1
−2𝑦𝜆1 = 0 𝑦=0
𝐿′𝑦 = 2 − 2𝑦𝜆1 − 𝜆2 = 0 (2)
𝟏
𝐿′𝑧 = 2 − 𝜆2 = 0 (3) Sustituyendo en (4) 𝑥=5 𝑠𝑖 𝑥 = 5 →→ (𝟓; 𝟎; −𝟓; − ; 𝟐)
25 − 𝑥 2 = 0 𝟏𝟎
(4)
𝐿′𝜆1 = 25 − 𝑥 2 − 𝑦 2 = 0 𝟏
𝑥 = −5 𝑠𝑖 𝑥 = −5 →→ (−𝟓; 𝟎; 𝟓; ; 𝟐)
De (5) 𝟏𝟎
𝐿′𝜆2 = −𝑥 − 𝑦 − 𝑧 = 0 (5)
𝑥 = −𝑧
Paso 3 - Verificar las condiciones de segundo orden
𝟎 𝟎 𝟐𝒙 𝟐𝒚 𝟎
𝐿′′𝑥𝑥 = −2𝜆1 𝐿′′𝑥𝑦 = 𝐿′′𝑦𝑥 = 0 𝟎 𝟎 𝟏 𝟏 𝟏
𝐿′′𝑥𝑧 = 𝐿′′𝑧𝑥 = 0
ഥ=
𝐻 𝟐𝒙 𝟏 −2𝜆1 0 0
𝐿′′𝑦𝑦 = −2𝜆1
𝐿′′𝑦𝑧 = 𝐿′′𝑧𝑦 = 0 𝟐𝒚 𝟏 0 −2𝜆1 0
𝐿′′𝑧𝑧 =0
𝟎 𝟏 0 0 0
N=3 ; m=2 – se evalúa el último menor principal valuado en cada punto crítico
Punto crítico → 𝒙∗ ; 𝒚∗ ; 𝒛∗ = 𝟓; 𝟎; −𝟓 Punto crítico → 𝒙∗ ; 𝒚∗ ; 𝒛∗ = −𝟓; 𝟎; 𝟓
𝟏 𝟏
𝒄𝒐𝒏 𝜆1 = − ; 𝜆 = 𝟐) 𝒄𝒐𝒏 𝜆1 = ; 𝜆 = 𝟐)
𝟏𝟎 2 𝟏𝟎 2
𝟎 𝟎 10 0 𝟎 𝟎 𝟎 −10 0 𝟎
𝟎 𝟎 𝟏 𝟏 𝟏 𝟎 𝟎 𝟏 𝟏 𝟏
ഥ=
𝐻 10 𝟏 1/5 0 0 = 20 > 0 ഥ=
𝐻 −10 𝟏 −1/5 0 0 = −20 < 0
0 𝟏 0 1/5 0 0 𝟏 0 −1/5 0
𝟎 𝟏 0 0 0 𝟎 𝟏 0 0 0
Es un mínimo condicionado Es un máximo condicionado
Notar que el sistema formado por las condiciones de primer orden
constituye un sistema de funciones implícitas 𝜕𝐹1 𝜕𝐹1 𝜕𝐹1 𝜕𝐹1 𝜕𝐹1
𝜕𝜆1 𝜕𝜆2 𝜕𝑥 𝜕𝑦 𝜕𝑧
F3 𝜕𝐹2 𝜕𝐹2 𝜕𝐹2 𝜕𝐹2 𝜕𝐹2
𝜕𝜆1 𝜕𝜆2 𝜕𝑥 𝜕𝑦 𝜕𝑧
F4
𝜕𝐹3 𝜕𝐹3 𝜕𝐹3 𝜕𝐹3 𝜕𝐹3
𝐽 = ≠0
F5 𝜕𝜆1 𝜕𝜆2 𝜕𝑥 𝜕𝑦 𝜕𝑧
𝜕𝐹4 𝜕𝐹4 𝜕𝐹4 𝜕𝐹4 𝜕𝐹4
F1 𝜕𝜆1 𝜕𝜆2 𝜕𝑥 𝜕𝑦 𝜕𝑧
𝜕𝐹5 𝜕𝐹5 𝜕𝐹5 𝜕𝐹5 𝜕𝐹5
F2
𝜕𝜆1 𝜕𝜆2 𝜕𝑥 𝜕𝑦 𝜕𝑧
𝟎 𝟎 𝟐𝒙 𝟐𝒚 𝟎 𝟎 𝟎 −𝟐𝒙 −𝟐𝒚 𝟎
𝟎 𝟎 𝟏 𝟏 𝟏 𝟎 𝟎 −𝟏 −𝟏 −𝟏
ഥ=
𝐻 𝟐𝒙 𝟏 −2𝜆1 0 0 𝐽 = −𝟐𝒙 −𝟏 −2𝜆1 0 0 ≠0
𝟐𝒚 𝟏 0 −2𝜆1 0 −𝟐𝒚 −𝟏 0 −2𝜆1 0
𝟎 𝟏 0 0 0 𝟎 −𝟏 0 0 0
Al verificar la condición de segundo orden también se está comprobando las condiciones del teorema de función implícita
La matriz Hessiana orlada
𝐿′′𝜆1𝜆1 𝐿′′𝜆1𝜆2 𝐿′′𝜆1𝑥 𝐿′′𝜆1𝑦 𝐿′′𝜆1𝑧
𝐿′′𝜆2 𝜆1 𝐿′′𝜆2𝜆2 𝐿′′𝜆2𝑥 𝐿′′𝜆2 𝑦 𝐿′′𝜆2𝑧
𝐿 𝑥, 𝑦, 𝑧, 𝜆1, 𝜆2 = f(x; y; z) + 𝜆1 𝑐1 − 𝑔(𝑥; 𝑦; 𝑧 + 𝜆2 𝑐2 − 𝑔(𝑥; 𝑦; 𝑧
ഥ=
𝐻 𝐿′′𝑥𝜆1 𝐿′′𝑥𝜆2 𝐿′′𝑥𝑥 𝐿′′𝑥𝑦 𝐿′′𝑥𝑧
𝐿′′𝑦𝜆1 𝐿′′𝑦𝜆2 𝐿′′𝑦𝑥 𝐿′′𝑦𝑦 𝐿′′𝑦𝑧
𝐿′′𝑧𝜆1 𝐿′′𝑧𝜆2 𝐿′′𝑧𝑥 𝐿′′𝑧𝑦 𝐿′′𝑧𝑧
Es el diferencial segundo de la función lagrangiana y es una forma cuadrática
𝐿′′𝜆1𝜆1 𝐿′′𝜆1𝜆2 𝐿′′𝜆1 𝑥 𝐿′′𝜆1𝑦 𝐿′′𝜆1𝑧
𝑑𝜆1
𝐿′′𝜆2𝜆1 𝐿′′𝜆2𝜆2 𝐿′′𝜆2𝑥 𝐿′′𝜆2𝑦 𝐿′′𝜆2𝑧 𝑑𝜆2
𝑑𝜆1 𝑑𝜆2 𝑑𝑥 𝑑𝑦 𝑑𝑧 𝐿′′𝑥𝜆1 𝐿′′𝑥𝜆2 𝐿′′𝑥𝑥 𝐿′′𝑥𝑦 𝐿′′𝑥𝑧 𝑑𝑥
𝐿′′𝑦𝜆1 𝐿′′𝑦𝜆2 𝐿′′𝑦𝑥 𝐿′′𝑦𝑦 𝐿′′𝑦𝑧 𝑑𝑦
𝐿′′𝑧𝜆1 𝐿′′𝑧𝜆2 𝐿′′𝑧𝑥 𝐿′′𝑧𝑦 𝐿′′𝑧𝑧 𝑑𝑧
Interpretación del multiplicador Lagrangeano para funciones con n variables independientes y m restricciones
Paso 1 – Identificar los componentes de la función a optimizar
Función objetivo: f ( x1 , x2 ,………,xn) Se tiene n variables independientes
Restricciones : g1( x1, x2,……..,xn)= c1
……………………………….
Se tiene m restricciones
gm(x1,x2,……….,xn)= cm
C1 a cm son constantes, que corresponden
a las restricciones de 1 a m
Paso 2 –Armar el lagrangiano “Z” e identificar sus componentes
El lagrangiano queda en Función objetivo Se agrega la suma de 1 a m términos, ya
función de cada variable que se tiene m restricciones.
independiente y cada Cada termino se compone de una
(variables accesorias), variable accesoria multiplicando a cada
se tendrá un por cada restricción (notar que las restricciones se
restricción, o sea “m”) expresan: “c – g(x1,x2…,xn)”
Paso 3- Plantear las condiciones de primer orden
Se obtiene un sistema de ”n +m” ecuaciones ,ya que se tiene n variables independientes y m terminos ( (c – g(x1,…xn))
Paso 4- Se verifican las condiciones de segundo orden , lo que define implícitamente:
Paso 5 - Armar la función valor
Se sustituye lo obtenido de las
CPO y CSO
En el lagrangiano
¡¡¡¡función valor máximo !!!!
Función valor función objetivo valuada en el óptimo
Paso 6- Diferenciar la función valor con respecto a “c”
Distribuyo
Reexpreso como reordeno
suma
Reordeno y obtengo
= 0 (por las cpo) = 0 (por las cpo)
Paso 7- Simplificar la expresión y sacar concluciones
𝜆∗ mide la variación del valor maximo de la funcion objetivo cuando se relajan las restricciones
Notar que ”c” ,interviene en el problema , a travez de las restricciones , pues no es argumento
de la función objetivo
”O sea , un valor de 𝜆∗ alto dice que un
pequeño cambio en la restricción da un
alto cambio en la función objetivo y
viceversa”
Ejemplo:
Dado el siguiente problema interpretar analíticamente el multiplicador lagrangeano
Paso 1- Armar la función Lagrangeana
Paso 2- Plantear las condiciones de primer orden (necesarias)
Paso 3 – Verificar las condiciones suficientes de 2 orden
Condición suficiente para máximo de L: que alternen de signo
los menores principales directores orlados, siendo el signo de
ഥ𝑚+1 igual al de (−1)𝑚+1
𝐻
Condición suficiente para mínimo de L: que los menores
principales directores orlados tomen todos el signo de (−1)𝑚
(si el número de restricciones es par, todos los determinantes
deberán ser positivos para un mínimo mientras que, si es
impar, negativos).
Si se verifican las condiciones suficientes, se puede definir:
Paso 4- se reemplazan los valores óptimos en la función lagrangiana y se obtiene así la función
valor maximo o función objetivo indirecta:
Paso 5 – se diferencia todo en función de U, y se deduce algebraicamente
Decimos entonces que λ*∗ indica como varía la función objetivo
valuada en el punto óptimo, habiendo relajado la restricción,
ante un cambio en el parámetro U .̄
