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

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Министерство образования и науки РФ

ФГОУ СПО «Шадринский политехнический колледж»

Заведующая учебной частью

____________ Блинова Н. А.

«_____»____________20__г

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

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

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

Студентка: ____________ Зорькина Э.Р./

Руководитель: ___________ Ханина О. В./

Шадринск, 2011г.

Содержание

Введение

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	//	III	IV	V	VI
А	68	72	75	83	75	69
В	56	60	58	63	61	59
С	35	38	40	45	25	27
D	40	42	47	45	53	36
Е	62	70	68	67	69	70
F	65	63	69	70	72	68

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

Решение.

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

Таблица 13.39. Модификация исходных данных и выявление минимальных элементов
Продавец	Торговые точки
	I	II	III	IV	V	VI	Минимальный элемент
А В С D Е F	-68 -56 -35 -40 -62 -65	-72 -60 -38 -42 -70 -63	-75 -58 -40 -47 -68 -69	-83 -63 -45 -45 -67 -70	-75 -61 -25 -53 -69 -72	-69 -59 -27 -36 -70 -68	-83 -63 -45 -53 -70 -72

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

Таблица 13.40. Вычитание минимального элемента по строкам и выявление минимальных элементов по столбцам
15	11	8	0	8	14	? Минимальный элемент
7	3	5	0	2	4
10	7	5	0	20	18
13 8	11 0	6 2	8 3	01	17 0
7	9	3	2	0	4
7	0	2	0	0	0

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

Таблица Вычитание минимального элемента по столбцам
8	11	6	0	8	14
0	3	3	0	2	4
3	7	3	0	20	18
6	11	4	8	0	17
1	0	0	3	1	0
0	9	1	2	0	4

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

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

Данную проблему можно решить так же, как и транспортную задачу. Если по той или иной причине некоторое назначение является недопустимым, то в соответствующей клетке проставляется значение стоимости, которое заведомо больше любого другого значения. После этого в ходе реализации алгоритма мы сможем избежать данного назначения 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 при матрице С будет равно

(3.3.12)

Но так как , то

і. (3.3.13)

Подставляя (3.3.13) в (3.3.12), получим с учетом (3.3.10)

(3.3.14)

Но и не зависит от плана Х_k, поэтому план Х_k оптимален и для исходной задачи с матрицей С.

Перейдем теперь к обоснованию алгоритма.

Предварительный этап. На предварительном этапе строят матрицу Х_k элементы которой удовлетворяют условиям

, (3.3.15)

(3.3.16)

Если все условия (3.3.15), (3.3.16) выполняются как строгие равенства, то план Х₀ - оптимален, согласно только что доказанному.

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

Второй этап. Он состоит в построении цепочки из нулей со штрихами и звездочками и переходе к Х_k+1. Пусть цепочка имеет вид

(3.3.17)

Элементы матрицы Х_k+1 вычисляют по рекуррентным формулами

где (3.3.18)

Так как в каждой строке и столбце имеется как 0', так и 0^*, либо они оба отсутствуют, за исключением строки и столбца , где имеется лишь 0', то

(3.3.19)

(3.3.20)

Поэтому, если матрица Х_k удовлетворяла ограничениям (3.3.15), (3.3.16), то и матрица Х_k+1 будет им также удовлетворять.

Наконец, на основании соотношений (3.3.19), (3.3.20) получим

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

Пример. Найти решение транспортной задачи со следующими условиями

Проверим условие баланса

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

Строим начальную матрицу перевозок

Невязки для столбцов d_j = 0, 1, 9, 0, для строк d_j = 4; 6; 0. Суммарная невязка

Первая итерация. Первый этап. Отмечаем знаком “+” сверху первый и четвертый столбцы, которым соответствуют нулевые невязки, а знаком “х” слева первую и вторую строки, которым отвечают ненулевые невязки, черточкой сверху - существенные нули.

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

Третий этап. Среди элементов невыделенных строк и столбцов матрицы С₀ находим минимальный элемент h = 1, прибавляем его ко всем элементам выделенных столбцов и вычитаем из всех элементов невыделенных строк. Получим матрицу С₁.

Переходим к первому этапу.

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

