Descarga la aplicación para disfrutar aún más
Vista previa del material en texto
1 Ejercicios de Clase KKT (Versión 0.3) Ejercicio 1 Considere el siguiente problema de optimización: * + a) Escriba las condiciones necesarias de primer orden para este problema. b) Encuentre todos los puntos que satisfacen las condiciones anteriores y el óptimo del problema. Universidad de los Andes Facultad de Ciencias Económicas y Empresariales Optimización 2 Solución: 3 4 La solución (1) no satisface la restricción de no-negatividad, por lo tanto se descarta. La solución (2) es el óptimo del problema. 5 Ejercicio 2 Una panadería ofrece, entre otros productos, empanadas de queso y dulce de membrillo. El panadero desea programar su producción dominical de ambos productos. La experiencia le ha enseñado que las demandas por ambos bienes se ajustan bastante bien a las relaciones: Donde el es el precio unitario de la empanada de queso, es el precio unitario del dulce de membrillo, y son las unidades demandadas en domingo, para empanadas de queso y dulce de membrillo respectivamente. Dentro de sus posibilidades de producción, el panadero sabe que el costo de producir una empanada de queso es $10 pesos y que puede comprar el dulce de membrillo a su proveedor a un precio de $15 pesos por unidad. Además, no puede vender diariamente más de 100 unidades de dulce de membrillo, por limitaciones del proveedor. a) Formule un modelo de optimización que permita al panadero programar su producción maximizando su beneficio derivado de la venta de ambos bienes. b) Sin exigir que las cantidades de los bienes sean enteras, resuelva el modelo y determine la producción óptima. c) ¿Qué desventaja tiene el no considerar los otros bienes que vende la panadería en el modelamiento? 6 Solución: 7 8 Ejercicio 3 Suponga que una empresa distribuidora cuenta con 250 unidades de un cierto producto en Concepción, 100 unidades en Los Ángeles y 325 unidades en Valparaíso. Por otra parte, debe abastecer con 140 unidades a Santiago, 220 unidades a Rancagua y 185 unidades a Teno. Los costos del flete entre las distintas ciudades, en miles de pesos por unidad, se presentan a continuación. Desde/Hacia Santiago Rancagua Teno Concepción 14 6 5 Los Ángeles 30 12 11 Valparaíso 5 7 8 Por convenios sindicales en Concepción, la empresa ha decidido que lo que se envía desde dicha ciudad a Santiago debe ser al menos el doble de lo que se envía desde dicha ciudad a Rancagua. Asimismo, en Santiago se exige que como máximo el 30% de lo que llegue provenga de Concepción. a) Plantee el problema de optimización correspondiente. b) ¿Cuántas restricciones pueden estar activas como máximo? c) ¿Qué representan los multiplicadores de KKT en cada restricción? 9 Solución: 10 Ejercicio 4 11 12 13 14 15 16 Ejercicio 5 Una empresa de lácteos quiere lanzar un nuevo tipo de leche al mercado. Dicho producto está dirigido a niños de entre 1 y 3 años de edad. Para la compañía no es tan complejo fabricar el nuevo tipo de leche ya que ésta se pueden elaborar a partir de la mezcla de cuatro tipos de leche que actualmente fabrica la compañía, estos tipos de leche son: Súper Calcio, Huesillos, Entera y Descremada. Los costos de elaboración, por litro de leche, para Súper Calcio, Huesillos, Entera y Descremada son de $95, $90, $60 y $77 respectivamente. Asuma que no hay costos adicionales en mezclar las leches. El nuevo tipo de leche, dado que está dirigido a niños pequeños, debe satisfacer exigentes requerimientos del Ministerio de Salud, donde se debe cumplir que en cada litro de leche debe haber al menos 1,15 gr de Calcio y 0,88 gr de Fósforo, así también, un litro de su mezcla no puede superar los 0,7 gr de Sodio ni los 15 gr de Grasa. Así también se le pide que por cada gramo de grasa haya al menos 0,02 gr de Calcio para que la leche esté más equilibrada. La cantidad de nutrientes que contiene cada tipo de leche se muestran en la tabla adjunta. Insumo Tipo de Leche Súper Calcio Huesillos Entera Descremada Calcio (g/litro) 1,28 1,00 1,18 1,12 Fósforo (g/litro) 1,03 0,90 0,85 0,68 Sodio (g/litro) 0,48 0,90 0,61 0,52 Grasa (g/litro) 20 17 31 1 a) Plantee el modelo que minimice el costo por litro. b) Plantee el Lagrangiano del problema. c) Escriba las condiciones que debe cumplir el óptimo (no es necesario que desarrolle las derivadas) Al resolver el problema se obtuvo lo siguiente: d) ¿Cuál es el costo de un litro de leche nueva? e) ¿Qué restricciones están activas? f) Interprete el significado económico de según el contexto del problema. g) Señale cómo cambiaría su costo por litro de leche nueva si el límite de cada uno de los nutrientes (Calcio, Fósforo, Sodio o Grasa), por separado, fuera 0,1 grs más que el actual (señale el cambio en el costo para esos cuatro escenarios mostrando si éste aumenta, disminuye o se mantiene y en cuánto lo hace). h) Si el Ministerio de Salud le permitiera modificar en 5% (en el sentido que usted quiera) cualquiera de los límites (Calcio, Fósforo, Sodio o Grasa). ¿Cuál escogería y por qué?¿En cuánto mejoraría el costo por litro de la leche nueva con esta situación? i) A usted que el Ministerio de Salud le ha dicho que por cada gramo de grasa debe haber al menos 0,02 gr de Calcio, suponga que le dicen que puede elegir si cumple con ese criterio o con otro que diga que por cada 0,85 gr de Sodio debe haber al menos 1 gr de Fósforo, al menos uno de esos dos criterios debe cumplirse. Señale los cambios que habría que hacerle al modelo de optimización del enunciado para que incorpore este nuevo cambio. El modelo matemático de este problema es el siguiente: 17 Solución: Sea la cantidad de leche tipo i en litros para hacer un litro de leche nueva, con i={1= Súper Calcio, 2=Huesillos, 3=Entera y 4=Descremada}. Función Objetivo R1: Calcio R2: Fósforo R3: Sodio R4: Grasa R5: Mezcla igual a 1 lt R6: Razón Calcio / Grasa1 No negatividad Tendremos: ( ) ( ) ( ) ( ) ( ) ( ) ( ) Las condiciones de primer orden serán: * + * + * + * + * + El costo por litro es de $83,45. Están activas las restricciones 2, 4, 5 y la no negatividad de . Corresponde a la tasa de cambio del costo nuevo de leche dada la situación óptima, si se aumenta el nivel exigido de Fósforo en una unidad, asumiendo el resto constante.1 La restricción 6 viene de la relación 18 Si aumenta 0,1 gr el nivel de un nutriente, el costo por litro cambia en: Calcio: no cambia Fósforo: aumenta en $11,87 Sodio: no cambia Grasa: disminuye en $0,12 Sabemos que no hay mejoras si movemos levemente los límites de Calcio y Sodio. Si bajamos el límite de Fósforo en 5% tendríamos un cambio en el costo por litro de: ( ) El costo disminuiría en $5,22. Si subimos el límite de Grasa en 5% tendríamos un cambio en el costo por litro de: ( ) El costo disminuiría en $0,93. Luego prefiero mover el nivel de fósforo ya que el costo mejora en $5,22 por litro. Sabemos que el criterio “Por cada gramo de grasa debe haber al menos 0,02 gr de Calcio” es: De la misma forma, el criterio “Por cada 0,85 gr de Sodio debe haber al menos 1 gr de Fósforo” es: Así agregamos dos variables binarias: Sea si se cumple el criterio Calcio/Grasa y 0 en caso contrario. Sea si se cumple el criterio Fósforo/Sodio y 0 en caso contrario. La función objetivo no cambia, la restricción 6 la cambiamos por: ( ) Y agregamos otra restricción: ( ) Finalmente para que al menos uno de los criterios se cumpla, agregamos la restricción: 19 Ejercicio 6 20 21 22 Ejercicio 7 Usted se encuentra trabajando en el departamento de desarrollo rural en el Ministerio de Desarrollo Social (MDS) y le han encargado el estudio para asignar presupuesto de una cartera de proyectos que incluye las siguientes dos iniciativas: Programa “Profesores para el Campo” que busca dar fomento en la capacitación de profesores de escuelas rulares y programa “Más libros para mi escuela” que busca fomentar la compra de libros para escuelas rurales. Luego de realizar una evaluación social de proyectos se ha determinado que el beneficio social para comunidades rurales de implementar estas dos iniciativas queda determinado por la siguiente expresión: ( ) Debido a que este programa espera postular a fondos concursables del Banco Mundial, esta entidad exige que para iniciativas de este tamaño que se concentran en la capacitación de profesores y compra de material educativo su índice de Herselov sea igual o superior a 80.000 puntos. Este índice se obtiene al multiplicar por un coeficiente ( ) el cuadrado del dinero en dólares por concepto de capacitación más la multiplicación lineal de la cantidad destinada a compra de material educativo por un coeficiente ( ). Por otra parte, estos programas están inmersos dentro de las políticas de desarrollo rural del MDS donde se establece que se debe invertir en programas relacionados a capacitar profesores una cantidad en dinero igual o superior a la que se invierte en programas de compra de material educativo. Finalmente, el Ministerio de Hacienda ha asignado un presupuesto total de US$ 2.000 (que ya incluye el financiamiento del Banco Mundial) a este conjunto de iniciativas y dado que se le ha asignado la categoría de alto impacto social, se establece que la totalidad del presupuesto asignado para estas dos iniciativas debe ejecutarse completamente y que cada una de las 2 iniciativas debe ser desarrollada. En base a lo anterior se pide lo siguiente: a. (2 puntos) Desarrolle un modelo de optimización que le permita maximizar el beneficio social de implementar estas 2 iniciativas cumpliendo con los requisitos tanto del Banco Mundial como del MDS y del Ministerio de Hacienda. b. (3 puntos) Grafique el dominio del problema de solución e identifique el punto de solución óptima. Considere en el eje horizontal la variable asociada al programa Profesores para el campo y en el eje vertical la variable asociada al programa Más libros para mi escuela. c. (1 punto) Escriba el Lagrangeano del Modelo de Solución d. (5 puntos) Escriba las Ecuaciones de Kuhn-Tucker del modelo de solución (Desarrolle las derivadas). e. (1 puntos) Determine los casos posibles del modelo de solución. f. (5 puntos) Analice los casos factibles Mediante análisis de KKT. g. (1 punto) Determine la solución óptima del problema en base al análisis de KKT elaborado en el punto anterior y evalúela función objetivo en el punto de solución óptima. 23 h. (2 puntos) Dado que se trata de un proyecto con alto impacto social determine cuál de las condiciones impuestas ya sea por el Banco Mundial, el MDS o el Ministerio de Hacienda tiene un mayor impacto en la función objetivo si es modificada, justifique matemáticamente su respuesta. Solución a. (2 puntos) Desarrolle un modelo de optimización que le permita maximizar el beneficio social de implementar estas 2 iniciativas cumpliendo con los requisitos tanto del Banco Mundial como del MDS y del Ministerio de Hacienda. Función Objetivo (0,25 ptos) , ( ) + Restricciones i) (0,5 pts) Índice de Herselov ii) (0,5 pts) Presupuesto MDS iii) (0,5 pts) Presupuesto de Hacienda iv) (0,25 pts) Ejecución de proyectos b. (3 puntos) Grafique el Dominio de la solución del problema (1 punto por cada restricción correctamente graficada El Dominio queda comprendido por el segmento punteado en Negro que va desde el punto A al punto B 24 c. (1 punto) Escriba el Lagrangeano del Modelo de Solución ( ) ( ) ( ) ( ) d. (5 puntos) Escriba las Ecuaciones de Kuhn-Tucker del modelo de solución (Desarrolle las derivadas). (0,5 puntos por cada ecuación de Kuhn-Tucker correcta) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) d. (1 puntos) Determine los casos posibles del modelo de solución. Debido a que se exige que tanto x como y sean ambos mayores que 0 por la condición de tener que realizar si o si cada una de las dos iniciativas, se descartan del análisis aquellos puntos don x e y son iguales a 0. (0,25 puntos por cada caso) Caso x y 1 >0 >0 <0 <0 2 >0 >0 <0 =0 3 >0 >0 =0 <0 4 >0 >0 =0 =0 e. (5 puntos) Analice los casos factibles. (1,25 puntos por cada caso bien analizado y bien verificado o rechazado) 25 Caso 1 ( ) ( ) ( ) ( ) ( ) } ( ) ( ) Dado que se tiene una contradicción en el análisis y que no es posible despejar los valores de por tener más variables que ecuaciones el caso N 1se considera indeterminado y se rechaza como candidato a solución óptima. También se acepta representación gráfica que muestre que las condiciones descritas en las EQ(7,8,9) no presentan punto de intersección único (Asignar 1,25 pts si un alumno demuestra eso y lo justifica con el gráfico). Caso 2 ( ) ( ) ( ) ( ) ( ) } ( ) ( ) ( ) ( ) ( ) ( ) ( ) 26 ( ) Verificación Caso 2 ( ) Debido a que el Caso 2 No Cumple con la condición de KKT , ya que se rechaza el caso 2 Caso 3 ( ) ( ) ( ) ( ) ( ) } ( ) ( )( ) ( ) ( ) ( ) ( ) Verificación Caso 3 ( ) Dado que se exige y el Caso 3 no cumple con todas las condiciones de Kuhn-Tucker y por ende se procede a rechazarlo. Caso 4 ( ) ( ) ( ) ( ) ( ) } 27 ( ) ( ) ( ) ( ) ( ) ( ) Verificación Caso 4 ( ) ( ) ( )( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) Debido a que el Caso 4 cumple con todas las condiciones de KKT, se propone como candidato a solución óptima f. (1 punto) Determine la solución óptima del problema en base al análisis de KKT elaborado en el punto anterior y evalúela función objetivo en el punto de solución óptima. Debido a que el Caso 4 fue el único que satisfizo todas las condiciones de Kuhn-Tucker es el punto de solución óptima. ( ) ( ) ( ) ( )( ) g. (2 puntos) Dado que se trata de un proyecto con alto impacto social determine cuál de las condiciones impuestas ya sea por el Banco Mundial, el MDS o el Ministerio de Hacienda tiene un mayor impacto en la función objetivo si es modificada, justifique matemáticamente su respuesta. 28 Debido a que en el Caso 4 los valores correspondientes a los precios sombra, es decir, las variaciones marginales de la función objetivo con respecto a los valores fijos 80.000, 0, 2.000 alcanzaron los valores de , se concluye que la mayor variación marginal de la función objetivo en el punto de solución óptima se logra al variar marginalmente la restricción asociada a presupuesto máximo del Ministerio de Hacienda, ya que el aumentar en 1 unidad marginal este presupuesto se espera una aumento de 23 unidades marginales en la función objetivo (1 punto). La variación marginal asociada a la restricción , Índice de Herselov presenta un valor de 0 lo cual hace insensible la variación de la función objetivo en el punto de optimalidad a cambios en el valor mínimo asignado puesto que no se encuentra en condición activa (0,5 puntos) Finalmente, la restricción asociada a , asignación de recursos de MDS, no presenta variación la Función Objetivo en el punto óptimo puesto que el valor de fue nulo, o bien la restricción no se encuentra en condición activa (0,5 puntos) 29 Problema 8 30 31 32 Problema 9 Considere el siguiente problema de optimización: ( ) a) (1 punto) Señale el Largangiano y las condiciones de primer orden de este problema. b) (1 punto) Señale y enumere los posibles casos de solución de este problema. c) (6 puntos) Usted sabe que está activa la no negatividad de x (x=0), ¿cuántos casos posibles hay en este escenario? Resuelva el problema (encuentre ) verificando cada uno de los casos. Suponga que la función ( ) corresponde a la función de costos de una empresa donde es la cantidad producida de un producto e la cantidad de otro, así también considere que la restricción significa que para la producción, el producto usa 3 unidades de materia prima y el sólo 2; siendo la disponibilidad máxima de materia prima de 20 unidades. d) (2 puntos) A la luz de lo anterior explique el significado económico de y señale cómo calcularía el valor de la función objetivo (sin resolver el problema nuevamente) si se dispusiera de un 5% menos de unidades de materia prima. Solución a) Tendremos: ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) 33 b) Tendremos 8 casos: Caso i) Caso ii) Caso iii) Caso iv) Caso v) Caso vi) Caso vii) Caso viii) c) Si está activa la no negatividad de x, nos quedan 4 casos. Revisamos los casos v), vi), vii) y viii) Vemos el caso v) ( ) ( ) Resolviendo: Lo descartamos porque debe sernegativo. Vemos el caso vi) ( ) Vemos que cumple con ( ) Y también con ( ) Luego tenemos un candidato a óptimo. Revisamos el caso vii) No cumple con la condición ( ) Puesto que tendría que ocurrir que con . 34 Finalmente vemos el caso viii) Ese caso no cumple con ( ) Luego, el óptimo (mínimo) está en el punto: d) corresponde a la tasa de cambio de la función de costos en el óptimo si se dispone de una unidad más de materia prima, asumiendo el resto constante. Considerando que el óptimo está en ( ) si se dispusiera de un 5% más de materia prima, tendríamos que el valor de la función objetivo en este caso sería de: ( ) 35 Problema 10 Usted es dueño de ICOM Foods, que se dedica a la producción de chocolates artesanales. Se producen dos tipos: Regular y Extra Cacao; los cuales difieren principalmente en el contenido de cacao líquido de la mezcla. Los chocolates de tipo Regular requieren de 1ml de Cacao líquido por kilo de chocolate, mientras que los Extra Cacao requieren de 3ml por kilo de chocolate, la fábrica puede disponer de 200 ml de cacao líquido por día. ICOM Foods tiene contrato con un par de tiendas y en total debe venderles al día al menos 20 kilos de chocolate Regular y 10 kilos de chocolate Extra Cacao; donde cada kilo de chocolate requiere de 1 hora hombre para su fabricación independiente del tipo, y la fábrica cuenta con 20 trabajadores que pueden trabajar hasta 5 horas al día. Considerando que el kilo de chocolate Regular tiene un beneficio unitario de $3.000 y que un kilo de chocolate Extra Cacao tiene un beneficio unitario de $5.000, se pide determinar la cantidad óptima a producir y vender para maximizar las utilidades diarias. El modelo de este problema es el siguiente: Variables : Cantidad de kilos de chocolate Regular a producir y vender. : Cantidad de kilos de chocolate Extra Cacao a producir y vender. ( ) ( ) ( ) ( ) a) (2 puntos) Grafique el dominio de este problema. b) (4 puntos) Resuelva el problema y señale cuántos kilos de cada tipo de chocolate se deben vender diariamente para maximizar la utilidad y señale también la utilidad diaria obtenida por la fábrica. c) (1 punto) ¿Qué restricciones están activas? d) (1 puntos) Escriba el Lagrangiano y las condiciones de optimalidad de KKT de este problema (no es necesario desarrollar las derivadas, sólo expresarlas). e) (1 punto) ¿Cuánto está dispuesto a pagar por disponer de una hora hombre adicional al día? f) (1 punto) ¿Cuánto está dispuesto a pagar por disponer de 1 ml de cacao líquido adicional al día? 36 Solución a) Tendremos: b) Dado que el problema es completamente lineal, sabemos que el óptimo estará en uno de los vértices, puesto que como las curvas de nivel son rectas, no puede haber una solución interior. f(20,10) =3.000 · 20 + 5.000 · 10 = $110.000 f(90,10) = 3.000 · 90 + 5.000 · 10 = $320.000 f(20,60) = 3.000 · 20 + 5.000 · 60 = $360.000 f(50,50) = 3.000 · 50 + 5.000 · 50 = $400.000 El óptimo está en vender 50 kilos de cada tipo de chocolate, lográndose una utilidad diaria de $400.000. 4 ptos (3 por procedimiento + 1 por resultado correcto; si se hizo con curvas de nivel también se considera correcto) c) Están activas R1 y R2. d) ( ) ( ) ( ) ( ) ( ) 𝑥 𝑥 𝑥 𝑥 𝑥 𝑥 37 Condiciones de KKT: e) Ya sabemos, de la solución gráfica, que = y que Luego, ( ) ( ) ( ) ( ) Luego, = 1.000 y =2.000. Por un ml adicional de cacao líquido pagaría como máximo $1.000 f) Por una hora hombre adicional pagaría como máximo $2.000. 38 Problema 11 IC Sports se dedica a la confección de ropa deportiva, considere que la empresa fabrica poleras y shorts, y que el precio de las poleras es de $10.000 por unidad, mientras que el precio de los shorts es de $7.000 por unidad. La compañía puede comprar un máximo de 500 m2 de tela a la semana para fabricar sus productos, considere que para hacer una polera se necesitan 3m2 de tela y que para hacer un short, se necesitan 2 m2. Asuma que el costo de la tela por m2 es de $1.000 Considere que la fábrica cuenta también con otros costos semanales de producción, los que quedan representados por la siguiente función (en pesos): ( ) Donde y son las cantidades producidas (en unidades semanales) de poleras y shorts respectivamente. a) (2 puntos) Elabore el modelo de optimización que le permita a la compañía maximizar sus utilidades diarias. b) (1 puntos) Determine el Lagrangiano, las condiciones de primer orden (no desarrolle las derivadas) y los casos posibles para este problema.2 c) (5 puntos) Usted sabe que la restricción de tela está activa ( ). Resuelva el modelo y señale los valores de y . Señale también ( ) (Su punto debe cumplir las condiciones de b)).3 d) (2 puntos) Sin resolver el modelo nuevamente, estime cómo quedaría el valor de la función objetivo en el óptimo si se dispusiera de 1 m2 adicional. e) (1 puntos) Sin resolver el modelo nuevamente, estime cómo quedaría el valor de la función objetivo en el óptimo si se dispusiera de 2 m2 de tela menos que el nivel original. 2 Las condiciones de primer orden para un problema de optimización con restricciones de desigualdad se conocen como condiciones de Karush Khun y Tucker (KKT), revise el apunte de optimización con restricciones de desigualdad y Apunte de KKT Generalizado para ver las condiciones de este problema. Se tendrán 8 casos, donde tanto como pueden ser iguales a cero o distintos de cero. 3 Use variables continuas. 39 Solución a) Tendremos que restar los costos unitarios de tela, luego 10.000-3.000=7.000 y del mismo modo, 7.000-2.000=5.000. Luego: ( ) (El enunciado originalmente decía maximizar utilidades diarias, en este caso se consideró semanal, si se toma diario la función objetivo se divide por 7, considerar también correcto ese caso) b) Tendremos ( ) ( ) * + * + * + Habrán8 casos posibles, 2 por cada variable ( ) y 2 por el ( ). Caso i) Caso ii) Caso iii) Caso iv) Caso v) Caso vi) Caso vii) Caso viii) 40 c) Como la restricción está activa, tenemos 4 casos a verificar, estos son los casos i), iii), v) y vii) Veamos el caso i) Resolvemos y obtenemos Ahora bien, la función objetivo es cuadrática y continua en todo su dominio, y como la solución encontrada cumple con no negatividad, sabemos que estamos en el óptimo, ya que si el problema no hubiese tenido restricción de no negatividad, hubiésemos llegado a la misma solución. La utilidad obtenida será de ( ) d) Mejoraría en $ , luego tendríamos $2.310.115,55. e) Hacemos .
Compartir