Matemáticas para Economistas (1º GE)Universidad de Cantabria
BLOQUE TEMÁTICO III:
Programación Clásica, No Lineal y Lineal
Matemáticas para Economistas1º GE Universidad de Cantabria
Matemáticas para Economistas (1º GE)Universidad de Cantabria
Tema 5: Programación Clásica
Tema 6: Programación No Lineal
Tema 7: Programación Lineal
Matemáticas para Economistas1º GE Universidad de Cantabria
Matemáticas para Economistas (1º GE)Universidad de Cantabria
Tema 5: Programación Clásica
5.1 Planteamiento general
5.2 Programación clásica sin restricciones
5.3 Programación clásica con restricciones: El método de los
multiplicadores de Lagrange
Matemáticas para Economistas1º GE Universidad de Cantabria
5.1 Planteamiento general
La programación clásica abarca dos tipos de programas de optimización matemática:
Programación sin restricciones (o libre)
Programación con restricciones (o restringida/condicionada)
𝑺𝑺 = 𝑫𝑫⋂𝑿𝑿 = (𝒙𝒙𝟏𝟏, … ,𝒙𝒙𝒏𝒏) ⊂ 𝑫𝑫 𝒇𝒇 𝒈𝒈𝒊𝒊(𝒙𝒙𝟏𝟏, … ,𝒙𝒙𝒏𝒏 = 𝒃𝒃𝒊𝒊, 𝒊𝒊 = 𝟏𝟏, … ,𝒎𝒎
Matemáticas para Economistas (1º GE)Universidad de Cantabria
PASOS PARA SU RESOLUCIÓN:
1º OBTENCIÓN DE PUNTOS CRÍTICOS E IDENTIFICACIÓN DE AQUELLOS
QUE SON ÓPTIMOS LOCALES
A) Condición Necesaria (de Óptimo Local) de 1º Orden
B) Condición Suficiente (de Óptimo Local) de 2º Orden
C) Teorema Local-Global (Tema 4)
Puntos críticos
Puntos críticos que son óptimos
locales
2º IDENTIFICACIÓN DE ÓPTIMOS LOCALES QUE SON GLOBALES
5.2 Programación clásica sin restricciones
Matemáticas para Economistas1º GE Universidad de Cantabria
A) Condición Necesaria de óptimo local de 1º Orden:
• El punto es un PUNTO CRÍTICO si:
Observaciones:
Que se anule el vector gradiente es una CONDICIÓN NECESARIA, que no suficiente,
de ÓPTIMO LOCAL: Pueden existir puntos para los cuales se anule el vector gradiente y
que no sean óptimos locales:
Aquellos puntos donde el vector gradiente no se anule no pueden ser óptimo locales.
- MÁXIMO LOCAL
- MÍNIMO LOCAL
- PUNTO DE SILLA
• Criterio basado en las derivadas parciales (de 1º orden) que permite identificar
los llamados PUNTOS CRÍTICOS.
Ejemplo:
La función toma valores mayores que cero en puntos
arbitrariamente cercanos al origen.
La función toma valores menores que cero en puntos
arbitrariamente cercanos al origen.
Conclusión: El punto (0,0) es un punto de silla, esto es, un punto crítico que no es
óptimo local.
Matemáticas para Economistas (1º GE)Universidad de Cantabria
PASOS PARA SU RESOLUCIÓN:
1º OBTENCIÓN DE PUNTOS CRÍTICOS E IDENTIFICACIÓN DE AQUELLOS
QUE SON ÓPTIMOS LOCALES
A) Condición Necesaria (de Óptimo Local) de 1º Orden
B) Condición Suficiente (de Óptimo Local) de 2º Orden
C) Teorema Local-Global (Tema 4)
Puntos críticos
Puntos críticos que son óptimos
locales
2º IDENTIFICACIÓN DE ÓPTIMOS LOCALES QUE SON GLOBALES
5.2 Programación clásica sin restricciones
Matemáticas para Economistas1º GE Universidad de Cantabria
B) Condición Suficiente de óptimo local de 2º orden:
Criterio basado en derivadas parciales de 2º orden (Matriz Hessiana) que permite
clasificar los puntos críticos en máximos locales, mínimos locales o puntos de silla.
Matemáticas para Economistas1º GE Universidad de Cantabria
Matemáticas para Economistas1º GE Universidad de Cantabria
Matemáticas para Economistas1º GE Universidad de Cantabria
Matemáticas para Economistas (1º GE)Universidad de Cantabria
• En aquellos casos en que no tengamos certeza de si un punto x* es mín/máx. o un punto
de silla (H es la matriz nula, H es semidefinida +, H es semidefinida – ), analizaremos
el VALOR DE LA FUNCIÓN EN EL ENTORNO DE DICHO PUNTO.
• Si en dicho entorno la función toma:
Valores mayores que en x* en unos casos y menores en otros, dicho punto será
PUNTO DE SILLA.
Valores mayores que en x*, dicho punto será un MÍNIMO LOCAL.
Valores menores que en x*, dicho punto será un MÁXIMO LOCAL.
Ejemplo:
Matemáticas para Economistas1º GE Universidad de Cantabria
C) TEOREMA LOCAL-GLOBAL (Condición Suficiente de Óptimo Global)
f es ESTRICTAMENTE CONVEXA
S es CONVEXO
f es CONVEXA
S es CONVEXO
f es ESTRICTAMENTE CÓNCAVA
S es CONVEXO
f es CÓNCAVA
S es CONVEXO
MÍNIMO GLOBAL ESTRICTO
MÍNIMO GLOBAL
MÁXIMO GLOBAL ESTRICTO
MÁXIMO GLOBAL
Matemáticas para Economistas (1º GE)Universidad de Cantabria
Matemáticas para Economistas1º GE Universidad de Cantabria
5.3 Programación clásica con restricciones: El método de
los multiplicadores de Lagrange
En Economía, muchos problemas de optimización están sujetos a restricciones (Ej.
restricciones presupuestarias, recursos limitados, etc.).
Si las restricciones son de igualdad, se tiene un problema de optimización clásico con
restricciones:
Interpretación geométrica: Caso de dos variables y una restricción
de igualdad
• La solución del programa matemático sin restringir sería (0,0).
B
• Si restringimos el programa, el mínimo se situaría en el punto B (1/2,1/2).
Valor óptimo de la función objetivo si no hubiéramos impuesto restricciones:
Valor óptimo de la función objetivo con restricción:
Al imponer restricciones el valor óptimo de la función objetivo
empeora:
Matemáticas para Economistas (1º GE)Universidad de Cantabria
Matemáticas para Economistas1º GE Universidad de Cantabria
Método de resolución: Método de los Multiplicadores de Lagrange
1º Construir la FUNCIÓN DE LAGRANGE o FUNCIÓN LAGRANGIANA
donde son los llamados multiplicadores de Lagrange.
2º Aplicar CONDICIÓN NECESARIA DE ÓPTIMO LOCAL DE 1º ORDEN a la función
Lagrangiana
- MAX. LOCAL- MÍN. LOCAL- PUNTO SILLA
3º CONDICIÓN SUFICIENTE DE ÓPTIMO LOCAL DE 2º ORDEN:
Matemáticas para Economistas1º GE Universidad de Cantabria
Observación: Si las restricciones son lineales, entonces:
Calcular la llamada matriz Hessiana reducida de la Lagrangiana:
que contiene las derivadas parciales de segundo orden de la función de Lagrangesólo con respecto a las variables de decisión (no respecto a los multiplicadores). Su dimensión será, por tanto,
𝒙𝒙∗ 𝒆𝒆𝒆𝒆 𝑴𝑴𝑴𝑴𝑴𝑴𝑴𝑴𝑴𝑴𝑴 𝑳𝑳𝑴𝑴𝑳𝑳𝑳𝑳𝑳𝑳
4º Aplicar TEOREMA LOCAL-GLOBAL
En el caso de que la Hessiana reducida sea SEMIDEFINIDA +, SEMIDEFINIDA –
o INDEFINIDA la condición Suficiente de 2º orden será:
• En el resto de casos será PUNTO DE SILLA.
• Si (h≠0) en el subespacio de vectores
𝑯𝑯 = 𝒉𝒉 ∈ ℝ𝒏𝒏 𝛁𝛁𝒈𝒈𝒊𝒊(𝒙𝒙∗ � 𝒉𝒉 = 𝟎𝟎, 𝒊𝒊 = 𝟏𝟏, … ,𝒎𝒎
𝒉𝒉𝑻𝑻 � 𝑯𝑯𝑿𝑿𝑳𝑳 𝒙𝒙∗,𝝀𝝀∗ � 𝒉𝒉 > 𝟎𝟎
entonces
• Si (h≠0) en el subespacio de vectores
entonces
𝒙𝒙∗ 𝒆𝒆𝒆𝒆 𝑴𝑴𝑴𝑿𝑿𝑴𝑴𝑴𝑴𝑴𝑴 𝑳𝑳𝑴𝑴𝑳𝑳𝑳𝑳𝑳𝑳
𝑯𝑯 = 𝒉𝒉 ∈ ℝ𝒏𝒏 𝛁𝛁𝒈𝒈𝒊𝒊(𝒙𝒙∗ � 𝒉𝒉 = 𝟎𝟎, 𝒊𝒊 = 𝟏𝟏, … ,𝒎𝒎
𝒉𝒉𝑻𝑻 � 𝑯𝑯𝑿𝑿𝑳𝑳 𝒙𝒙∗,𝝀𝝀∗ � 𝒉𝒉 < 𝟎𝟎
PRODUCTO ESCALAR!!
Interpretación económica de los multiplicadores de Lagrange
Consideremos el siguiente problema de optimización:
Al aplicar el método de los multiplicadores de Lagrange, tanto la solución óptima
como el valor óptimo de la función dependen de :
Matemáticas para Economistas (1º GE)Universidad de Cantabria
Matemáticas para Economistas1º GE Universidad de Cantabria
Cuando en un problema de optimización se imponen restricciones nos exponemos a
que el valor óptimo de la función objetivo como consecuencia de S es un conjunto más
reducido. Este problema se ve agravado cuando las restricciones son de igualdad.
¿Cómo se podrían variar los términos independientes de las restricciones para
mejorar el valor de la función objetivo?
Supongamos un incremento muy pequeño en el término independiente , tal que:
Matemáticas para Economistas (1º GE)Universidad de Cantabria
Matemáticas para Economistas1º GE Universidad de Cantabria
Bajo ciertas condiciones de regularidad se cumple:
Los multiplicadores de Lagrange miden la variación que experimenta el valor óptimo
de la función objetivo ante cambios en la disponibilidad de ciertos recursos. En
un problema de maximización con multiplicador positivo la función objetivo mejorará si
aumentamos el término independiente, mientras que con multiplicador negativo dicho
valor disminuirá.
Los multiplicadores de Lagrange miden el coste de mejorar el valor óptimo de la
función, actuando, por tanto, como un sistema de precios. En Economía los
multiplicadores de Lagrange reciben el nombre de PRECIOS SOMBRA o VALOR MARGINAL
DE UNA UNIDAD DEL RECURSO k.
De acuerdo con la expresión anterior, el incremento que experimenta la función
objetivo con unidades adicionales de un determinado recurso es:
Matemáticas para Economistas (1º GE)Universidad de Cantabria
Tema 5:
Programación Clásica
Matemáticas para Economistas1º GE Universidad de Cantabria