06-Designação



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.

FONTE: 

Arenales, M. Armentano, V. Morabito, R. Yanasse, H. Pesquisa Operacional para cursos de engenharia, Ed. Campus, 2007

Wikipedia: http://en.wikipedia.org/wiki/Assignment_problem

Exercício do vídeo: 

Otimização em alocação de equipes

Um hospital trabalha com atendimento variável em demanda durante as 24 horas do dia. As necessidades distribuem-se segundo a tabela abaixo:

 Turno de Trabalho HorárioMínimo de enfermeiro(a)s 
 1 08h às 12h 50
 2 12h às 16h 60
 3 16h às 20h 50
 4 20h às 00h 40
 5 00h às 04h 30
 6 04h às 08h 20

O horário de trabalho de um enfermeiro é de oito horas quando ele entra nos turnos  1,2,3,4 e 6. O enfermeiro que entra no turno 4 recebe uma gratificação de 50% sobre o salário e o enfermeiro que entra no turno 5 trabalha apenas quatro horas.

Veja a elaboração do modelo de programação linear inteira que minimiza o gasto com a mão de obra.