Preguntas Finales 1 2017

Vista previa del material en texto

PREGUNTAS TEÓRICAS DE FINALES
Final 1 – Clase Teórica 16
C1 ¿Es útil como cota para el problema de coloreo de grafos la resolución de la
relajación lineal (es decir, haciendo que todas las variables sean continuas)? ¿por qué?
En particular para el problema del coloreo de grafos no resulta útil la relajación lineal,
ya que la solución devuelta será siempre de 2 colores (utiliza la mitad de uno y la mitad
del otro para cada nodo).
C2 ¿Cuándo se dice que un problema está en NP? Un problema de programación lineal
continua ¿está en NP?
Un problema de decisión está en NP si una máquina de Turing no determinística puede
resolverlo en un tiempo polinomial. A su vez, una máquina determinística debería poder
verificar que una solución propuesta es válida en tiempo polinomial.
Un problema de programación lineal continua está en P. Ergo, está en NP.
Final 2 – 3/8/2017
C1 Es necesario resolver varios problemas del viajante, de 3, 4, 10, 30, 100 y 5000
ciudades respectivamente, ¿cómo encararía cada uno? ¿Lo haría en todos los casos de la
misma manera o en alguno/s lo haría diferente? ¿por qué?
Siempre va a depender de lo que priorice la persona que pretende resolver el problema:
una solución exacta sin importar el tiempo que demore o una solución aproximada en un
tiempo razonable.
Más allá de esto, yo encararía los problemas de hasta 30 ciudades con un modelo de
P.L.E, dado que al pasárselo a un software tipo GLPK o LINDO obtengo una solución
exacta en un tiempo dentro de todo razonable. En cambio, para los problemas de más de
30 ciudades aplicaría una heurística de construcción (vecino más próximo, por ej.) y
luego una de mejoramiento (K-Intercambios, por ej.), para así obtener una solución
aproximada pero en un tiempo más que razonable.
C2 Indique diferencias y similitudes entre el problema del viajante y el problema de
asignación cuadrática
El problema del viajante consiste en encontrar el orden en el cual un viajante debe
visitar todas las ciudades exactamente una vez y volver al origen, de manera tal que la
distancia total recorrida sea mínima.
El problema de la asignación cuadrática consiste en determinar qué fábricas se
instalarán en qué ciudades de manera tal que el costo total de comunicación entre las
fábricas sea mínimo. Dicho costo depende de la frecuencia de comunicación y la
distancia entre las fábricas.
Ambos problemas son NP-Hard y tienen importantes aplicaciones en situaciones
cotidianas de la realidad.
Algunas aplicaciones del problema del viajante son: recorrido de una persona por
distintas ciudades o lugares de manera tal que la distancia total sea mínima, fabricación
de circuitos electrónicos, proveer almuerzos calientes a personas incapacitadas para
caminar.
Algunas aplicaciones del problema de la asignación cuadrática son: disposición de
tiendas en los centros comerciales de manera tal que el público recorra lo menos
posible, diseño de terminales en aeropuertos de manera tal que aquellos que realizan un
trasbordo recorran lo menos posible, diseño de teclados de computadoras de manera tal
que el desplazamiento con los dedos sea el menor posible, diseño de circuitos eléctricos
de manera tal que se minimice la distancia entre ciertos chips.
Final 3 – 27/7/2017
C1 ¿Cuál fue el aporte del método del elipsoide para resolver modelos de programación
lineal continua?
El método del elipsoide da una forma teóricamente satisfactoria de reconocer si un
sistema de desigualdades tiene solución.
Este algoritmo no pudo ser aplicado en la práctica, pero tiene un gran valor teórico ya
que demuestra que la programación lineal está en P.
C2 Detalle los pasos a seguir para resolver un problema de programación lineal entera
utilizando planos de cortes Gomory (no es necesario indicar cómo se obtienen los
cortes)
Algoritmo de planos de corte Gomory:
1 – Se resuelve la relajación lineal del problema
2 – Si la solución es entera  FIN
 Si no  Identificar una variable fraccionaria y agregarla al plano de corte Gomory
