Programacion Lineal Entera / Investigacion Operativa 1

MODELIZACI ON Y RESOLUCI ON CON SOLVER. Hoja 3

Para los siguientes problemas, se pide:

1. Plantear el correspondiente modelo de Programacion Lineal Entera.

2. Resolver el modelo con ayuda del Solver de Excel.

1. En una galerıa de arte cuyo plano es el de la figura, se desean instalar camaras de video para tenerla

completamente vigilada. Hay 9 zonasA, B, . . . , I, y 9 posibles puntos1, . . . , 9 de instalacion de

las camaras. Una camara colocada en cualquiera de los puntos senalados vigila todas las zonas

adyacentes a dicho punto. Por consideracion a los visitantes, no se permite que mas de 2 camaras

vigilen la misma zona.

8

6

4

I

G

9

31

D

C

2

E

A

BH

5

7

F

Ademas, si la zonaA queda vigilada solo por una camara, entonces la zonaD debe quedar vigilada

solo por 1 camara.

Las camaras situadas en puntos capaces de vigilar 2, 3 y 4 zonas cuestan 5, 7 y 8 unidades mone-

tarias, respectivamente.

Formula el correspondiente modelo para determinar que camaras se deben instalar de manera que

se minimice el coste total y se cumplan las condiciones anteriores.

Solucion. Se trata esencialmente de un problema de cubrimiento. Hay que decidir que camaras se

instalan:variables de decision binarias

xi =

1 si la camarai se instala

0 si no se instala, i = 1, . . . , 9

Programacion Lineal Entera / Investigacion Operativa 2

Las condiciones de cubrimiento garantizan que cada zona queda vigilada:

Zona A: x1 + x2 + x3 ≥ 1

Zona B: x3 + x8 ≥ 1

Zona C: x7 + x8 + x9 ≥ 1

Zona D: x1 + x9 ≥ 1

Zona E: x2 + x4 + x5 ≥ 1

Zona F: x5 + x8 ≥ 1

Zona G: x6 + x7 + x8 ≥ 1

Zona H: x6 ≥ 1

Zona I: x4 + x6 ≥ 1

La condicion de que no mas de 2 camaras vigilen simultaneamente una zona es necesaria solo para

las zonas accesibles desde mas de 2 camaras:

Zona A: x1 + x2 + x3 ≤ 2

Zona C: x7 + x8 + x9 ≤ 2

Zona E: x2 + x4 + x5 ≤ 2

Zona G: x6 + x7 + x8 ≤ 2

Para modelar las implicaciones “si la zonaA queda vigilada solo por una camara, entonces la zona

B debe quedar vigilada por 2 camaras y la zonaD solo por 1”, es suficiente con tener en cuenta

quex1 + x2 + x3 = numero de camaras que vigilan la zona A solo puede ser igual a 1 o 2:

x3 + x8 ≥ 3 − x1 − x2 − x3

x1 + x9 ≤ x1 + x2 + x3

2. Una empresa fabrica tres productos 1, 2 y 3, que deben procesarse en dos tipos de maquinaria

denominadas A y B. En la siguiente tabla se recogen los tiempos de procesamiento (por tonelada

procesada) con cada maquina, los beneficios (por tonelada procesada) en euros, y la disponibilidad

de cada tipo de maquinaria (en horas por semana):

Tipo de Productos Disponibilidad

maquinaria 1 2 3 (horas)

A 2 5 4 70

B 3 4 6 86

Benef./ton. (miles de euros)800 700 950

La empresa considera aumentar la disponibilidad de tiempo de procesamiento de la maquinaria.

Para ello, puede llevar a cabo alguna de las posibilidades indicadas a continuacion

Programacion Lineal Entera / Investigacion Operativa 3

Tipo de maquinaria A B

Incremento de disp. (horas) 10 15 8 12

Coste inversion (miles de euros)1600 1700 1700 1750

A lo sumo, se puede realizar un tipo de incremento para cada m´aquina. Gracias a un estudio de

mercado se conocen los lımites de demanda de los productos,que son

Demanda (ton.)

Producto mınima maxima

1 6 17

2 3 8

3 7 20

Ademas, la inversion total no puede exceder de 3400000 euros. Se pide:

(a) Formular el problema que se debe plantear la direccion de la empresa para obtener el plan de

procesamiento e inversion de mayor beneficio.

(b) Si la empresa desease aumentar la disponibilidad de un s´olo tipo de maquinaria, ¿como se

