Практическая работа №2 / 0375_Yablokov_№2

from functools import reduce
from math import log10, pow, sqrt
import pandas as pd
from tabulate import tabulate
from cvxopt import matrix, glpk


def print_constraints(constraints, constr_names, var_names):
    """Выводит правую часть матрицы ограничений в виде таблицы."""
    data = dict(zip(constr_names, constraints))
    df = pd.DataFrame(data, index=var_names)
    print(tabulate(df, headers='keys', tablefmt='psql'))


def recalculate_raiting(r, task_coor, worker_coor):
    """
    Возвращает модифицированный рейтинг рабочего для каждой задачи
    с учетом расстояния.
    """
    x1, y1 = task_coor
    x2, y2 = worker_coor
    length = sqrt(pow(x2 - x1, 2) + pow(y2 - y1, 2))
    return round(1 - log10(length) + r, 2)


# Переменные
# mi - булева: взял ли работник задачу.
# m1-4 - первый работник, задачи 1-4;
# m5-8 - второй работник, задачи 1-4;
# и т.д.

INEQUALITIES_LIMITS_COUNT = 11
QUALITIES_LIMITS_COUNT = 4
WORKER_COUNT = 10
TASK_COUNT = 4
VAR_COUNT = 40
LOW_SALARY = 60
HIGH_SALARY = 100
# Рейтинг рабочих с 1 по 10
R = [0.85, 0.65, 0.59, 0.65, 0.35, 0.27, 0.65, 0.85, 0.47, 0.39]

# Координаты местонахождения рабочих и задач.
task_x = [6, 19, 12, 4]
task_y = [1, 18, 14, 7]
worker_x = [11, 10, 17, 13, 17, 0, 6, 0, 5, 8]
worker_y = [10, 15, 7, 11, 19, 9, 19, 19, 17, 13]

task_coor = list(zip(task_x, task_y))
worker_coor = list(zip(worker_x, worker_y))

# Пересчет коэффициентов целевой функции, где учитывается расстояние
# от задания до работника.
new_R = []
for i in range(WORKER_COUNT):
    for j in range(TASK_COUNT):
        # Задача максимизации - знак переменных меняется.
        new_R.append(-recalculate_raiting(R[i], task_coor[j], worker_coor[i]))

# Задаем коэффициенты целевой функции, не учитывающей расстояние
# между работником и задачей.
# Задача максимизации - знак переменных меняется.
a = [[-r] * 4 for r in R]
c = list(reduce(lambda a, b: a + b, a))

# Раскомментировать для решения второго пункта.
#c = new_R

# Задаем ограничения равенства.
A = []
# Каждое задание может взять только один человек.
A.append([1, 0, 0, 0] * 10)
A.append([0, 1, 0, 0] * 10)
A.append([0, 0, 1, 0] * 10)
A.append([0, 0, 0, 1] * 10)

# Задаем ограничения неравенства.
# Ограничение на суммарную зарплату.
a = [[LOW_SALARY if r < 0.7 else HIGH_SALARY] * 4 for r in R]
G = [list(reduce(lambda a, b: a + b, a))]

# Каждый человек может взять только одно задание.
for i in range(0, 10):
    G.append([1 if i*4 <= j < i*4 + 4 else 0 for j in range(VAR_COUNT)])


# Вывод ограничений равенств в виде матрицы.
indexes = [f'm({i // 4 + 1},{i % 4 + 1})' for i in range(VAR_COUNT)]
column_names = [f'Задача №{i + 1}' for i in range(TASK_COUNT)]
columns = A.copy()

print("Матрица ограничений равенств:")
print_constraints(columns, var_names=indexes, constr_names=column_names)

# Вывод ограничений неравенств в виде матрицы.
column_names = [f'Работник №{i + 1}' for i in range(WORKER_COUNT)]
column_names.append("Сумм. зарплата")
columns = G.copy()

print("Матрица ограничений неравенств:")
print_constraints(columns, var_names=indexes, constr_names=column_names)


# Правая часть матрицы ограничений неравенств.
h = [310]
h.extend([1] * (INEQUALITIES_LIMITS_COUNT - 1))

# Правая часть матрицы ограничений равенств.
b = [1] * QUALITIES_LIMITS_COUNT

assert(len(c) == VAR_COUNT)
assert(len(G[0]) == VAR_COUNT)
assert(len(A[0]) == VAR_COUNT)
assert(len(A) == QUALITIES_LIMITS_COUNT)
assert(len(b) == QUALITIES_LIMITS_COUNT)
assert(len(G) == INEQUALITIES_LIMITS_COUNT)
assert(len(h) == INEQUALITIES_LIMITS_COUNT)

c = matrix(c, tc='d')
G = matrix(G, tc='d')
A = matrix(A, tc='d')
h = matrix(h, tc='d')
b = matrix(b, tc='d')

B = set(range(VAR_COUNT))
status, solution = glpk.ilp(c=c, G=G.T, h=h, A=A.T, b=b, B=B)

# Вывод решения и расчет целевой функции.
m = [list(map(int, solution[i*4:i*4 + 4])) for i in range(10)]

print("\nРезультаты решения:")
objective = 0
cost = 0
for j in range(WORKER_COUNT):
    for i in range(TASK_COUNT):
        if m[j][i] != 0:
            print(f"{j+1}-ый работник взял {i+1} задачу;")
            objective += R[j]
            cost += LOW_SALARY if R[j] < 0.7 else HIGH_SALARY

print(f"\nЗначение целевой функции: {objective} единиц рейтинга.")
print(f"Суммарная стоимость работников: {cost} ДЕ.")