2014 S1 Examen

ING200 Optimizaci´on
Examen
Prof. G. Canessa, R. Carrasco, A. Cubillos, E. Moreno, O. Rivera & W. Yushimito
Primer Semestre, 10 de julio de 2014

Nombre:

Instrucciones:
1. Usted tiene 2 horas para hacer el examen.
2. La prueba tiene 4 preguntas, con un total de 60 puntos.
3. No hay consultas durante la prueba. Si hay algo que usted considera que falta, haga un
supuesto razonable e ind´ıquelocl´aramente en su respuesta.
4. El examen es sin apuntes, libros, ni computadores. S´olo est´an permitidas calculadoras no
programables.
5. Si realiza esta prueba con l´
apiz mina no tiene derecho a revisi´on.
6. Conteste las preguntas s´
olo en el espacio entregado para ello. Sea conciso.
Importante: Copie y firme el siguiente c´odigo de honor y entr´eguelo junto a sus respuestas.
Prometo, por mihonor, que no entregar´e o solicitar´e ayuda durante la realizaci´
on de esta prueba.

Firma
El alumno que sea sorprendido usando o intentando usar procedimientos il´ıcitos durante el
desarrollo de interrogaciones o en la realizaci´on de trabajos, al menos ser´a calificado con la nota
m´ınima (1.0) en dicha interrogaci´
on o trabajo y su caso ser´a enviado a la direcci´on de la Universidad.b.1407111307

1

ING200 Optimizaci´
on

Examen

[15 pts.] 1. Problema de Modelamiento

[15 pts.]

El Profesor Carrasco acaba de cambiarse de casa. En su nuevo lugar, los cajones de los roperos
tienen un tama˜
no diferente al que ten´ıan en su casa anterior, por lo que tiene que volver a
decidir como doblar sus s´
abanas para que quepan en los nuevos cajones.
Cada s´abana es de s1 por s2 metros y elprofesor prefiere doblar sus s´abanas ya sea por la mitad
(un solo doblez) o en tercios (dos dobleces) cada vez. Esto lo hace en repetidas ocasiones, tanto
vertical como horizontalmente hasta asegurar que la s´
abana doblada quepa en el caj´
on. Los
cajones, por su parte, son de c1 por c2 cent´ımetros.
El profesor tiene otras dos restricciones adicionales:
• Debido a lo dif´ıcil que se vuelve seguirdoblando una s´abana tras doblarla en tercios, el
profesor decidi´o hacer esta operaci´on a lo m´
as dos veces, contando las veces que lo hace
tanto horizontal como verticalmente.
• Al profesor le gusta ir alternando los dobleces horizontales y verticales. Para que esto sea
factible en la soluci´
on final, la cantidad total de operaciones hechas en forma horizontal y
vertical no pueden diferir enm´as de 1.
Escriba un modelo que le permita, al profesor, identificar de qu´e forma doblar sus s´
abanas
minimizando el n´
umero de dobleces que tiene que hacer, de forma que quepa en el caj´on. Sea
detallado en explicar las variables, funci´on objetivo y restricciones. El problema no tiene por
qu´e ser lineal.
Soluci´
on:
Sea hd y ht la cantidad de dobleces por la mitad y en tercios,respectivamente, que se hagan en
forma horizontal. Similarmente, sea vd y vt la cantidad de dobleces por la mitad y en tercios
hechos verticalmente.
Usando estas variables la funci´
on objetivo es entonces:
min

hd ,ht ,vd ,vt

hd + 2ht + vd + 2vt ,

sujeto a las siguientes restricciones:
1. A lo m´
as pueden hacerse dos dobleces en tercios:
ht + vt ≤ 2.
2. La cantidad de operaciones horizontales y verticales nopueden diferir en m´as de 1:
| (hd + ht ) − (vd + vt ) |≤ 1.
3. La s´
abana doblada debe caber en el caj´on:
Esta es la restricci´
on m´
as complicada. Uno podr´ıa pensar que basta con asegurar que
100s1
100s2
≤ c1 y v vt ≤ c2 ,
2 d3
2hd 3ht

P´agina 2 de 7

ING200 Optimizaci´
on

Examen

pero esto asume que uno puede poner la s´abana s´olo en esta posici´on, lo que est´a mal pues
uno puederotarla 90 grados para probar de esa forma. Para agregar esta opci´on creamos
una variable auxiliar
y=

1 si se pone la parte horizontal de la sabana con la horizontal del cajon
0 si no

Con esta variable, la restricci´
on entonces queda como
100s1
≤ yc1 + (1 − y)c2 ,
2hd 3ht
y
100s2
≤ (1 − y)c1 + yc2 .
2vd 3vt
4. Hay variables enteras y binarias:
y ∈ {0, 1},
y
hd , ht , vd , vt ∈ Z+ .
2....