Designação pcp

DESIGNAÇÃO
Introdução Um caso especial do modelo de transportes é aquele em que cada origem tem uma unidade disponível e cada destino necessita também de uma unidade. É o caso de escalar vendedores para regiões de vendas, máquinas para diversos locais etc. Essa característica torna o algoritmo de soluções bastante simples. Antes de aplicá-lo, devemos verificar se o modelo está equilibrado. No modelo de designação, o número de origens deve ser igual ao número de destinos devido a sua característica. Caso isso não ocorra, devemos construir origens ou destinos auxiliares, com custo de transferência zero. Exemplo: o quadro representa os custos de transporte de uma máquina dos locais de depósito para as fábricas onde deverão ser instaladas. Designar uma máquina para cada fábrica com o menor custo total possível: F1 L1 L2 L3 L4 Descrição do Algoritmo a. Subtrair de cada linha seu menor valor. Em seguida fazer o mesmo com as colunas. Cada linha e cada coluna deverá então apresentar pelo menos um elemento nulo.
Subtrair o menor número de cada linha

F2 12 12 16 12

F3 15 13 19 13

F4 16 18 15 15

10 14 10 14

F1 0 2 0 2

F2 2 0 6 0

F3 5 1 9 1

F4 6 6 5 3

L1 L2 L3 L4

Pesquisa Operacional

Prof. Célio Moliterno

Subtrair o menor número de cada coluna

F1 0 2 0 2

F2 2 0 6 0

F3 4 0 8 0

F4 3 3 2 0

L1 L2 L3 L4

b. Designar origens para destinos nas células em que aparece o elemento nulo. Dar preferência a linhas ou colunas que tenham apenas um zero disponível. Cada designação efetuada invalida os outros zeros na linha e na coluna da célula designada. Se a designação se completa, o problema está resolvido. F1 L1 L2 L3 L4
0

F2 2
0

F3 4 0 8 0

F4 3 3 2
0

2 0 2

6 0

A designação não se completou devido a origem 3 e ao destino 3, então: c. Cobrir os zeros da tabela com o menor número de linhas possível. Isto pode ser feito da seguinte forma: • • • • marcar as linhas sem designação; nas linhas marcadas, marcar as colunas