Upload
arnaldo-jr
View
215
Download
1
Embed Size (px)
DESCRIPTION
Material sobre uma das aplicações praticas da Pesquisa Operacional .
Citation preview
Problemas de Alocação e Alocação Capacitada (Assignment Problem)
Problema de alocaçãoFormulação
Um problema de transporte de dimensão (nxn), em que:
1º. As variáveis de decisão xij podem tomar valores 0 ou 1;2º. Todas as ofertas e as procuras são unitárias
Exemplo típico: Distribuir n trabalhadores por n tarefas de forma que cada trabalhador execute apenas uma tarefa, e que cada tarefa seja executada apenas por um trabalhador, sendo conhecidos os custos da realização de cada tarefa por cada trabalhador.
Problema de alocaçãoFormulação
Difícil encontrar a solução ótima por
tentativas: por exemplo, para um problema com 5
tarefas o número de soluções possíveis seria 5! = 120, e
para um problema de 10 tarefas o
número de soluções possíveis seria
3 620 800
O problema de alocação envolve a determinação de n! alocações (soluções) possíveis;
Cada possível alocação que consiste em alocar o trabalhador i à tarefa ti, i=1,2,...,n pode ser entendida como uma permutação de 1,2,...n onde a solução ótima pode ser a permutação para a qual o custo total é mínimo
Problema de alocaçãoFormulação
n trabalhadoresn trabalhadoresn trabalhadores n origensn origensn origens
n destinosn destinosn destinosn tarefasn tarefasn tarefas
Cada trabalhador i é indicado a uma tarefaCada trabalhador i é Cada trabalhador i é
indicado a uma tarefaindicado a uma tarefa ai=1, i=1,2,...,naaii=1=1, , i=1i=1,2,...,n,2,...,n
Cada tarefa j é executada por um trabalhador
Cada tarefa j é executada por Cada tarefa j é executada por um trabalhadorum trabalhador bj=1,j=1,2,...,nbbjj=1=1,,j=1j=1,2,...,n,2,...,n
Cij - custo de alocaçãotrabalhador i
tarefa j
CCijij -- custo de alocaçãocusto de alocaçãotrabalhador itrabalhador i
tarefa j tarefa j cij custo unitário de
transporte da origem i para o destino j
ccijij custo unitário de custo unitário de transporte da origem transporte da origem i i
para o destinopara o destino jj
Xij=1, se o trabalhador i for alocado pela tareja j, caso
contrário xij=0
XXijij=1=1, se o trabalhador i for , se o trabalhador i for alocado pela alocado pela tarejatareja j, caso j, caso
contrário contrário xij=0xij=0Xij unidades a distribuir da origem i para o destino j;
xij=0,1
XXij ij unidades a distribuir da unidades a distribuir da origem i para o destino j;origem i para o destino j;
xij=0xij=0,1,1
Problema de alocaçãoFormulação como problema de transporte
∑∑= =
=n
i
n
jijij xcz
1 1
Minimizar
sujeito a:
∑=
=n
jijx
11 ni ,...,2,1 , =
Cada trabalhador é alocado a uma
só tarefa
0≥ijx nj ,...,2,1 , =
nj ,...,2,1 , =Cada tarefa é
executada apenas por um
trabalhador∑=
=n
iijx
11
ni ,...,2,1 , =
Problema de alocaçãoFormulação como problema de transporte
DestinoOrigem
1 2 … n1 2 … n Oferta
11
22......
n
1
1......
1
Procura 1 1 ……
cc1111 cc1212 cc1n1n
cc2121 cc2222 cc2n2n
ccm1n1 ccm2n2 ccmnnn
xx1111 xx1212 xx1n1n……
xx2121 xx2222 xx2n2n……
xxm1n1 xxm2n2 xxmnnn……
..
..
..
..
..
..
..
..
..
1
Problema de alocaçãoExemplo1
Máquina/Empregado
1 2 3
1 25 31 35
2 24 17 16
3 15 23 18
Admita que em uma fábrica foram instalados três novas máquinas e admitidos três novos empregados. É objetivo da direção estabelecer uma alocação máquina-empregado recíproca e exclusiva com esta finalidade. Após vários testes estimou-se a seguinte matriz de custos:
Formule o problema de alocação, com o objetivo de minimizar os custos de trabalho
Máquina/Empregado
1 2 3
1 25 31 35
2 24 17 16
3 15 23 18
Problema de AlocaçãoExemplo
Formulação
Minimizar z = 25 x11 + 31 x12 + 35 x13 +24 x21 + 17 x22 + 16 x23 +15 x31 + 23 x32 + 18 x33
sujeito a:x11 + x12 + x13 = 1
x21 + x22 + x23 = 1x31 + x32 + x33 = 1
x11 + x21 + x31 = 1x12 + x22 + x32 = 1
x13 + x23 + x33 = 1
xij≥ 0 ( i=1, 2, 3; j = 1, 2, 3 )
Resolução no LINDOMin 25x11 + 31x12 + 35x13 + 24x21 + 17x22 + 16x23 + 15x31 + 23x32 + 18x33
S.t.
x11 + x12 + x13 = 1
x21 + x22 + x23 = 1 Restrições de Máquinas
x31 + x32 + x33 = 1
x11 + x21 + x31 = 1
x12 + x22 + x32 = 1 Restrições de Empregados
x13 + x23 + x33 = 1
Problema de alocaçãoExemplo 2
Considere a necessidade de se alocar 5 trabalhadores a 5 tarefas. A matriz dos custos associados à realização de cada tarefa por trabalhador é a seguinte:
1 2 3 4 5
1 17,5 15 9 5,5 12
2 16 16,5 10,5 5 10,5
3 12 15,5 14,5 11 5,5
4 4,5 8 14 17,5 13
5 13 9,5 8,5 12 17,5
Formule o problema de alocação, com o objetivo de minimizar os custos de trabalho
Resolução no LINDOMin 17.5x11 + 15x12 + 9x13 + 5.5x14 + 12x15 + 16x21 + 16.5x22 + 10.5x23 + 5x24 + 10.5x25 + 12x31 + 15.5x32 + 14.5x33 + 11x34 + 5.5x35 + 4.5x41 + 8x42 + 14x43 + 17.5x44 + 13x45 + 13x51 + 9.5x52 + 8.5x53 + 12x54 + 17.5x55S.t. x11 + x12 + x13 + x14 + x15 = 1
x21 + x22 + x23 + x24 + x25 = 1
x31 + x32 + x33 + x34 + x35 = 1 Restrições de Trabalhadores
x41 + x42 + x43 + x44 + x45 = 1
x51 + x52 + x53 + x54 + x55 = 1
x11 + x21 + x31 + x41 + x51 = 1
x12 + x22 + x32 + x42 + x52 = 1
x13 + x23 + x33 + x43 + x53 = 1 Restrições de Tarefas
x14 + x24 + x34 + x44 + x54 = 1
x15 + x25 + x35 + x45 + x55 = 1
Problema de alocação generalizadaIntrodução
Dado n tarefas, m servidores e a capacidade de cada servidor, o problema de alocar essas tarefas aos
servidores, sem exceder a capacidade de cada
fornecedor, é denominada problema de alocação
generalizada.
Modelos de programação matemática utilizados em processos complicados de processos de roteamento de veículos tem obtido importantes resultados, inclusive com significativa redução de custos logísticos. Uma variante do problema de alocação, denominada problema de alocação capacitada, tornou-se uma eficiente ferramenta para auxiliar a solucionar problemas de roteamento de
veículos(vehicle routing).
Problema de alocação generalizadaModelagemModelagem
Parâmetros:
nn –– número de tarefas requeridas;mm –– número de servidores; ccijij –– custo de alocar uma tarefa i ao servidor j;bbjj –– unidades de recursos disponíveis para
servidor j;aaijij –– unidades do servidor i requeridas para
executar a tarefa j;
Problema de alocação generalizadaFormulação
∑∑= =
=n
i
m
jijij xcz
1 1
Minimizar
sujeito a:
∑=
=m
jijx
11 ni ,...,2,1 , =
Cada tarefa é executada apenas por um servidor
∑=
≤n
ijijij bxa
1
mj ,...,2,1 , =O requerimento da
capacidade do servidor não é excedido
},1,0{∈ijx nj ,...,2,1 , =ni ,...,2,1=
Problema de alocação generalizadaFormulação
Nesta formulação xij = 1 se a “tarefa” i está assinalada ao “servidor” j, caso contrário xij = 0 . A função objetivo cijrepresenta o custo de alocar uma tarefa i ao servidor j. O primeiro conjunto de restrições obriga que toda tarefa seja executada por exatamente um servidor e, finalmente, o segundo conjunto de restrições garante que a capacidade disponível no servidor j não seja ultrapassada.
O problema de alocação generalizada tem sido usado em vários problemas, tais como: localização capacitada, roteamento de veículos, roteamento de remoção de neve,
problema do caixeiro viajante e problema de alocação do vigor de vendas(sales force allocation).
Problema de alocação capacitadaAplicação
Uma importante aplicação deste problema na área de roteamento de veículos é alocar clientes a caminhões. Cada caminhão j é um “servidor” com a capacidade de bj e aij unidades (capacidade de caminhões) que serão utilizadas quando o cliente i for assinalado ao caminhão j. Um cliente é alocado ao caminhão se a rota for necessária ao caminhão. Por simplicidade, assume-se um caminhão com capacidade infinita e o objetivo é encontrar a rotade custo mínimo para que o caminhão saia do depósito de origem, percorra as n cidades, e retorne ao depósito inicial.
Problema de alocaçãoExemplo1
Sabendo-se que se n=4, m=2, b1=13 e b2=10,
Cji 1 2 3 4
1 2 7 20 5
2 11 7 2 5
Aji 1 2 3 4
1 3 6 5 7
2 2 4 10 4
Formule o problema de alocação generalizada, com o objetivo de minimizar os custos cij.
Problema de alocação generalizadaExemplo1 - Resolução
min 2x11 + 11x12 + 7x21 + 7x22 + 20x31 + 2x32 + 5x41 + 5x42
s.t.x11 + x12 = 1x21 + x22 = 1 Restrições dos Clientesx31 + x32 = 1x41 + x42 = 1
3x11 + 6x21 + 5x31 + 7x41 <= 13 Restrições dos Caminhões2x12 + 4x22 + 10x32 + 4x42 <= 10
EndINT 8
Problema de alocação capacitadaMatriz de restrições do problema
A matriz das restrições do problema e alocação capacitada para oexemplo apresenta a seguinte estrutura:
x11 x12 x13 x14 x21 x22 x23 x24 x31 x32 x33 x34
A=A=
Problema de alocação generalizadaExemplo1 - Resolução
Problema de alocaçãoExercício1
Um especialista em planejamento de viagens precisa alocar 4 caminhões à 3 rotas distintas que levam ao mesmo destino. Sabe-se que devido ao tráfego, no máximo 2 caminhões podem percorrer a mesma rota. A tabela a seguir mostra o custo de cada caminhão i percorrer a rota j.
O custo do caminhão i em percorrer a rota j é decorrente do pedágio pago na rota, do combustível gasto pelo caminhão,
e da localização inicial do caminhão.
Problema de alocaçãoExercício1
Rota / Rota / CaminhãoCaminhão
1 2 3
1 10 20 30
2 5 8 8
3 4 6 10
4 20 40 80
Formule o problema de alocação generalizada, com o objetivo de minimizar os custos do roteamento dos veículos.
Resolução usando o LINDOMin 10x11 + 20x12 + 30x13 + 5x21 + 8x22 + 8x23 + 4x31 + 6x32 + 10x33 + 20x41 + 40x42 + 80x43
S.t.
x11 + x12 + x13 = 1
x21 + x22 + x23 = 1
x31 + x32 + x33 = 1
x41 + x42 + x43 = 1
x11 + x21 + x31 + x41 <= 2
x12 + x22 + x32 + x42 <= 2
x13 + x23 + x33 + x43 <= 2