Repaso P2-Solucion (1)

Esta es una vista previa del archivo. Inicie sesión para ver el archivo original

1 
 
Optimización 
Repaso Prueba 2 
Prof. Matías Rojas 
Problema 1 
 
Considere el siguiente problema de optimización: 
 
𝑀𝑖𝑛 𝑓(𝑥, 𝑦) = 10𝑥2 + 𝑦2 − 4𝑥𝑦 + 10𝑥 − 4𝑦 + 10 
 𝑠. 𝑎. 3𝑥 + 2𝑦 ≤ 20 
 𝑥, 𝑦 ≥ 0 
 
a) Señale el Largangiano y las condiciones de primer orden de este problema. 
b) Señale y enumere los posibles casos de solución de este problema. 
c) 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) 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: 
ℒ(𝑥, 𝑦, 𝜆) = 10𝑥2 + 𝑦2 − 4𝑥𝑦 + 10𝑥 − 4𝑦 + 10 + 𝜆(20 − 3𝑥 − 2𝑦) 
 
𝑥
𝜕ℒ
𝜕𝑥
= 𝑥(20𝑥 − 4𝑦 + 10 − 3𝜆) = 0 
𝜕ℒ
𝜕𝑥
= (20𝑥 − 4𝑦 + 10 − 3𝜆) ≥ 0 
𝑦
𝜕ℒ
𝜕𝑦
= 𝑦(2𝑦 − 4𝑥 − 4 − 2𝜆) = 0 
𝜕ℒ
𝜕𝑦
= (2𝑦 − 4𝑥 − 4 − 2𝜆) ≥ 0 
𝜆
𝜕ℒ
𝜕𝜆
= 𝜆(20 − 3𝑥 − 2𝑦) = 0 
𝜕ℒ
𝜕𝜆
= (20 − 3𝑥 − 2𝑦) ≥ 0 
𝑥, 𝑦 ≥ 0 
𝜆 ≤ 0 
b) Tendremos 8 casos: 
Caso i) 𝑥 ≠ 0 𝑦 ≠ 0 𝜆 ≠ 0 
Caso ii) 𝑥 ≠ 0 𝑦 ≠ 0 𝜆 = 0 
Caso iii) 𝑥 ≠ 0 𝑦 = 0 𝜆 ≠ 0 
Caso iv) 𝑥 ≠ 0 𝑦 = 0 𝜆 = 0 
Caso v) 𝑥 = 0 𝑦 ≠ 0 𝜆 ≠ 0 
Caso vi) 𝑥 = 0 𝑦 ≠ 0 𝜆 = 0 
Caso vii) 𝑥 = 0 𝑦 = 0 𝜆 ≠ 0 
Caso viii) 𝑥 = 0 𝑦 = 0 𝜆 = 0 
2 
 
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) 
𝜕ℒ
𝜕𝑦
= (2𝑦 − 4 ∙ 0 − 4 − 2𝜆) = 0 
𝜕ℒ
𝜕𝜆
= (20 − 3 ∙ 0 − 2𝑦) = 0 
Resolviendo: 
𝑥 = 0 
𝑦 = 10 
𝜆 = 8 
 
Lo descartamos porque 𝜆 debe ser negativo. 
 
Vemos el caso vi) 
𝜕ℒ
𝜕𝑦
= (2𝑦 − 4 ∙ 0 − 4 − 2 ∙ 0) = 0 
𝑥 = 0 
𝑦 = 2 
𝜆 = 0 
 
Vemos que cumple con 
𝜕ℒ
𝜕𝑥
= (20𝑥 − 4𝑦 + 10 − 3𝜆) ≥ 0 
Y también con 
𝜕ℒ
𝜕𝜆
= (20 − 3𝑥 − 2𝑦) ≥ 0 
 
Luego tenemos un candidato a óptimo. 
 
Revisamos el caso vii) 
 
No cumple con la condición 
𝜆
𝜕ℒ
𝜕𝜆
= 𝜆(20 − 3𝑥 − 2𝑦) = 0 
Puesto que tendría que ocurrir que 𝜆 ∙ 20 = 0 con 𝜆 ≠ 0. 
 
Finalmente vemos el caso viii) 
 
Ese caso no cumple con 
𝜕ℒ
𝜕𝑦
= (2𝑦 − 4𝑥 − 4 − 2𝜆) ≥ 0 
 
 
Luego, el óptimo (mínimo) está en el punto: 
 
𝑥 = 0 
𝑦 = 2 
𝜆 = 0 
 
 
 
3 
 
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: 
𝑓(𝑥∗, 𝑦∗, 𝜆∗) + 𝜆∗ ∙ 5% ∙ 20 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
4 
 
