Problema de Designação - daroncho.com · Um problema de transporte é um caso específico de programação linear Portanto um Problema de Designação também é um caso de Problema

Problema de DesignaçãoMÉTODOS QUANTITATIVOS DE GESTÃO

MQG

Aula 5

Problema de TransportePROBLEMA DE DESIGNAÇÃO

2

Fatec Zona Leste | MQG | Prof Celio Daroncho |

Problema de Designação✓ Um Problema de Designação é um caso específico de um Problema de

Transporte

✓ Um problema de transporte é um caso específico de programação linear

✓ Portanto um Problema de Designação também é um caso de Problema de Programação Linear

Aula 05 - Problema de Designação 3


Consiste em designar✓ Uma origem a um destinos, de maneira ótima


2

1

2

33

Origens Destinos

1


Aplicações✓ Designar pessoas para tarefas ✓ Escalar vendedores para determinadas regiões de venda

✓ Designar máquinas para localizações✓ Qual equipamento para qual planta

✓ Designar produtos de uma fábrica para um determinado armazém✓ Qual produto para qual armazém

✓ Designar produtos de um armazém para um determinado distribuidor✓ Qual produto para qual CD

✓ Designar para maximizar receitas



Considerações1. O número de origens deve ser igual ao número de destinos (𝑛)

2. Cada origem deve ser designada para exatamente (e somente) um destino

3. Cada destino deve ser designado para exatamente (e somente) uma origem

4. Há um custo 𝑐𝑖𝑗 associado em designar a origem 𝑖 𝑖 = 1,2,…… . 𝑛 para o destino 𝑗 𝑗 = 1,2,… . . 𝑛

5. O objetivo é determinar como todas as 𝑛 designações devem ser realizadas para minimizar (ou maximizar) o custo (ou o lucro) total



Considerações1. O número de origens deve ser igual ao número de destinos (𝑛)

2. Cada origem deve ser designada para exatamente (e somente) um destino

3. Cada destino deve ser designado para exatamente (e somente) uma origem

4. Há um custo 𝑐𝑖𝑗 associado em designar a origem 𝑖 𝑖 = 1,2,…… . 𝑛 para o destino 𝑗 𝑗 = 1,2,… . . 𝑛

5. O objetivo é determinar como todas as 𝑛 designações devem ser realizadas para minimizar (ou maximizar) o custo (ou o lucro) total



Modelo


2

1

2

nm

Origens Destinos

1a1

a2

am

b1

b2

bn

Sendo que: 𝑎1, 𝑎2, … , 𝑎𝑚, 𝑏1, 𝑏2, … , 𝑏𝑛 = 1


Equacionamento do Problema✓ Minimizar

✓ Sujeito a


𝑧 =

𝑖=1

𝑚

𝑗=1

𝑛

𝑐𝑖𝑗, 𝑥𝑖𝑗

𝑖=1

𝑛

𝑥𝑖𝑗 = 𝑎𝑖 (𝑖 = 1, 2,… ,𝑚)

𝑗=1

𝑛

𝑥𝑖𝑗 = 𝑏𝑗 (𝑗 = 1, 2,… , 𝑛)

𝑥𝑖𝑗 = 1 𝑠𝑒 𝑖 𝑑𝑒𝑠𝑖𝑔𝑛𝑎𝑑𝑜 𝑝𝑎𝑟𝑎 𝑗; 𝑥𝑖𝑗 = 0 𝑐𝑎𝑠𝑜 𝑐𝑜𝑛𝑡𝑟á𝑟𝑖𝑜


Verificação✓ Como só é permitido uma alocação (designação) em cada linha e coluna

trata-se de um problema que poderá ser resolvido utilizando-se do algoritmo Simplex de Designação

✓ Antes de aplicar este algoritmo, deve-se verificar se o modelo está equilibrado✓ Ou seja, o número de origens deve ser igual ao número de destinos

✓ Caso isto não ocorra, deve-se construir origens ou destinos auxiliares, com custo de designação zero



Método1. Subtrair o menor elemento de cada linha dos elementos restantes

dessa linha

2. Subtrair o menor elemento de cada coluna dos outros elementos dessa mesma coluna

