Курсовая_САиМУР.Никита. Курсовая работа по дисциплине Ситуационный анализ и моделирование управленческих решений

• Название: Курсовая работа по дисциплине Ситуационный анализ и моделирование управленческих решений
• Дата: 09.04.2023
• Размер: 179.84 Kb.
• Имя файла: Курсовая_САиМУР.Никита.docx
• Тип: Курсовая; #1048522

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РЕСПУБЛИКИ БЕЛАРУСЬ

УЧРЕЖДЕНИЕ ОБРАЗОВАНИЯ «ВИТЕБСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИМЕНИ П.М. МАШЕРОВА»

Факультет математики и информационных технологий

Кафедра информационных технологий и управления бизнесом

КУРСОВАЯ РАБОТА

по дисциплине «Ситуационный анализ и моделирование управленческих решений»
ЗАДАЧА О НАЗНАЧЕНИЯХ. ВЕНГЕРСКИЙ МЕТОД

Дуброва Никита Николаевич

3 курс, 33 группа

Руководитель:

Кавитова Татьяна Валерьевна

ст. преподаватель кафедры математики, кандидат физ.-математ. наук
Витебск, 2022

Содержание

Введение 3

1. Основы задач о назначениях в теории 4

2. Задача о назначениях 5

3. Венгерский метод решения задач о назначениях 5

4. Сущность и решение венгерским методом 5

5. Реализация задачи о назначениях 12

Заключение 14

Список используемой литературы 15

Введение

Алгоритм под названием “венгерский” был разработан Гарольдом Куном в 1955 году. Кун дал такое название основываясь на том, что этот алгоритм в значительной степени является трудами венгерских математиков Денеша Кёнига (Dénes Kőnig) и Эйгена Эгервари (Jenő Egerváry).

Чуть позже, в 1957 году, Джеймс Манкерс (James Munkres) доказал, что венгерский алгоритм работает за полиномиальное время (т.е. за время порядка полинома, и не зависит от величины стоимостей).

Основываясь на этом алгоритм стали называть не только “венгерским”, но и “алгоритмом Куна-Манкреса” (“алгоритмом Манкреса”).

Однако, в 2006 году было выявлено, что этот алгоритм был изобретён веком ранее, немецким математиком Карлом Густавом Якоби (Carl Gustav Jacobi). Всё дело в том, что напечатанная посмертно, в 1890 году, работа была написана на латыни и была не замечена математиками.

Цель работы:

Исследовать решение задач о назначениях.

Задачи:

Рассмотреть теоретическую часть задач о назначениях.

Проанализировать Венгерский метод решения задач о назначениях.

1. Основы задач о назначениях в теории

Задача о назначениях является ничем иным как частным случаем классической транспортной задачи и, тем самым, является задачей транспортного типа.

Транспортными задачами называются задачи о наиболее выгодном плане перевозок грузов однородного или взаимозаменяемого продукта из станции отправления (пункта производства), в станции назначения (пункты потребления). Несмотря на название данных задач, они имеют обширное применение не только в сфере транспортных перевозок.

Основными аспектами интереса к этим задачам можно назвать следующие причины:

1. Задачи транспортного типа решаются, как и задачи линейного программирования, симплекс-методом. Однако некоторые специфические особенности задач данного класса послужили толчком для разработки более эффективных методов решения. А поскольку на практике данные задачи могут быть весьма объёмными, использование специализированных алгоритмов становится не просто возможностью облегчить труд, но и необходимостью.

2. Зачастую для задач транспортного типа используется граф определённой формы. Такое представление является более естественным и удобным. В некоторых случаях представление в виде графа позволяет преобразовать задачи к транспортным (те, которые не имеют ничего общего с ними) и использовать при их решении вычислительные алгоритмы относящиеся к транспортным.

3. Задачи транспортного типа тесно связаны с детерминированными динамическими задачами исследования операций, в том числе и с многошаговыми задачами принятия решений в условиях определенности, имеющими большое прикладное значение.

Некоторые особенности задач о назначениях позволили разработать венгерский метод, как более эффективный метод их решения.

