En programación matemática, las condiciones de Karush-Kuhn-Tucker (también conocidas como las condiciones KKT o Kuhn-Tucker) son condiciones necesarias y suficientes para que la solución de un problema de programación matemática séa óptima. Es una generalización del método de los Multiplicadores de Lagrange.
Optimización con restricciones de desigualdad:
las condiciones de kuhn-tucker
Muchos modelos en economía son, naturalmente,
formulados, como problemas de optimización con restricciones de desigualdad.
Muchos modelos en economía son, naturalmente,
formulados, como problemas de optimización con restricciones de desigualdad.
Consideremos, por ejemplo, el problema de la elección
del consumidor. No hay ninguna razón para insistir en que un consumidor pasa
toda su riqueza, por lo que su problema de optimización se formula con
restricciones de desigualdad:
x max u
(x) en p · x ≤ w y x ≥ 0.
Un enfoque para la solución de este problema comienza por determinar cuál de estas dos condiciones se cumple en una solución. En problemas más complejos, con más de una restricción, este enfoque no funciona bien. Consideremos, por ejemplo, un consumidor que se enfrenta a dos limitaciones (tal vez tiempo y dinero). Tres ejemplos se muestran en la figura siguiente, que debe convencer de que no podemos deducir de propiedades simples de u solo que de las limitaciones, en su caso, están satisfechos con la igualdad en una solución.
Se considera un problema de la forma
Máximo x f (x) en g j (x) ≤ c j para j = 1, ..., m,
Donde f y g j para j = 1, ..., m son funciones de n variables, x = (x 1, ..., x n), y c j para j 1, ..., m son constantes = .
Todos los problemas que hemos estudiado hasta ahora podrán ponerse en esta forma.
La igualdad de las limitaciones
Presentamos dos restricciones de desigualdad para cada restricción de igualdad. Por ejemplo, el problema
máximo x f (x) en h (x) = 0
se puede escribir como
máximo x f (x) en h (x) ≤ 0 y - h (x) ≤ 0.
Restricciones de no negatividad
Para un problema con una restricción k x ≥ 0 dejamos g j (x) = - x k y c j = 0 para algún j.
Minimización de los problemas
Por un problema de minimización se multiplica la función objetivo por -1:
min x h (x) en g j (x) ≤ c j para j = 1 ,..., m
es el mismo que
máximo x f (x) en g j (x) ≤ c j para j = 1 ,..., m,
donde f (x) = - h (x).
Para empezar a pensar en cómo resolver el problema general, en primer lugar de un asunto con una única restricción (m = 1). Podemos escribir un problema como
máximo x f (x) en g (x) ≤ c.
Hay dos posibilidades para la solución de este problema. En las siguientes figuras, las curvas cerradas negro son los contornos de f, los valores del aumento de la función en la dirección indicada por las flechas azules. La línea roja-pendiente hacia abajo es el conjunto de puntos x g satisface (x) = c, el conjunto de puntos x g satisface (x) se encuentran por debajo de c ≤ y el de la izquierda de la línea, y los que g satisface (x) ≥ c están por encima ya la derecha de la línea.
En cada panel de la solución del problema es el punto x *. En el panel izquierdo de la restricción se une a la solución: un cambio en los cambios de c la solución. En el panel de la derecha, la restricción es holgura en la solución: pequeños cambios en la letra c no tienen efecto en la solución.
al igual que antes, definir la función de Lagrange L por
L (x) = f (x) - λ (g (x) - c).
Luego de nuestro análisis anterior de los problemas con restricciones de igualdad y sin restricciones.
- si g (x *) = c (como en la mano izquierda) y la restricción satisface una condición de regularidad, a continuación L (x *) = 0 para todo lo que
- si g (x *) <c (como en el panel de la derecha-mano), entonces f i (x *) = 0 para todo i.
Ahora, me dicen que en el primer caso (es decir, si g (x *) = c) tenemos λ ≥ 0. Supongamos, por el contrario, que λ <0. Entonces se sabe que una pequeña disminución en la c eleva el valor máximo de f. Es decir, en movimiento * x dentro de la restricción aumenta el valor de f, lo que contradice el hecho de que x * es la solución del problema.
En el segundo caso, el valor de λ no entra en las condiciones, por lo que puede elegir cualquier valor para él. Teniendo en cuenta la interpretación de λ, el establecimiento de λ = 0 tiene sentido. Bajo este supuesto tenemos f i (x) = L 'i (x) para todo x, de modo que' i L (x *) = 0 para todo i.
Así, en ambos casos tenemos "i L (x *) = 0 para todo i, λ ≥ 0, y g (x *) ≤ c. En el primer caso tenemos g (x *) = c, y en el segundo caso λ = 0.
Podemos combinar los dos casos por escrito las condiciones que
L i '(x *) = 0 para j = 1, ..., n
λ ≥ 0, g (x *) ≤ c, y, o bien λ = 0 y g (x *) - c = 0.
Ahora, el producto de dos números es cero si y sólo si al menos uno de ellos es cero, por lo que alternativamente puede escribir estas condiciones,
L i '(x *) = 0 para j = 1, ..., n
λ ≥ 0, g (x *) ≤ c, y λ [g (x *) - c] = 0.
El argumento que han dado sugiere que si x * resuelve el problema y la restricción satisface una condición de regularidad, entonces x * debe cumplir estas condiciones.
Tenga en cuenta que las condiciones no se descarta la posibilidad de que tanto λ = 0 y g (x *) = c.
Las desigualdades λ ≥ 0 y g (x *) ≤ c se denominan condiciones de holgura complementaria, la mayoría en una de estas condiciones es floja (es decir, no una igualdad).
Por un problema con muchas limitaciones, a continuación, como antes se introduce un multiplicador para cada restricción y obtener la condiciones de Kuhn-Tucker, que se define de la siguiente manera.
Definición
Las condiciones de Kuhn-Tucker para el problema
máximo x f (x) en g j (x) ≤ c j para j = 1, ..., m
se
L i '(x)
= 0 para i = 1 ,..., n
0 λ ≥ j, j g (x) y c ≤ λ j j [j g (x) - c j]
= 0 para j = 1, ..., m,
donde
L (x) = f (x) - Σ j = 1 λ m j (j g (x) - c j).
Estas condiciones se nombran en honor de Harold W. Kuhn, miembro emérito del Departamento de Matemáticas de Princeton, y Albert W. Tucker , quien formuló por primera vez y estudió las condiciones.
En las siguientes secciones discutir los resultados que especifican la relación precisa entre las soluciones de las condiciones de Kuhn-Tucker y las soluciones del problema. El siguiente ejemplo ilustra la forma de las condiciones en un caso concreto.
Ejemplo
Considere el problema
máximo x 1, x 2 [- (x 1 - 4) 2 - (x 2 - 4) 2] con sujeción a x 1 + x 2 ≤ 4 y x 1 + 3 x 2 ≤ 9,
se ilustra en la siguiente figura.
Hemos
L (x 1, x 2) = - (x 1 - 4) 2 - (x 2 - 4) 2 - λ 1 (x 1 + x 2 - 4) - λ 2 (x 1 + 3 x 2 - 9) .
Las condiciones de Kuhn-Tucker son
2 (x 1 - 4) - λ 1 - λ 2
=
0
-2 (X 2 - 4) - λ 1 - 2 3λ
=
0
x 1 + x 2 ≤ 4, λ 1 ≥ 0 y λ 1 (x 1 + x 2 - 4)
=
0
x 1 + 3 x 2 ≤ 9, λ 2 ≥ 0, y λ 2 (x 1 + 3 x 2 - 9)
=
0.
por ultimo se explicara un breve resumen de los beneficios que trae la optimización a la toma de decisiones dentro de las organizaciones:
si bien para comenzar debemos saber que la optimización es el proceso de modificar un sistema para mejorar su eficiencia o también el uso de los recursos disponibles. una organización necesita de una buena optimizacion ya que se debe actualizar y mejoras a nivel productivo y de sus sistemas y así estar a la vanguardia tecnología y realizar los procesos de una forma eficiente y eficaz entre los procesos a optimizar en una organizacion estan:
- maximizar la tasa de producción
- minimizar el costo de operación
- maximizar la utilidad
- minimizar el desperdicio de información
- maximizar las ganancias
¿Porque se deben optimizar los procesos productivos de una organización?
La competitividad en los procesos organizacionales debe ser el objetivo principal a conseguir y para ello es necesario el control y la consideración de aspectos clave que nos permitan alcanzar una planificación ajustada a la producción. La producción ajustada nos debe permitir la utilización eficiente de los recursos reduciendo tiempos de preparación, minimizando errores, eliminando tiempos de espera logrando un flujo continuo en la línea, minimizando los transportes internos y evitando retrasos. Otro de los aspectos relevantes es la reducción de stock. Cabe destacar que la acumulación de inventarios supone un coste notable en la contabilidad de las empresas y conseguir aprovisionar lo que se va a manufacturar sin que ello suponga retrasos en la línea de producción es sin duda uno de los grandes retos.
El principal beneficio de un estudio de esta naturaleza es el incremento en eficiencia y la consecuente reducción en costos y/o aumento de las utilidades. Un beneficio indirecto, pero de gran trascendencia, es el mucho mejor entendimiento del sistema derivado del proceso de construcción del modelo de optimización.
Toma de decisiones organizacionales
En el proceso de toma de decisiones dentro de una empresa se pasa por distintas fases que suelen seguir un esquema similar a: recogida de información, fijación de objetivos, toma de la decisión, acción o ejecución de la decisión y, por último, retroalimentación o feedback, que nos permite controlar cómo están siendo los resultados que se están obteniendo con la acción ejecutada respecto a los objetivos fijados. dentro de la toma de decisiones surge la necesidad de optimizar estos procesos para así haber mejor entendimiento de la información y tener como resultado un mejoramiento continuo en la organización.
aplicación de la condiciones de kuhn-tucker
La toma de decisiones organizacionales, se fundamenta matemáticamente
el teorema de suficiencia de kuhn-tucker los problemas de restricción de
desigualdad pueden ajustarse mejor a situaciones reales, puede pensarse que una
restricción de igualdad significa agotar completamente cierto recurso. dentro de la solución de los problemas están:
- diagnostico del problema
- investigación u obtencion de informacion
- desarrollo de alternativas
- experimentación
- análisis de restricciones
- evaluación de alternativas
- formulación del plan
- ejecución y control
- fijación de objetivos
- objetivos que se contradicen
- jerarquía de objetivos horizonte de planeacion
para obtener mas información y ejercicios revisar el link:
x max u
(x) en p · x ≤ w y x ≥ 0.
En el carácter de la función
y los valores de u p y w, podemos tener p
x · w <dependiendo o p
· x = w a una solución de este problema.
Un enfoque para la solución de este problema comienza por determinar cuál de estas dos condiciones se cumple en una solución. En problemas más complejos, con más de una restricción, este enfoque no funciona bien. Consideremos, por ejemplo, un consumidor que se enfrenta a dos limitaciones (tal vez tiempo y dinero). Tres ejemplos se muestran en la figura siguiente, que debe convencer de que no podemos deducir de propiedades simples de u solo que de las limitaciones, en su caso, están satisfechos con la igualdad en una solución.
Se considera un problema de la forma
Máximo x f (x) en g j (x) ≤ c j para j = 1, ..., m,
Donde f y g j para j = 1, ..., m son funciones de n variables, x = (x 1, ..., x n), y c j para j 1, ..., m son constantes = .
Todos los problemas que hemos estudiado hasta ahora podrán ponerse en esta forma.
La igualdad de las limitaciones
Presentamos dos restricciones de desigualdad para cada restricción de igualdad. Por ejemplo, el problema
máximo x f (x) en h (x) = 0
se puede escribir como
máximo x f (x) en h (x) ≤ 0 y - h (x) ≤ 0.
Restricciones de no negatividad
Para un problema con una restricción k x ≥ 0 dejamos g j (x) = - x k y c j = 0 para algún j.
Minimización de los problemas
Por un problema de minimización se multiplica la función objetivo por -1:
min x h (x) en g j (x) ≤ c j para j = 1 ,..., m
es el mismo que
máximo x f (x) en g j (x) ≤ c j para j = 1 ,..., m,
donde f (x) = - h (x).
Para empezar a pensar en cómo resolver el problema general, en primer lugar de un asunto con una única restricción (m = 1). Podemos escribir un problema como
máximo x f (x) en g (x) ≤ c.
Hay dos posibilidades para la solución de este problema. En las siguientes figuras, las curvas cerradas negro son los contornos de f, los valores del aumento de la función en la dirección indicada por las flechas azules. La línea roja-pendiente hacia abajo es el conjunto de puntos x g satisface (x) = c, el conjunto de puntos x g satisface (x) se encuentran por debajo de c ≤ y el de la izquierda de la línea, y los que g satisface (x) ≥ c están por encima ya la derecha de la línea.
al igual que antes, definir la función de Lagrange L por
L (x) = f (x) - λ (g (x) - c).
Luego de nuestro análisis anterior de los problemas con restricciones de igualdad y sin restricciones.
- si g (x *) = c (como en la mano izquierda) y la restricción satisface una condición de regularidad, a continuación L (x *) = 0 para todo lo que
- si g (x *) <c (como en el panel de la derecha-mano), entonces f i (x *) = 0 para todo i.
Ahora, me dicen que en el primer caso (es decir, si g (x *) = c) tenemos λ ≥ 0. Supongamos, por el contrario, que λ <0. Entonces se sabe que una pequeña disminución en la c eleva el valor máximo de f. Es decir, en movimiento * x dentro de la restricción aumenta el valor de f, lo que contradice el hecho de que x * es la solución del problema.
En el segundo caso, el valor de λ no entra en las condiciones, por lo que puede elegir cualquier valor para él. Teniendo en cuenta la interpretación de λ, el establecimiento de λ = 0 tiene sentido. Bajo este supuesto tenemos f i (x) = L 'i (x) para todo x, de modo que' i L (x *) = 0 para todo i.
Así, en ambos casos tenemos "i L (x *) = 0 para todo i, λ ≥ 0, y g (x *) ≤ c. En el primer caso tenemos g (x *) = c, y en el segundo caso λ = 0.
Podemos combinar los dos casos por escrito las condiciones que
L i '(x *) = 0 para j = 1, ..., n
λ ≥ 0, g (x *) ≤ c, y, o bien λ = 0 y g (x *) - c = 0.
Ahora, el producto de dos números es cero si y sólo si al menos uno de ellos es cero, por lo que alternativamente puede escribir estas condiciones,
L i '(x *) = 0 para j = 1, ..., n
λ ≥ 0, g (x *) ≤ c, y λ [g (x *) - c] = 0.
El argumento que han dado sugiere que si x * resuelve el problema y la restricción satisface una condición de regularidad, entonces x * debe cumplir estas condiciones.
Tenga en cuenta que las condiciones no se descarta la posibilidad de que tanto λ = 0 y g (x *) = c.
Las desigualdades λ ≥ 0 y g (x *) ≤ c se denominan condiciones de holgura complementaria, la mayoría en una de estas condiciones es floja (es decir, no una igualdad).
Por un problema con muchas limitaciones, a continuación, como antes se introduce un multiplicador para cada restricción y obtener la condiciones de Kuhn-Tucker, que se define de la siguiente manera.
Definición
Las condiciones de Kuhn-Tucker para el problema
máximo x f (x) en g j (x) ≤ c j para j = 1, ..., m
se
L i '(x)
= 0 para i = 1 ,..., n
0 λ ≥ j, j g (x) y c ≤ λ j j [j g (x) - c j]
= 0 para j = 1, ..., m,
donde
L (x) = f (x) - Σ j = 1 λ m j (j g (x) - c j).
Estas condiciones se nombran en honor de Harold W. Kuhn, miembro emérito del Departamento de Matemáticas de Princeton, y Albert W. Tucker , quien formuló por primera vez y estudió las condiciones.
En las siguientes secciones discutir los resultados que especifican la relación precisa entre las soluciones de las condiciones de Kuhn-Tucker y las soluciones del problema. El siguiente ejemplo ilustra la forma de las condiciones en un caso concreto.
Ejemplo
Considere el problema
máximo x 1, x 2 [- (x 1 - 4) 2 - (x 2 - 4) 2] con sujeción a x 1 + x 2 ≤ 4 y x 1 + 3 x 2 ≤ 9,
se ilustra en la siguiente figura.
Hemos
L (x 1, x 2) = - (x 1 - 4) 2 - (x 2 - 4) 2 - λ 1 (x 1 + x 2 - 4) - λ 2 (x 1 + 3 x 2 - 9) .
Las condiciones de Kuhn-Tucker son
2 (x 1 - 4) - λ 1 - λ 2
=
0
-2 (X 2 - 4) - λ 1 - 2 3λ
=
0
x 1 + x 2 ≤ 4, λ 1 ≥ 0 y λ 1 (x 1 + x 2 - 4)
=
0
x 1 + 3 x 2 ≤ 9, λ 2 ≥ 0, y λ 2 (x 1 + 3 x 2 - 9)
=
0.
por ultimo se explicara un breve resumen de los beneficios que trae la optimización a la toma de decisiones dentro de las organizaciones:
si bien para comenzar debemos saber que la optimización es el proceso de modificar un sistema para mejorar su eficiencia o también el uso de los recursos disponibles. una organización necesita de una buena optimizacion ya que se debe actualizar y mejoras a nivel productivo y de sus sistemas y así estar a la vanguardia tecnología y realizar los procesos de una forma eficiente y eficaz entre los procesos a optimizar en una organizacion estan:
- maximizar la tasa de producción
- minimizar el costo de operación
- maximizar la utilidad
- minimizar el desperdicio de información
- maximizar las ganancias
¿Porque se deben optimizar los procesos productivos de una organización?
La competitividad en los procesos organizacionales debe ser el objetivo principal a conseguir y para ello es necesario el control y la consideración de aspectos clave que nos permitan alcanzar una planificación ajustada a la producción. La producción ajustada nos debe permitir la utilización eficiente de los recursos reduciendo tiempos de preparación, minimizando errores, eliminando tiempos de espera logrando un flujo continuo en la línea, minimizando los transportes internos y evitando retrasos. Otro de los aspectos relevantes es la reducción de stock. Cabe destacar que la acumulación de inventarios supone un coste notable en la contabilidad de las empresas y conseguir aprovisionar lo que se va a manufacturar sin que ello suponga retrasos en la línea de producción es sin duda uno de los grandes retos.
El principal beneficio de un estudio de esta naturaleza es el incremento en eficiencia y la consecuente reducción en costos y/o aumento de las utilidades. Un beneficio indirecto, pero de gran trascendencia, es el mucho mejor entendimiento del sistema derivado del proceso de construcción del modelo de optimización.
Toma de decisiones organizacionales
En el proceso de toma de decisiones dentro de una empresa se pasa por distintas fases que suelen seguir un esquema similar a: recogida de información, fijación de objetivos, toma de la decisión, acción o ejecución de la decisión y, por último, retroalimentación o feedback, que nos permite controlar cómo están siendo los resultados que se están obteniendo con la acción ejecutada respecto a los objetivos fijados. dentro de la toma de decisiones surge la necesidad de optimizar estos procesos para así haber mejor entendimiento de la información y tener como resultado un mejoramiento continuo en la organización.
aplicación de la condiciones de kuhn-tucker
La toma de decisiones organizacionales, se fundamenta matemáticamente
el teorema de suficiencia de kuhn-tucker los problemas de restricción de
desigualdad pueden ajustarse mejor a situaciones reales, puede pensarse que una
restricción de igualdad significa agotar completamente cierto recurso. dentro de la solución de los problemas están:
- diagnostico del problema
- investigación u obtencion de informacion
- desarrollo de alternativas
- experimentación
- análisis de restricciones
- evaluación de alternativas
- formulación del plan
- ejecución y control
- fijación de objetivos
- objetivos que se contradicen
- jerarquía de objetivos horizonte de planeacion
para obtener mas información y ejercicios revisar el link:
No hay comentarios:
Publicar un comentario