modifica el modelo anterior reflejando tal situacion?

(c) Si no se quiere anadir disponibilidad de B a menos que se anada de A, ¿como se representa

esta nueva condicion?

(d) La empresa desea ampliar la disponibilidad con la maquinaria B si, y solo si, se incrementa

tambien la A. ¿Como debe modificarse la condicion considerada en el apartado anterior?

Solucion.

Las variables de decision son:

x1, x2 y x3: cantidad de cada producto que se fabrica.

Variables binarias que nos indican si se realiza cada uno de los 4 posibles incrementos o no:

δA1, δA2, δB1 y δB2.

δA1 =

1, si se realiza el incremento de 10 h. en la maquina A,

0, si no se realiza

δA2, δB1 y δB2 se definen analogamente para los incrementos de 15 h. en la m´aquina A y 8 y

12 h. en la maquina B, respectivamente.

Programacion Lineal Entera / Investigacion Operativa 4

La funcion objetivo a maximizar: beneficios de venta - costeincremento de capacidad de las

maquinas

800x1 + 700x2 + 950x3 − 1600δA1 − 1700δA2 − 1700δB1 − 1750δB2

Las restricciones son:

Disponibilidad de maquinaria:

2x1 + 5x2 + 4x3 ≤ 70 + 10δA1 + 15δA2

3x1 + 4x2 + 6x3 ≤ 86 + 8δB1 + 12δB2

A lo sumo, se puede realizar un tipo de incremento para cada m´aquina:

δA1 + δA2 ≤ 1 (1)

δB1 + δB2 ≤ 1 (2)

Lımites de la demanda de cada producto:

6 ≤ x1 ≤ 17, 3 ≤ x2 ≤ 8, 7 ≤ x3 ≤ 20

La inversion total no puede exceder de 3400000 euros:

1600δA1 + 1700δA2 + 1700δB1 + 1750δB2 ≤ 3400

x1, x2, x3 ≥ 0 y δA1, δA2, δB1 y δB2 variables binarias.

(b) Si la empresa desease aumentar la disponibilidad de un s´olo tipo de maquinaria, ¿como se

modifica el modelo anterior reflejando tal situacion?

Si se siguen manteniendo las restricciones (1) y (2), entonces es suficiente con anadir:

δA1 + δA2 + δB1 + δB2 ≤ 1

Si no se mantienen, es decir, solo se puede invertir en una m´aquina pero las ampliaciones

se pueden acumular, entonces hay que anadir 2 nuevas variables binarias que indiquen si se

invierte o no en cada maquina:

δA =

1, si se realiza algun incremento en la maquina A,

0, si no se realiza

Programacion Lineal Entera / Investigacion Operativa 5

Analogamente se defineδB. Estas 2 variables toman su valor en funcion del valor de lasvari-

ables binarias previamente definidas:

δA1 + δA2 ≤ 2δA (3)

δB1 + δB2 ≤ 2δB (4)

Estas 2 restricciones sustituirıan a las anteriores (1) y (2). Ademas, habrıa que anadir para

modelizar la condicion que se nos pide ahora:

δA + δB ≤ 1

(b) Si no se quiere anadir disponibilidad de B a menos que se anada de A, ¿como se representa

esta nueva condicion?

Como antes, si no se elimina la condicion de, a lo sumo 1 inversion en cada maquina, habrıa

que anadir la restriccion:

δB1 + δB2 ≤ δA1 + δA2

Si se elimina la condicion, entonces se definenδA y δB como antes y se anade la restriccion:

δB ≤ δA

(b) La empresa desea ampliar la disponibilidad con la maquinaria B si, y solo si, se incrementa

tambien la A. ¿Como debe modificarse la condicion considerada en el apartado anterior?

Se debe cambiar la desigualdad por una igualdad.

3. Considera el siguiente problema de localizacion de almacenes:

Una empresa tiene que decidir donde localizar 2 posibles almacenes de distribucion para atender

la demanda de 4 posibles clientes. Cada cliente correspondea una zona geografica. La empresa

tiene 3 posibles ubicaciones para los almacenes, de las que tiene que seleccionar 2.

Para cada ubicacion se conoce:

Costes fijos por levantar cada almacen (P1, P2 y P3) y capacidad maxima de cada uno de

ellos

costes fijos capacidades

P1 25 12

P2 12 10

P3 13 8

Costes de asignacion almacen–cliente y demandas de cada cliente

