Asignación de tareas - Solución

Asignación de tareas - Solución#

Tags: Asignación, Variable binaria, Recurso

Enunciado#

El equipo de Principios de Optimización se encuentra realizando un rediseño estructural del curso. Dado el largo trabajo que este rediseño implica, los integrantes del equipo han definido diez responsabilidades que deben ser ejecutadas. Para esto, el equipo debe decidir cuál es la mejor asignación de responsabilidades a los diferentes integrantes del equipo para el periodo intersemestral.

Cada uno de los cinco miembros del equipo está en la capacidad de encargarse de cualquiera de estas diez responsabilidades, sin embargo, debido sus preferencias y habilidades, cada uno ha determinado el tiempo (en horas) que le tomará realizar cada una de las responsabilidades que le pueden ser asignadas. Además, cada uno de ellos cuenta con una disponibilidad horaria de acuerdo con su contrato y sus demás compromisos personales. La información descrita anteriormente se encuentra disponible en la Tabla 1.

Tabla 1. Tiempos de realización y disponibilidad (en horas)

	Integrantes
Responsabilidades	1	2	3	4	5
Diseño parciales	25	75	125	200	250
Diseño tareas	75	25	225	250	200
Diseño y grabación videos magistrales	50	125	100	175	225
Diseño talleres magistrales	100	50	250	225	175
Diseño jupyter notebooks	125	150	25	150	50
Grabación videos trabajo asistido	175	175	50	100	75
Edición videos trabajo asistido	225	200	175	25	150
Diseño talleres trabajo asistido	150	100	75	125	100
Diseño y grabación videos PulP	200	225	150	75	50
Edición videos PulP	250	250	200	50	125
Disponibilidad	200	150	150	100	75

Aparte de hacer un curso agradable y productivo para cada uno de los estudiantes, el equipo del curso se siente motivado y a gusto en el proceso de rediseño. Por lo anterior, cada uno ha definido el índice de preferencia asociado a realizar cada una de las responsabilidades. Este índice se encuentra en una escala de 1 a 10, correspondiendo 1 y 10 a la responsabilidad menos deseada y a la preferida, respectivamente. En la Tabla 2 se presenta esta información.

Tabla 2. Preferencias

	Integrantes
Responsabilidades	1	2	3	4	5
Diseño parciales	1	3	5	8	10
Diseño tareas	3	1	9	10	8
Diseño y grabación videos magistrales	2	5	4	7	9
Diseño talleres magistrales	4	2	10	9	7
Diseño jupyter notebooks	5	6	1	6	2
Grabación videos trabajo asistido	7	7	2	4	3
Edición videos trabajo asistido	9	8	7	1	6
Diseño talleres trabajo asistido	6	4	3	5	4
Diseño y grabación videos PulP	8	9	6	3	1
Edición videos PulP	10	10	8	2	5

El equipo de Principios de Optimización te ha pedido que plantees y resuelvas un modelo matemático que represente la situación.

Formulación#

a. Formula matemáticamente un modelo de optimización de forma general que represente la situación anterior. Defina clara y rigurosamente:

Conjuntos
Parámetros
Variables de decisión
Restricciones
Naturaleza de las variables
Función objetivo

Conjuntos#

\(I\): Integrantes
\(R\): Responsabilidades

Parámetros#

\(t_{ir}\): tiempo que le tomaría al integrante \(i\in I\) realizar la responsabilidad \(r\in R\)
\(d_{i}\): disponibilidad de tiempo del integrante \(i\in I\)
\(p_{ir}\): preferencia del integrante \(i\in I\) por realizar la responsabilidad \(r\in R\)

Variables de decisión#

\(x_{ir}: \begin{cases}1\text{,}&\text{ si el integrante }i\in I\text{ realiza la responsabilidad }r\in R\text{;}\\ 0\text{,} & \text{ d.l.c.} \end{cases}\)

Restricciones#

Cada responsabilidad se debe asignar a una persona \(r \in R\):

\[ \sum_{i\in I}x_{ir}=1, \forall r\in R; \]

Se debe respetar la limitación de tiempo de cada integrante \(i\in I\):

\[ \sum_{r\in R}t_{ir}\cdot x_{ir}\le d_i, \forall i\in I; \]

Naturaleza de las Variables#

