Blog‎ > ‎

Problema da designação

postado em 28 de nov de 2012 13:12 por João Flávio de Freitas Almeida   [ 17 de abr de 2014 07:34 atualizado‎(s)‎ ]

O problema de designação é um dos problemas clássicos da área de otimização combinatória em Pesquisa Operacional. Uma forma de descrever o problema é usando o exemplo de designação de atividades às pessoas. A atividade deve ser designada a apenas uma pessoa, e cada pessoa pode ter no máximo uma atividade. Existe um valor associado a cada possível designação de cada atividade a cada pessoa. O problema consiste em encontrar a melhor designação em termos de valor. Se o valor é custo, busca-se encontrar a designação com custo mínimo, se for lucro, o problema consiste em encontrar a designação com lucro máximo.


Uma versão geral do problema de designação é o problema de designação generalizado, onde cada atividade deve ser atribuída a apenas uma pessoa, mas uma pessoa pode receber mais que uma atividade. O problema é encontrar a melhor designação de atividades às pessoas respeitando a capacidade máxima de processamento (execução das atividades) de cada pessoa. Uma versão especialista do problema de designação é o problema de designação quadrático. Esse problema é comumente aplicado a problemas de localização de facilidades. O modelo deve representar o seguinte problema real logístico: “Existem facilidades e localizações. Para cada par de localizações uma distância é especificada, e para cada par de facilidades um fluxo é especificado (ex: quantidade de materiais transportados de uma facilidade a outra). O problema consiste em designar todas as facilidades às diferentes localizações de forma que o custo total, representado pelo fluxo de materiais multiplicado pelas distâncias, seja mínimo.