Metodo Ramificacion Y Acotamiento

Algoritmos Branch and Bound

1. Resolver el problema de la mochila 0-1 con los siguientes valores: Tama˜o de la mochila M = 61; n´mero n u de objetos n = 5; matriz de pesos W = (1, 11, 21, 23, 33);matriz de ganancias P = (11, 21, 31, 33, 43). Representar el ´rbol de estados que se obtendr´ al utilizar la t´cnica Branch and Bound explicada en a ıa e clase. Numerar los nodos seg´n el orden enque son expandidos y comentar los criterios que se siguen para u la expansi´n o poda de los nodos. o 2. La empresa DAMORSA es un negocio familiar, fundado hace 70 a˜os por el visionario D. EusebioP´rez, n e en paz descanse, que actualmente est´ gestionada por su nieto Carlos. DAMORSA siempre ha destacado a por el buen trato a sus empleados y Carlos quiere continuar con la tradici´n. Para eso, legustar´ que o ıa los empleados estuvieran lo m´s contentos que se pueda con su puesto de trabajo. A cada uno de los N a empleados de DAMORSA se le ha distribuido una relaci´n de los N puestos de trabajode la empresa, o para que cada empleado asigne un valor a cada puesto de trabajo repesentando lo satisfecho que estar´ ıa en ese puesto (a m´s valor, m´s satisfecho estar´ Por tanto, Carlos haobtenido una tabla N por N a a ıa). donde en la casilla (i, j) est´ el valor de satisfacci´n que tendr´ el trabajador i en el puesto j. Ayudar a a o ıa Carlos, dise˜ando un algoritmo que devuelva laasignaci´n de los puestos de trabajo que produce que la n o suma del valor de satisfacci´n de todos sus empleados es m´xima. o a 3. En una regi´n existen N ciudades comunicadas por carreteras. Algunas de lascarreteras cruzan por o debajo de otras mediante puentes. Deseamos enviar un cami´n de una ciudad a otra con una carga de o altura descomunal de tal forma que pueda no cruzar por debajo de algunospuentes. Son conocidas las carreteras existentes y la localizaci´n y altura de todos los puentes. Dise˜a un algoritmo de ramificaci´n o n o y poda que determine el trayecto de longitud m´ ınima para un...