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

Курсовая работа

по дисциплине «Математические  методы»

на тему «Задача о назначениях»

Студентка: ____________ ./

Руководитель: ___________ /

Содержание

Введение

1. Теоретические основы  задач о назначениях

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

1.2 Особые случаи задачи о назначениях

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

2.1 Сущность Венгерского  метода

2.2 Описание алгоритма венгерского метода

2.3 Венгерский метод для транспортной задачи

2.4 Обоснование Венгерского метода

3. Алгоритм решения задачи назначениях

Заключение

Список литературы

Введение

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

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

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

В современных  условиях развития каждое предприятие  стремится с наименьшими затратами  функционировать в сложившихся  условиях с целью получения высоких  доходов. Экономико-математические задачи о назначениях позволяют найти  оптимальный вариант размещения одного кандидата на выполнение одной  работы таким образом, чтобы минимизировать суммарные затраты по выполнению комплекса работ группой исполнителей. Также возможны некоторые модификации задачи о назначениях: во-первых, она иногда формулируется как задача максимизации (например, суммарного дохода от назначения всех исполнителей на работы); во-вторых, штатный состав организации может быть представлен большим количеством исполнителей, нежели количество работ, на которые должны быть назначены или, наоборот, большее количество работы, при недостаточном количестве исполнителей для ее выполнения; в-третьих, выполнение какой-либо работы по каким-либо причинам запрещается исполнять какому-либо работнику. В такой постановке данная задача относится к классу комбинаторных, решение которых путем прямого перебора невозможно при достаточно больших n, так как число вариантов назначений составляет n!. Данный программный продукт позволяет за короткий промежуток времени решать описанные модификации задачи о назначениях венгерским методом, с определением оптимального варианта размещения исполнителей по работам, исходя из поставленных условий. Идея метода была высказана венгерским математиком Эгервари и состоит в следующем. Строится начальный план, не удовлетворяющий в общем случае всем условиям задачи. Далее осуществляется переход к новому плану, более близкому к оптимальному. Последовательное применение этого приема за конечное число итераций приводит к решению задачи.

Цель работы - исследовать  решение задач о назначениях.

Задачи:

1. Рассмотреть  теоретические основы задач о  назначениях;

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

Глава 1. Теоретические  основы задач о назначениях

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

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

1.2 Особые случаи задачи о назначениях

МАКСИМИЗАЦИЯ ЦЕЛЕВОЙ  ФУНКЦИИ

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

Пример: В распоряжении некоторой  компании имеется 6 торговых точек и 6 продавцов. Из прошлого опыта известно, что эффективность работы продавцов  в различных торговых точках неодинакова. Коммерческий директор компании произвел оценку деятельности каждого продавца в каждой торговой точке. Результаты этой оценки представлены в табл. 13.38.

Таблица 13.38. Объемы продаж в  различных торговых точках для различных  продавцов

Как коммерческий директор должен осуществить назначение продавцов  по торговым точкам, чтобы достичь  максимального объема продаж?

Решение.

Все элементы исходной таблицы  умножаются на (-1);

Минимальный (наибольший по абсолютной величине) элемент вычитается из всех элементов соответствующей  строки.

Минимальный элемент вычитается из всех элементов соответствующего столбца.

Дальнейший поиск оптимального решения осуществляется в соответствии с обычным алгоритмом (см. пример).

НЕДОПУСТИМЫЕ НАЗНАЧЕНИЯ

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

НЕСООТВЕТСТВИЕ ЧИСЛА  ПУНКТОВ ПРОИЗВОДСТВА И НАЗНАЧЕНИЯ

Если исходная таблица  не является квадратной, в нее следует  включить дополнительные фиктивные  строки и столбцы, необходимые для  приведения ее к квадратной форме. Значения стоимости, соответствующие фиктивным  клеткам, как правило, равны нулю.

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

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

2.1 Сущность Венгерского  метода

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