В современном мире все предприятия стараются минимизировать расходы и тем самым увеличить прибыль. С этим помогают экономико-математические задачи о назначениях. Такой вид задач позволяет разместить одного кандидата на выполнение одной работы таким образом, чтобы затраты на выполнение комплекса работ группой исполнителей стали минимальными. Также задачи о назначениях могут быть модифицированы под определённые обстоятельства: во-первых, иногда такие задачи формируются как задачи максимизации (максимизация дохода при назначениях исполнителей на работу); во-вторых, количество рабочих мест может быть меньше, чем количество штатных рабочих и наоборот, количество рабочих может быть меньше, чем количество рабочих мест; в-третьих, выполнение работы может быть запрещено работнику по какому-либо поводу.

Данная задача в такой постановке относится к классу комбинаторных, решение которых, при больших n, становится фактически невозможным для решения перебором (так как число вариантов назначений составляет n!).

2. Задача о назначениях

Задача о назначениях – это задача о самом выигрышном распределении работ между таким же числом исполнителей. При решении этой задачи ищут оптимальное назначение из условия максимума общей производительности, которая равна сумме производительности исполнителей. К задаче о назначении можно отнести множество интерпретаций: распределение работников на предприятии в соответствии их работоспособности и навыкам, распределение работы различных механизмов и их энергозатрат и т.д. Венгерский метод является наиболее подходящим для решения данных задач.

3. Венгерский метод решения задач о назначениях

Специфические особенности задач о назначениях послужили поводом к появлению эффективного венгерского метода их решения. Основная идея венгерского метода заключается в переходе от исходной квадратной матрицы стоимости С к эквивалентной ей матрице Сэ с неотрицательными элементами и системой n независимых нулей, из которых никакие два не принадлежат одной и той же строке или одному и тому же столбцу.

Структура алгоритма такова: есть последовательные шаги, на каждом из которых делается попытка выбрать назначение при неотрицательной матрице убытков так, чтобы все выбранные элементы матрицы были нулевыми. Если это сделать не удается, матрица изменяется с сохранением свойства неотрицательности. Первоначально подготовка матрицы заключается в том, что от каждого элемента каждой строки матрицы в каждой строке. Вычитание из каждого столбца наименьшего в нем элемента обеспечивает существование нулевых элементов и в столбцах. Для заданного n существует n! допустимых решений. Если в матрице назначения X расположить n единиц так, что в каждой строке и столбце находится только по одной единице, расставленных в соответствии с расположенными n независимыми нулями эквивалентной матрицы стоимости Сэ, то получим допустимые решения задачи о назначениях.

Следует иметь в виду, что для любого недопустимого назначения соответствующая ему стоимость условно полагается равной достаточно большому числу М в задачах на минимум. Если исходная матрица не является квадратной, то следует ввести дополнительно необходимое количество строк или столбцов, а их элементам присвоить значения, определяемые условиями задачи, возможно после редукции, а доминирующие альтернативы дорогие или дешевые исключить.

4. Сущность и решение венгерским методом

Сущность Венгерского метода заключается в продолжении процесса приведения матрицы до тех пор, пока все подлежащие распределению единицы не попадут в клетки с нулевой стоимостью. Это означает, что итоговое значение приведенной целевой функции будет равно нулю. Так как существует ограничение на неотрицательность переменных, нулевое значение целевой функции является оптимальным.

Приведем пример: имеется определенное число работников и определенное число мест. На каждом месте работник имеет определенную заработную плату. Расставить оптимально работников так, чтобы заработная плата была меньше всего. Будем рассматривать с точки зрения руководителя. Работа будет производиться на минимум. В каждой строчке матрицы мы будем выбирать по одному элементу, нельзя чтобы работник работал сразу на двух местах. На каждой строчке и на каждом столбце должно быть по одному выделенному элементу. Распишем сущность алгоритма венгерским методом. Имеем исходную матрицу:

1	7	1	3
1	6	4	6
17	1	5	1
1	6	10	4

Таблица 4.1 – Исходная матрица

Нам нужно вычесть самое маленькое значение из первой строчки. И так далее, вычитаем из каждой строчки до тех пор, чтобы в каждой строчке было хотя бы по одному нулю. Можно и более.