Problema 2 
 
Usted es dueño del local Dolce al Cioccolato, 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. 
Dolce al Cioccolato 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 
x1 : Cantidad de kilos de chocolate Regular a producir y vender. 
x2: Cantidad de kilos de chocolate Extra Cacao a producir y vender. 
 
 𝑀𝑎𝑥 3.000𝑥1 + 5.000𝑥2 
 𝑠. 𝑎. 𝑥1 + 3𝑥2 ≤ 200 (𝑅1) 
 𝑥1 + 𝑥2 ≤ 100 (𝑅2) 
 𝑥1 ≥ 20 (𝑅3) 
 𝑥2 ≥ 10 (𝑅4) 
 𝑥1, 𝑥2 ≥ 0 
 
a) Grafique el dominio de este problema. 
 
b) 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) ¿Qué restricciones están activas? 
 
d) Escriba el Lagrangiano y las condiciones de optimalidad de KKT de este problema (no es necesario 
desarrollar las derivadas, sólo expresarlas). 
 
e) ¿Cuánto está dispuesto a pagar por disponer de una hora hombre adicional al día? 
 
f) ¿Cuánto está dispuesto a pagar por disponer de 1 ml de cacao líquido adicional al día? 
 
 
 
 
 
5 
 
 
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. 
 
𝑓(20,10) = 3.000 · 20 + 5.000 · 10 = $110.000 
𝑓(90,10) = 3.000 · 90 + 5.000 · 10 = $320.000 
𝑓(20,60) = 3.000 · 20 + 5.000 · 60 = $360.000 
𝑓(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. 
c) Están activas R1 y R2. 
 
d) 
ℒ(𝑥1, 𝑥2, 𝜆1, 𝜆2, 𝜆3, 𝜆4) = 
3.000𝑥1 + 5.000𝑥2 + 𝜆1(200 − 𝑥1 − 3𝑥2) + 𝜆2(100 − 𝑥1 − 𝑥2) + 𝜆3(20 − 𝑥1) + 𝜆4(10 − 𝑥2) 
Condiciones de KKT: 
𝑥𝑖
𝜕ℒ
𝜕𝑥𝑖
= 0 ∀𝑖 
𝜕ℒ
𝜕𝑥𝑖
≤ 0 ∀𝑖 𝑥𝑖 ≥ 0 ∀𝑖 
𝜆𝑗
𝜕ℒ
𝜕𝜆𝑗
= 0 ∀𝑗 = 1,2 
𝛿ℒ
𝜕𝜆𝑗
≥ 0 ∀𝑗 = 1,2 𝜆𝑗 ≥ 0 ∀𝑗 = 1,2 
𝜆𝑗
𝜕ℒ
𝜕𝜆𝑗
= 0 ∀𝑗 = 3,4 
𝛿ℒ
𝜕𝜆𝑗
≤ 0 ∀𝑗 = 3,4 𝜆𝑗 ≤ 0 ∀𝑗 = 3,4 
 
𝑥1 + 𝑥2 ≤ 100 
𝑥1 ≥ 20 
𝑥1 + 3𝑥2 ≤ 200 
𝑥2 ≥ 10 
6 
 
 
e) Ya sabemos, de la solución gráfica, que 𝜆3=𝜆4 = 0 y que 𝑥1, 𝑥2 ≠ 0 
Luego, 
𝑥1
𝜕ℒ
𝜕𝑥1
= 0 
𝑥1(3.000 − 𝜆1 − 𝜆2) = 0 
(3.000 − 𝜆1 − 𝜆2) = 0 
𝑥2
𝜕ℒ
𝜕𝑥2
= 0 
𝑥2(5.000 − 3𝜆1 − 𝜆2) = 0 
(5.000 − 3𝜆1 − 𝜆2) = 0 
 Luego, 𝜆1= 1.000 y 𝜆2=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. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
7 
 
 
Problema 3 
 
Un alumno de Ingeniería Comercial debe rendir exámenes en los cursos de Finanzas, Optimización, 
Estadística, Inglés y Teología. Para estudiar para estos cinco exámenes dispone de solamente 30 horas en 
total. La nota que puede obtener en un examen determinado dependerá del número de horas que dedique 
al estudio de ese curso, suponga que el alumno en caso de estudiar un ramo, le asigna un número entero 
de horas. Sea 𝑁𝑖𝑗 la nota que obtendrá en el curso i (i={1=Finanzas, 2=Optimización, 3=Estadística, 
4=Inglés y 5=Teología}) si le asigna j horas
de tiempo, con j = 0, 1, 2, 3,…, 29,…,30. Asuma que los 𝑁𝑖𝑗 son 
conocidos (datos). 
 
