Ejercicio corregido Branch and Bound

Esta página presenta un ejercicio corregido detallado del problema de programación lineal resuelto por el algoritmo de rama y atado.

rama y atado

El dueño de un taller de maquinaria planea expandirse comprando nuevas máquinas, prensas y tornos. El propietario estimó que cada prensa comprada aumentará las ganancias en 100 $ por día y cada giro aumentará las ganancias en 150 $ por día. La cantidad de máquinas que el propietario puede comprar está limitada por el costo de las máquinas y el espacio disponible en el taller. Los precios de compra de la máquina y los requisitos de espacio son los siguientes.

separación y evaluación de sucursales y límites

El propietario tiene un presupuesto de 40.000 $ para la compra de maquinaria y 200 pies cuadrados de superficie disponible. El propietario quiere saber cuántas máquinas de cada tipo comprar para maximizar el aumento diario de las ganancias. Resuelve este problema.

Solución

El primer paso es modelar el problema, este es un problema lineal como un número entero (por lo que el símplex no puede aplicar).

separación y evaluación de sucursales y límites

Siendo x_1 el número de pulsaciones y x_2 el número de vueltas.

Comenzamos el método de bifurcación y acotación resolviendo primero el problema como un modelo de programación lineal regular sin restricciones sobre los números enteros (es decir, las restricciones sobre los números enteros se relajan o se relajan). El modelo de programación lineal para el problema y la solución relajada óptima es

separación y evaluación de sucursales y límites

La solución óptima relajada es x_1=2.22 y x_2=5.56 con Z=1055.56.

El método de bifurcación y vinculación utiliza un diagrama que consiste en nodos y bifurcaciones como marco para el proceso de solución. El primer nodo en el diagrama de rama y vínculo, que se muestra en la Figura C-1, contiene la solución de programación lineal relajada que se mostró anteriormente y la solución redondeada.

separación y evaluación de sucursales y límites

Denotamos límite superior el resultado de la solución óptima relajada y límite inferior el resultado de la solución óptima como un número entero (redondeado hacia abajo).

Primera conexión

Cree dos restricciones (o subconjuntos) para eliminar la parte fraccionaria del valor de la solución y ver cuál está más lejos del valor entero redondeado (es decir, qué variable tiene la parte fraccionaria más grande en valor absoluto). La parte 0,56 de 5,56 es la parte fraccionaria más grande; por lo tanto, x_2 será la variable a la que vamos a "conectar".

Es decir, crearemos dos programas lineales alternativos teniendo en cuenta respectivamente que x_2 debe ser menor o igual a 5 por un lado; y x_2 debe ser mayor o igual a 6 por otro lado.

Entonces tenemos la siguiente conexión:

separación y evaluación de sucursales y límites

Resolvamos el problema de la izquierda:

separación y evaluación de sucursales y límites

Esto da la solución x_1=2.5, x_2=5 y Z=1000.

Resolvamos el sistema de la derecha:

separación y evaluación de sucursales y límites

Este sistema tiene por solución x_1=1.33 y x_2=6, Z=1033.33

Desde un punto de vista práctico, cortamos el campo de definición con la restricción x_2=6 y se han resuelto a ambos lados de la restricción que libera el sistema lineal.

separación y evaluación de sucursales y límites

Actualicemos nuestro grafico con los nuevos UB y LB de cada sistema obtenidos.

separación y evaluación de sucursales y límites

Dado que aún no tenemos una solución entera óptima y factible, debemos continuar ramificando (es decir, dividiendo) el modelo, ya sea desde el nodo 2 o desde el nodo 3. Una mirada a la Figura revela que si ramificamos desde el nodo 2, el el valor máximo que posiblemente se puede alcanzar es 1000 $ (el límite superior).

Sin embargo, si comenzamos desde el nodo 3, es posible un valor máximo más alto de 1033 $. Por lo tanto, nos bifurcaremos desde el nodo 3. En general, siempre bifurquemos desde el nodo con el límite superior máximo.

Segunda conexión

Ahora los pasos de bifurcación seguidos previamente en el nodo 1 se repiten en el nodo 3. Primero, se selecciona la variable que tiene el valor con la parte fraccionaria más grande. Como x_2 tiene un valor entero, x_1, con una parte fraccionaria de 0.33, es la única variable que podemos seleccionar. Por tanto, se desarrollan dos nuevas restricciones a partir de x_1.

separación y evaluación de sucursales y límites

Tomando el nodo 4, tenemos el siguiente programa lineal:

separación y evaluación de sucursales y límites

La solución al problema es x_1=1 y x_2=6.17 con Z=1025.

El segundo problema es:

separación y evaluación de sucursales y límites

Este problema no admite solución (se viola la primera restricción). Entonces tenemos el siguiente gráfico solución:

separación y evaluación de sucursales y límites

Todavía no tenemos una solución entera, por lo que tenemos que continuar con el algoritmo de bifurcación y límite.

Tercera conexión

El nodo 4 tiene la mejor UB. Dado que x_2 es la única variable que no es un número entero, nos bifurcaremos a esta variable.

separación y evaluación de sucursales y límites

Después de resolver los dos programas lineales en los nodos 6 y 7, obtenemos el resultados siguiendo:

separación y evaluación de sucursales y límites

La solución al nodo 6 corresponde a los criterios del problema original (es decir, en número entero). Solo la rama en 3 y 4 tiene una UB superior al nodo 6, sin embargo, la rama que da a los nodos 5 y 7 no tiene solución factible. Concluimos que la solución óptima se encuentra en el nodo 6.

Resumen del método

Aquí hay un resumen en inglés del método que acabamos de usar.

separación y evaluación de sucursales y límites

Compartir, repartir
es_ESES
A los bloggers de %d les gusta esto: