Tarea Programación
EJERCICIO: 5
GRUPO: 10
Ana David Cardells, Gonzalo Rodolfo Salomoni y Silvia Miralles Navarro
CODIFICACIÓN
V = vector de números enteros de m componentes. Donde V(j) = i si el grupo j realiza el proyecto i-ésimo.
VARIABLES
n = número de proyectos
m = número de grupos de trabajo
Presup = presupuesto para gastar en proyectos
Coste ij = coste del proyecto i si lo realiza el grupo j
F = Max Adequación
Adec ij = adecuación del proyecto i si lo realiza el grupo j
ALGORITMO (INTELIGENTE ALEATORIZADO)
1. L = {1,…,m} lista de grupos j . P = {1,...,n} lista de proyectos i ;V(j) = 0 ; j = 1, …, m;
2. Costeacum = 0, función objetivo f = 0.
3. Escogemos el grupo j = 1 y lo eliminamos de L
4. Hacemos una lista P’ en la que se añaden los tres proyectos con mayor Adec ij.
5. Mientras L ≠ ø
5.1. Escoger aleatoriamente uno de ellos y llamarlo i.
5.2. Si Costeacum + c(i) <= Presup . Sino eliminar i de P’ y añadir el siguiente proyecto con mayor
Adec ij
5.3
5.3.1. V(j) = i. f = f + Adec ij .
5.3.2. Costeacum = Costeacum + Coste ij .
5.3. 3 Eliminamos i de P’.
5.3.4. j = j + 1
5.4. Si P’ está vacío significa que no se puede asignar ningún proyecto a ese grupo
5.4.1. . j = j + 1
5. Proporcionamos V y la función objetivo f.
1. L = {1,…,m}
2. P = {1,…,n}
3. V(j) = 0
4. CosteAcum = 0
5. f = 0
6. Inicializa una lista de proyectos disponibles como P_disponibles = P
7. Para cada grupo j en L:
7.1. Hacer una lista P' de los 3 proyectos en P_disponibles con mayor Adec ij
7.2. Mientras P' no esté vacío:
7.2.1. Escoger aleatoriamente un proyecto i de P'
7.2.2. Si CosteAcum + coste(i,j) <= Presupuesto:
7.2.2.1. Asignar el proyecto i al grupo j: V(j) = i
7.2.2.2. f = f + Adec(i,j)
7.2.2.3. CosteAcum = CosteAcum + coste(i,j)
7.2.2.4. Eliminar i de P_disponibles
7.2.2.5. Eliminar i de P' (ya que ha sido asignado)
7.2.3. Si CosteAcum + coste(i,j) > Presupuesto:
7.2.3.1. Eliminar i de P' y añadir el siguiente proyecto de P_disponibles con mayor Adec ij
7.2.4. Si P' está vacío:
7.2.4.2. Romper el bucle y pasar al siguiente grupo.
8. Proporcionar V y la función objetivo f.
PYTHON
import numpy as np
# Inicializar datos de ejemplo
coste = np.array([[17, 23, 16, 34, 9],
[22, 28, 31, 24, 17],
[31, 27, 35, 29, 23],
[27, 32, 29, 32, 25],
[32, 28, 34, 29, 19],
[29, 16, 19, 18, 11],
[41, 33, 27, 36, 29]])
adecuacion = np.array([[8.3, 6.5, 1.5, 4.5, 4.6],
[5.1, 8.5, 9.5, 6.5, 6.5],
[6.5, 4.9, 6.4, 5.7, 4.8],
[4.0, 9.2, 6.5, 8.7, 8.6],
[9.4, 5.0, 6.3, 9.0, 6.5],
[2.3, 3.5, 6.0, 5.4, 6.5],
[4.5, 3.1, 8.8, 7.0, 7.3]])
presupuesto = 125
m, n = coste.shape
# Inicialización
V = [0] * m # Asignaciones de proyectos a grupos
coste_acum = 0 # Coste acumulado
f = 0 # Función objetivo
# Lista de proyectos disponibles
P_disponibles = list(range(n))
# Iterar sobre cada grupo
for j in range(m):
while True:
# Filtrar los proyectos que están disponibles
P_adecuados = [(i, adecuacion[i][j]) for i in P_disponibles]
# Ordenar por adecuación y tomar los 3 mejores
P_adecuados = sorted(P_adecuados, key=lambda x: x[1], reverse=True)[:3]
if not P_adecuados: # Si no hay proyectos disponibles
break
# Elegir aleatoriamente uno de los tres mejores
i = np.random.choice([p[0] for p in P_adecuados])
# Comprobar coste
if coste_acum + coste[i][j] <= presupuesto:
V[j] = i # Asignar el proyecto i al grupo j
f += adecuacion[i][j] # Actualizar la función objetivo
coste_acum += coste[i][j] # Actualizar coste acumulado
P_disponibles.remove(i) # Eliminar el proyecto de la lista de disponibles
else:
# Si el coste excede el presupuesto, eliminarlo de los adecuados
P_adecuados.remove((i, adecuacion[i][j]))
# Si no hay proyectos adecuados, salir del bucle
if not P_adecuados:
break
# Resultados
V, f, coste_acum
