Cap tulo V

6. Problemas de afectação
6.1 Introdução e definição de problema de afectação
Um problema de transporte de dimensão (nxn), em que as variáveis podem tomar apenas os valores 0 ou 1, e em que todas as necessidades e todas as disponibilidades são unitárias, designa-se por problema de afectação. Um exemplo típico de um problema de afectação consiste na distribuição de n trabalhadores por n tarefas para que cada trabalhador execute apenas uma tarefa, e que cada tarefa seja executada apenas por um trabalhador, sendo conhecidos os custos (ou os benefícios) da realização de cada tarefa por cada trabalhador.
Num problema deste tipo existem n! soluções possíveis, pelo que é manifestamente inconveniente, ou mesmo impossível, encontrar a solução óptima por tentativas. Para um problema que envolvesse 5 tarefas seria necessário procurar a solução óptima entre 120 soluções possíveis.
Um problema de afectação, tal como um problema de transportes pode ser formulado em termos de programação linear.
Considere-se que xij (i =1,2,...,n; j = 1,2,...,n) representa a afectação do trabalhador i à tarefa j. Esta variável toma o valor 1 se o trabalhador i for efectivamente associado à tarefa j, e toma o valor 0 no caso contrário. O custo de o trabalhador i realizar a tarefa j representa-se por cij . Assim, pode formular-se o seguinte problema de
PL:
n

n

Minimizar F   cij xij i 1 j 1

Sujeito a: n x j 1

ij

n

x i 1

ij

 1 (i  1,2,..., n)

 1 ( j  1,2,..., n)

xij  0 ou 1 (i, j  1,2,..., n)

A última restrição do problema formulado, não é facilmente tomada em conta por um algoritmo de PL, podendo tirar-se partido da estrutura particular do problema de
52

afectação para desenvolver um algoritmo específico, que se designa por Método
Húngaro.
Este método tem por base o facto de a solução óptima de um problema de afectação não ser alterada se for adicionada (ou subtraída) a mesma quantidade a todos os elementos de uma qualquer linha ou coluna da matriz de custos.
O Método