Problema 1 prueba 2021

Problema 1 prueba 2021

de Agustina Behrens Lorenzi -
Número de respuestas: 1

Buenas tardes! Resolviendo el Branch and Bound de la prueba de 2021, en vez de continuar por la rama de x<= 2 como hicieron ustedes, arranque evaluando la de x>=3 (tengo entendido que se puede comenzar por cualquiera de las dos ramificaciones).

Resolviendo el problema, me dio la solucion x=3, y=0.5, y dividiendo en dos subproblemas llegue a la solucion factible x=3, y=0, la cual me da el mismo valor optimo z que la solucion pero con distintos valores de x e y. 

Queria consultar si esto esta igualmente correcto que el punto obtenido en las soluciones, o si debe comenzarse el algoritmo por la opcion mas baja siempre (el camino de x <=2). 

De ser correcto, deberia continuar evaluando la rama de 2 y al evaluar el punto x=2, y=1 podar por acotamiento? (z2 ≤ z3, en particular son iguales). La solucion optima al final me quedaria x=3, y=0.

En respuesta a Agustina Behrens Lorenzi

Re: Problema 1 prueba 2021

de Pedro Piñeyro -
Hola.
Si, es correcto tomar cualquiera de los subproblemas no resueltos, no importa el orden. Se debería llegar a la misma solución siempre, o a otra diferente, pero siempre el valor óptimo del problema original deber ser el mismo (en este caso 3). Siempre que el valor óptimo de un subproblema sea mejor que el de la mejor solución entera hasta al momento, hay que resolverlo, como en este caso, ya que P1 tiene un valor óptimo de 3,33, que es mejor que 3, por ser un problema de maximización. Al resolverlo, vas a determinar otra solución óptima del problema, que es x=2, y=1. De todas maneras, aclaro que en este problema, en la parte a, se pedía aplicar branch-and-bound para determinar una solución factible, es decir, entera. Por lo tanto no era necesario terminar el algoritmo de branch-and-bound, solamente determinar una solución entera.
Saludos,
Pedro.-