Угорський алгоритм, або про те, як математика допомагає у розподілі призначень

Привіт, друзі! У цій статті хотів би розповісти про цікавий алгоритм з дисципліни «Дослідження операцій» а саме про Угорський метод і як з його допомогою вирішувати задачі про призначення. Трохи торкнуся теорії про те, в яких випадках і для яких завдань застосуємо даний алгоритм, поетапно розберу його на вигаданому мною прикладі, і поділюся своїм скромним начерком коду його реалізації на мові R. Приступимо!

Пару слів про метод

Для того щоб не розписувати багато теорії з математичними термінами та визначеннями, пропоную розглянути кілька варіантів побудови задачі про призначення, і я думаю Ви відразу зрозумієте в яких випадках застосовується Угорський метод:

  • Задача про призначення працівників на посади. Необхідно розподілити працівників на посади так, щоб досягалася максимальна ефективність, або були мінімальні витрати на роботу.
  • Призначення машин на виробничі секції. Розподіл машин так, щоб при їх роботі виробництво було максимально прибутковим, або витрати на їх утримання мінімальні.
  • Вибір кандидатів на різні вакансії за оцінками. Цей приклад розберемо нижче.

Як Ви бачите, варіантів для яких застосуємо Угорський метод багато, при цьому подібні задачі виникають у багатьох сферах діяльності.

У підсумку задача повинна бути вирішена так, щоб один виконавець (людина, машина, знаряддя, …) міг виконувати тільки одну роботу, і кожна робота виконувалася тільки одним виконавцем.

Необхідна і достатня умова розв’язання задачі – це її закритий тип. Тобто коли кількість виконавців = кількістю робіт (N=M). Якщо ж ця умова не виконується, то можна додати вигаданих виконавців, або вигадані роботи, для яких значення в матриці будуть нульовими. На вирішення завдання це ніяк не вплине, лише додасть їй той необхідний закритий тип.

Step-by-step алгоритм на прикладі

Постановка задачі: Нехай намічається важлива наукова конференція. Для її проведення необхідно налаштувати звук, світло, зображення, зареєструвати гостей і підготуватися до перерв між виступами. Для цієї задачі є 5 організаторів. Кожен з них має певні оцінки виконання тієї чи іншої роботи (припустимо, що ці оцінки виставлені як середнє арифметичне за відгуками їх співробітників). Необхідно розподілити організаторів так, щоб сумарна оцінка була максимальною. Завдання має наступний вигляд:

Читайте також  Математична модель фонеми людського голосу

Якщо завдання вирішується на максимум (як в нашому випадку), то в кожному рядку матриці необхідно знайти максимальний елемент, його ж відняти з кожного елемента відповідного рядка і помножити всю матрицю на -1. Якщо завдання вирішується на мінімум, то цей крок необхідно пропустити.

В кожному рядку і в кожному стовпці повинен бути тільки один вибраний нуль. (тобто коли вибрали нуль, то інші нулі в цьому рядку або стовпці вже не беремо до уваги). У цьому випадку це зробити неможливо:

(Якщо завдання вирішується на мінімум, то необхідно починати з цього кроку). Продовжуємо рішення далі. Редукція матриці по рядках (шукаємо мінімальний елемент в кожному рядку і віднімаємо його з кожного елемента відповідно):

Т. до. все мінімальні елементи – нульові, то матриця не змінилася. Проводимо редукцію по стовпцях:

Знову ж дивимося у кожному стовпці і в кожному рядку був тільки один вибраний нуль. Як видно нижче, у цьому випадку це зробити неможливо. Представив два варіанти, як можна вибрати нулі, але жоден з них не дав потрібний результат:

Продовжуємо рішення далі. Викреслюємо рядки і стовпці, які містять нульові елементи (ВАЖЛИВО! Кількість закреслювань повинно бути мінімальним). Серед решти елементів шукаємо мінімальний, віднімаємо його з решти елементів (які не закреслені) і додаємо до елементів, які розташовані на перетині вилучених рядків і стовпців (те, що позначено зеленим – там віднімаємо; те, що зазначено золотистим – там підсумовуємо; те, що не зафарбовано – не чіпаємо):

Як тепер видно, в кожному стовпці і рядку є тільки один вибраний нуль. Рішення завдання завершуємо!

Підставляємо в початкову таблицю розташування вибраних нулів. Таким чином ми отримуємо оптимум, або оптимальний план, при якому організатори розподілені по роботах і сума оцінок вийшла максимальної:

Читайте також  Як зробити презентацію: на комп'ютері в Power Point

Якщо ж ви вирішуєте задачу і у вас досі неможливо вибрати нулі так, щоб в кожному стовпці і рядку був тільки один, тоді повторюємо алгоритм з того місця де проводилася редукція по рядках (мінімальний елемент у кожному рядку)

Реалізація мовою програмування R

Угорський алгоритм реалізував за допомогою рекурсій. Буду сподіватися що мій код не буде викликати труднощів. Для початку необхідно скомпілювати три функції, а потім починати розрахунки.
Дані для розв’язання задачі беруться з файлу example.csv який має вигляд:


Код додав у спойлер бо стаття була б занадто великою з-за нього

#Підключаємо бібліотеку для зручності розрахунків
library(dplyr)

#Зчитуємо csv фаил (перший стовпчик - назви рядків; перший рядок - назви стовпців)
table <- read.csv("example.csv",header=TRUE,row.names=1,sep=";")

#Проводимо розрахунки
unique_index <- hungarian_algorithm(table,T)

#Виводимо
cat(paste(row.names(table[as.vector(unique_index$row),])," - ",names(table[as.vector(unique_index$col)])),sep = "n")

