Atribuição
Mantenha tudo organizado com as coleções
Salve e categorize o conteúdo com base nas suas preferências.
Um dos problemas de otimização combinatória mais conhecidos é o
problema de atribuição. Veja um exemplo: suponha que um grupo de workers precise executar um conjunto de tarefas e, para
cada worker e tarefa, há um custo para atribuir o worker à tarefa.
O problema é atribuir cada worker a no máximo uma tarefa, sem dois workers
executando a mesma tarefa, minimizando o custo total.
É possível visualizar esse problema no gráfico abaixo, no qual há quatro workers e quatro tarefas. As bordas representam todas as maneiras possíveis de atribuir workers
a tarefas. Os identificadores nas bordas são os custos de atribuir workers a tarefas.
Uma atribuição corresponde a um subconjunto das arestas, em que cada worker tem no
máximo uma borda que sai da frente, e não há dois workers com bordas que levam à mesma
tarefa. Uma possível atribuição é mostrada abaixo.
O custo total da atividade é de 70 + 55 + 95 + 45 = 265.
A próxima seção mostra como resolver
um problema de atribuição usando o solucionador MIP e CP-SAT.
Outras ferramentas para resolver problemas na atribuição
O OR-Tools também fornece algumas outras ferramentas para resolver problemas de atribuição,
que podem ser mais rápidas do que os solucionadores MIP ou CP:
No entanto, essas ferramentas só podem resolver tipos simples de problemas de atribuição.
Portanto, para solucionadores gerais que podem lidar com uma grande variedade de problemas (e são rápidos o suficiente para a maioria dos aplicativos), recomendamos os solucionadores MIP e CP-SAT.
[[["Fácil de entender","easyToUnderstand","thumb-up"],["Meu problema foi resolvido","solvedMyProblem","thumb-up"],["Outro","otherUp","thumb-up"]],[["Não contém as informações de que eu preciso","missingTheInformationINeed","thumb-down"],["Muito complicado / etapas demais","tooComplicatedTooManySteps","thumb-down"],["Desatualizado","outOfDate","thumb-down"],["Problema na tradução","translationIssue","thumb-down"],["Problema com as amostras / o código","samplesCodeIssue","thumb-down"],["Outro","otherDown","thumb-down"]],["Última atualização 2024-08-09 UTC."],[],["The content describes the assignment problem, a combinatorial optimization challenge where workers are assigned to tasks to minimize total cost. Each worker is assigned to at most one task, and each task is done by at most one worker. The example shows how the problem can be represented graphically, with edges representing possible assignments and their costs. The total cost is calculated by adding up the costs of the assigned edges. OR-Tools offer multiple tools to solve such problems, among which the MIP and CP-SAT are the most general.\n"]]
