El problema de asignar el número mínimo de ejecutores

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 15 de agosto de 2017; las comprobaciones requieren 6 ediciones .

En matemáticas aplicadas , la tarea de asignar un número mínimo de ejecutantes se entiende como un problema de optimización combinatoria que generaliza el problema de cubrir un conjunto y es similar en formulación al problema de asignación .

En este problema, el conjunto de trabajadores tiene un tamaño no necesariamente igual al tamaño del conjunto de puestos de trabajo. En este caso, se puede asignar un ejecutor para realizar varios trabajos al mismo tiempo, y solo se asigna un ejecutor a cada trabajo. Existe un presupuesto total para la ejecución de todas las actividades, que es la restricción de asignación. Se requiere encontrar tal designación de artistas para la realización del trabajo de modo que el número de artistas involucrados en la realización del trabajo sea mínimo y no exceda el presupuesto asignado para todo el complejo de obras.

Definición

Hay n ejecutantes y m trabajos. Para cada par de ejecutante y obra, se da el costo de realizar la obra . Existe un presupuesto general para la ejecución de todo el complejo de obras. La solución es un subconjunto de ejecutores U y distribución de asignaciones de ejecutores de U entre trabajos. La decisión es aceptable si se asignan ejecutores para todas las obras y el monto de los costos para esto no excede el presupuesto . Se requiere minimizar el número de ejecutantes asignados ( L ). En otras palabras, se requiere elegir el conjunto mínimo (en términos de poder) de ejecutantes que juntos pueden realizar todo el trabajo. $w_{i,j}$ $w$ $w$

El problema se puede resolver dividiéndolo en dos problemas:

Selección del número mínimo de ejecutantes que juntos podrán completar todo el trabajo y cumplir con el presupuesto . Este problema es NP-difícil ya que es una generalización del problema de cobertura de conjunto NP-completo . $w$
Cita en un grupo seleccionado de artistas para el trabajo.

Matemáticamente, el problema de asignar el número mínimo de ejecutantes se puede formular de la siguiente manera [1] :

minimizar

{\displaystyle L=\mid U\mid =\sum _{i=1}^{n}\max _{j=1}^{m}x_{ij))

sujeto a

\sum _{i=1}^{n}\sum _{j=1}^{m}w_{ij}x_{ij}\leq w.

\sum _{i=1}^{n}x_{ij}=1\qquad j=1,\ldots,m

;

x_{ij}\in \{0,1\}\qquad i=1,\ldots,n,\quad j=1,\ldots,m

En esta configuración, la función objetivo del problema no es lineal, lo que no permite encontrar directamente la solución óptima utilizando métodos de programación lineal exactos , incluido el método simplex . Sin embargo, la tarea se puede linealizar mediante la inclusión de variables adicionales , mostrando el hecho de la selección en el grupo del ejecutante . También necesita enlazar variables y . Entonces la función objetivo tomará la forma ${\ Displaystyle y_ {yo}}$ $i$ $y_{i}\in \{0,1\}\qquad i=1,\ldots,n$ ${\ Displaystyle y_ {yo}}$ $x_{ij}$

minimizar _

{\displaystyle L=\mid U\mid =\sum _{i=1}^{n}y_{i))

La conexión de variables se puede especificar mediante la siguiente condición:

y_{i}\leq \sum _{j=1}^{m}x_{ij}\leq my_{i}\qquad i=1,\ldots,n

Algoritmos aproximados

Para resolver rápidamente problemas de grandes dimensiones, es recomendable utilizar algoritmos aproximados: el algoritmo del número máximo de elementos mínimos (MCME) y el algoritmo del número máximo de elementos admisibles (MCDE) [2] .

Véase también

Notas

↑ Kataev A.V., Kataeva T.M., Kozhenko Ya.V. Kataev A. V., Kataeva T. M., Kozhenko Ya. V. Optimización del tamaño del equipo del proyecto: herramientas económicas y matemáticas // Competitividad en el mundo global: economía, ciencia, tecnología. 2016. - Nº 8-3 (22). – págs. 101-104
↑ Kataev AV, Kataeva T.M. Gestión de proyectos basada en una red dinámica de socios: monografía. - Rostov-on-Don - Taganrog: Editorial de la Universidad Federal del Sur, 2017. - 125 p.