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

На предварительном этапе формируются нули матрицы С в позициях с минимальными элементами.

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

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

3. По матрице формируется матрица . В этой матрице полагаются равными нулю , для которых соответствующие элементы не равны нулю. , . Остальные элементы матрицы находятся метолом северо-западного угла.

Далее вычисляются невязки в по строкам и столбцам и вычисляется суммарная невязка . При этом может оказаться, что полученный план является недопустимым (,). План недопустим, если не равно нулю. Если , то полученный план является оптимальным. Если , то переходим к первой итерации. Допустим, проведено k итераций. На каждой итерации вычислялась невязка . И после проведения k итераций . В этом случае необходимо, используя матрицы и провести (k+1) итерацию. Перед началом итерации выделяются знаком <+> те столбцы матрицы , для которых невязка по столбцу равна нулю, т.е. .

Этап первый

1. Просматриваются, невыделенные знаком <+> столбцы матрицы . В них отыскиваются не выделенные знаком <’> нули. Если таких нулей нет , то переход к этапу 3. Если такой нуль найден, он отмечается знаком <’> и определяется невязка по строке в , в которой находится этот ноль. Если невязка этой строки больше нуля, то переход на этап 2. Если невязка равна нулю, то в матрице эта строка помечается <+>.

2. В выделенной строке ищется существенный ноль. Если он есть, то он помечается знаком <*>, а знак <+> над соответствующим столбцом матрицы аннулируется (отмечается ).

3. В этом столбце ищется невыделенный ноль, расположенный в строке, не помеченной <+>. Если такой ноль есть, он помечается <’>, а соответствующая строка помечается <+>. Далее определяется невязка этой строки. Если она больше нуля (), то переход на этап 2, если , то в этой строке ищется существенный ноль. Далее процесс выделения нулей может закончиться одним из двух исходов:

• Найден , для которого невязка по строке равна нулю. В этом случае переход к этапу 2.

• Все нули матрицы оказались выделенными, причём для всех невязки по строкам равны нулю.

Этап второй

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

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

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

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

ЭТАП ТРЕТИЙ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

одну работу.

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

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

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

Идея метода состоит из предварительного этапа и итераций. Их количество не больше n-2. Каждая итерация включает три этапа, начинаем первым этапом, заканчиваем вторым. Могут несколько раз повторяться первый и третий этапы. Каждая итерация связана с эквивалентным преобразованием матрицы C, полученной в результате предыдущей итерации и выбором максимального числа независимых нулей. Если число независимых нулей станет равным n то найдено оптимальное распределение.

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

Шаг первый: В матрице C в каждом столбце находится максимальный элемент. Строится матрица элементы которой равны:

Шаг второй: В матрице в каждой строке ищется минимальный элемент Строится матрица элементы которой будут равны .

Шаг третий: В матриц выделяются независимые . Для этого последовательно просматриваются столбцы. В первом столбце любой 0 объявляется независимым и помечается знаком “ * ”, а столбец помечается знаком “ + ”. Далее просматриваются 0 второго столбца .Если во втором столбце найдется 0 который находится в строке где нет этого то он объявляется независимым и также помечается ” * ” и столбец помечается “ +” и т. д. Если в матрице выделено n независимых 0 т.е. все столбцы помечены знаком «+» то получено оптимальное решение. Этому решению соответствует позиция независимых 0 матрицы . Переходим на первый этап итерации.

Предположим, проведено k итераций. Приступаем к k+1 итерации.

Этап первый.

Шаг первый: Просматриваются невыделенные столбцы матрицы . Если в этих столбцах отсутствуют 0 то переход к этапу три .Если найден 0 то его отмечают знаком штрих, а строчку помечают знаком "+". Переходим на шаг второй.

Шаг второй: В отмеченной строке осуществляется поиск независимого 0 если он отсутствует, то переход к этапу второму. Если такой 0 есть, то аннулируется знак "+ " над столбцом в котором этот независимый 0 расположен.

Шаг третий: В этом столбце осуществляется поиск невыделенного 0, т.е. он должен находиться в строке, не помеченной знаком "+". Если такого 0 нет, то переход к этапу третьему. Если такой 0 есть, то он помечается знаком штрих, а строка помечается знаком "+". Затем просматривается эта строка. И отыскивается, если он есть независимый 0. Если есть, то аннулируется знак "+" над столбцом и т.д.За конечное число шагов процесс поиска заканчивается одним из двух исходов:

1. В строке, где есть 0 со штрихом нет независимых 0 - в этом случае переходим ко второму этапу.

2. Все 0 матрицы выделены, т.е. находятся в выделенных строках или столбцах, в этом случае переход к третьему этапу.

   Этап второй.

   Шаг первый: В матрице строится цепочка из следующих элементов первый элемент это последний 0 со штрихом. Второй элемент это 0 со звездочкой, находящийся в том же столбце, что и первый 0 со штрихом. Третий элемент 0 со штрихом находится в той же строке что и второй элемент 0 со звездочкой и т.д.

Последний элемент цепочки это 0 со штрихом.

Шаг второй: В построенной цепочке 0 со штрихом заменяется на 0 со звездочкой, а звездочка аннулируется. А остальные элементы матрицы C_k которые не вошли в цепочку, остаются без изменения. Все штрихи и все "+ " в строках уничтожаются. Остаются 0 со звездочкой. Получаем матрицу .

В матрице все столбцы с независимым 0 помечаются знаком "+" при этом матрице С_к+1 количество независимых 0 увеличится на один. Если количество 0 станет равным n, то конец. Записывается матрица X с единицами в позициях соответствующим независимым 0 в С_к+1 и вычисляется критерий эффективности.