A cada integrante \(i\in I\) solo se le puede asignar (1) o no (0) una responsabilidad \(r \in R\):

\[ x_{ir}\in\{0,1\},\forall i\in I, r\in R. \]

Función objetivo#

Se debe maximizar la preferencia satisfecha:

\[ \operatorname{máx}\ \sum_{i\in I}\sum_{r\in R}p_{ir}\cdot x_{ir} \]

Implementación#

b. Resuelve el modelo planteado utilizando la librería de PuLP en Python. ¿Cuál es la solución óptima del problema?

Librerías#

Importa la librería pulp para crear y resolver el modelo.

import pulp as lp

Conjuntos#

Define los conjuntos I y R que representan respectivamente los integrantes y las responsabilidades.

Recuerda que por conveniencia de preservar el orden de los elementos de los conjuntos, no siempre deberás definirlos con el tipo set.

# Integrantes
I = list(range(1, 6))

# Responsabilidades
R = [
    "Diseño parciales",
    "Diseño tareas",
    "Diseño y grabación videos magistrales",
    "Diseño talleres magistrales",
    "Diseño jupyter notebooks",
    "Grabación videos trabajo asistido",
    "Edición videos trabajo asistido",
    "Diseño talleres trabajo asistido",
    "Diseño y grabación videos PuLP",
    "Edición videos PuLP",
]

Parámetros#

Define o importa los parámetros del modelo.

# Tiempo que consume i en I en realizar r in R
t = {
    (1, "Diseño parciales"): 25,
    (2, "Diseño parciales"): 75,
    (3, "Diseño parciales"): 125,
    (4, "Diseño parciales"): 200,
    (5, "Diseño parciales"): 250,
    (1, "Diseño tareas"): 75,
    (2, "Diseño tareas"): 25,
    (3, "Diseño tareas"): 225,
    (4, "Diseño tareas"): 250,
    (5, "Diseño tareas"): 200,
    (1, "Diseño y grabación videos magistrales"): 50,
    (2, "Diseño y grabación videos magistrales"): 125,
    (3, "Diseño y grabación videos magistrales"): 100,
    (4, "Diseño y grabación videos magistrales"): 175,
    (5, "Diseño y grabación videos magistrales"): 225,
    (1, "Diseño talleres magistrales"): 100,
    (2, "Diseño talleres magistrales"): 50,
    (3, "Diseño talleres magistrales"): 250,
    (4, "Diseño talleres magistrales"): 225,
    (5, "Diseño talleres magistrales"): 175,
    (1, "Diseño jupyter notebooks"): 125,
    (2, "Diseño jupyter notebooks"): 150,
    (3, "Diseño jupyter notebooks"): 25,
    (4, "Diseño jupyter notebooks"): 150,
    (5, "Diseño jupyter notebooks"): 50,
    (1, "Grabación videos trabajo asistido"): 175,
    (2, "Grabación videos trabajo asistido"): 175,
    (3, "Grabación videos trabajo asistido"): 50,
    (4, "Grabación videos trabajo asistido"): 100,
    (5, "Grabación videos trabajo asistido"): 75,
    (1, "Edición videos trabajo asistido"): 225,
    (2, "Edición videos trabajo asistido"): 200,
    (3, "Edición videos trabajo asistido"): 175,
    (4, "Edición videos trabajo asistido"): 25,
    (5, "Edición videos trabajo asistido"): 150,
    (1, "Diseño talleres trabajo asistido"): 150,
    (2, "Diseño talleres trabajo asistido"): 100,
    (3, "Diseño talleres trabajo asistido"): 75,
    (4, "Diseño talleres trabajo asistido"): 125,
    (5, "Diseño talleres trabajo asistido"): 100,
    (1, "Diseño y grabación videos PuLP"): 200,
    (2, "Diseño y grabación videos PuLP"): 225,
    (3, "Diseño y grabación videos PuLP"): 150,
    (4, "Diseño y grabación videos PuLP"): 75,
    (5, "Diseño y grabación videos PuLP"): 25,
    (1, "Edición videos PuLP"): 250,
    (2, "Edición videos PuLP"): 250,
    (3, "Edición videos PuLP"): 200,
    (4, "Edición videos PuLP"): 50,
    (5, "Edición videos PuLP"): 125,
}