Понижаем порядок матрицы на один.

0	6	0	2
0	5	3	5
16	0	4	0
0	5	9	3

Таблица 4.2 – Исходная матрица с пониженным порядком

Каждый ноль соответствует ребру двудольного графа, напомню, что двудольный граф – это граф, который распадается на два множества, внутри они не соединяются, а соединяются только друг с другом. От I к j вершине. Итак, вершины распадаются на два множества. Первый 0 на месте (1.1) первая вершина соединяется с первой.


Рисунок 4.1– Соединение первой вершины правой доли двудольного графа



Рисунок 4.2– Второе соединение первой вершины правой доли двудольного графа

Первая с третьим.

Переходим к второй вершине первой доли.


Рисунок 4.3– Соединение второй вершины правой доли двудольного графа

Третья вершина соединяется в двух местах.


Рисунок 4.4– Соединение третьей вершины правой доли двудольного графа

И последняя соединяется только с первой.


Рисунок 4.5– Соединение четвёртой вершины правой доли двудольного графа

Получился двудольный граф. В нем мы будем искать паросочетания. Паросочетания - это тоже двудольный граф, особенность у него в том, что все степени вершин будут равны единице-это означает что от одной вершины два ребра не пойдет.

Сначала берем любое, затем максимальное и только затем из максимального находим наибольшее. Так находим наибольшее паросочетания. Мы взяли максимальное паросочетание, теперь нам нужно проверить является ли оно наибольшим.



Рисунок 4.6– Первая итерация поиска максимального паросочетания

На отдельном графике найдем наибольшие паросочетания. Если мы будем программировать на компьютере, то он перебирает все возможные варианты. И будет выводить первый попавшийся.

Если есть чередующаяся цепь, то эта чередующаяся цепь состоит из множества X, Y. Состоит из толстых и тонких линий. Тонкие ребра - это все паросочетания полученные из матрицы. Толстые входят в максимальное паросочетание. Из Х прийти в Y по тонким из Y в Х и снова из Х в Y. Потом мы обращаем эту цепь и получаем все наоборот. Из 3 в 2 мы оставим как есть. И добавим тонкие ребра, чтобы посмотреть, есть ли еще чередующаяся цепь.


Рисунок 4.7–Вторая итерация поиска максимального паросочетания

Есть подозрение, что это максимальное паросочетание.

Но это не единственное максимальное паросочетание. Посмотрим еще один вариант.


Рисунок 4.8– Третья итерация поиска максимального паросочетания

Это паросочетание тоже является наибольшим. По черным вперед по красным назад. Их количество должно быть нечетным.

Обозначим вершины, которые не охватываются наибольшим паросочетанием.

Xm=	{X4}
Ym=	{Y4}

Таблица 4.3 – Вершины, не охватываемые наибольшим паросочетанием

По этим множествам создадим еще 2 множества: X’ и Y’.

Возьмем Xm и X. Нужно выйти из Xm и вернуться в X. Исходя из той же стратегии: движемся вперед по черным вперед, назад по красным. И смотрим какие при этом мы проходим вершины. Те которые мы проходим вершины помещаем в множества X’ Y’. Выходим из X4 в Y1, затем попадаем в X2.

Получаем:

X'=	{x4, x2}
Y'=	{y1}

Таблица 4.4 – Обратный ход поиска вершин, не охватываемых наибольшим паросочетанием

