1.
- ( 20 pts) La Compaña Air Condition construye aviones comerciales para varias líneas aéreas de
todo el mundo. La última etapa del proceso de producción consiste en fabricar las turbinas de jet
e instalarlas —una operación muy rápida— en la estructura del avión terminado. La compañía
tiene varios contratos de trabajo que la obligan a entregar un número considerable de aviones en
un futuro cercano y en este momento debe programar la producción de motores de turbina para
los próximos cuatro meses. En la segunda columna de la tabla siguiente se indica la cantidad de
motores que debe estar lista para su instalación a fin de cumplir con las fechas de entrega
contratadas. De ella se desprende que el número acumulado de motores que deben producirse al
final de los meses 1, 2, 3 y 4 debe ser por lo menos de 10, 25, 50 y 70 unidades,
respectivamente. Las instalaciones disponibles para producir las turbinas varían de acuerdo con
otros programas de producción, mantenimiento y renovación durante el periodo. Las diferencias
mensuales debidas al número máximo que se puede producir y el costo unitario de producción
(en millones de dólares) se presentan en la tercera y cuarta columnas de la tabla que se presenta
a continuación. Dadas las variaciones de los costos de producción, podría valer la pena fabricar
algunas turbinas uno o más meses antes de su fecha de instalación; en la actualidad se estudia
esta posibilidad. El inconveniente es que esas turbinas deberán almacenarse hasta que sean
instaladas, pues la estructura de los aviones no estará lista antes. El costo de almacenamiento de
cada turbina es de 15 mil dólares por mes —suma que incluye el interés sobre el capital
invertido—,1 como se muestra en la última columna de la tabla a continuación. El gerente de
producción quiere desarrollar la programación del número de turbinas que se deben fabricar en
cada uno de los cuatro meses, de manera que se minimicen los costos totales de producción y
almacenamiento. Suponga que las cantidades producidas deben ser enteros múltiplos de cinco.
Instalaciones Producció Costo Unitario Costo Unitario
Mes
Programadas n Máxima de Producción de Almacenaje *
1 10 25 1.08 0.015
2 15 35 1.11 0.015
3 35 30 1.10 0.015
4 20 10 1.13
* El costo está expresado en millones de dólares
Utilice Programación Dinámica para resolver el problema de programación de la producción
de la Compañía Air Condition.
a.- Defina y explique las variables de decisión
Nomenclatura:
n= número de estado
Sn= turbinas disponibles en el estado n
Xn= Cantidad a producir en el estado n
Ca= costo de almacenamiento en el estado n
Cp= costo de producción en el estado n.
xn= instalaciones programadas para el estado n
Variables de decisión:
Sn y Xn debido a que son valores que van a ir cambiando en cada estado. Sn es el mínimo que se debe
tener de turbinas para que al sumarlas con la cantidad de producción (Xn) del estado satisfaga las
instalaciones programadas para el estado n.
b.- Defina y explique los estados
Los estados que hay (Sn) son la cantidad de inventario que hay en el estado n. Esta cantidad tiene una
relación directa con el el número deseado de turbinas en cada mes y la cantidad a producir ese mes. Así
podemos relacionarlo con las siguientes etapas.
c.- ¿Cuántas etapas son?.
Son 4 etapas porque son 4 meses los que hay en el problema.
d. Defina y explique las etapas.
Las etapas que se ven este problema son los meses 1, 2, 3 y 4. En cada etapa se debe ir hallando las
soluciones óptimas que satisfagan las necesidades del mes siguiente. Pero lo resolvemos de atrás para
adelante y al final tomamos la decisión de cuál es la respuesta que nos beneficia de mejor manera.
e.- Escriba explícitamente la función recursiva para todas las etapas
Tenemos que saber que:
Costo de producción= Cp*Xn
Almacenamiento= Cantidad producida + inventario actual – instalaciones programadas
Costo almacenamiento= Ca*( Cantidad producida + inventario actual – instalaciones programadas)=
Ca*(Xn+Sn-xn)
Función recursiva:
Fn¿ ( Sn )=Min[Cp∗Xn+Ca∗( Xn+ Sn−xn ) + Fn +1¿ ( Xn+ Sn−xn)]
f.- Genere la tabla para la última etapa
n=4
F n+1¿ ( X 5+ S 5−x 5 )=0
F 4¿ ( S 4 )=Min[Cp∗X 4+Ca∗( X 4 +S 4−x 4 ) ]
A partir de ahora se divide las cantidades de turbinas para 5 para dejarla en sus múltiplos y se transforman
los valores de los costos con un factor de 5. S4 debe estar entre 2 y 4 ya que para satisfacer la cantidad de
instalaciones programadas debe haber mínimo de 2 múltiplos de 5 y se necesitan 4. D4 que es la cantidad a
producir en ese estado debe ser una cantidad que ayude a suplir las instalaciones programadas y esta
puede llegar hasta los 2 múltiplos ya que el mínimo de S4 es 2 y no pueden sumar más que 4 que es lo que
se necesita:
S4 D4 F4*(S4) D4(s4)
0 1 2
2 11,3 11,3 2
3 5,65 5,65 1
4 0 0
2.- ( 20 pts) La compañía aérea Gold Air construye jets pequeños que vende a corporaciones para uso
ejecutivo. Para cumplir con sus necesidades en ocasiones los clientes ordenan aviones con diseño
especial. Cuando es así, se incurre en un elevado costo de preparación para iniciar la producción de las
aeronaves. Gold Air acaba de recibir pedidos de tres clientes con fechas de entrega cercanas. Debido a
que las instalaciones de producción están comprometidas para cumplir contratos anteriores, no podrán
aceptar los tres pedidos. En consecuencia, debe decidirse el número de aviones que producirán (si lo
hacen) para cada uno de los tres clientes. Los datos relevantes se presentan en la siguiente tabla. El
costo de arranque representa los costos fijos para iniciar la producción de aviones de cada cliente. La
capacidad usada por avión son los porcentajes de capacidad de producción disponibles para cada avión.
El pedido máximo es el número máximo de aviones pedidos por cada cliente (aunque aceptarían
menos). La compañía Gold Air desea determinar cuántos aviones debe producir para cada cliente (si lo
hace) de modo que se maximice su ganancia total (ingresos netos menos costos fijos).
a. Formule un modelo con variables enteras y variables binarias para representar este
problema. Defina y explique las variables.
Solución:
x i=número de aviones a producir para el iésimo cliente
y i=es una bariable binaria que se activa si se construye un avión para el cliente1 o 2.
Función objetivo=Ganacias : Ingreso neto marginal−costo de arranque
Ganacia=2 x 1 +3 x2 +0,8 x 3−3 y 1−2 y 2
Restricciones:
x i ≤ M y i parai=1,2 siendo M un número muy grande
Capacidad = 0.2 x 1+0.4 x2 +0.2 x 3 ≤ 1
Pedidos máximos:
x1 ≤ 3
x2 ≤ 2
x3 ≤ 5
xi ≥ 0
y i Binaria
b. Use la computadora (Solver) para resolver el modelo e indique una interpretación de los
resultados. Suba el archivo de Excel con la resolución de esta parte del problema.
Así que se deben producir 2 aviones para el cliente 2 y 1 para el 3 con una ganancia de 4.8 millones.
3.- (20 pts) Considere el siguiente problema. Escriba las condiciones de KKT que le permita derivar una
solución óptima. Pruebe que (x, y) = (2, 0) es solución óptima
Max f(x, y) = 8x – x2 + 4y – y2
s.a x+y2
x 0, y 0
Las condiciones de KKT son:
m
∂f ∂g
1.
2. x ¿j (
−∑ ui i ≤ 0
∂ x j i=1 ∂ x j
∂f
m
∂g
−∑ ui i =0
∂ x j i=1 ∂ x j ) }en x=x ¿ , para j=1,2 , … , n
3. g i ( x ¿ )−bi ≤ 0
4. ui [ g i ( x ¿ )−bi ]=0 } para i=1,2 , … , m
¿
5. x j ≥ 0 para j=1,2 , … , n
6. ui ≥ 0 para i=1,2 , … ,m
Así que con F ( x , y ) =8 x−x 2+ 4 y− y 2
Tenemos:
∂f
=f x ( x , y )=8−2 x → g x ( x , y )=1
∂x
∂f
=f y ( x , y )=4−2 y → g y ( x , y )=1
∂y
Entonces aplicando las condiciones:
¿
1. 8−2 x ¿−u ≤ 0
{
4−2 y −u ≤ 0
¿ ¿
2. x¿ ( 8−2 x ¿−u )=0
{
y ( 4−2 y −u )=0
3. x¿ + y ¿−2≤ 0
4. u ( x ¿ + y ¿ −2 )=0
5. x¿ , y ¿ ≥ 0
6. u ≥0
Siendo x ¿ y y ¿ las soluciones óptimas. Ahora reemplazamos (2,0) para las condiciones:
1. 8−2 ( 2 )−u ≤ 0
{
4−2 ( 0 )−u ≤ 0
2. ( 2 ) ( 8−2 ( 2 )−u )=0
{
( 0 ) ( 4−2 ( 0 )−u ) =0
3. ( 2 )+ ( 0 )−2=2−2=0 ≤0
4. u ( ( 2 ) + ( 0 ) −2 )=u· 0=0
5. 2,0≥ 0
6. u ≥0
Y nos quedamos con las que aún no se cumplen porque tiene el valor u que debemos hallar:
1. 4−u ≤0
{
4−u ≤0
2. ( 8−2 u )=0
{ 0=0
6. u ≥0
Si despejamos u en la segunda que es una igualdad hallamos que u=4. Y al reemplazarlo se
cumplen todas las condiciones de KKT. Así que (2,0) si es una solución óptima.
4.- (10 pts) BONO Considere el siguiente problema de programación no lineal
Max f(x, y) = x + y
s.a x 2 + y2 1
x 0, y 0
a.- Verifique que se trata de un problema de programación convexa. Mostrar todos los pasos para
obtener crédito completo.
Para saber si es programación convexa necesitamos respetar las reglas de que la función debe ser
cóncava y sus restricciones deben ser funciones convexas. La función objetivo es lineal y sabemos que las
funciones lineales son tanto cóncavas como convexas. Por otro lado, la función de restricción es un circulo
de radio 1. Y un círculo es una función convexa así que se cumple todo para saber que si es un problema de
programación convexa
