Исследование математической модели

Для решения задачи о назначении имеется насколько методов. Самый распространенный - венгерский метод.

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

Решение считается оптимальным, если все измененные искусственные затраты и можно отыскать такой набор ,что

Алгоритм метода включает следующие основные этапы:

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

Таблица 2

Вj Аi	В1	В2	В3	В4
А1
А2
А3
А4

Таблица 3

Вj Аi	В1	В2	В3	В4
А1	-0-º	-2-	-2-	-2-
А2	- -	-0-	-2-	-0-
А3			0 ˝
А4

2) Поиск оптимального решения. Для поиска оптимального решения необходимо рассмотреть сначала одну из строк табл.3, имеющую меньше нулей. Отметить точкой одни из нулей этой строки и зачеркнуть все остальные нули этой строки и того столбца, в которых находится этот нуль. Аналогичные операции последовательно проводятся для всех строк. Если назначения, которые получены при всех нулях, отмеченных точкой, являются полными (т.е.,число нулей отмеченных точкой, равно n), то решение является оптимальным, в противном случае переход к следующему этапу.

3) Поиск минимального набора строк и столбцов, содержащих нули. Для этого необходимо отметить точкой:

а) все строки, в которых не имеется ни одного отмеченного точкой нуля (табл.3);

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

в) все строки, содержащие отмеченные точкой нули, хотя бы в одном из отмеченных точкой столбцов (табл.2,3).

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

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

Таблица 4

Вj Аi	В1	В2	В3	В4
А1	0 ◦
А2		0 ◦
А3			0 ◦
А4				0 ◦

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

Оптимальное решение может быть не единственным. Для нашей задачи минимальное значение целевой функции будет равно