Mantieni tutto organizzato con le raccolte
Salva e classifica i contenuti in base alle tue preferenze.
Uno dei problemi di ottimizzazione combinatoria più noti è il problema di assegnazione. Ecco un esempio: supponiamo che un gruppo di lavoratori debba eseguire una serie di attività e che per ogni worker e attività sia previsto un costo per l'assegnazione del worker all'attività.
Il problema è assegnare ogni worker al massimo a un'attività, senza che due worker
eseguano la stessa attività, riducendo al minimo il costo totale.
Puoi visualizzare questo problema dal grafico qui sotto, in cui ci sono quattro worker e quattro attività. I bordi rappresentano tutti i modi possibili
per assegnare worker alle attività. Le etichette ai bordi rappresentano i costi associati all'assegnazione dei lavoratori alle attività.
Un'assegnazione corrisponde a un sottoinsieme di perimetri, in cui ciascun worker ha al massimo un bordo che conduce all'esterno e nessun worker ha un bordo che conduce alla stessa attività. Di seguito è riportata una possibile assegnazione.
Il costo totale dell'assegnazione è 70 + 55 + 95 + 45 = 265.
La sezione successiva mostra come risolvere un problema di assegnazione, utilizzando sia il risolutore MIP sia quello CP-SAT.
Altri strumenti per risolvere problemi relativi ai compiti
OR-Tools fornisce anche un paio di altri strumenti per risolvere problemi di assegnazione,
che possono essere più veloci dei risolutori MIP o CP:
Tuttavia, questi strumenti possono risolvere solo tipi semplici di problemi relativi ai compiti.
Per i risolutori generici in grado di gestire un'ampia varietà di problemi (e abbastanza veloci per la maggior parte delle applicazioni), consigliamo i risolutori MIP e CP-SAT.
[[["Facile da capire","easyToUnderstand","thumb-up"],["Il problema è stato risolto","solvedMyProblem","thumb-up"],["Altra","otherUp","thumb-up"]],[["Mancano le informazioni di cui ho bisogno","missingTheInformationINeed","thumb-down"],["Troppo complicato/troppi passaggi","tooComplicatedTooManySteps","thumb-down"],["Obsoleti","outOfDate","thumb-down"],["Problema di traduzione","translationIssue","thumb-down"],["Problema relativo a esempi/codice","samplesCodeIssue","thumb-down"],["Altra","otherDown","thumb-down"]],["Ultimo aggiornamento 2024-08-09 UTC."],[[["The assignment problem focuses on optimally assigning workers to tasks to minimize the total cost, where each worker is assigned at most one task and no task is assigned to multiple workers."],["This problem can be visualized using a graph where edges represent worker-task assignments and edge labels represent the cost of each assignment."],["OR-Tools offers various solvers like MIP, CP-SAT, Linear Sum Assignment, and Minimum Cost Flow, but MIP and CP-SAT are recommended for their versatility and efficiency in handling a broader range of assignment problems."]]],["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"]]