3. Testar se a solução é ótimaa. Traçar o número mínimo de retas que cubra todos os zeros do quadro de

soluções (horizontal ou vertical)

b. Se o número de retas for igual a n, número de linhas ou colunas, fazer uma atribuição ótima e seguir para o passo 5, caso contrario, siga para o passo 4



Método4. Procurar o menor elemento não coberto pelas linhas e subtrair

esse elemento dos demais não cobertosa. Some depois esse elemento (o menor não coberto) aos elementos que

estão na interseção das retas

b. Todos os demais elementos devem permanecer inalterados

c. Volte ao para o passo 3

5. Faça uma atribuição ótima4. Esta atribuição é feita achando-se onde os zeros estão situados no quadro

final



Observações✓ O problema de designação exige uma matriz m x m

✓ Se o número de linhas é menor que o número de colunas a matriz é completada com linhas com elementos nulos✓ Isso equivale a dizer que algumas das origens não serão designadas,

ou não atenderão destinos

✓ Se o número de colunas é menor que o número de linhas a matriz é completada com colunas com elementos nulos✓ Isso equivale a dizer que alguns destinos não serão designados, ou

não atendidos pelas origens


Problema de DesignaçãoEXEMPLO

14


Exemplo Enunciado✓ A empresa MRT têm quatro fábricas, localizadas em Los Angeles

(LA), Detroit (DE), New Orleans (NO) e Denver (DN) e quatro grandes centrais de distribuição, localizados em Miami (MI), St Luis (SL), Dallas (DA) e New York (NY)

✓ Sabendo que cada CD só pode ser abastecido por uma fábrica, e utilizando o método de designação, encontre o menor custo de distribuição

✓ O custo de transporte entre as fabricas e as centrais de distribuição são fornecidos conforme tabela abaixo.



Exemplo Tabela


Origem\Destino MI SL DA NY Oferta

LA 1 4 6 3 1

DE 9 7 10 9 1

NO 4 5 11 7 1

DN 8 7 8 5 1

Demanda 1 1 1 1 4


Exemplo Resolvendo1. Identificar o menor elemento em cada linha e subtrair este dos

demais elementos da linha



LA 1 4 6 3 1

DE 9 7 10 9 1

NO 4 5 11 7 1

DN 8 7 8 5 1

Demanda 1 1 1 1 4

1 – 1 = 04 – 1 = 36 – 1 = 53 – 1 = 2

Linha – 7

Linha – 4

Linha – 5


Exemplo Resolvendo2. Identificar o menor elemento em cada coluna



LA 0 3 5 2 1

DE 2 0 3 2 1

NO 0 1 7 3 1

DN 3 2 3 0 1

Demanda 1 1 1 1 4

Não consigo resolver o Destino Dallas


Exemplo Resolvendo3. Subtrair o menor elemento de cada coluna



LA 0 3 5 2 1

DE 2 0 3 2 1

NO 0 1 7 3 1

DN 3 2 3 0 1

Demanda 1 1 1 1 4

2

0

4

0

Não consigo resolver os Destinos

Miami e Dallas


Exemplo Resolvendo4. Testar a otimalidade traçando um n° mínimo de retas (horizontais

e verticais) que cubram todos os zeros da tabela



LA 0 3 2 2 1

DE 2 0 0 2 1

NO 0 1 4 3 1

DN 3 2 0 0 1

Demanda 1 1 1 1 4

Se o n° de retas for igual ao n° de linhas ou colunas,

pode-se fazer uma designação ótima

(ou solução ótima) NÃO É O CASO Nova iteração


Exemplo Resolvendo5. Escolher o menor elemento não coberto pelas retas e subtrair este

elemento de todos os demais elementos não cobertos pelas retas



LA 0 3 2 2 1

DE 2 0 0 2 1

NO 0 1 4 3 1

DN 3 2 0 0 1

Demanda 1 1 1 1 4

2 1 1

3 20


Exemplo Resolvendo6. Somar depois este elemento (valor 1) aos elementos que se

encontram na interseção das retas. Traçar novas retas.



LA 0 2 1 1 1

DE 2 0 0 2 1

NO 0 0 3 2 1

DN 3 2 0 0 1

Demanda 1 1 1 1 4