Programacion Lineal Entera / Investigacion Operativa 6

costes de asignacion

almacen cliente 1 cliente 2 cliente 3 cliente 4

P1 5 6 3 2

P2 3 4 2 3

P3 4 2 3 5

demandas 2 4 4 3

El objetivo es determinar que almacenes se levantan y que clientes se atienden desde cada almacen

cuando cada cliente solo puede ser atendido desde un almac´en y es obligatorio que cada cliente

tenga asignado un almacen.

La variables de decision binarias son:

Decision respecto a que almacen se levanta:

xi =

1 si el almaceni se levanta

0 en otro casoparai = 1, . . . , 3

Decision respecto a que almacen sirve a cada cliente:

yij =

1 si el almaceni sirve al clientej

0 en otro caso

parai = 1, 2, 3, j = 1, 2, 3, 4 (variables de asignacion)

Mientras que el objetivo es minimizar el coste total: coste de levantar un almacen mas coste de

asignacion cliente-almacen.

En cuanto a las restricciones, una posibilidad es:

(1) Si el almaceni no se levanta (xi = 0), no puede servir al clientej (yij = 0):

yij ≤ xi parai = 1, 2, 3, j = 1, . . . , 4

(2) Cada cliente debe ser servido por exactamente un almacen:

3∑

i=1

yij = 1 paraj = 1, . . . , 4

(3) Cada almacen no puede servir mas de su capacidad:

4∑

j=1

njyij ≤ CAPi parai = 1, 2, 3,

dondenj = demanda del clientej, j = 1, . . . , 4.

Programacion Lineal Entera / Investigacion Operativa 7

(4) El numero maximo de almacenes es2:

3∑

i=1

xi ≤ 2

(5) Las variables son binarias:

xi ∈ {0, 1} ∀i = 1, 2, 3

y

yij ∈ {0, 1} ∀i = 1, 2, 3, j = 1, 2, 3, 4

Todas las restricciones anteriores, junto con la funcion objetivo, componen elModelo 1.

Si nos fijamos en las restricciones (1) y (3), observamos que se pueden combinar en una unica

restriccion (13), manteniendo el resto de restricciones

(13) Si el almaceni no se levanta (xi = 0), no puede servir a ningun clientej (yij = 0), j =

1, . . . , 4, y si se levanta, la demanda de su cartera de clientes no puedeexceder su capacidad:

4∑

j=1

njyij ≤ CAPixi parai = 1, 2, 3

LlamamemosModelo 2 al modelo resultante. Plantea y resuelve la relajacion lineal del Modelo

1 y del Modelo 2 con el Solver de Excel. ¿Que relacion hay entre el valor optimo de ambos

problemas?, ¿la solucion optima de la relajacion linealdel modelo 1 verifica todas las restricciones

(13) del modelo 2?, ¿cual de los dos modelos crees que es “mejor”?, ¿por que?

Construye un tercer modelo,Modelo 3, manteniendo el conjunto de restricciones (1) del Modelo 1

y sustituyendo el conjunto de restricciones (3) por las restricciones (13). Compara el valor optimo

de la relajacion lineal de este nuevo modelo con las soluciones de las relajaciones lineales de

los Modelos 1 y 2. ¿La solucion optima de la relajacion lineal del modelo 2 verifica todas las

restricciones del modelo 3?, ¿cual de los 3 modelos te parece “mejor”?

Solucion.

Los valores optimos de las relajaciones lineales de los problemas 1, 2 y 3, son respectivamente:

z∗1

= 24.6923067 < z∗2

= 27.3 < z∗3

= 28.5

Como estos valores se van a usar para obtener cotasinferiores para el valor optimo del problema

entero, la mejor de todas ellas es la proporcionada al resolver la relajacion lineal del Modelo 3.

Efectivamente, se trata de la formulacion “mas fuerte”.

Programacion Lineal Entera / Investigacion Operativa 8

La solucion optima de la relajacion lineal del Modelo 1 noverifica las restricciones de ca-

pacidad (13) del Modelo 2 correspondientes a las localizaciones 2 y 3.

La solucion optima de la relajacion lineal del Modelo 2 noverifica las restricciones (1) del

Modelo 3 correspondientes a las localizaciones 2 y 3:

y∗

21= y∗

23= y∗

24= 1 0.9 = x∗

2

y∗

32= 1 0.5 = x∗

3

dondex∗ es la solucion optima de la relajacion lineal del Modelo 2.