Scribd
Cargar
1K vistas5 páginas

Las Condiciones KKT

Las condiciones KKT son condiciones necesarias y suficientes para que la solución de un problema de optimización sea óptima. Proporcionan un criterio de parada para algoritmos de optimización y permiten determinar si se ha alcanzado un óptimo local restringido. El documento explica las condiciones KKT, incluida la condición estacionaria, de factibilidad, de holgura y de signo, y provee un ejemplo de su aplicación para maximizar beneficios sujetos a una restricción de producción.

Cargado por

eliad5000
Derechos de autor
© © All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como DOCX, PDF, TXT o lee en línea desde Scribd
1K vistas5 páginas

Las Condiciones KKT

Las condiciones KKT son condiciones necesarias y suficientes para que la solución de un problema de optimización sea óptima. Proporcionan un criterio de parada para algoritmos de optimización y permiten determinar si se ha alcanzado un óptimo local restringido. El documento explica las condiciones KKT, incluida la condición estacionaria, de factibilidad, de holgura y de signo, y provee un ejemplo de su aplicación para maximizar beneficios sujetos a una restricción de producción.

Cargado por

eliad5000
Derechos de autor
© © All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como DOCX, PDF, TXT o lee en línea desde Scribd

Las condiciones KKT, algoritmo y un ejemplo:

Las condiciones de Karush-Kuhn-Tucker (tambin conocidas como las


condiciones KKT o Kuhn-Tucker) son condiciones necesarias y suficientes para
que la solucin de un problema de programacin sea ptima. Se dice que esta
condicin es una generalizacin del mtodo de los multiplicadores de LaGrange.

Las condiciones de Karush-kuhn-Tucker constituyen la base para el desarrollo de


muchos algoritmos computacionales y proporcionan un criterio de parada para
muchos otros, permitiendo establecer cuando ha sido alcanzado un ptimo local
restringido. En los problemas diferenciables de optimizacin no restringida la
condicin necesaria para que una solucin sea un mnimo local es que se anule el
gradiente. Por el contrario, esta propiedad no es cierta para problemas
diferenciables restringidos.

Consideremos el problema de optimizacin


Donde
f(x)= Es la funcin objetivo a minimizar.
gj(x)= Son las restricciones de desigualdad.
hi(x)= Son las restricciones de igualdad.
m y p= Son el nmero de restricciones de desigualdad e igualdad,
respectivamente.

[Link] estacionaria:

[Link] de factibilidad

[Link] de holgura:

4. Condicin de signo:
Una vez que se cumplen las condiciones anteriores el punto es de

Algunos problemas econmicos requieren condiciones de desigualdades, por


ejemplo, cuando se desea maximizar la utilidad sujeta a gastar no ms que x soles
o minimizar costos sujetos a producir no menos que x unidades de produccin.
Dado un problema de maximizacin sujeto a una restriccin de desigualdad con la
siguiente funcin objetivo cncava diferenciable:

As, la funcin Lagrangiana correspondiente ser:

Las condiciones suficientes y necesarias de primer orden para la maximizacin,


llamadas condiciones de Kuhn-Tucker son:

Donde las condiciones en (c) son llamadas condiciones complementarias,


significando que tanto x como f '(x) no pueden ser -simultneamente- cero. Puesto
que una funcin lineal es cncava y convexa, aunque no estrictamente cncava o
estrictamente convexa.
En las condiciones de Kuhn-Tucker la restriccin es siempre expresada como ms
grande o igual que cero. Esto significa que a diferencia de las restricciones de
igualdad que son establecidas igual a cero, el orden de la sustraccin es
importante en programacin cncava.
Para el mximo en F, una solucin interior (Figura a)
Para el mximo en G, una solucin de frontera (Figura b)
Para el mximo en H o J, ambas soluciones de frontera (Figura c)
Todas las posibilidades para un mximo en el primer cuadrante pueden ser
resumidas
como:
Los cuales son reconocibles como parte de las condiciones de Kuhn-Tucker. Notar
que tales condiciones automticamente excluyen un punto como K en (a) el cual
no es un mximo, porque f(K) > 0. Cabe mencionar que la expresin x f(x) = 0
significa que al menos una de las dos cantidades debe tomar el valor cero.
El problema entonces se reduce a probar las 8 diferentes posibilidades:

Normalmente, las posibilidades encerradas en el recuadro son las ms comunes.


Por ello, se sugiere que sean las primeras en ser probadas.

Ejemplo:
Maximizar la funcin de beneficio sujeto a una restriccin de produccin

Solucin.
Paso 1: Formamos la funcin Lagrangiana
Paso 2: Por las condiciones de Kuhn-Tucker

Paso 3: Se testean o revisan las condiciones de Kuhn-Tucke

Usando la Regla de Cramer donde:

También podría gustarte