# Preferencia de i en I por r en R
p = {
    (1, "Diseño parciales"): 1,
    (2, "Diseño parciales"): 3,
    (3, "Diseño parciales"): 5,
    (4, "Diseño parciales"): 8,
    (5, "Diseño parciales"): 10,
    (1, "Diseño tareas"): 3,
    (2, "Diseño tareas"): 1,
    (3, "Diseño tareas"): 9,
    (4, "Diseño tareas"): 10,
    (5, "Diseño tareas"): 8,
    (1, "Diseño y grabación videos magistrales"): 2,
    (2, "Diseño y grabación videos magistrales"): 5,
    (3, "Diseño y grabación videos magistrales"): 4,
    (4, "Diseño y grabación videos magistrales"): 7,
    (5, "Diseño y grabación videos magistrales"): 9,
    (1, "Diseño talleres magistrales"): 4,
    (2, "Diseño talleres magistrales"): 2,
    (3, "Diseño talleres magistrales"): 10,
    (4, "Diseño talleres magistrales"): 9,
    (5, "Diseño talleres magistrales"): 7,
    (1, "Diseño jupyter notebooks"): 5,
    (2, "Diseño jupyter notebooks"): 6,
    (3, "Diseño jupyter notebooks"): 1,
    (4, "Diseño jupyter notebooks"): 6,
    (5, "Diseño jupyter notebooks"): 2,
    (1, "Grabación videos trabajo asistido"): 7,
    (2, "Grabación videos trabajo asistido"): 7,
    (3, "Grabación videos trabajo asistido"): 2,
    (4, "Grabación videos trabajo asistido"): 4,
    (5, "Grabación videos trabajo asistido"): 3,
    (1, "Edición videos trabajo asistido"): 9,
    (2, "Edición videos trabajo asistido"): 8,
    (3, "Edición videos trabajo asistido"): 7,
    (4, "Edición videos trabajo asistido"): 1,
    (5, "Edición videos trabajo asistido"): 6,
    (1, "Diseño talleres trabajo asistido"): 6,
    (2, "Diseño talleres trabajo asistido"): 4,
    (3, "Diseño talleres trabajo asistido"): 3,
    (4, "Diseño talleres trabajo asistido"): 5,
    (5, "Diseño talleres trabajo asistido"): 4,
    (1, "Diseño y grabación videos PuLP"): 8,
    (2, "Diseño y grabación videos PuLP"): 9,
    (3, "Diseño y grabación videos PuLP"): 6,
    (4, "Diseño y grabación videos PuLP"): 3,
    (5, "Diseño y grabación videos PuLP"): 1,
    (1, "Edición videos PuLP"): 10,
    (2, "Edición videos PuLP"): 10,
    (3, "Edición videos PuLP"): 8,
    (4, "Edición videos PuLP"): 2,
    (5, "Edición videos PuLP"): 5,
}

# Disponibilidad en tiempo de i en I
d = {
    1: 200,
    2: 150,
    3: 150,
    4: 100,
    5: 75,
}

Objeto del modelo#

Construye un problema al que luego agregarás las restricciones y la función objetivo.

problema = lp.LpProblem(name="Asignación", sense=lp.LpMinimize)

Variables de decisión#

Define las variables del problema de manera que estén contenidas en diccionarios indexados en los conjuntos de sus variables respectivas.

# Si i en I realiza r en R
x = {
    (i, r): lp.LpVariable(
        name=f"{i}_realiza_{r}", lowBound=0, upBound=None, cat=lp.LpBinary
    )
    for i in I
    for r in R
}

Función objetivo#

Agrega al problema la función objetivo. Recuerda que al definir el problema, ya definiste si este es de maximización o minimización.

problema += sum(p[i, r] * x[i, r] for i in I for r in R), "satisfaccion_total"

Restricciones#

Agrega al problema las restricciones del modelo.

# Se asigna cada tarea a una persona
for r in R:
    problema += (
        sum(x[i, r] for i in I) == 1,
        f"asigna_responsabilidad_{r}",
    )

# Se respeta la disponibilidad de horas de i en I
for i in I:
    problema += sum(t[i, r] * x[i, r] for r in R) <= d[i], f"disponibilidad_{i}"

Resolver el problema#

Invoca el optimizador. Este paso le asigna un valor a las variables incluidas en las restricciones o función objetivo del modelo.

