I. Предварительный этап.

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

II. Этап расстановки пометок.

Данный этап либо позволяет определить ,что ММНДК построена, либо найти возможность увеличить построенное мн-во на 1-у клетку.

1. Строки, в которых нет единицы помечаются «-». Если таких строк нет, то ММНДК построена.

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

3. В произвольном порядке просматриваем помеченные столбцы, находим в помеченном столбце единицу и соотв-ую строку помечаем номером просматриваемого столбца. Если встретился столбец без единицы, то построенное мн-во независимых допустимых клеток можно увеличить на единицу и переходим к этапу III, в противном случае переходим к шагу 2, с новыми помеченными строками.

III. Этап переброски.

В рез-те осуществ. данного этапа кол-во незав. допустимых клеток увеличивается на единицу. Пометки, сделанные на II-м этапе указывают для столбца номера строки, где надо поставить единицу в этом столбце, а для строки – номер столбца, из которого следует убрать единицу.

1. Просматриваем столбец, в кот. нет единицы и ставим единицу в ту строку, на которую указывает пометка данного столбца.

2. Убираем единицу из строки, где только что была поставлена новая единица и перемещаем ее по столбцу в ту строку с номером пометки этого столбца.

Процесс переброски единиц проводим до тех пор, пока не поставим единицу в строку, помеченную «-».

Далее следует стереть все пометки и перейти к этапу II.

14. Классическая задача о назначении.

Пусть имеется исполнителей и работ, пусть - стоимость выполнения -ой работы -ым исполнителем.

Построим математическую модель задачи:

Целевая функция

,

.

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

Приведем свойства оптимального решения задачи (1), (2).

Свойство1. Пусть - некоторый план задачи (1), (2). Пусть и - некоторые числа. Если план - оптимален для задачи (1),(2), то он будет оптимальным для задачи (3),(2), где .

Справедливо и обратное утверждение.

Док-во. Рассмотрим целевую функцию (3)

Отсюда следует справедливость устанавливаемого свойства.

Свойство 2. Пусть , тогда если найдем такой план , на котором целевая функция принимает значение равное 0, то построенный план оптимален.

Док-во. Следует из ограниченности целевой функции снизу нулем.

Венгерский метод решения задачи о назначении.

I этап. Приведение матрицы.

1. Каждой строке матрицы находим минимальный элемент , который вычитаем из каждого элемента рассматриваемой строки. Полученую матрицу обозначим -.

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