Частным случаем транспортной задачи является задача о назначениях, в которой число пунктов производства равно числу пунктов назначения, т.е. транспортная таблица имеет форму квадрата. Кроме того, в каждом пункте назначения объем потребности равен 1, и величина предложения каждого пункта производства равна 1. Любая задача о назначениях 2может быть решена с использованием методов линейного программирования или алгоритма решения транспортной задачи. Однако ввиду особой структуры данной задачи был разработан специальный алгоритм, получивший название Венгерского метода.

Венгерский метод является одним из интереснейших и наиболее распространенных методов решения  транспортных задач.

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

Постановка задачи. Предположим, что имеется различных работ и механизмов , каждый из которых может выполнять любую работу, но с неодинаковой эффективностью. Производительность механизма при выполнении работы обозначим , и = 1,...,n; j = 1,...,n. Требуется так распределить механизмы по работам, чтобы суммарный эффект от их использования был максимален. Такая задача называется задачей выбора или задачей о назначениях.

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

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

Введем следующие понятия.

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

Две прямоугольные матрицы С и D называются эквивалентными (C ~ D), если для всех i,j . Задачи о назначениях, определяемые эквивалентными матрицами, являются эквивалентными (т.е. оптимальные решения одной из них будут оптимальными и для второй, и наоборот).

2.2 Описание алгоритма венгерского метода

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

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

Далее рассматривают i - ю  строку полученной матрицы, разыскивают  ее минимальный элемент a_i и из каждого элемента этой строки вычитают минимальный. Эту процедуру повторяют со всеми строками. В результате получим матрицу С₀ (С₀ ~ C), в каждой строке и столбце которой имеется, по крайней мере, один нуль. Описанный процесс преобразования С в С₀ называется приведением матрицы.

Находим произвольный нуль в первом столбце и отмечаем его  звездочкой. Затем просматриваем  второй столбец, и если в нем есть нуль, расположенный в строке, где  нет нуля со звездочкой, то отмечаем его звездочкой. Аналогично просматриваем  один за другим все столбцы матрицы  С₀ и отмечаем, если возможно, следующие нули знаком “*”. Очевидно, что нули матрицы С₀, отмеченные звездочкой, являются независимыми. На этом предварительный этап заканчивается.

(k+1)-ая итерация. Допустим, что k-я итерация уже проведена и в результате получена матрица С_k. Если в ней имеется ровно n нулей со звездочкой, то процесс решения заканчивается. В противном случае переходим к (k+1) - й итерации.

Каждая итерация начинается первым и заканчивается вторым этапом. Между ними может несколько раз  проводиться пара этапов: третий - первый. Перед началом итерации знаком “+”  выделяют столбцы матрицы С_k, которые содержат нули со звездочками.

Первый этап. Просматривают  невыделенные столбцы С_k. Если среди них не окажется нулевых элементов, то переходят к третьему этапу. Если же невыделенный нуль матрицы С_k обнаружен, то возможен один из двух случаев: 1) строка, содержащая невыделенный нуль, содержит также и нуль со звездочкой; 2) эта строка не содержит нуля со звездочкой.

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

В первом случае этот невыделенный нуль отмечают штрихом и выделяют строку, в которой он содержится (знаком “+” справа от строки). Просматривают  эту строку, находят нуль со звездочкой и уничтожают знак “+” выделения  столбца, в котором содержится данный нуль.

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

Этот процесс за конечное число шагов заканчивается одним  из следующих исходов:

1). все нули матрицы С_k выделены, т.е. находятся в выделенных строках или столбцах. При этом переходят к третьему этапу;

2). имеется такой невыделенный нуль в строке, где нет нуля со звездочкой. Тогда переходят ко второму этапу, отметив этот нуль штрихом.

Второй этап. На этом этапе  строят следующую цепочку из нулей  матрицы С_k: исходный нуль со штрихом, нуль со звездочкой, расположенный в одном столбце с первым нулем со штрихом в одной строке с предшествующим нулем со звездочкой и т.д. Итак, цепочка образуется передвижением от 0' к 0^* по столбцу, от 0^* к 0' по строке и т.д.

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

