Problemas Gotham City

WINSTON – PROBLEMA 21

Gotham City fue divida en 8 distritos. El tiempo en minutos que tarda una ambulancia en llegar de un distrito a otro se muestra en la tabla. La población de cada distrito en miles es como se indica:

Distrito 1 2 3 4 5 6 7 8

Población 40 30 35 20 15 50 45 60

La ciudad solo tiene 2 ambulancias y desea ubicarlas en tales lugares que se maximice el número de personas que viven a dos minutos de una ambulancia.

Distrito

Distrito 1 2 3 4 5 6 7 8

1 0 3 4 6 8 9 8 10

2 3 0 5 4 8 6 12 9

3 4 5 0 2 2 3 5 7

4 6 4 2 0 3 2 5 4

5 8 8 2 3 0 2 2 4

6 9 6 3 2 2 0 3 2

7 8 12 5 5 2 3 0 2

8 10 9 7 4 4 2 2 0

Variables de Decisión:

Xi = 1 si el distrito i cuenta con ambulancia

0 en caso contrario

Yi = 1 si el distrito i es atendido

0 en caso contrario

(i = 1,2,3,4,5,6,7,8)

Función objetivo:

MAX Z= 40 Y1 + 30 Y2 + 35 Y3 + 20 Y4 + 15 Y5 + 50 Y6 + 45 Y7 + 60 Y8

Restricciones:

La ciudad solo tiene dos ambulancias

X1 + X2 + X3 + X4 + X5 + X6 + X7 + X8 = 2

Solo los distritos sombreados en la tabla pueden ser atendidos pues las personas viven a dos minutos o menos de las ambulancias. Por ejemplo, en la cuarta ecuación si por lo menos uno de los distritos 3, 4, 6 posee una ambulancia entonces Y4 podría ser 0 o 1.

Por otro lado, como Y3 está en la función objetivo y esta es de maximización, el valor de Y4 sería 1, es decir que la ciudad si es atendida. A continuación se muestra para cada distritos las restricciones que cumplan con esas condiciones.

X1 – Y1 >= 0

X2 - Y2 >= 0

X3 - Y3 + X4 + X5 >= 0

X3 + X4 – Y4 + X6 >= 0

X3 + X5 - Y5 + X6 + X7 >= 0

X4 + X5 + X6 - Y6 + X8 >= 0

X5 + X7 - Y7 + X8 >= 0

X6 + X7 + X8 – Y8 >= 0

Rango de existencia:

X1,X2,X3,X4,X5,X6,X7,X8,Y1,Y2,Y3,Y4,Y5,Y6,Y7,Y8 = 0 ó 1

...