Содержание

Введение            3

1 Задача о назначениях. Венгерский метод      4

   1.1 Задача о назначениях        4

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

2 Решение задачи о назначениях с помощью венгерского метода  15

Заключение           20

Список использованной литературы       21

 

Введение

      Задача  о назначениях является частным случаем классической транспортной задачи и, как следствие, является задачей транспортного типа.

     Транспортная  задача – задача о наиболее экономном плане перевозок однородного или взаимозаменяемого продукта из пункта производства (станций отправления), в пункты потребления (станции назначения) – является важнейшей частной задачей линейного программирования, имеющей обширные практические приложения не только к проблемам транспорта.

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

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

1.1 Задача о назначениях

      Предположим, что имеется п различных работ, каждую из которых может выполнить любой из п привлеченных исполнителей. Стоимость выполнения і-й работы j-м исполнителем известна и равна C_іj (в условных денежных единицах). Необходимо распределить исполнителей по работам (назначить одного исполнителя на каждую работу) так, чтобы минимизировать суммарные затраты, связанные с выполнением всего комплекса работ.

      В исследовании операций задача, сформулированная выше, известна как задача о назначениях. Введем переменные X_ij, где X_ij принимает значение 1 в случае, когда і-ю работу выполняет j-й исполнитель, и значение 0 во всех остальных случаях, i,j = 1, п. Тогда ограничение

      гарантирует выполнение каждой работы лишь одним  исполнителем, ограничение

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

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

                   

      

(1)

      Задача  о назначениях (1) является частным  случаем классической транспортной задачи, в которой надо положить При этом условие означает выполнение требования целочисленности переменных x_іj. Это связано с тем, что мощности всех источников и стоков равны единице, откуда следует, что в допустимом целочисленном решении значениями переменных могут быть только 0 и 1.

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

      В задаче о назначениях переменное х_іj может принимать значение 0 или 1. При этом, согласно (1), в любом допустимом решении лишь п переменных могут принимать значения 1. Таким образом, любое допустимое базисное решение задачи о назначениях будет вырожденным.

      На  практике встречаются задачи о назначениях, в постановках которых параметр понимается как эффективность выполнения і-й работы j-м исполнителем. В этих случаях нужно так распределить работы между исполнителями, чтобы суммарная эффективность их выполнения была бы максимальной, т.е.

                                     (2)

      где максимум ищется при ограничениях, указанных в (1).

      Параметры задачи о назначениях (1) удобно представлять матрицей , которую называют матрицей стоимости. Предположим, что и С  = (c_іj) — две матрицы стоимости, элементы которых связаны следующим образом:

      где — некоторые постоянные. Таким образом, для получения матрицы С* нужно к элементам каждой і-й строки матрицы С прибавить число d,-, а к элементам ее каждого j-гo столбца — число Ц. В этом случае, если X — допустимое решение, удовлетворяющее ограничениям из (1), и

      

      то  с учетом ограничений из (1) типа равенства имеем

      где

      Таким образом, для любого допустимого решения X соответствующие ему значения функций будут отличаться на постоянную у, которая не зависит от X. Поэтому, если есть две задачи о назначениях с одним и тем же множеством G допустимых решений и целевыми функциями соответственно, то их оптимальные решения совпадают. Нетрудно убедиться в наличии аналогичного свойства и у классической транспортной задачи.

      Если  задача о назначениях является задачей  максимизации, т.е. ищется максимум целевой  функции на множестве G допустимых решений, которое задается системой ограничений из (1), то эквивалентную ей задачу минимизации

                                 (3)

      формально нельзя отнести к задачам о  назначениях, поскольку коэффициенты ее целевой функции не являются положительными. Это несоответствие можно преодолеть, заменив (3) эквивалентной задачей

                                  (4)

      в которой

      

      так как в этом случае для всех имеет место неравенство .

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

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

 

Заключение

      Суть  венгерского метода состоит в следующем: Путем прибавления определенным образом найденных чисел к некоторым столбцам и вычитания из них некоторых чисел находят систему так называемых независимых нулей. Набор нулей называется системой независимых нулей, если никакие два (или больше) нуля не лежат на одной линии (в строке или столбце). Если число независимых нулей равно n, то, приняв соответствующие им переменные x_ij равными 1, а все остальные – равными 0, согласно утверждению 2, получим оптимальный план назначения.

      Алгоритм  венгерского метода состоит из предварительного шага и не более, чем (n-2) последовательно повторяющихся итераций. На предварительном этапе в случае решения задачи на максимум, ее преобразуют в эквивалентную задачу на минимум. На этом же этапе выделяется система независимых нулей. Каждая последующая итерация направлена на увеличение хотя бы на 1 числа независимых нулей. Как только число независимых нулей k станет равным размерности матрицы (k=n) , задача решена.

      Оптимальный план назначения определится положением независимых нулей на последней итерации. 

 

Список использованной литературы

1. Волков  И.К., Загоруйко Е.А. Исследование операций: Учеб. для вузов. 2-е узд. / Под ред.. В.С. Зарубина, А.П. Крищенко. – М.: Узд-во МГТУ им. Н.Э. Баумана, 2002. – 436 с.
2. Зайченко Ю.П. Исследование операций: Учеб. пособие для студентов вузов. – 2-е изд., перераб. и доп. – Киев: Вища школа. Главное изд-во, 1979. 392 с.
3. И. А. Акулич. Математическое программирование в примерах и задачах. - М.: «Высшая школа», 1986.- 319 с.
4. Сакович В.А. Исследование операций (детерминированные методы и модели): Справочное пособие. - Мн.: Выш. шк., 1984.-256с.
5. Таха Х. Введение в исследование операций: в двух книгах. Кн.1,2 Пер. с англ. - М.: Мир, 1985.
6. Хазанова Л.Э. Математическое программирование в экономике: Учебное пособие. – М.: Издательство БЕК, 1998. – 141с.