Далее над элементами цепочки, стоящими на нечетных местах ( 0' ) -, ставим звездочки, уничтожая их над четными элементами ( 0^* ). Затем уничтожаем все штрихи над элементами С_k и знаки выделения “+”. Количество независимых нулей будет увеличено на единицу. На этом (k+1) -я итерация закончена.

Третий этап. К этому  этапу переходят после первого, если все нули матрицы С_k выделены. В таком случае среди невыделенных элементов С_k выбирают минимальный и обозначают его h (h>0). Далее вычитают h из всех элементов матрицы С_k, расположенных в невыделенных строках и прибавляют ко всем элементам, расположенным в выделенных столбцах. В результате получают новую матрицу С^'_k, эквивалентную С_k. Заметим, что при таком преобразовании, все нули со звездочкой матрицы С_k остаются нулями и в С^'_k, кроме того, в ней появляются новые невыделенные нули. Поэтому переходят вновь к первому этапу. Завершив первый этап, в зависимости от его результата либо переходят ко второму этапу, либо вновь возвращаются к третьему этапу.

После конечного числа  повторений очередной первый этап обязательно  закончится переходом на второй этап. После его выполнения количество независимых нулей увеличится на единицу и (k+1) - я итерация будет  закончена.

Пример. Решить задачу о назначениях  с матрицей

При решении задачи используем следующие обозначения:

Знак выделения “+”, подлежащий уничтожению, обводим кружком; цепочку, как и ранее, указываем стрелками.

Предварительный этап. Отыскиваем максимальный элемент первого столбца - 4. Вычитаем из него все элементы этого  столбца. Аналогично для получения  второго, третьего, четвертого и пятого столбцов новой матрицы вычитаем все элементы этих столбцов от п'яти, трех, двух и трех соответственно. Получим матрицу С^'(C^'~C). Так как в каждой строке С^' есть нуль, то С^' = С₀ и процесс приведения матрицы заканчивается. Далее ищем и отмечаем знаком “*” независимые нули в С₀, начиная с первой строки.

Первая итерация. Первый этап. Выделяем знаком “+” первый, второй, и четвертый столбцы матрицы  С₀, которые содержат 0^*.

Просматриваем невыделенный третий столбец, находим в нем  невыделенный нуль С₂₃ = 0, отмечаем его штрихом и выделяем знаком “+” вторую строку. Просматриваем эту строку, находим в ней элемент С₂₂ = 0^* и уничтожаем знак выделения второго столбца, содержащего 0^*. Затем просматриваем второй столбец - в нем нет невыделенных элементов. Переходим к последнему невыделенному столбцу (пятому), ищем в нем невыделенные нули. Поскольку невыделенных нулей нет, то переходим к третьему этапу.

Третий этап. Находим минимальный  элемент в невыделенной части  матрицы С₀ (т.е. элементы, которые лежат в столбцах и строках, не отмеченных знаком “+”). Он равен h = 1.

Вычтем h = 1 из всех элементов  невыделенных строк (т.е. всех, кроме  второго) и прибавим ко всем элементам  выделенных столбцов (первого и четвертого). Получим матрицу С^'₁ и перейдем к первому этапу.

Первый этап. Перед его  началом вновь выделяем знаком “+”  первый, второй и четвертый столбцы. Просматриваем невыделенный третий столбец, находим в нем невыделенный нуль С₂₃ = 0, отмечаем его знаком штрих. Поскольку во второй строке есть 0^* (элемент С₂₂), то выделяем знаком “+” вторую строку, далее уничтожаем знак выделения второго столбца, где лежит 0^*. Потом просмотрим второй столбец, находим в нем невыделенный нуль С₁₂ = 0, отмечаем его знаком штрих. Поскольку в первой строке есть нуль со звездочкой С₁₄ = 0^*, то выделяем его знаком “+”, и уничтожаем знак выделения четвертого столбца, где находился этот знак 0^*. Затем пересматриваем четвертый столбец и находим в нем невыделенный нуль С₅₄ = 0. Так как в строке, где он находится, нет нуля со звездочкой, то отметив этот 0 штрихом, переходим ко второму этапу.

Второй этап. Начиная с  элемента с₅₄ = 0', строим цепочку, двигаясь от него по столбцу. Находим нуль со звездочкой с₁₄ = 0^*, далее от него движемся вдоль первой строки и находим 0'(с₁₂), от этого элемента движемся вдоль первого столбца к с₂₂ = 0^*, в конечном итоге, двигаясь от с₂₂ = 0^* вдоль второй строки приходим к исходному с₂₃ = 0'. Таким образом, цепочка построена: 0'₅₄-0^*_14-0'_12-0^*_22-0'₂₃. Заменяем штрих на звездочку и уничтожаем звездочки над четными элементами цепочки, а также все знаки выделения столбцов и строк. На этом первая итерация заканчивается. В результате число независимых нулей увеличилось на единицу. Поскольку следующие итерации выполняются аналогично, то приведем результаты их выполнения без дополнительных пояснений. После второй итерации количество независимых нулей (0^*) стало равно 5 (размерности матрицы С) и поэтому алгоритм заканчивает работу. Искомые элементы назначения соответствуют позициям независимых нулей матрицы С₃ (т.е. 0^*).

Соответствующее значение целевой  функции

Первая итерация. Первый этап Третий этап

h=1

Первая итерация. Первый этап. Второй этап.

Вторая итерация

Первый этап Второй этап

2.3 Венгерский метод для транспортной задачи

Рассмотренная выше задача о назначениях представляет собой  частный случай Т-задачи, когда . Поэтому венгерский метод, применимый для решения транспортной задачи специального вида, можно распространить на общий случай Т-задачи. [18; 59].

Пусть требуется решить Т-задачу следующего вида минимизировать

при условиях

Алгоритм решения Т-задачи, основанный на венгерском методе, состоит  из предварительного этапа и конечного  числа однотипных итераций.

В результате предварительного этапа вычисляют матрицу

элементы которой удовлетворяют следующим условиям:

(3.3.1)

(3.3.2)

Если в условиях (3.3.1), (3.3.2) строгие равенства, то матрица Х₀ является решением Т-задачи.

Матрицу, построенную в  результате k-й итерации, обозначим

Обозначим также

(3.3.3)

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

Описание алгоритма Венгерского метода

Предварительный этап. В каждом из столбцов матрицы транспортных издержек отыскивают минимальный элемент, который вычитают из всех элементов этого столбца. Получают матрицу С'. Далее в каждой строке матрицы С' выбирают минимальный элемент и вычитают его из всех элементов рассматриваемой строки. Приходят к матрице С₀ (С₀ ~ C), все элементы которой неотрицательны, причем в каждой строке и столбце С₀ имеем по крайней мере, один нуль. Строят матрицу Х₀ так, чтобы ее ненулевые элементы были расположены в позициях нулей матрицы С₀.

Пусть -- номер строки, в которой расположен k-й нуль j-го столбца матрицы С₀. Тогда элементы первого столбца матрицы Х₀ определяют по рекуррентной формуле

(3.3.4)

Т.е. все элементы первого  столбца , которым соответствуют ненулевые элементы в матрицы С₀, заполняют нулями, а остальные элементы этого столбца заполняют по методу северо-западного угла.

Допустим, что столбцы  Х₀ от первого до (j-1) - го включительно уже заполнены. Тогда элементы j-го столбца определяют в соответствии с формулой

(3.3.5)

Если , то Х₀ - оптимальный план Т-задачи. Если , то переходим к первой итерации.

(k+1)-я итерация. Допустим, что уже проведено k итераций, причем . В этом случае необходимо, используя матрицы С_k и Х_k, провести следующую (k+1)-ю итерацию. Перед началом итерации выделяют знаком «+» те столбцы матрицы С_k, для которых невязки по столбцам равны

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

Возможен один из двух случаев: 1) , 2) . В первом случае -ю строку С_k отмечают знаком “+” справа от нее, а сам невыделенный нуль отмечают штрихом. Далее просматривают элементы -й строки, которые лежат в выделенных столбцах и ищут среди них существенные нули (напомним, что существенным нулем С_k называется такой элемент , для которого ). Если таким существенным нулем оказался элемент , а сам столбец m -- выделен, то знак выделения “+” над столбцом m уничтожают, а сам этот нуль отмечают звездочкой.