Para aprobar el curso de Finanzas necesita obtener al menos nota 3,8 en el examen, para aprobar el de 
Optimización, un 4,2 y para Estadística, un 3,1. Los otros dos cursos ya están pasados, es decir, los 
aprueba con cualquier nota en el examen. 
 
 Construya un modelo de optimización que permita determinar una asignación del tiempo óptima 
al estudiante para poder aprobar los 5 cursos, obteniendo la máxima suma de notas en los 
exámenes (puede resultarle más fácil usar notación de sumatorias). 
 
 
 
Solución 
 
Variables: 
Sea 𝑥𝑖𝑗 = 1 si se asignan j horas de estudio al curso i y 0 en caso contrario, con i={1=Finanzas, 
2=Optimización, 3=Estadística, 4=Inglés y 5=Teología } y j ={ 0, 1, 2, 3,…, 29,…,30} 
 
Función Objetivo: 
Nuestra función objetivo será la suma de todas las notas, es decir: 
𝑀𝑎𝑥 ∑ ∑ 𝑥𝑖𝑗𝑁𝑖𝑗
5
𝑖=1
30
𝑗=0
 
Restricciones: 
Todo ramo debe ser considerado con una sola asignación de horario (incluso si a alguno se le asigna 0 
horas de estudio) 
∑ 𝑥𝑖𝑗 = 1 ∀𝑖
30
𝑗=0
 
Debe aprobar Finanzas, Optimización y Estadística, luego: 
 
∑ 𝑥1𝑗𝑁1𝑗 ≥ 3,8
30
𝑗=0
 
∑ 𝑥2𝑗𝑁2𝑗 ≥ 4,2
30
𝑗=0
 
∑ 𝑥3𝑗𝑁3𝑗 ≥ 3,1
30
𝑗=0
 
Se dispone de sólo 30 horas para estudiar: 
 
∑ ∑ 𝑗 ∙ 𝑥𝑖𝑗
5
𝑖=1
30
𝑗=0
≤ 30 
 
Binarias: 
𝑥𝑖𝑗 𝑏𝑖𝑛𝑎𝑟𝑖𝑎 
 
8 
 
Problema 4 
Considere un restaurant que funciona las 24 horas del día los 7 días de la semana. Basado en su 
experiencia usted sabe que la dotación mínima de empleados por día de la semana que se necesita para 
operar el negocio es la siguiente: 
Día L M W J V S D 
Cantidad 14 13 15 16 19 18 11 
 
Cada empleado debe trabajar 5 días consecutivos y descansar los dos días siguientes, repitiendo este 
patrón de manera indefinida. 
a) Se le pide formular un modelo1 de optimización que permita minimizar la cantidad de empleados en 
el restaurant. 
 
 
Solución 
 
Como los empleados trabajan 5 días seguidos y descansan 2, tenemos 7 tipos de turnos posibles: 
Turnos Posibles: 
1) Trabaja L M W J V 
 
Descansa S D 
2) Trabaja M W J V S 
 
Descansa D L 
3) Trabaja W J V S D 
 
Descansa L M 
4) Trabaja J V S D L 
 
Descansa M W 
5) Trabaja V S D L M 
 
Descansa W J 
6) Trabaja S D L M W 
 
Descansa J V 
7) Trabaja D L M W J 
 
Descansa V S 
Así tenderemos: 
Sea 𝑥𝑖 la cantidad de personas que trabajan el turno i. 
𝑀𝑖𝑛 ∑ 𝑥𝑖
7
𝑖=1
 
𝑠. 𝑎. 𝑥1 + 𝑥4 + 𝑥5 + 𝑥6 + 𝑥7 ≥ 14 
 𝑥1 + 𝑥2 + 𝑥5 + 𝑥6 + 𝑥7 ≥ 13 
𝑥3 + 𝑥6 + 𝑥7 + 𝑥1 + 𝑥2 ≥ 15 
𝑥1 + 𝑥2 + 𝑥3 + 𝑥4 + 𝑥7 ≥ 16 
𝑥1 + 𝑥2 + 𝑥3 + 𝑥4 + 𝑥5 ≥ 19 
𝑥2 + 𝑥3 + 𝑥4 + 𝑥5 + 𝑥6 ≥ 18 
𝑥3 + 𝑥4 + 𝑥5 + 𝑥6 + 𝑥7 ≥ 11 
𝑥𝑖 ≥ 0 ∀𝑖 
 
 
1 Sea muy cuidadoso a la hora de definir sus variables.