Этап второй

Этап 2 следует за первым этапом, если для какой-то строки . Этап 2 заключается в построении цепочки в матрице и построении матрицы .

1. В матрице строится цепочка, первый элемент которой , расположенный в строке, для которой . Второй элемент - , расположенный в том же столбце, что и . Третий элемент -, расположенный в той же строке, что и и т.д. Последний элемент цепочки всегда .

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

Далее для вычисляется суммарная невязка. Если , то конец алгоритма, иначе – следующая итерация.

ЭТАП ТРЕТИЙ

На этом этапе осуществляется переход от матрицы к , в которой появляется один или более невыделенных нулей.

1. Среди невыделенных элементов матрицы ищется минимальный: .

2. Значение h добавляется ко всем элементам выделенных знаком <+> столбцов и вычитается из всех элементов невыделенных строк матрицы . В результате получаем и переходим к этапу 1.

Лекция 14. Задача назначения.

Постановка задачи назначения: имеется n исполнителей и имеется n работ

Которые необходимо выполнить. Заданы эффективности выполнение каждым из исполнителей каждой работы.

Необходимо распределить исполнителей по работам таким образом, чтобы суммарная эффективность была максимальной. При этом каждый исполнитель исполняет только одну работу. Эта задача относится к классу комбинаторных задач. Общее количество вариантов n!

Математическая постановка:

Введем переменные:

Матрица состоит из 0 и 1.Строки-исполнители, столбцы-работы. В каждой строчке и в каждом столбце будет одна единица.

Критерий суммарной эффективности:

Ограничения:

Каждая работа выполняется

одним исполнителем.

Каждый исполнитель выполняет

одну работу.

Эта задача линейного программирования. Будем решать эту задачу венгерским методом.

Определение1: Нулевые элементы матрицы называются независимыми, если в строках и столбцах где они находятся, не содержится других.

Дата добавления: 2014-01-07