Respuestas Teoricas Final docx

Vista previa del material en texto

1) La relajación lineal para el problema de coloreo de grafos no es útil porque
siempre da 2.
2) Un problema es NP si este puede ser resuelto en una máquina no deterministica
de turing en un tiempo polinomial. El método del elipsoide demuestra que la
programación lineal esta en P. Como P está incluida o es igual a NP, la PL está en
NP.
3) La heurística de la mochila tiende a funcionar en la mayoría de los casos pero
existen casos patológicos.
Definiendo a: Z como el valor de la sol optima; Z’ como el valor de la sol obtenida
aplicando la heurística; Z’/Z índice de performance de la heurística.
Se puede demostrar que existen casos en el cual el índice de performance de la
heurística sea tan cercana a 0 como se quiera.
4) Branch and bound y branch and cut. El enfoque branch and bound intenta
reducir la cantidad de pasos en un esquema de enumeración exhaustiva. Constituye
un esquema de división y conquista que intenta resolver el problema original
dividiéndolo en problemas más pequeños, para los cuales se computan cotas
inferiores y superiores del valor óptimo. En un problema de minimización si la cota
inferior sobre un noda A del arbol de numeración es mayor que la cota superior de
algun otro nodo B, se descarta el A. Eso se conoce como poda. Idealmente el
algoritmo termina cuando todos los nodos son podados o resueltos.
Branch and Bound forma parte de una de los conceptos básicos que hacen al
método Branch and Cut. El mismo surge como un híbrido de los métodos de
Branch and Bound y los métodos de plano de corte. Si luego de resolver la relajación
lineal de un subproblema no se puede cerrar el nodo correspondiente entonces se
busca una desigualdad violada por el óptimo de la relajación. Si se encuentran
desigualdades violadas (cortes) se agregan a la formulación y se resuelve el
problema lineal nuevamente. Si no se encuentra ningún corte se continua con el
proceso de branching.
5) Branch and Cut es un metodo de optimizacion combinatoria para resolver
problemas de programación lineal entera donde alguna o todos las incógnitas son
enteras. Es un híbrido entre el método Branch and Count y algoritmos de planos de
corte.
6) Complejidad se define según la relación entra la cantidad de instrucciones
computadas y el tamaño de la instancia. Una instancia es cada una de las posibles
entradas del problema.
7) El problema del viajante es un problema de complejidad NP-HARD, es decir no se
conoce un algoritmo de tiempo polinomial que pueda resolverlo exactamente. Por
esto, se utilizan heurísticas para obtener soluciones aproximadas en un tiempo
razonable.
8) Probar una heurística con problemas ya resueltos exactamente permite obtener
una medida de cuan buena es la heurística, prueba su robustez. Si la heurística se
prueba solo con problemas elaborados por el autor se corre el riesgo de que la
heurística sea buena solo para ese problema o solo para ese conjunto de entradas.
9) Para determinar si alguno de los problemas es difícil podríamos analizar el
problema y ver si se asemeja o se puede llevar a un problema ya estudiado
teóricamente, es decir ya se conoce su complejidad. Por ejemplo, si determinamos
que un problema se parece al problema de viajante entonces el problema
presentado es difícil. Si no podemos encontrar un problema conocido semejante
diremos que el problema es dificil si su resolución implica una ejecución mayor a
determinado tiempo. Este tiempo dependerá de la naturaleza del problema. Con este
metodo tambien podemos comparar algoritmos, quel que tarde mas lo
consideraremos más difícil.
10) Teóricamente los problemas NP-HARD son aquellos que al menos son tan
difíciles como los problemas NP. Un problema está en NP-HARD si todo problema
L en NP se puede transformar a H en tiempo polinomial.
11) El problema de distribución y transporte es un problema facil si la oferta es igual
a la demanda ambos son números enteros y las restricciones todas igualdades,
entonces el problema puede resolverse con PLC y el resultado es entero. Como PLC
está en P el problema no es difícil.
12) Resolución de modelos de PLE:
Métodos enumerativos (para problemas cuyas variables son todas bivalentes):
consisten en encontrar todas las posibles soluciones del problema, armando un
árbol de decisión en el cual cada una de las hojas es un conjunto posible de valores
para las variables binarias o bivalentes. Por ejemplo, en un problema que tiene tres
variables bivalentes, una hoja mostrará la solución Y1= 0, Y2 = 0, Y3 = 0 con su
valor de funcional, otra hoja mostrará la solución Y1= 1, Y2= 0, Y3 = 0 con su valor
de funcional, y así sucesivamente. La solución elegida será la que tenga mejor valor
de funcional.
Métodos pseudo-booleanos (para problemas cuyas variables son todas
bivalentes): consisten en convertir el modelo en un conjunto de expresiones del
álgebra de Boole y resolverlo para optimizar el valor de la función objetivo.
Métodos de planos cortantes (para cualquier tipo de variables enteras): Los
métodos de planos cortantes consisten en hacer el poliedro como si las variables
pudieran tomar valores continuos y luego “recortarle” los bordes (como cuando uno
hace masa para empanadas) para tratar de que quede el poliedro de soluciones
enteras. Por lo general ese trabajo no se hace en todo el poliedro sino en las
inmediaciones de la solución óptima.
13) ¿Cuándo un algoritmo es de clase P?: Un problema de decisión está en P si una
máquina de Turing puede resolverlo en tiempo polinomial.
14) 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.
15) Algoritmo de planos de corte Gomory
1.Se resuelve la relajación lineal del problema (se resuelve como si las variables
fueran continuas)
2.Si la solución es entera FIN
3.Identificar una variable fraccionaria y agregar el plano de corte Gomory
4.Volver a 1
16) Características del algoritmo de corte Gomory:
● Convergencia finita dada cierta regla para la elección de la variable
fraccionaria en el paso 3
● Generalmente es necesario un gran número de planos de corte
● Errores numéricos pueden generar soluciones incorrectas o que el programa
falle
● Recién se obtiene una solución factible al finalizar el algoritmo
17) ¿Cómo se resuelve un problema de optimización combinatoria?
Se pueden resolver usando:
● Enumeración (fuerza bruta)
● Soluciones exactas
● Heurísticas
18) ¿En qué afecta a la resolución de modelos de programación lineal entera que
no se haya podido probar aún si P es igual o distinto que NP?
Afecta en el hecho de generar incertidumbre acerca de si existe algun algoritmo que
resuelva dicho problema en tiempo polinomial, lo que tal vez podria obligarnos a
utilizar un Heuristica que no nos garantiza que la solucion sea optima.
19) Si existen procedimientos como Branch and Bound, Branch and Cut y otros,
que resuelven de manera exacta un problema de programación lineal entera
¿por qué algunos problemas se resuelven de manera aproximada con un
algoritmo heurístico?
Por que aun utilizando esos metodos la cantidad de ramas a recorrer es demasiado
extensa y llevaría demasiado tiempo
20) Para resolver un problema de Programación Lineal Entera, uno de los
procedimientos que se pueden utilizar es Branch & Bound ¿Cómo se puede
acelerar la resolución por Branch & Bound para que termine antes?
Para optimizar en el caso de tener soluciones alternativas lo que se puede hacer es
encuentro una solucion y le agrego un % y su una rama no es mayor a la sol+ % no
la analizo para no perder tiempo analizando soluciones similares.
la solución que encontrás debe ser válida (es decir, las variables que requieren ser
enteras, deben serlo). Genéricamente, lo que se hace es utilizar cotas.
21) ¿Para qué utiliza el método Branch and Bound la mejor solución entera
encontrada hastael momento?
Esta solución se usa para el paso de cota ("bound"), en el cual se eliminan de la lista
de problemas a explotrar todas las ramas que no se han explorado por completo y
tengan un funcional peor que la cota (es decir, que la mencionada solución entera).
22) Para resolver un modelo de Programación Lineal Entera ¿podemos usar el
método simplex? ¿qué diferencias hay entre resolver un modelo de
Programación Lineal Entera y un modelo de Programación Lineal Continua
No ya que en el metodo simplex voy recorriendo el poliedro de soluciones
moviendome por las restricciones, en el caso de tener una solucion entera que no
pertenezca a los vertices del poliedro, no podre hallar la solucion.
La diferencia seria que en el problema de plc se que la solucion se encuentra en
alguno (uno o mas) de los vertices del poliedro de soluciones en caso de existir y en
los problemas de PLE no tengo esa certeza.
23) En términos de complejidad ¿cuándo se dice que un problema es difícil?
Mencione un ejemplo
A la vez es un problema complejo, si por complejidad nos referimos a la
computacional. Un problema se cataloga como inherentemente difícil si su solución
requiere de una cantidad significativa de recursos computacionales, sin importar el
algoritmo utilizado. El problema de la mochila forma parte de una lista histórica de
problemas NP Completos elaborada por Richard Karp en 1972 2 . En el caso del
problema de la mochila, si contáramos con 4 productos, para saber cuál es la mejor
solución podríamos probar las 24=16 posibilidades. El 2 se desprende del hecho de
que cada decisión es incluir o no al producto y el 4 de la cantidad de productos. 16
posibilidades es un número manejable, sin embargo, si la cantidad de elementos por
ejemplo ascendiera a 20, tendríamos que analizar nada más y nada menos que
220=1048576 posibilidades.
24) Si el problema de distribución se puede resolver de manera exacta como un
problema de programación lineal continua ¿por qué se utilizan heurísticas de
construcción para ese problema?
Porque en la mayoría de los casos no se puede transportar partes fraccionarias de
productos, es decir, el uso más conocido es para variables enteras. Por este motivo
se utilizan heurísticas,
ya que su resolución en programación lineal entera es un problema difícil. Muchas
veces se requiere una solución aproximada, que se acerque lo suficiente a la
exacta, pero sin perder demasiado tiempo en procesamiento.
25) ¿Es el problema de Asignación un problema difícil? ¿Por qué?. El problema de
Asignación ¿es un problema difícil? ¿se puede resolver de manera exacta
aplicando el método Simplex, sin tener que aplicar Branch & Bound u otro
método para que las variables tengan valor entero?
Asignación es un problema difícil, porque es un problema combinatorio donde el
software tiene que evaluar cada posibilidad antes de dar con un resultado. En el
caso de haber muchas combinaciones esto puede ser muy costoso. Sin embargo, su
relajación lineal se resuelve en tiempo polinomial y da una solución entera.
Recordar que el problema de asignación es un problema de distribución o
transporte con orígenes y destinos de 1.
26) De los dos planteos de modelización más conocidos para el viajante (plantear
todas las restricciones que evitan subtours, también llamado MZT y el que
agrega las restricciones de Ui) ¿cuál es el mejor en términos de resolución del
problema? ¿por qué piensa que ese es el mejor?
El número exponencial de restricciones hace impráctico resolverlo directamente por
el método de Ui. Una opción es agregar únicamente las restricciones para evitar
subtours en los casos en los cuales arma subtour y no en todos los casos. Este
último es mejor cuando el problema del viajante tiene muchas ciudades, es decir,
muchas ecuaciones del problema en sí. En cambio el método de las Ui es muy
práctico cuando hay pocas ciudades ya que no aumenta considerablemente el
número de ecuaciones y resulta más práctico la resolución.
27) El problema de conjuntos a cubrir ¿es un problema difícil?. Definir brevemente
el problema e indicar por qué es un problema difícil o por qué no lo es.
Es un problema NP Completo (está en la lista de los 21 problemas NP Completos de
Karp). Dado un conjunto de elementos (llamado universo ) y
conjuntos cuya unión comprende el universo, el set cover problem consiste en
identificar el menor número de conjuntos cuya unión aun contiene todos los
elementos del universo. Por ejemplo, sea
y los conjuntos
Claramente, la unión de todos los conjuntos de contiene todos los elementos de
. Sin embargo, podemos cubrir todos los elementos con el siguiente conjunto de
elementos, con menor número de elementos
28) Si en el problema de la mochila se permitiera colocar fracciones de objetos en
lugar de exigir que los objetos se coloquen enteros ¿sería el problema
igualmente difícil? ¿por qué?
El problema es difícil porque la solución continua no me sirve para determinar qué
objetos deben entrar o no, en especial con el objeto crítico (el primero que no entra
y convendría que entrara). Si el problema fuera continuo la complejidad sería mucho
menor, porque la solución continua me sirve (sirve que entre una fracción de un
objeto)
29) ¿Cuándo se considera que un problema es “difícil”?. Justifique en base a lo
visto en las clases teórico prácticas acerca de complejidad.
A la vez es un problema complejo, si por complejidad nos referimos a la
computacional. Un problema se cataloga como inherentemente difícil si su solución
requiere de una cantidad
significativa de recursos computacionales, sin importar el algoritmo utilizado
30) ¿El problema de trasbordo es facil?
Los problemas combinatorios tienen distintas clasificaciones. Hay problemas P,
problemas NP, problemas NP-Completos, etc. Lo que cambia de una clase a otra es
la dificultad para resolverlos. La mayoría de los problemas combinatorios que vemos
en Modelos 1 (Viajante, Mochila, Cobertura de Conjuntos, Secuenciación, Coloreo
de Grafos, Asignación Cuadrática, etc.) suelen ser NP-Completos. Estos problemas
necesitan de programación lineal entera para ser resueltos. Sin embargo, hay un
caso particular que son los de Distribución, Transporte o Trasbordo, en donde el
problema es NP-Completo, pero se puede plantear con programación lineal
continua, y ser resuelto muy rápidamente con el método Simplex. La definición del
problema lo clasifica como NP-Completo, pero la resolución es sencilla ya que se
puede usar programación lineal continua.
31)
32)