problema.solve()

Welcome to the CBC MILP Solver 
Version: 2.10.8 
Build Date: May  6 2022 

command line - cbc /tmp/2ae50e8db7c44fe3a1b9baa598b944c6-pulp.mps timeMode elapsed branch printingOptions all solution /tmp/2ae50e8db7c44fe3a1b9baa598b944c6-pulp.sol (default strategy 1)
At line 2 NAME          MODEL
At line 3 ROWS
At line 20 COLUMNS
At line 271 RHS
At line 287 BOUNDS
At line 338 ENDATA
Problem MODEL has 15 rows, 50 columns and 100 elements
Coin0008I MODEL read with 0 errors
Option for timeMode changed from cpu to elapsed
Continuous objective value is 16 - 0.00 seconds
Cgl0003I 5 fixed, 0 tightened bounds, 0 strengthened rows, 0 substitutions
Cgl0003I 5 fixed, 0 tightened bounds, 1 strengthened rows, 0 substitutions
Cgl0003I 0 fixed, 0 tightened bounds, 1 strengthened rows, 0 substitutions
Cgl0004I processed model has 7 rows, 12 columns (12 integer (12 of which binary)) and 26 elements
Cutoff increment increased from 1e-05 to 0.9999
Cbc0038I Initial state - 0 integers unsatisfied sum - 0
Cbc0038I Solution found of 16
Cbc0038I Before mini branch and bound, 12 integers at bound fixed and 0 continuous
Cbc0038I Mini branch and bound did not improve solution (0.00 seconds)
Cbc0038I After 0.00 seconds - Feasibility pump exiting with objective of 16 - took 0.00 seconds
Cbc0012I Integer solution of 16 found by feasibility pump after 0 iterations and 0 nodes (0.00 seconds)
Cbc0001I Search completed - best objective 16, took 0 iterations and 0 nodes (0.00 seconds)
Cbc0035I Maximum depth 0, 0 variables fixed on reduced cost
Cuts at root node changed objective from 16 to 16
Probing was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
Gomory was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
Knapsack was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
Clique was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
MixedIntegerRounding2 was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
FlowCover was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
TwoMirCuts was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)
ZeroHalf was tried 0 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds)

Result - Optimal solution found

Objective value:                16.00000000
Enumerated nodes:               0
Total iterations:               0
Time (CPU seconds):             0.00
Time (Wallclock seconds):       0.00

Option for printingOptions changed from normal to all
Total time (CPU seconds):       0.00   (Wallclock seconds):       0.00

Imprimir resultados#

Antes de estudiar el óptimo del modelo, identifica en el estado del optimizador si pudo resolver el problema.

f"Estado del optimizador: {lp.LpStatus[problema.status]}"

'Estado del optimizador: Optimal'

Identifica también el valor de la función objetivo.

f"Satisfacción total: {lp.value(problema.objective)}"

'Satisfacción total: 16.0'

Por último, imprime de manera estructurada el valor de las variables de decisión y otras expresiones de interés.

for i in I:
    print(f"Integrante {i}:")
    for r in R:
        if lp.value(x[i, r]) >= 0.5:
            print("\t", r)

Integrante 1:
	 Diseño parciales
	 Diseño y grabación videos magistrales
Integrante 2:
	 Diseño tareas
	 Diseño talleres magistrales
Integrante 3:
	 Diseño jupyter notebooks
	 Grabación videos trabajo asistido
	 Diseño talleres trabajo asistido
Integrante 4:
	 Edición videos trabajo asistido
	 Edición videos PuLP
Integrante 5:
	 Diseño y grabación videos PuLP

Créditos#

Equipo Principios de Optimización
Autores: Juan Felipe Rengifo
Desarrollo: Juan Felipe Rengifo, Alejandro Mantilla
Última fecha de modificación: 08/04/2023

Asignación de tareas - Solución

Contents

Asignación de tareas - Solución#

Enunciado#

Formulación#

Conjuntos#

Parámetros#

Variables de decisión#

Restricciones#

Naturaleza de las Variables#

Función objetivo#

Implementación#

Librerías#

Conjuntos#

Parámetros#

Objeto del modelo#

Variables de decisión#

Función objetivo#

Restricciones#

Resolver el problema#

Imprimir resultados#

Créditos#