Второй этап. Цепочка состоит из одного элемента С₂₂ = 0. Находим и прибавим q₁ = 1 к элементу х₁. Получим матрицу Х₁.

Вторая итерация. Первый этап. В матрице С₁ отмечаем знаком “+” первый, второй и четвертый столбцы, которым отвечают нулевые невязки. Находим в третьем столбце нуль С₃₃ = 0 и отмечаем его штрихом.

Так как невязка в третьей строке равна нулю, то выделяем ее знаком “+”. Просматриваем эту строку, находим в ней существенный нуль С₃₂, расположенный в выделенном столбце. Отмечаем его звездочкой и уничтожаем знак выделения второго столбца.

Далее просматриваем второй столбец и отыскиваем в нем невыделенный нуль С₂₂. Так как невязка по строке d₂ > 0, то отметив этот нуль штрихом, переходим ко второму этапу.

Второй этап. Строим цепочку в матрице С₁ вида , а затем аналогичную цепочку в матрице Х₁.

В результате получаем матрицу Х₂: q₂ = min {5, 8, 9} = 5

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

h = min {4, 3, 2} = 2

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

Третий этап. Находим минимальный невыделенный элемент в матрице С₂ h = 2, вычитаем h из всех элементов невыделенных строк и прибавляем ко всем элементам выделенных столбцов (т.е. прибавляем к четвертому столбцу и вычитаем из первой строки). В результате получим матрицу С₃, в которой появился новый невыделенный нуль (С ₁₃). Переходим к первому этапу.

Первый этап. В матрице С₃ находим невыделенный нуль С₁₃. Так как d₁ > 0, то переходим ко второму этапу.

Второй этап. Вся цепочка состоит из одного элемента . Поэтому q₃ = min {d₁ = 4, d₂ = 4} = 4. Прибавим q₃ к , получим матрицу X₃.

Так как D₃ = 0, то Х₃ - оптимальный план. Соответствующее значение целевой функции L_орт = (сравните с результатами решения этой задачи методом потенциалов, см. пример 3.3).

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

Этот алгоритм состоит из трех этапов.

Этап 1:

1. Формализация проблемы в виде транспортной таблицы по аналогии с решением транспортной задачи.

2. В каждой строке таблицы найти наименьший элемент и вычесть его из всех элементов данной строки.

3. Повторить ту же самую процедуру для столбцов.

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

Этап 2.

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

1. Найти строку, содержащую только одно нулевое значение стоимости, и в клетку, соответствующую данному значению, поместить один элемент. Если такие строки отсутствуют, допустимо начать с любого нулевого значения стоимости.

2. Зачеркнуть оставшиеся нулевые значения данного столбца.

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

4. Найти столбец, содержащий только одно нулевое значение, и в соответствующую клетку поместить один элемент.

5. Зачеркнуть оставшиеся нули в данной строке.

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

Если окажется, что таблица содержит неучтенные нули, повторить операции 1-6. Если решение является допустимым, т.е. все элементы распределены в клетки, которым соответствует нулевая стоимость, то полученное решение одновременно является оптимальным. Если решение является недопустимым, осуществляется переход к этапу 3.

Этап 3.

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

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

3. Вычесть его из всех элементов, через которые не проходят прямые.

4. Прибавить найденный элемент ко всем элементам таблицы, которые лежат на пересечении проведенных ранее прямых

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

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

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

Таблица Расстояние от сбытовых баз до потребителей
Сбытовая база	Расстояние, миль Потребители
	I	II	III	IV
А В С D	68 56 3847	72 60 40 42	75 58 35 40	83 63 45 45

Решение

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

Этап 1 Венгерского метода: В каждой строке находится наименьший элемент.

Таблица Выявление наименьших элементов по строкам
	Потребители	Наименьший элемент строки
	I	II	III	IV
А В С D	68 56 38 47	72 60 40 42	75 58 35 40	83 63 45 45	68 56 35 40

Наименьший элемент вычитается из всех элементов соответствующей строки

Таблица 13.31. Вычитание наименьшего элемента по строкам и выявление наименьшего элемента по столбцам
0	4	7	15
0	4	2	7
3	5	0	10
7	2	0	5
0	2	0	0	?Наименьший элемент столбца

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