3 – Volver a 1
Final 4 – 20/7/2017
C1 El problema del viajante con ventanas de tiempo agrega la restricción de "horarios
de atención" en cada ciudad, indique y justifique a que clase(s) de complejidad
pertenece.
Considerando que el problema clásico del viajante de comercio (TSP) y que éste
(TSPTW) es una variante que complejiza la toma de decisiones y reduce las
posibilidades de las ciudades a visitar, concluyo que pertenece a la clase NP-Hard, al
igual que el TSP.
C2 Compare simplex con el método de punto interior de Karmarkar. Indique pros y
contras de cada uno.
El método de Karmarkar nos asegura que, si se encuentra el centro del poliedro, termina
en tiempo polinomial. Pero, si no se halla dicho centro, el algoritmo puede encontrar
una solución factible o no (más allá de la compatibilidad del problema). A su vez, no
nos ofrece soluciones alternativas.
En cambio, el método Simplex en promedio es polinomial (en la práctica), aunque en el
peor caso es exponencial (en la teoría). A pesar de esto, siempre devuelve una solución
(y nos permite detectar los 4 casos particulares, en caso de que los haya).
FINAL 5 – 13/7/2017
C1 En el caso de un modelo de programación lineal continua que maximiza beneficios
¿hay alguna variación en el poliedro de soluciones si la función objetivo pasara a ser
minimizar costos?
No hay ninguna variación en el poliedro de soluciones, aunque sí la habrá en el punto
óptimo. A su vez, un problema de maximización que resultaba en un poliedro abierto,
tendrá solución si se tratase de un problema de minimización.
C2 Indique diferencias y similitudes entre el problema del viajante y el problema de
distribución o transporte.
El problema del viajante consiste en encontrar el orden en el cual un viajante debe
visitar todas las ciudades exactamente una vez y volver al origen, de manera tal que la
distancia total recorrida sea mínima.
El problema de distribución o transporte consiste en determinar la cantidad de unidades
de producto que cada origen envía a cada destino, de manera tal que el costo total por
transporte sea mínimo.
Ambos problemas son NP-Hard y tienen importantes aplicaciones en situaciones de la
realidad.
En el problema de distribución o transporte puedo utilizar variables continuas y el
problema devolverá una solución entera (demostrado por teorema), mientras que esto no
es factible en el problema del viajante.
FINAL 6 – 6/7/2017
C1 ¿Qué es un plano de corte? ¿En qué caso la solución óptima de la relajación de un
PL Entero es también una solución óptima del PL Entero?
Un plano de corte es una desigualdad válida, no es parte de la formulación actual, no es
satisfecha por la solución óptima de la relajación lineal actual (la corta) y tiene un
algoritmo para encontrarlo.
Los métodos de planos de corte consisten en hacer el poliedro como si las variables
fueran continuas y luego recortarle los “bordes” para tratar de que quede el poliedro de
soluciones enteras. Por lo general, este trabajo no se hace en todo el poliedro, sino en las
inmediaciones de la solución óptima.
La solución óptima de la relajación lineal de un problema de PLE coincide con la
solución óptima del problema de PLE en sí cuando…
C2 Indique diferencias y similitudes entre el problema de distribución y el problema de
asignación cuadrática.
El problema de distribución o transporte consiste en determinar la cantidad de unidades
de producto que cada origen envía a cada destino, de manera tal que el costo total por
transporte sea mínimo.
El problema de la asignación cuadrática consiste en determinar qué fábricas se
instalarán en qué ciudades de manera tal que el costo total de comunicación entre las
fábricas sea mínimo. Dicho costo depende de la frecuencia de comunicación y la
distancia entre las fábricas.
Ambos problemas son NP-Hard y tienen importantes aplicacionesen situaciones de la
realidad.
En el problema de distribución o transporte puedo utilizar variables continuas y el
problema devolverá una solución entera (demostrado por teorema), mientras que esto no
es factible en el problema de la asignación cuadrática.
FINAL 7 – 23/2/2017
C1 En términos de complejidad ¿cuándo un algoritmo es de clase NP y cuándo es de
clase NP Completo?
Un algoritmo es de clase NP cuando es no determinista polinómico. Es decir, se puede
resolver de manera polinomial en una máquina de Turing no determinista (a su vez, se
puede comprar en tiempo polinomial si una solución propuesta es válida o no).
En cambio, un algoritmo es de clase NP-Completo cuando se trata de un problema NP
específico con la particularidad de que si existe un algoritmo de clase P para resolverlo,
entonces cualquier problema NP puede resolverse con un algoritmo de clase P.
C2 Indique diferencias y similitudes entre el problema del viajante y el problema de la
mochila.
El problema del viajante consiste en encontrar el orden en el cual un viajante debe
visitar todas las ciudades exactamente una vez y volver al origen, de manera tal que la
distancia total recorrida sea mínima.
El problema de la mochila consiste en determinar qué objetos meter en la mochila sin
superar su límite de peso, de manera tal que el beneficio de los objetos guardados sea
máximo.
Ambos problemas son NP-Hard y tienen importantes aplicaciones en situaciones de la
realidad.
En ninguno de los dos problemas es factible la relajación lineal, aunque en el caso de la
mochila puede ser utilizada como cota para medir si una heurística es buena o no.
FINAL 8 – 16/2/2017
C1 Indique diferencias entre planos de corte generales y específicos.
Los planos de corte generales sólo se basan en la condición de la integrabilidad de las
variables, pueden ser utilizados para cualquier PLE y son muy débiles. Ejemplos de
estos son los planos de corte Gomory.
En cambio, los planos de corte específicos son particulares para cada problema de PLE
y resultan más robustos. Ejemplos de estos son las desigualdades de cubrimiento
extendida y ajustada y para conjuntos independientes.
C2 ¿En qué se parecen y en qué se diferencian el problema de distribución y el
problema de asignación?
El problema de distribución o transporte consiste en determinar la cantidad de unidades
de producto que cada origen envía a cada destino, de manera tal que el costo total por
transporte sea mínimo.
El problema de asignación consiste en determinar qué personas realizan cada uno de los
trabajos, de manera tal que la ganancia total por la realización de los trabajos con las
personas determinadas sea máxima. Es un caso particular del problema de transporte,
donde todas las ofertas y demandas son igual a 1.
Ambos problemas son NP-Hard y tienen importantes aplicaciones en situaciones de la
realidad.
Tanto en el problema de distribución o transporte como en el de asignación puedo
utilizar variables continuas y el problema devolverá una solución entera (demostrado
por teorema).
FINAL 9 – 9/2/2017
C1 Indique diferencias entre el algoritmo Branch and Bound y planos de corte.
El método de Branch and Bound consiste en ir armando un árbol de soluciones, de
manera tal que a cada nodo del árbol le corresponde un subproblema, mientras que el
problema original se encuentra en la raíz. En cada nodo del árbol se calcula una cota del
óptimo restringido a ese espacio de soluciones.
Lo interesante aquí es que, si llegamos a una cota que es peor que la mejor solución
obtenida hasta el momento, ya podemos dejar de explorar esa rama del árbol. La cota de
cada nodo se obtiene resolviendo la relajación lineal del subproblema en cuestión.
Un nodo no tiene sucesores cuando el subproblema no es factible, cuando se llega a una
solución no entera peor que la mejor solución o cuando se llega a una solución entera.
En cambio, los métodos de planos de corte consisten en hacer el poliedro como si las
variables pudieran tomar valores continuos y luego “recortarle” los bordes para tratar de
que quede el poliedro de soluciones enteras. Esto se suele hacer en las inmediaciones de
la solución óptima, no en todo el poliedro.
C2 ¿Por qué el problema del viajante es un problema difícil? ¿Todos los problemas del
viajante son igualmente difíciles?
Un problema en general se categoriza como difícil si su solución requiere de una
cantidad significativa de recursos computaciones, más allá del algoritmo utilizado.
En particular, el problema del viajante pertenece a esta categoría (es NP-Hard).
Cualquier algoritmo conocido para su resolución lleva un número exponencial de pasos.
La cantidad de caminos posibles a realizar es n!, donde n es la cantidad de ciudades del
problema.
No todos los problemas del viajante son igual de difíciles: algunos resultan más triviales
que otros, por las distintas conexiones entre las ciudades. 
FINAL 10 – 22/12/2016
C1 En planos de corte ¿qué es la cápsula convexa? ¿qué es una faceta?
La cápsula convexa es el recinto más chico que contiene a todas las soluciones factibles.
Se lo puede formular utilizando solo facetas.
Una faceta es una desigualdad válida cuya intersección con el poliedro tiene dimensión
igual a la dimensión del poliedro menos uno.
C2 En una de las formulaciones del problema del viajante se agregan variables Ui ¿para
qué se agregan? ¿cuál es el significado de esas variables? ¿son enteras o continuas?
Las variables Ui (son enteras, aunque no se las defina de tal forma) se agregan para
evitar subtours. Se define Ui como el número de secuencia en el cual la i-ésima ciudad
es visitada. El rango de i es desde 1 hasta n. Notar que el 0 queda afuera, ya que es la
ciudad de origen a la cual hay que regresar.
FINAL 11 – 15/12/2016
C1 Mencione y explique brevemente cotas que se pueden usar para resolver el problema
de la mochila con heurísticas.
En la resolución heurística del problema de la mochila, las cotas se utilizan para medir
qué tan buena es nuestra heurística. Si sabemos que el óptimo es X y nuestra heurística
nos está dando un resultado de X4, se sospecha que no es para nada buena.
A continuación, algunas cotas que se pueden utilizar:
- Relajación Lineal. Implica permitirle tomar valor continuo a las variables.
- Dantzig. Aplica una condición de integralidad.
- Martello & Toth. Establece la integridad del elemento crítico.
C2 ¿Cuándo termina el algoritmo Branch and Bound? ¿puede terminar sin encontrar el
óptimo entero?
El algoritmo termina cuando se terminan de explorar todas las ramas del árbol generado.
Es importante tener en cuenta que un nodo no tiene sucesores cuando:
- El subproblema no es factible
- El subproblema tiene una solución no entera peor a la mejor solución encontrada
hasta el momento
- El suproblema tiene una solución entera
Puede terminar sin encontrar el óptimo entero en caso de llegar a todas ramas
incompatibles.