Затем просматривают m-й столбец  и отыскивают в нем нуль (нули), расположенные в отличных от -й строках. Если такой нуль имеется, то отмечают его штрихом и анализируют невязку его строки.

Далее процесс поиска нулей  и выделение их (штрихами или звездочками) продолжается аналогично, и за несколько  шагов он заканчивается одним  из следующих исходов:

1) найдем очередной невыделенный  нуль матрицы С_k, для которого невязкая в строке . Тогда отметив его штрихом, переходим ко второму этапу;

2) все нули матрицы  С_k оказались выделенными, причем для каждого из нулей, выделяемых штрихом, невязка . Тогда переходим к третьему этапу.

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

Второй этап. Состоит в  построении цепочки из нулей матрицы  С_k, отмеченных штрихами и звездочками, и в последующем переходе к новой матрице Х_k+1

Пусть для некоторого нуля со штрихом матрицы С_k, расположенного, например, в позиции ( ), невязка строки . Начиная с этого элемента , строят цепочку из отмеченных нулей матрицы С_k: двигаясь по столбцу , выбирают нуль со звездочкой , далее двигаясь от него по строке , находят нуль со штрихом . Потом движутся от него по столбцу m₂ к следующему нулю со звездочкой и т.д.. Такой последовательный переход от 0' к 0^* по столбцу и от 0^* к 0' по строке осуществляют до тех пор, пока это возможно.

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