#Вважаємо оптимальний план
cat("Оптимальне значення -",sum(mapply(function(i, j) table[i, j], unique_index$row, unique_index$col, SIMPLIFY = TRUE)))



#____________________Алгоритм угорського методу__________________________________

hungarian_algorithm <- function(data,optim=F){

#Якщо optim = T, то буде шукатися максимальне оптимальне значення
if(optim==T)
{
 data <- data %>% 
 apply(1,function(x) (x-max(x))*(-1)) %>% 
 t() %>% 
as.data.frame()
 optim <- F
}

#Редукція матриці по рядках
 data <- data %>%
 apply(1,function(x) x-min(x)) %>% 
 t() %>% 
as.data.frame()

#Знаходження індексів усіх нулів
 zero_index <- which(data==0, arr.ind = T)

#Знаходження всіх "неповторюваних" нулів зліва-направо
 unique_index <- from_the_beginning(zero_index)

#Якщо кількість "неповторюваних" нулів не дорівнює кількості рядків у вихідній таблиці, то..
if(nrow(unique_index)!=nrow(data))
#..Шукаємо "неповторювані" нулі справа-наліво
 unique_index <- from_the_end(zero_index)

#Якщо все ще не дорівнює, то продовжуємо алгоритм далі
if(nrow(unique_index)!=nrow(data))
{

#Редукція матриці по стовпцях
 data <- data %>%
 apply(2,function(x) x-min(x)) %>% 
as.data.frame()

 zero_index <- which(data==0, arr.ind = T)
 unique_index <- from_the_beginning(zero_index)

if(nrow(unique_index)!=nrow(data))
 unique_index <- from_the_end(zero_index)

if(nrow(unique_index)!=nrow(data))
{

#"Викреслюємо" рядки і стовпці, які містять нульові елементи (ВАЖЛИВО! кількість вычеркиваний повинно бути мінімальним)
 index <- which(apply(data,1,function(x) length(x[x==0])>1))
 index2 <- which(apply(data[-index],2,function(x) length(x[x==0])>0))

#Серед решти елементів шукаємо мінімальний
 min_from_table < min(data[-index,-index2])

#Віднімаємо мінімальний з решти елементів
 data[-index,-index2] <- data[-index,-index2]-min_from_table

#Додаємо до елементам, розташованим на перетині вилучених рядків і стовпців
 data[index,index2] <- data[index,index2]+min_from_table

 zero_index <- which(data==0, arr.ind = T)
 unique_index <- from_the_beginning(zero_index)

if(nrow(unique_index)!=nrow(data))
 unique_index <- from_the_end(zero_index)

#Якщо все ще кількість "неповторюваних" нулів не дорівнює кількості рядків у вихідній таблиці, то..
if(nrow(unique_index)!=nrow(data))
#..Повторюємо весь алгоритм заново
hungarian_algorithm(data,optim)

else
#Виводимо індекси "неповторюваних" нулів
unique_index
}
else
#Виводимо індекси "неповторюваних" нулів
unique_index
}
else
#Виводимо індекси "неповторюваних" нулів
unique_index
}
#_________________________________________________________________________________


#__________Функція для знаходження "неповторюваних" нулів зліва-направо___________

from_the_beginning <- function(x,i=0,j=0,index = data.frame(row=numeric(),col=numeric())){

#Вибір індексів нулів, які не лежать на рядках i, і стовпцях j
 find_zero <- x[(!x[,1] %in% i) & (!x[,2] %in% j)]

if(length(find_zero)>2){

#Записуємо індекс рядка вектор
 i <- c(i,as.vector(find_zero[1,1]))

#Записуємо індекс стовпця вектор
 j <- c(j,as.vector(find_zero[1,2]))

#Індекси записуємо в data frame (це і є індекси унікальних нулів)
 index <- rbind(index,setNames(as.list(find_zero[1,]), names(index)))

#Повторюємо поки не пройдемо по всіх рядках і стовпчиках
from_the_beginning(find_zero,i,j,index)}
else
rbind(index,find_zero)
}
#_________________________________________________________________________________

#__________Функція для знаходження "неповторюваних" нулів праворуч-ліворуч___________

from_the_end <- function(x,i=0,j=0,index = data.frame(row=numeric(),col=numeric())){
 find_zero <- x[(!x[,1] %in% i) & (!x[,2] %in% j)]
if(length(find_zero)>2){
 i <- c(i,as.vector(find_zero[nrow(find_zero),1]))
 j <- c(j,as.vector(find_zero[nrow(find_zero),2]))
 index <- rbind(index,setNames(as.list(find_zero[nrow(find_zero),]), names(index)))
from_the_end(find_zero,i,j,index)}
else
rbind(index,find_zero)
}
#_________________________________________________________________________________

Результат виконання програми:

Читайте також  WPA3 міг би бути і безпечніше: думка експертів

На завершення

Дякую що витратили час на читання моєї статті. Всі використовувані надам посилання нижче. Сподіваюся, Ви дізналися щось для себе нове або оновили старі знання. Всім успіхів, добра і удачі!

Використовувані ресурси

1. Штурмував вікіпедію
2. І інші хороші сайти
3. Підкреслив для себе трохи інформації з цієї статті

Степан Лютий

Обожнюю технології в сучасному світі. Хоча частенько і замислююся над тим, як далеко вони нас заведуть. Не те, щоб я прям і знаюся на ядрах, пікселях, коллайдерах і інших парсеках. Просто приходжу в захват від того, що може в творчому пориві вигадати людський розум.

You may also like...

Залишити відповідь

Ваша e-mail адреса не оприлюднюватиметься. Обов’язкові поля позначені *