Задача о назначениях
Назначение сервиса. С помощью данного онлайн калькулятора можно:- найти путь с минимальной стоимостью назначения и с максимальной стоимостью назначения, решить задачу о назначении венгерским методом (методом Куна), решить задачу о назначении методом потенциалов;
- найти оптимальное использование рабочих агентов;
Инструкция. Выберите размерность матрицы (количество вакансий и количество кандидатов). После ввода данных, создается шаблон решения в Excel (см. задача о назначениях в Excel).
Типичное задание:
В цехе предприятия имеются 5 универсальных станков, которые могут выполнять 4 вида работ. Каждую работу единовременно может выполнять только один станок, и каждый станок можно загружать только одной работой.
В таблице даны затраты времени при выполнении станком определённой работы. Определить наиболее рациональное распределение работ между станками, минимизирующее суммарные затраты времени.
Задача. Служба занятости имеет в наличии четыре вакантных места по разным специальностям, на которые претендуют шесть человек. Проведено тестирование претендентов, результаты которого в виде баллов представлены в матрице
Распределить претендентов на вакантные места таким образом, чтобы на каждое место был назначен человек с наибольшим набранным по тестированию баллом.
Пример решения задачи о назначении с минимальной стоимостью;
Пример решения задачи о назначении с максимальной стоимостью;
Постановка задачи о назначениях
Сделаем содержательную постановку задачи. В объединении находится n автомобилей, способных каждый перевозить в месяц Qi тонн груза (i = 1,2,…,n). С их помощью необходимо обеспечить перевозку грузов (пиломатериал, шурупы и т.д.) от поставщиков к потребителям по n маршрутам в количестве Rj тонн в месяц (j = 1,2,…,n).Распределить автомобили по маршрутам так, чтобы минимизировать суммарную величину неиспользуемой провозной способности. Конкретизируем задачу (рис. 1). Пусть имеется 4 автомобиля и 4 маршрута. Характеристики провозных способностей автомобилей соответственно равны Q1 = 30 т., Q2 = 35 т., Q3 = 5 т., Q4 = 5 т. Характеристики потребностей потребителей соответственно равны R1 = 25 т., R2 = 32 т., R3 = 5 т., R4 = 4 т. Задача заключается в том, чтобы перевезти все грузы с минимальными издержками, для этого надо каждый автомобиль пустить по одному и только его маршруту. Понятно, если возможность автомобиля в перевозке груза ниже потребности потребителя этого груза, то на данный маршрут автомобиль не может быть назначен. Поэтому составим матрицу С, характеризующую издержки i-го автомобиля, в случае, если он будет назначен на j-й маршрут. Элементы маршрута будут равны:
В таблице 1 приводятся оценки возможных транспортных издержек.
Таблица 1 - Оценки транспортных издержек
Rj Qi |
25 |
32 |
5 |
4 |
30 |
5 |
М |
25 |
26 |
35 |
10 |
3 |
30 |
31 |
5 |
М |
М |
0 |
1 |
5 |
М |
М |
0 |
1 |
Переменные. В качестве переменной введем величину
Ограничения. Каждый автомобиль i должен быть назначен только один раз на любой из маршрутов.
или 
.
На каждый маршрут j должен быть назначен один из автомобилей
или 
.
Целевая функция. В качестве целевой функции, подлежащей минимизации, выступают суммарные издержки на перевозку.
Модель задачи о назначениях примет вид:
при ограничениях:
,
,
.
Все предполагаемые алгоритмы поиска решения задачи о назначениях базируются на следующем утверждении: оптимальное решение задачи не изменится, если к любой строке или столбцу матрицы издержек прибавить (или вычесть) постоянную величину в силу того, что приоритет назначения не изменится. И весь алгоритм ведется на матрице издержек с соответствующими преобразованиями для получения в ней нулевых элементов, образующих систему так называемых «независимых нулей». Число независимых нулей равно размерности матрицы, а их расположение таково, что каждый из них встречается один раз в строке и один раз в столбце. Если такие независимые нули будут найдены, то в матрице решения в соответствии с их положением будут проставлены единицы. В матрице 1 нулевые элементы получены вычитанием наименьшего элемента в каждой строке.
(1)Как только будут получены нулевые элементы, применяют различные алгоритмы: Мака, венгерский, минимальных линий. Рассмотрим процедуру вычеркивания нулевых элементов минимальным числом прямых линий. В матрице 2 показано, как используется это правило. Могут быть и другие варианты вычеркивания.
Если все нулевые элементы в матрице будут вычеркнуты, а минимальное число линий будет равно размерности матрицы, то независимые нули в матрице существуют, и решение найдено. В противном случае выбирается наименьший элемент из невычеркнутых элементов (он равен 1). Этот элемент вычитается из каждого невычеркнутого элемента и прибавляется к каждому элементу, стоящему на пересечении проведенных прямых.
В результате получается матрица (3), которая указывает на два оптимальных решения (матрицы решений 4 и 5).
Значение целевой Z = 5 + 3 + 0 + 1 = 9 . Оптимальное решение можно было получить и сразу, не применяя процедуру вычеркивания нулей, если в матрице 2 из столбца 4 вычесть минимальный элемент. Сделано было иначе только для демонстрации процедуры вычеркивания.
Следует заметить, что, если на последнем шаге оптимальное решение не достигнуто, то процедуру проведения прямых следует повторять до тех пор, пока не будет получено допустимое решение.
Модель назначений
Модель назначений часто встречается в задачах управления, где требуется, например, распределить мастеров-ремонтников по вызовам, продавщиц по отделам, аудиторов по фирмам и т. д. В качестве примера рассмотрим возможную постановку задачи назначения.Пример. Руководство фирмы приняло решение произвести инспекцию своих предприятий в Лейпциге, Нанси, Льеже и Тилбурге, направляя туда своих вице-президентов, каждый из которых в компании возглавляет одно из направлений (финансы, маркетинг, производство и персонал). Хотя может существовать большое число факторов, которые нужно учесть при таком назначении (знание языка, узкая специализация, невозможность оторваться от прямых обязанностей и т. д.), руководство компании решило оптимизировать в качестве первого шага только суммарные затраты на командировку вице-президентов. Таблица командировочных расходов в различные города (тыс. долларов) приведена ниже.
| Вице-президенты | Лейпциг | Нанси | Льеж | Тилбург |
По финансам | 24 | 10 | 21 | 11 |
По маркетингу | 14 | 22 | 10 | 15 |
По производству | 15 | 17 | 20 | 19 |
По персоналу | 11 | 19 | 14 |
Требуется составить схему распределения вице-президентов по филиалам, минимизирующую командировочные расходы.
Решение. Табличная модель этой задачи после проведенной оптимизации приведена на рис.
Модель назначений является разновидностью транспортной модели. От последней она отличается только тем, что в ней единица предложения не может распределяться по нескольким местам назначения (ср. рис.).
Таким образом, модель назначений всегда можно построить в виде транспортной модели, в которой предложение в каждой исходной точке и спрос в каждом конечном пункте равны единице.
Точно так же, как и транспортная модель, модель назначений может быть несбалансированной, содержать недопустимые назначения, иметь альтернативные решения при одном и том же значении целевой функции. Эти варианты моделей назначения строятся в полной аналогии с соответствующими транспортными моделями.
Оптимальное распределение продавцов по торговым точкам
Задание. Существует 4 продавца А1, А2, А3, А4 и 4 торговые точки В1, В2, В3, В4. Эффективность работы продавцов на торговых точках задаётся следующей матрицей:| 9 | 3 | 4 | 8 |
| 4 | 6 | 7 | 11 |
| 5 | 8 | 8 | 4 |
| 6 | 12 | 15 | 9 |
Найти оптимальное распределение продавцов по торговым точкам.
Поскольку задана матрица эффективности, то искать необходимо максимальные значения, следовательно, целевая функция стремится к максимуму. Именно поэтому при решении выбираем вид Максимальная прибыль.
Модифицируем матрицу умножением всех элементов на (-1) и затем сложением их с максимальным элементом матрицы (15) так, чтобы матрица не содержала бы отрицательных элементов:
| 6 | 12 | 11 | 7 |
| 11 | 9 | 8 | 4 |
| 10 | 7 | 7 | 11 |
| 9 | 3 | 0 | 6 |
1. Проводим редукцию матрицы по строкам. В связи с этим во вновь полученной матрице в каждой строке будет как минимум один ноль.
| 0 | 6 | 5 | 1 | 6 |
| 7 | 5 | 4 | 0 | 4 |
| 3 | 0 | 0 | 4 | 7 |
| 9 | 3 | 0 | 6 | 0 |
| 0 | 6 | 5 | 1 |
| 7 | 5 | 4 | 0 |
| 3 | 0 | 0 | 4 |
| 9 | 3 | 0 | 6 |
| 0 | 0 | 0 | 0 |
2. Методом проб и ошибок проводим поиск допустимого решения, для которого все назначения имеют нулевую стоимость.
Фиксируем нулевое значение в клетке (1, 1). Другие нули в строке 1 и столбце 1 вычеркиваем.
Фиксируем нулевое значение в клетке (2, 4). Другие нули в строке 2 и столбце 4 вычеркиваем.
Фиксируем нулевое значение в клетке (3, 2). Другие нули в строке 3 и столбце 2 вычеркиваем.
Фиксируем нулевое значение в клетке (4, 3). Другие нули в строке 4 и столбце 3 вычеркиваем.
В итоге получаем следующую матрицу:
| [0] | 6 | 5 | 1 |
| 7 | 5 | 4 | [0] |
| 3 | [0] | [-0-] | 4 |
| 9 | 3 | [0] | 6 |
| 0 | 6 | 5 | 1 |
| 7 | 5 | 4 | 0 |
| 3 | 0 | 0 | 4 |
| 9 | 3 | 0 | 6 |
| [0] | 6 | 5 | 1 |
| 7 | 5 | 4 | [0] |
| 3 | [0] | [-0-] | 4 |
| 9 | 3 | [0] | 6 |
Cmax = 9 + 11 + 8 + 15 = 43
Таким образом, распределение продавцов по торговым точкам будет следующее:
1 продавец – торговая точка №1
2 продавец – торговая точка №4
3 продавец – торговая точка №2
4 продавец – торговая точка №3.
При таком назначении, максимальная эффективность составит 43.
Задача о назначениях как вид транспортной задачи
Рассмотрим ситуацию, когда требуется распределить m работ (или исполнителей) по n станкам. Работа i (i=1,...,m), выполняемая на станке j (j=1,...,n), связана с затратами cij. Задача состоит в таком распределении работ по станкам (одна работа выполняется на одном станке), которое соответствует минимизации суммарных затрат.Эту задачу можно рассматривать как частный случай транспортной задачи. Здесь работы представляют «исходные пункты», а станки – «пункты назначения». Предложение в каждом исходном пункте равно 1, т.е. ai = 1 для всех i. Аналогично спрос в каждом пункте назначения равен 1, т.е. bj = 1 для всех j. Стоимость «перевозки» (прикрепления) работы i к станку j равна cij. Если какую-либо работу нельзя выполнять на некотором станке, то соответствующая стоимость берется равной очень большому числу. Матрица стоимостей C определяется следующим образом:
Прежде чем решать такую задачу необходимо ликвидировать дисбаланс, добавив фиктивные работы или станки в зависимости от начальных условий. Поэтому без потери общности можно положить m = n.
Пусть
xij = 0, если j-я работа не выполняется на i-м станке,
xij = 1, если j-я работа выполняется на i-м станке.
Таким образом, решение задачи может быть записано в виде двумерного массива X = (xij). Допустимое решение называется назначением. Допустимое решение строится путем выбора ровно одного элемента в каждой строке матрицы X = (xij) и ровно одного элемента в каждом столбце этой матрицы. Для заданного значения n существует n! допустимых решений.
Теперь задача будет формулироваться следующим образом:
Ограничения первой группы необходимы для того, чтобы каждая работа выполнялась ровно один раз. Ограничения второй группы гарантируют, что каждому станку будет приписана ровно одна работа.
Венгерский алгоритм
Шаг 1. (Редукция строк и столбцов).
Цель данного шага состоит в получении максимально возможного числа нулевых элементов в матрице стоимостей. Для этого из всех элементов каждой строки вычитают минимальный элемент соответствующей строки, а затем из всех элементов каждого столбца полученной матрицы вычитают минимальный элемент соответствующего столбца. В результате получают редуцированную матрицу стоимостей и переходят к поиску назначений.
Шаг 2. (Определение назначений).
а) Найти строки, содержащие ровно один невычеркнутый нулевой элемент. В каждой такой строке произвести назначение, соответствующее невычеркнутому нулевому элементу. В каждом столбце, в котором было произведено назначение, вычеркнуть все невычеркнутые ранее нулевые элементы. Строки рассматриваются в порядке возрастания их номеров.
б) Найти столбцы, содержащие ровно один невычеркнутый нулевой элемент. В каждом таком столбце произвести назначение, соответствующее невычеркнутому нулевому элементу. В каждой строке, в которой было произведено назначение, вычеркнуть все невычеркнутые ранее нулевые элементы. Столбцы рассматриваются в порядке возрастания их номеров.
в) Выполнять пункты а) и б) до тех пор, пока не будет вычеркнуто максимально возможное число нулевых элементов. Если построенное назначение полное, то оно является оптимальным.
Если некоторые нули остались невычеркнутыми, то можно попытаться найти полное назначение.
Если нельзя найти полного назначения, то необходима дальнейшая модификация матрицы стоимостей, т.е. перейти к шагу 3.
Шаг 3. (Модификация редуцированной матрицы).
Для редуцированной матрицы стоимостей:
а) Вычислить число нулей в каждой невычеркнутой строке и каждом невычеркнутом столбце.
б) Вычеркнуть строку или столбец с максимальным числом нулей.
в) Выполнять пункты а) и б) до тех пор, пока не будут вычеркнуты все нули.
г) Из всех невычеркнутых элементов вычесть минимальный невычеркнутый элемент и прибавить его к каждому элементу, расположенному на пересечении двух линий.
Перейти к шагу 2.
Замечания.
1) Если число линий, необходимое, для того чтобы вычеркнуть нулевые элементы, равно числу строк (столбцов), то существует полное назначение.
2) Если исходная задача является задачей максимизации, то все элементы матрицы стоимостей следует умножить на (-1) и сложить их с достаточно большим числом так, чтобы матрица не содержала бы отрицательных элементов. Затем задачу следует решать как задачу минимизации.