Problema de asignación de cuello de botella lineal
En la optimización combinatoria , un campo dentro de las matemáticas, el problema de asignación de cuello de botella lineal ( LBAP ) es similar al problema de asignación lineal . [1]
El término " cuello de botella " se explica por un tipo común de aplicación del problema, donde el costo es la duración de la tarea realizada por un agente. En esta configuración, el "costo máximo" es la "duración máxima", que es el cuello de botella para minimizar el cronograma del trabajo general.
Por lo general, la función de peso se ve como una matriz cuadrada de valor real C , por lo que la función de costo se escribe como:
Sea el valor óptimo de la función objetivo para el problema con n agentes y n tareas. Si los costos se muestrean de la distribución uniforme en (0,1), entonces [2]
