XII Международная студенческая научная конференция Студенческий научный форум - 2020

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

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

Задача о назначенияхявляется одной из базовых задач комбинаторной оптимизации, применяемой в сфере математической оптимизации или при исследовании операций. Её смысл заключается в поиске минимальной суммы дуг во взвешенном двудольном графе. Стоит отметить, что задача о назначениях есть частный случай транспортной задачи [1].

Двудольный граф – граф, множество вершин которого возможно разбить на две части так, чтобы каждое его ребро соединяло произвольную вершину из одной части с произвольной вершиной другой части, то есть не существовало бы ребра, соединяющего две вершины из одной части [1].

Общая формулировка задачи о назначениях такова:

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

Существуют и другие варианты формулировки данной задачи [3]:

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

Дана матрица А размером n*n. Необходимо в каждой её строке выбрать по одному числу таким образом, чтобы в любом столбце также было выбрано ровно по одному числу, и при этом сумма выбранных чисел была минимальной.

Дан полный двудольный граф с n вершинами, каждое его ребро имеет некоторый вес. Найти совершенное паросочетание минимального веса.

Имеются склады и магазины с заданным между ними расстоянием. Необходимо минимизировать (максимизировать) суммарное расстояние между ними и т.д.

Задачу о назначениях можно решить любым алгоритмом линейного программирования, однако более эффективным является венгерский метод, заключающийся в выполнении венгерского алгоритма, который был разработан и опубликован Гарольдом Куном в 1955 году. Автор дал ему такое имя в связи с тем, что алгоритм в большей степени основан на более ранних работах двух венгерских математиков.

Описание венгерского алгоритма:

В каждой строке матрицы назначения находят min элемент и вычитают его из всех элементов строки.

Аналогичное действие делают со столбцами.

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

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

Если после выполнения шагов 3-4 остались неотмеченные 0, то отмечают любой из них, а в строке и столбце, содержащих отмеченный ноль, все остальные 0 зачёркивают.

Оптимальное решение достигнуто в том случае, если в каждой строке и в каждом столбце матрицы есть ровно один отмеченный 0. В противном случае проводят минимальное число пересекающихся вертикальных и горизонтальных прямых через все 0. Среди не зачёркнутых прямыми чисел ищут минимальное, вычитая его из всех не зачёркнутых чисел и прибавляя ко всем числам, стоящим на пересечении прямых. К полученной матрице применяют алгоритм, начиная с шага 3 [2].

Применим венгерский алгоритм на практическом примере.

Имеются четыре склада С1, С2, С3, С4 и четыре магазина D1, D2, D3, D4. Расстояние между ними заданы матрицей (в усл. ед.) :

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

Решение

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

Аналогично поступив со столбцами полученной матрицы, имеем:

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

Проведём прямые через все 0:

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

Применяем алгоритм с третьего шага.

Распределение не является оптимальным, так как в 4-ой строке нет отмеченных 0. Проведём прямые или выделим цветом соответствующие строки и столбцы:

Минимальный элемент среди не зачёркнутых чисел равен 2. Проделываем действия, аналогичные шагу 4, затем отмечаем 0 аналогично шагу 3):

Распределение не оптимально, так как в первой строке нет отмеченных 0, проведём прямые или выделим соответствующие строки и столбцы:

Минимальный элемент равен 2. Проделываем действия, аналогичные шагу 4. Имеем:

Решение оптимально, так как каждая строка и каждый столбец содержит ровно один отмеченный 0. Чтобы найти искомое минимальное суммарное расстояние, сложим числа, расположенные в исходной матрице на месте отмеченных 0. Это числа 6, 5, 4, 8. Следовательно, искомое расстояние равно 6 + 5 + 4 + 8 = 23 (усл. ед.)

Ответ: 23 усл. ед.

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

В задаче о назначениях данного типа также может требоваться максимизировать суммарное расстояние между объектами. В этом случае элементы исходной матрицы умножают на (-1), а затем применяют венгерский алгоритм.

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

Список литературы

Задача о назначениях [электронный ресурс] Режим доступа: https://ru.wikipedia.org/

Задача о назначениях [электронный ресурс] Режим доступа: https://wikimatik.ru/article/37

Венгерский алгоритм решения задачи о назначениях [электронный ресурс] Режим доступа: https://e-maxx.ru/algo/assignment_hungary

Описание алгоритма венгерского метода [электронный ресурс] Режим доступа: https://www.cena5.ru/opisanie-algoritma-vengerskogo-metoda-zadacha-o-naznacheniyah-vengerskii-metod.html

Акулич И. Л. Математическое программирование в примерах и задачах. – СПб.: «Лань», 2011 [электронный ресурс] Режим доступа: https://lanbook.com/catalog/matematika/matematicheskoe-programmirovanie-v-primerah-i-zadachah-54562506/

Ашманов С.А. Линейное программирование [электронный ресурс] Режим доступа: http://en.bookfi.net/book/636235

Шапкин, А. С. Математические методы и модели исследования операций: учебник / А. С. Шапкин, В. А. Шапкин. – М.: Дашков и К, 2016 [электронный ресурс] Режим доступа: https://znanium.com/spec/catalog/author/?id=e6af2db0-34c2-11e4-b05e-00237dd2fde2