Organiza tus páginas con colecciones
Guarda y categoriza el contenido según tus preferencias.
Uno de los problemas de optimización combinatoria más conocidos es el problema de asignación. Por ejemplo, supongamos que un grupo de trabajadores necesita realizar un conjunto de tareas y que hay un costo por asignar el trabajador a cada tarea.
El problema es asignar a cada trabajador como máximo una tarea, sin que dos trabajadores realicen la misma tarea, y, al mismo tiempo, se minimiza el costo total.
Puedes visualizar este problema en el siguiente gráfico, en el que hay cuatro trabajadores y cuatro tareas. Los perímetros representan todas las formas posibles de asignar trabajadores a tareas. Las etiquetas en los perímetros indican los costos de asignar trabajadores a las tareas.
Una asignación corresponde a un subconjunto de bordes, en el que cada trabajador tiene como máximo un borde que sale y no hay dos trabajadores que tengan bordes que dirijan a la misma tarea. A continuación, se muestra una posible tarea.
El costo total de la asignación es de 70 + 55 + 95 + 45 = 265.
En la siguiente sección, se muestra cómo resolver un problema de asignación usando el solucionador de MIP y el solucionador de problemas CP-SAT.
Otras herramientas para resolver problemas de tareas
Las herramientas OR también proporcionan algunas otras herramientas para resolver problemas de tareas, que pueden ser más rápidas que las soluciones MIP o CP:
Sin embargo, estas herramientas solo pueden resolver tipos simples de problemas de asignación.
Por lo tanto, en el caso de los solucionadores generales que pueden manejar una amplia variedad de problemas (y son lo suficientemente rápidos para la mayoría de las aplicaciones), recomendamos los solucionadores MIP y CP-SAT.
[[["Fácil de comprender","easyToUnderstand","thumb-up"],["Resolvió mi problema","solvedMyProblem","thumb-up"],["Otro","otherUp","thumb-up"]],[["Falta la información que necesito","missingTheInformationINeed","thumb-down"],["Muy complicado o demasiados pasos","tooComplicatedTooManySteps","thumb-down"],["Desactualizado","outOfDate","thumb-down"],["Problema de traducción","translationIssue","thumb-down"],["Problema con las muestras o los códigos","samplesCodeIssue","thumb-down"],["Otro","otherDown","thumb-down"]],["Última actualización: 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"]]
