Решение задачи о назначениях венгерским методом

Решение задачи о назначениях венгерским методом

Постановка задачи:

Пусть управление механизации имеет 5 кранов. Требуется возвести 5 объектов. Известна себестоимость строительства каждым краном отдельного объекта. Требуется так распределить краны по объектам, чтобы обеспечить возведение всех объектов с минимальными суммарными затратами.

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

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

Математическая модель задачи примет вид:

найти план назначений    

при следующих ограничениях:

1.  Каждый исполнитель назначается только на одну работу:

2.  Каждый исполнитель назначается только на одну работу:

условие целочисленности:

где переменные , если  вид работ выполняется  исполнителем,  - в остальных случаях,

и чтобы общая стоимость возведения 5-ти объектов была минимальна:

Составим матрицу стоимостей выполнения работ:

Находим минимальный элемент в каждой строке исходной матрицы:

                                                                                     _min

Затем вычитаем минимальные элементы из всех элементов соответствующих строк и находим минимальные элементы в столбцах новой матрицы:

Вычитаем данные элементы из соответствующих столбцов матрицы:

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

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

План не оптимален, так как не построена система из n=5 независимых нулей.

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

План является оптимальным, так как построена система из n=5 независимых нулей.

z(x^*)=20+31+38+20+11=120 ден. ед.

Вывод: необходимо назначить первый кран на строительство 2-го объекта, второй на строительство 5-го, третий кран на 3-й объект, четвертый на строительство 1-го, а пятый кран на строительство 4-го объекта. При этом себестоимость минимальна и составляет 120 ден. ед.