Теперь по этим номерам строим так называемое альфа-преобразование. Из преобразованной матрицы берем вторую и четвертую строчки и не первый столбец. Из множества Y мы вычитаем Y’: Ym/{Y'}

Выделяем в преобразованной матрице строку 2 и 4, и столбцы все, кроме первой. Нас интересует то, что находится в пересечении.

Мы получили шесть элементов.

0	6	0	2
0	5	3	5
16	0	4	0
0	5	9	3

Таблица 4.5 – Исходная матрица с пониженным порядком

И в этих шести элементах находим минимальное значение. В данном случае получили 3. Далее из этих строк вычитаем тройки и вставляем их в первый столбец. Таким образом, получается:

3	6	0	2
0	2	0	2
19	0	4	0
0	2	6	0

Таблица 4.6 – Вычитание из матрицы с пониженным порядком

По аналогии строим граф.


Рисунок 4.9– Построение графа по матрице после вычитания

В этом двудольном графе ищем вариант, который соответствует максимальному значению. Возьмем первую вершину и исследуем её. Проводим от X1 к Y3. От X2 к Y1. От X3 к Y2. Смотрим на то, чтобы не были заняты вершины графа. ОТ X4 к Y4.



Рисунок 4.10– Граф с совершенным паросочетанием

Получилось совершенное паросочетание. Все степени вершин имеют по единице. Возвращаемся в исходную матрицу.

1	7	1	3
1	6	4	6
17	1	5	1
1	6	10	4

Таблица 4.7– Исходная матрица

Вычисляем сумму выделенных элементов:
1+1+1+4=7
Это и есть ответ решения задачи о назначениях венгерским методом.

5. Реализация задачи о назначениях

Общая структура алгоритма такова: он состоит из последовательных шагов, на каждом из которых делается попытка выбрать назначение при неотрицательной матрице убытков так, чтобы все выбранные элементы матрицы были нулевыми. Если это сделать не удается, матрица изменяется с сохранением свойства неотрицательности.

При неотрицательной матрице значение целевой функции задачи должно быть неотрицательно, поэтому если удастся получить "нулевое" назначение, о котором сказано выше, оно, очевидно, будет оптимальным. Для получения "нулевого" назначения нужно таким образом изменить матрицу, чтобы минимальное значение целевой функции равнялось нулю. Таким образом, невозможность получить "нулевое" назначение показывает, что матрица еще недостаточно изменена.

Метод изменения матрицы очень прост — он состоит из прибавления ко всем элементам какой-либо строки или столбца матрицы одного и того же числа. Поскольку в любом допустимом решении должен быть ровно один элемент из этой строки (или этого столбца), к значению целевой функции при этом изменении прибавляется то же число.

Первоначальная подготовка матрицы заключается в том, что от каждого элемента каждой строки матрицы вычитается наименьший в этой строке элемент Матрица становится неотрицательной с нулевым элементом в каждой строке. Вычитание из каждого столбца наименьшего в нем элемента обеспечивает существование нулевых элементов и в столбцах.

Основной шаг алгоритма состоит из поиска "нулевого" назначения и преобразования матрицы. Для "нулевого" назначения лучше воспользоваться терминологией простых графов, считать, что Мх — множество строк матрицы, М2 — множество столбцов и дуга из i в j идет в том и только в том случае, если a[i, j] = 0. Тогда существование "нулевого" назначения эквивалентно существованию в этом графе полного паросочетания. Будем разыскивать в нашем графе максимальное паросочетание (дающее наибольшее число "независимых" нулей - нулей, расположенных в различных строках и столбцах матрицы). Число дуг в максимальном паросочетании равно наименьшему числу вершин в множестве, которому инцидентны все дуги графа. В терминах теорема звучит следующим образом: наибольшее число независимых нулей равно наименьшему числу вертикальных и горизонтальных линий (столбцов и строк), которыми можно перечеркнуть все нули матрицы.

В данной реализации представлен поиск максимального паросочетания в двудольном графе.

Будем рассчитывать из вводимых данных: рабочие, количество назначаемых задания, количество пар (рабочий-задание).

А в выводе отображается количество заданий, заданных по такой схеме.

Заключение

Основной принцип работы венгерского метода состоит в следующем: прибавлением определенным образом найденных чисел к некоторым столбцам и вычитания из них некоторых чисел находят систему так именуемых независимых нулей. Набор из нулей называется системой независимых нулей, если никакие два (или больше) нуля не лежат на одной линии (в строке или столбце). Если число независимых нулей равно n, то, приняв соответствующие им переменные xij равными 1, а все остальные – равными 0, тогда получим оптимальный план назначения.

Алгоритм венгерского метода состоит из предварительного шага и не более чем (n-2) последовательно повторяющихся итераций. На предварительном этапе в случае решения задачи на максимум, ее преобразуют в эквивалентную задачу на минимум. На этом же этапе выделяется система независимых нулей. Каждая последующая итерация направлена на увеличение хотя бы на 1 числа независимых нулей. Как только число независимых нулей k станет равным размерности матрицы (k=n), задача решена. Оптимальный план назначения определится положением независимых нулей на последней итерации.

задача назначение венгерский полином

Список используемой литературы

1. Асанов М.О., Баранский В.А., Расин В.В. – Дискретная математика: Графы, матроиды, алгоритмы: Учебное пособие.

2. И.В. Романовский – Алгоритмы решения экстремальных задач.

3. Е.С. Вентцель – Исследование операций: задачи, принципы, методология.


ПРИЛОЖЕНИЕ А

Листинг A –Реализация венгерского алгоритма на языке программирования Pyton
import itertools
import numpy as np
from numpy import random
from scipy.optimize import linear_sum_assignment


# Назначение задачи
class TaskAssignment:

# Инициализация класса, обязательными входными параметрами являются матрица задач и метод распределения, среди которых есть два метода распределения, метод all_permutation или метод Венгрии.
def __init__(self, matrix, mode):
self.matrix = matrix
self.mode = mode
if mode == 'Vengr':
self.min_cost, self.best_solution = self.Vengr(matrix)


def Vengr(self, matrix):
b = matrix.copy()
# Строка и столбец минус 0
for i in range(len(b)):
row_min = np.min(b[i])
for j in range(len(b[i])):
b[i][j] -= row_min
for i in range(len(b[0])):
col_min = np.min(b[:, i])
for j in range(len(b)):
b[j][i] -= col_min
line_count = 0
# Когда количество строк меньше длины матрицы, цикл
while (line_count < len(b)):
line_count = 0
row_zero_count = []
col_zero_count = []
for i in range(len(b)):
row_zero_count.append(np.sum(b[i] == 0))
for i in range(len(b[0])):
col_zero_count.append((np.sum(b[:, i] == 0)))

line_order = []
row_or_col = []
for i in range(len(b[0]), 0, -1):
while (i in row_zero_count):
line_order.append(row_zero_count.index(i))
row_or_col.append(0)
row_zero_count[row_zero_count.index(i)] = 0
while (i in col_zero_count):
line_order.append(col_zero_count.index(i))
row_or_col.append(1)
col_zero_count[col_zero_count.index(i)] = 0
# Нарисуйте линию, покрывающую 0, и получите матрицу после строки минус минимальное значение и столбец плюс минимальное значение
delete_count_of_row = []
delete_count_of_rol = []
row_and_col = [i for i in range(len(b))]
for i in range(len(line_order)):
if row_or_col[i] == 0:
delete_count_of_row.append(line_order[i])
else:
delete_count_of_rol.append(line_order[i])
c = np.delete(b, delete_count_of_row, axis=0)
c = np.delete(c, delete_count_of_rol, axis=1)
line_count = len(delete_count_of_row) + len(delete_count_of_rol)
# Когда количество строк равно длине матрицы, выскакиваем
if line_count == len(b):
break
# Определяем, нужно ли рисовать линию, чтобы покрыть все нули, если она покрывает, операции сложения и вычитания
if 0 not in c:
row_sub = list(set(row_and_col) - set(delete_count_of_row))
min_value = np.min(c)
for i in row_sub:
b[i] = b[i] - min_value
for i in delete_count_of_rol:
b[:, i] = b[:, i] + min_value
break
row_ind, col_ind = linear_sum_assignment(b)
min_cost = matrix[row_ind, col_ind].sum()
best_solution = list(matrix[row_ind, col_ind])
return min_cost, best_solution


# Сгенерировать матрицу затрат
#rd = random.RandomState(10000) # Для случайных значений
#matrix = rd.randint(0, 100, size=(5, 5))
matrix =np.array([[1,7,1,3],[1,6,4,6],[17,1,5,1],[1,6,10,4]])
# Используйте метод Венгрии для распределения задач
ass_by_Hun = TaskAssignment(matrix, 'Vengr')
print('cost matrix = ', '\n', matrix)
print('Назначение задачи по венгерскому методу:')
print('min cost = ', ass_by_Hun.min_cost)
print('best solution = ', ass_by_Hun.best_solution)