Introducción

Los planteamientos de cobertura de conjuntos son un problema binario que nos puede ser de utilidad en casos donde necesitamos cubrir ciertas condiciones, ya sean espacios o lugares, pero con el mínimo número de elementos, en la clase revisamos alg unos como lo fue la ubicación de una línea telefónica que cubriera todas las calles (ejemplo que revisaremos a continuación) o para acceder a ciertas tuberías perforando la menor cantidad de zonas.

Problema

Con el fin de promover la seguridad de los estudiantes, el Depto. de Seguridad de la UNAM se encuentra en proceso de instalar teléfonos de emergencia en ubicaciones selectas dentro de sus instalaciones. El Depto quiere instalar un número mínimo de teléfonos, siempre y cuando cada una de las principales calles del campus cuente por lo menos con un teléfono. En el siguiente mapa se proporciona el mapa de las calles principales en la Facultad.

Planteamiento

xi={1 se pone el teléfono en el lugar i, 0 no se pone el teléfono en el lugar i}

Min z = x1+x2+x3+x4+ x5+x6+x7+x8

s.a.

x1+x2+x3 >= 1

x1 +x6 >= 1

x2 +x6 >= 1

x2 +x4 +x7 >= 1

x4+x5 >= 1

x3 +x5 +x8 >= 1

x6+x7+x8 >= 1

xi {0,1} xi0

Planteamiento con explicación

Las variables

xi={1 se pone el teléfono en el lugar i, 0 no se pone el teléfono en el lugar i}

Esta es sencilla, únicamente queremos que teléfonos ubicar.

Función objetivo

Min z = x1+x2+x3+x4+ x5+x6+x7+x8

Lo que queremos es gastar lo menos posible en teléfonos y para esto es necesario minimizar el número de teléfonos instalados.

Restricciones

x1+x2+x3 >= 1

x1 +x6 >= 1

x2 +x6 >= 1

x2 +x4 +x7 >= 1

x4+x5 >= 1

x3 +x5 +x8 >= 1

x6+x7+x8 >= 1

Estas restricciones hacen referencia a que queremos poner cuanto menos un teléfono que cubra cierto espacio, y en este caso en particular cada restricción equivale a una calle.

Sabias que:

• "El método de ramificación y acotamiento fue propuesto por A. H. Land and A. G. Doig en 1960"

-A. H. Land and A. G. Doig (1960). "An automatic method of solving discrete programming problems". Econometrica. pp. 497–520. doi:10.2307/1910129

Resolución del modelo

Método de ramificación y acotamiento para problemas binarios

El método de ramificación y acotamiento es una herramienta muy poderosa a la hora de analizar cualquier problema de programación entera y esta no es la excepción, para comenzar tenemos que trabajar con el modelo relajado, pero al no poder incluir la condición de que los valores tienen que se 0 o 1 en el modelo de programación lineal, es necesario incluir más restricciones dejando el modelo de programación lineal de la siguiente manera.

xi={1 se pone el teléfono en el lugar i, 0 no se pone el teléfono en el lugar i}

Min z = x1+x2+x3+x4+ x5+x6+x7+x8

s.a.

x1+x2+x3 >= 1

x1 +x6 >= 1

x2 +x6 >= 1

x2 +x4 +x7 >= 1

x4+x5 >= 1

x3 +x5 +x8 >= 1

x6+x7+x8 >= 1

xi <= 1

xi >= 0

Y este es el modelo que debemos de resolver para comenzar a iterar con el método de ramificación y acotamiento.

Al resolver el modelo relajado obtenemos lo siguiente:

x1=0

x2=0

x3=1

x4=1

x5=0

x6=1

x7=0

x8=0

Modelo que convenientemente es una solución factible y óptima con una z = 3 y que da por terminado el método de ramificación y acotamiento.

Así que conviene instalar los teléfonos 3, 4 y 6.