modelos de localização de redes

DET 362– PESQUISA OPERACIONAL
Prof. Heleno do Nascimento Santos

MODELOS DE LOCALIZAÇÃO EM REDES

Uma importante classe de problemas aparece associada à estrutura denominada
REDE, onde pares de nós são conectados por ligações identificadas como arcos, se providas de direção ou como arestas, caso contrário. Como exemplos de tal estrutura existem as redes de computadores, comunicações, transportes, elétricas, hidráulicas, etc.. A seguir, serão decritos, sucintamente, alguns tipos desses problemas e os modelos associados. 1. Problema de Localização Capacitado (PLC)
Este problema aparece quando há necessidade de se escolher, dentre M nós candidatos a receberem instalações (centros de atendimento, armazéns, fábricas, etc.), aqueles que efetivamente receberão tais instalações, com o objetivo de atender a demanda de clientes localizados em N nós da rede, a um custo mínimo.
Associados a cada instalação i existem um custo fixo de abertura Fi e uma capacidade de atendimento Qi, que não pode ser violada.
Associado a cada cliente j existe uma demanda Dj, que deve ser atendida.
Finalmente, associado a cada par (i,j), instalação - cliente, existe um custo de atendimento Cij de toda a demanda Dj do cliente j, pela instalação associada ao nó i, se ela for aberta.
As variáveis de decisão:
Xij representa a fração da demanda do cliente j atendida pela instalação associada ao nó i, variando continuamente de 0 a 1;
Yi é uma variável binária, que assume o valor 1 se uma instalação for aberta no nó i, assumindo 0, caso contrário.
A função objetivo é formada pela soma dos custos de atendimento dos clientes (que diminui com o aumento do número de instalações abertas) e de abertura das instalações
(que aumenta com o aumento do número de instalações abertas).

O modelo:

∑∑ C

MIN

ij

i

j

X ij + ∑ FiYi

(1)

i

s.a.

∑X

ij

= 1, j = 1,2,..., N ;

(2)

i

∑D X j ij

≤ QiYi , i = 1,2,..., M ;

(3)

j

0 ≤ X ij ≤ 1,