После того как цепочка  вида

построена, осуществляют переход  к матрице от матрицы Х_k по формулам

(3.3.7)

где (3.3.8)

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

Вычисляем невязку для

На этом (k+1)-я итерация заканчивается.

Третий этап. Итак, допустим, что все нули выделены. Третий этап заключается в переходе от матрицы  С_k к эквивалентной матрице С?_k, в которой появляется новый невыделенный нуль (или нули). Пусть , где минимум выбирают из всех невыделенных элементов матрицы С_k. Тогда из всех элементов невыделенных строк матрицы С_k вычитают h, а ко всем элементам выделенных столбцов прибавляют h. В результате получают матрицу С'_k(С'_k ~ C_k), в которой все существенные нули матрицы С_k остаются нулями, и кроме того, появляются новые невыделенные нули.

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

Если после выполнения второго этапа то Х_k+1 - оптимальный план. В противном случае переходим к (k+2) итерации.

Отметим некоторые важные особенности венгерского метода.

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

Метод позволяет на каждой итерации по величине невязки оценить близость Х_k к оптимальному плану, а также верхнюю границу необходимого числа оставшихся итераций N_ост:

(3.3.9)

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

2.4 Обоснование венгерского метода

Прежде всего введем справедливость признака оптимальности, т.е. если , то план Х_k - оптимален.

Действительно, в силу построения Х_k, если , то (эти нули называют существенными). Поэтому план Х_k оказывается оптимальным для задачи с матрицей С_k, так как

(3.3.10)

Но матрица С_k получена эквивалентными преобразованиями из исходной матрицы С. Докажем, что Х_k - оптимален и для задачи с матрицей С. Матрицы С и С_k как эквивалентные связаны соотношениями

для всех (i,j) (3.3.11)

Тогда значение целевой функции  для плана Х_k при матрице С будет равно