Таблица Вычитание наименьшего элемента по столбцам
0	2	7	10
0	2	2	2
3	3	0	5
7	0	0	0

В соответствии с процедурой, описанной в этапе 2, осуществляются назначения. Наличие назначения обозначается через

Таблица Назначения в клетки с нулевыми значениями

0	2	7	10
0	2	2	2
3	3	0	5
7	0	0	0

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

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

Таблица Скорректированная таблица с назначениями для нулевых клеток
	I	II	III	IV
А	0	0	7	8
В	0	0	2	0
С	3	1	0	3
D	9	0	2	0

Теперь требование о размещении четырех назначений в клетки с нулевой стоимостью выполняется, следовательно, полученное решение является оптимальным. Перевозки осуществляются со сбытовой базы А к потребителю I, с базы В -- к потребителю II, с базы С -- к потребителю III и с базы D -- к потребителю IV. Хотя данное решение и является оптимальным, однако оно не единственное. В любом оптимальном решении должен присутствовать маршрут (С,III), поскольку это единственный элемент с нулевой стоимостью в строке С. Два других оптимальных распределения назначений представлены ниже.

Таблица Первое альтернативное оптимальное решение
	I	II	III	IV
A	0	0	1	8
В	0	0	2	0
С	3	1	0	3
D	9	0	2	0
Таблица Второе альтернативное оптимальное решение
	I	II	III	IV
А	0	0	7	8
В	0	0	2	0
С	3	1	0	3
D	9	0	2	0

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

Решение 1: 68 + 60 + 35 + 45 - 208 миль;

Решение 2: 68 + 63 + 35 + 42 = 208 миль;

Решение 3: 72 + 56 + 35 + 45 = 208 миль.

Общая дальность перевозок для всех трех решений одинакова.

Примечание: в задачах большей размерности, чем задача из примера 13.7. убедиться в том, что проведенное в соответствии с пунктом 1 этапа 3 число прямых является минимальным, гораздо труднее. В этой связи может оказаться полезным так называемое "правило правой руки":

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

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

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

4. Пункты 1-3 повторяются до тех пор, пока не будут учтены все входящие в таблицу нули.

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

Заключение

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

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

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

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

1. Агальцов, В.П. Математические методы в программировании: учебник. В.П. Агальцов, И.В. Волдайская. - М.: ИД «ФОРУМ»: ИНФРА-М, 2006 г. - 224 с.: ил.

2. Акулич И. А. Математическое программирование в примерах и задачах. - М.: «Высшая школа», 1986.- 319 с.

3. Волков И.К., Загоруйко Е.А. Исследование операций: Учеб. для вузов. 2-е узд. / Под ред.. В.С. Зарубина, А.П. Крищенко. - М.: Узд-во МГТУ им. Н.Э. Баумана, 2002. - 436 с.

4. Грызина, Н.Ю. Математические методы исследования операций / Н. Грызина. Учеб. Пособие. Москва: МЭСИ, 2005.- 12 с.

5. Зайченко Ю.П. Исследование операций: Учеб. пособие для студентов вузов. - 2-е изд., перераб. и доп. - Киев: Вища школа. Главное изд-во, 1979. 392 с.

6. Наследов, А.Д. Математические методы А. Наследов. - СПб: Речь, 2004. 38 с.

7. Партыка, Т.Л. Математические методы: учебник. / Т.Л. Партыка, И.И.

8. Попов. - 2-е изд., испр. - М.:ФОРУМ: ИНФРА-М, 2009 г. - 464 с.: ил.

9. Сакович В.А. Исследование операций (детерминированные методы и модели): Справочное пособие. - Мн.: Выш. шк., 1984.-256с.

10. Таха Х. Введение в исследование операций: в двух книгах. Кн.1,2 Пер. с англ. - М.: Мир, 1985.

11. Хазанова Л.Э. Математическое программирование в экономике: Учебное пособие. - М.: Издательство БЕК, 1998. - 141с.

12. Цирель, С. В. Венгерский способ/ С. Цирель. Москва: УРСС, 2007.- 120 с.

13. Шапкин, А.С. Математические методы / А. Шапкин. Учебник. Москва, 2004.- 104 с.

Размещено на Allbest.ru