РЕШЕНИЕ ЗАДАЧИ О НАЗНАЧЕНИЯХ

Введение

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

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

Возможный набор условий, необходимый для решения задачи о назначениях

1. Необходимо выполнить n-ое количество работ.
2. Привлечь n исполнителей
3. Каждый из n исполнителей за определенную плату готов взяться за выполнение любой работы (при невозможности выполнения стоимость для простоты возможно указать максимально возможной за данную работу)
4. 1 работа = 1 исполнитель
5. Цель - минимальные суммарные затраты на выполнение всех видов работ

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

Алгоритм основан на двух идеях: 

1. если из всех элементов некой строки или столбца вычесть одно и то же число Y, общая стоимость уменьшится на Y, а оптимальное решение не изменится;
2. если есть решение нулевой стоимости, оно оптимально.

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

Математическая постановка задачи

Пусть имеется n рабочих и n работ.  Известны затраты p_ij на выполнение j работы i работником. Необходимо составить план работ так, чтобы все работы были выполнены при минимальных суммарных затратах.

Введем некоторую булеву функцию

Целевая функция p_ij

При условиях:

1. каждая работа должна быть выполнена для каждого вида работ j=1..n

2. Каждый работник выполняет не более одной работы для каждого работника I =1..n

Алгоритмизация

1. Поиск наименьшего элемента строки i.
2. Вычитание найденного минимального элемента из каждого элемента i-той строки
3. Поиск наименьшего элемента столбца j.
4. Вычитание найденного минимального элемента из каждого элемента j-того столбца.
5. В результате выполнения шагов 1,2,3 получается редуцированная матрица.
6. Заполнение векторов I, J соответственными нулевыми элементами редуцированной матрицы.
7. Если в каждом столбце и в каждой строке найден нулевой элемент, тогда найдено совершенное паросочетание.
8. Выбрать нулевые элементы так, чтобы никакие два нуля не находились в одном и том же столбце или строке. Данные элементы входят в паросочетание.
9. Выполнить шаги с 1 по 8 пока ни выполнится 6 шаг.

Пример: Директор фирмы K принял решение перераспределить своих действующих менеджеров между отделами для сохранения лояльности к рядовым сотрудникам и сохранению финансового благосостояния компании. Максимально возможная заработная плата - 70 тыс рублей, поэтому для подтверждения невозможности постановку на предыдущую должность у каждого менеджера она отмечается заработной платой в 100 тыс.

Таблица 1.

Исходные данные

1. Ищем минимум для каждой строки (и вычитаем найденный минимум из эл-в строки -> след. таблица)

Таблица 2.

Результаты для первого этапа

2. Ищем минимум для каждого столбца (и вычитаем найденный минимум из эл-в столбца -> след. таблица)

Таблица 3.

Результаты для второго этапа

3. Фиксируем нулевые эл-ты для нахождения оптимального решения

Таблица 4.

Результаты для третьего этапа

4. Получаем матрицу решений, заменяя все зафиксированные элементы на 1, остальные на 0.

Таблица 5.

Результаты для четвертого этапа

т.о. min затраты -> 54 + 37 + 41 + 65 = 197

Программная реализация и ее анализ.

Был разработан алгоритм для решения поставленной задачи. Для разработки в качестве инструмента использовался компилируемый язык программирования C++. В своей работе мы производим сравнение разработанного алгоритма с работой программы TransTrade интегрированной в такие системы как 1С, АТИ, Почта России и многие другие. Конкретно в данной программе было произведено исследование функции подбора исполнителей. Производилась оценку времени работы при различном количестве входных данных.

Таблица 6.

Результаты скорости работы

Рисунок 1. Графики скорости работы

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

1. При объеме входных данных менее 30 алгоритм программы TrаnsTrade работает лучше
2. При увеличении объема входных данных наш алгоритм обладает более высокой скоростью работы
3. Наш алгоритм обладает более высокой стабильностью - значений, при которых работа алгоритма аварийно прекращается, обнаружено не было, в отличие от TrаnsTrade.

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

1. Диниц Е.А., Крондрл М.А. Один алгоритм решения задачи о назначении./ДАН СССР.-1969.-Т.189.-№1.-С.23-25.
2. Флейшман С.Б. Оптимальные назначения специального вида. -М., 1990.-15с. (Препр./АН СССР Ин-т точн. механ. и вычислит. техн. Им. С.А. Лебедева; №2).