Решение задачи о назначении.

Пусть имеется п работ (задач) и п кандидатов на их выполнение (персонала, процессоров, мест, машин). Пусть c\j (i,j = 1,2 n) — затра

ты (стоимость, время), связанные с назначением кандидата г на работу j.

Таблица 2.11

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

Задача может быть сформулирована как задача ЛП:

Есть специальный метод решения этой задачи, называемый венгерским методом. Рассмотрим конкретный пример. Пусть имеется 4 кандидата и 4 работы. Исходные данные задачи нс Vi 11' 11111 ы затрат c\j (i,j = 1,2,..., 4) содержатся в табл. 2.11.

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

Алгоритм решения задачи разбивается на несколько этапов.

1. Получение нулей во всех строках и столбцах матрицы.

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

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

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

отмеченными нулями Xij = 1, а ДЛЯ других Xij = 0. В противном случае переходим к следующему этапу.

1. Этап разметки строк и столбцов.

1.1.Отмечаем точкой строку, не содержащую ни одного отмеченного нуля.

1.2.Отмечаем столбец, содержащий перечёркнутый нуль в отмеченной строке.

1.3.Отмечаем строку, содержащую отмеченный нуль хотя бы в одном из отмеченных точкой столбцов.

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

2. Перестановка отмеченных нулей.

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

Результаты 1-го и 2-го (заключительного) этапов отражены в таблицах 2.12, 2.13.

Таблица 2.12

Т аб л ица 2.13

В данном случае получаем решение (отмеченные нули выделены полужирным шрифтом и подчёркнуты), для которого с =17.

2.5.