Теоретический материал к выполнению задания № 1

1. Составление экономико-математической модели задачи

где С_ij – стоимость назначения i -го ресурса на j -й объект;

n – число ресурсов (объектов).

2. Алгоритм решения задачи о назначениях венгерским методом.

2.1 Составление приведенной матрицы

2.1.1 Составление матрицы С размером n x n

2.1.2 Приведение матрицы.

2.1.2.1 Нахождение в каждой строке наименьшего элемента и вычитание его из элементов данной строки.

2.1.2.2 Повторение процедуры п.2.1.2.1 для столбцов.

2.2 Определение назначений.

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

При отсутствии строк, содержащих только одну нулевую клетку, допустимо начинать с любого нулевого значения.

2.2.2 Зачеркивание оставшихся нулевых значений в столбцах, соответствующих конкретным назначениям.

2.2.3 Если после выполнения пунктов 2.2.1 и 2.2.2 в каждой строке и в каждом столбце матрицы С можно выбрать по одному нулевому элементу, в который можно сделать назначение, то полученное решение будет оптимальным назначением. Задача решена.

Если пункт 2.2.3 выполнить невозможно, то переход к п.2.3.

2.3 Модификация приведенной матрицы.

2.3.1 Минимальным числом прямых (только параллельных и взаимно перпендикулярных) зачеркиваются все пути в приведенной матрице.

2.3.2 Из невычеркнутых элементов выбирается наименьший.

2.3.3 Найденный в п.2.3.2 элемент, вычитается из каждого невычеркнутого элемента.

2.3.4 Найденный в п.2.3.2 элемент суммируется с элементами, стоящими на пересечении проведенных в п.2.3.1 прямых.

2.3.5 Полученная модифицированная матрица имеет дополнительное число нулей.

2.3.6 Возврат к п.2.3