Exemplos de modelagem da primeira aula
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.