Problema de designação PDF

Preview

Summary

Passo a passo ilustrado da montagem e solução de um problema de designação....

Description

Modelo de Rede: Problema da designação

O modelo da designação é uma particularidade do modelo de rede, pois nesse tipo de problema temos tarefas ou alocações: máquinas, funcionários e outros tipos de situações dessa natureza. Nesse tipo de modelo as variáveis de decisões são de a forma binária:

Ex: supor que uma fábrica tenha três máquinas para serem alocadas em quatro setores da empresa, de forma que sejam minimizados seus custos conforme tabela abaixo:

Mq/St

S1

S2

S3

S4

A1

13

16

12

11

A2

15

-

13

20

A3

5

7

10

6

Custo por setores: Designados:

Tarefas:

M -> custo alto M -> +infinito Min CT: 13x11 + 16x12 + 12x33 + 11x14 + 15x21 + Mx22 + 13x23 + 20x24 + 5x31 + 7x32 + 10x33 + 6x34

Designados:

A1: x11 + x12 + x13 + x14 = 1 A2: x21 + x22 +x23 + x24 = 1 A3: x31 + x32 + x33 + x34 = 1

Tarefas: S1: x11 + x21 + x31 =< 1 S2: x12 + x22 + x32 == 0; i = 1, 2, 3 J = 1, 2, 3, 4

Propriedades do problema de designação: I) O número de designadores e o número de tarefas deve ser o mesmo (na resolução). Caso não seja, cria-se um designado ou uma tarefa “fantasma” (dummy). II) Deve-se atribuir a cada designado exatamente uma tarefa; III) Há um custo associado a cada designado i (i =1,...,n) executando a tarefa j (j=1,...,n). IV) O objetivo é cij, ou seja, determinar como todas as designações devem ser feitas para minimizar o custo.

Algoritmo de resolução: I) Criar, caso seja necessário, uma designação ou tarefa (dummy) de forma que o modelo fique equilibrado. Atribuindo valor de custo igual a zero e sem realizar designação. II) Subtrai-se de cada coeficiente da linha o menor custo da própria linha. III) A designação será executada para as tarefas que apresentarem valor igual a 0 e que não sejam dos dummies.

S1

S2

S3

S4

A1

13

16

12

11

(-11)

A2

15

M

13

20

(-13)

A3

5

7

10

6

(-5)

D4

0

0

0

0

(-0)

Nova tabela:

S1

S2

S3

S4

A1

2

5

1

0

A2

2

M

0

7

A3

0

2

5

1

D4

0

0

0

0

Resolução: A1 -> S4 A2 -> S3 A3 -> S1 CT = 11 + 13 + 5 CT = 29...