3

4

Nova configuração de retas = n° de linhas/colunas SOLUÇÃO ÓTIMA


Exemplo Resolvendo7. Obtenção da solução ótima



LA 0 2 1 1 1

DE 3 0 0 2 1

NO 0 0 3 2 1

DN 4 2 0 0 1

Demanda 1 1 1 1 4


Exemplo Resolvendo8. Calculando



LA 1 4 6 3 1

DE 9 7 10 9 1

NO 4 5 11 7 1

DN 8 7 8 5 1

Demanda 1 1 1 1 4

𝑍 = 1 + 10 + 5 + 5 = 21


Exercício Com vocês | 1


Origem\Destino F1 F2 F3 F4 Oferta

D1 1 4 6 3 1

D2 9 7 10 9 1

D3 4 5 11 7 1

D4 8 7 8 5 1

Demanda 1 1 1 1 4

O quadro abaixo representa os custos de transporte de uma máquina dos depósitos (Dx) para as fábricas onde deverão ser instaladas (Fx). Designar uma máquina para cada fábrica com o menor custo possível


Exercício Com vocês | 2


Origem\Destino 1 2 3 4 5 6

A 20 15 26 40 32 12

B 15 32 46 26 28 20

C 18 15 2 12 6 14

D 8 24 12 22 22 20

E 12 20 18 10 22 15

Uma empresa possui caminhões disponíveis nas cidades A,B,C,D e E. Alocar estes nas cidades 1, 2, 3, 4, 5 e 6, minimizando a quilometragem percorrida, com base na distância entre as cidades em km

MaximizaçãoPROBLEMA DE DESIGNAÇÃO

27


Maximização


✓ Procede-se da mesma maneira que no problema de transporte, ou seja, escolhe-se o valor máximo e subtrai-se dos demais valores

✓ A partir desta nova tabela se procede como no problema de minimização

✓ Quando a solução ótima é encontrada o valor máximo total será encontrado a partir dos valores unitários da tabela original

MaximizaçãoEXEMPLO

29


Exemplo Enunciado✓ O diretor de uma empresa precisa enviar quatro gerentes para

quatro lojas localizadas em cidades vizinhas, um para cada loja

✓ A seleção será realizada em função da eficiência obtida pelos vendedores da cidade

✓ O diretor atribuiu uma nota, conforme as vendas realizadas por cada um dos vendedores, durante um período de pesquisa e os resultados foram expressos na tabela abaixo

✓ Se o objetivo é maximizar as vendas, qual cidade deve ser atribuída a cada vendedor?



Exemplo Tabela


Cid. 1 Cid. 2 Cid. 3 Cid. 4

Vend. A 8 9 7 5

Vend. B 7 7 8 3

Vend. C 6 8 5 7

Vend. D 5 5 6 8


Exemplo Resolvendo1. Encontrar o maior valor e efetuar a subtração em todos os outros

elementos



Vend. A 8 9 7 5

Vend. B 7 7 8 3

Vend. C 6 8 5 7

Vend. D 5 5 6 8

9 – 8 = 19 – 9 = 09 – 7 = 29 – 5 = 4


Exemplo Resolvendo2. De agora em diante seguir os mesmos passos da minimização



Vend. A 1 0 2 4

Vend. B 2 2 1 6

Vend. C 3 1 4 2

Vend. D 4 4 3 1

MaximizaçãoEXERCÍCIO

34


Exercício Enunciado✓ Uma empresa de vendas atende quatro regiões e dispõe de quatro

vendedores a designar, um para cada região. As regiões não são igualmente ricas em seu potencial de vendas, a região I tem potencial de 60.000 vendas, a região II de 50.000, a região III de 40.000 e a região IV de 30.000.

✓ Os vendedores diferem em sua habilidade e, sob as mesmas condições, o vendedor A tem 70%, o vendedor B tem 50%, o vendedor C tem 50% e vendedor D tem 40% de eficiência.

✓ Se o objetivo e maximizar as vendas totais, qual deve ser a região atribuída a cada vendedor


Documents

Problema de Designação - daroncho.com · Um problema de transporte é um caso específico de programação linear Portanto um Problema de Designação também é um caso de Problema