Problema de alocação de recursos humanos (Dantzig):

Numa empresa o setor de RH recebeu a tarefa de recrutar 70 pessoas para preencher 70 vagas. Ao avaliar cada candidato o setor definiu parâmetros de adequação a_{i,j} que representam quão bem o candidato i se sairia ao preencher a vaga j. O problema é definir a atribuição de candidatos às vagas de modo a maximizar a adequação da atribuição.

Número de atribuições = 70! > 10^100 > # estimado de partículas elementares no universo (impossível fazer força bruta!)

Por mais tentador que seja usar alguma técnica gulosa, também não vai funcionar (ex. simples: a_{i,i} = 1, a_{1,2}=10 e a_{i,j}=0 no restante).

Ideia do Dantzig:

seja x_{i,j} = 1 se o candidato i for atribuído à vaga j,
               0 caso contrário

Restrições:

cada vaga é preenchida por exatamente uma pessoa: sum_i(x_{i,j}) = 1

cada pessoa é atribuída a exatamente uma vaga: sum_j(x_{i,j}) = 1

x_{i,j}\in {0,1} (na verdade dá pra relaxar pra 0<=x_{i,j}<=1 e procurar soluções entre os vértices).

Objetivo: maximizar a expressão sum_i(sum_j(a_{i,j}*x_{i,j})).


------------------------------------------------------------------------------


Problema de transporte:

A Ambev trabalha com K marcas de cerveja, distribuídas a partir de M centros de estocagem a N pontos de revenda. Cada centro de estocagem m possui E_{k,m} litros da cerveja k, e cada ponto de revenda n deve atender a uma demanda de D_{k,n} litros da cerveja k. O custo por litro do envio de cerveja do centro de estocagem m ao ponto de revenda n é C_{m,n}, independentemente do tipo de cerveja. Encontre a maneira mais barata de distribuir toda a cerveja demandada pelos pontos de revenda.

Solução:

x_{k,m,n} = quantidade de cerveja k enviada do centro m ao ponto n.

Restrições:

limite de estoque: sum_n(x_{k,m,n}) <= E_{k,m}, para cada cerveja k=1,...,K e para cada centro m=1,...,M  (K*M restrições)

suprimento da demanda: sum_m(x_{k,m,n}) = D_{k,n}, para cada cerveja k=1,...,K e para cada ponto n=1,...,N (K*N restrições)

quantidades têm que ser não-negativas: x_{k,m,n}>=0, para todo k,m,n

Objetivo: minimizar custo sum_m(sum_n(C_{m,n}*sum_k(x_{k,m,n})))

Obs.1: a restrição de sinal pode parecer estúpida, mas a falta dela poderia gerar soluções bizarras se um custo C_{m,n} fosse muito maior que os demais, a ponto de valer a pena enviar -1000 unidades neste caminho e compensar enviando outras 1000 unidades de outros centros.

Obs.2: como não existe interações entre as marcas de cerveja, este problema poderia ser resolvido separadamente como k problemas menores. Não seria este o caso se houvesse alguma restrição de capacidade (por exemplo, tamanho dos caminhões) associada aos arcos {m,n}, por exemplo sum_k(x_{k,m,n})<=C_{m,n} para todo m,n.

Última atualização: sábado, 16 mar. 2013, 16:47