Применение транспортной модели к решению задач оптимального назначения (выбора)

«Венгерский метод»

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

Венгерский  метод предполагает следующие этапы:

Этап 1:

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

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

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

Допустимым является решение, в котором каждой строке и каждому столбцу соответствует только один элемент.

Этап 2:

1. Найти строку (столбец) с одним нулевым элементом и в клетку этого  элемента сделать назначение.
2. Зачеркнуть оставшиеся нули данного столбца (строки).
3. Повторять п.п. 1 и 2, пока это возможно.

Если полученное решение окажется допустимым, то оно  будет и оптимальным. Если решение окажется недопустимым, то надо перейти к этапу 3.

Этап 3:

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

В задачах большой  размерности бывает трудно убедиться, что в соответствии с  п. 3.1. число проведенных линий минимально. Рекомендуется  следующее правило. Выбирается строка (столбец) с одним нулем. Если выбрана строка, то прямая проводится через столбец, в котором находится нуль. Если выбран столбец, то прямая проводится через строку и т.д., пока не будут учтены все нули.

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

В результате 3 – го этапа должен появиться еще  хотя бы один ноль. Далее повторяется этап 2, пока не появится оптимальное решение.

 

Рассмотрим, как  происходит решение задач линейного  программирования в Microsoft Excel с помощью надстройки «Поиск решения».

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

1. На листе Excel обозначить ячейки, в которых будут находиться неизвестные переменные, и ввести в них некоторые начальные значения (например, 0);

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

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

4. Открыть надстройку «поиск решения» (сервис – надстройка – поиск решения для Microsoft Office Excel 2003 или Данные – поиск решения для Microsoft Office Excel 2007). Далее: а) указать адрес ячейки целевой функции; б) установить критерии решения задачи; в) в окно изменения ячейки ввести адреса ячеек с переменными; г) в окно ограничения ввести адреса ячеек с ограничениями. Открыть «параметры» и выбрать тип задачи, опции решения задачи и нажать «ок». Затем нажать «выполнить». После решения задачи необходимо поставить галочки на отчетах, чтобы их вывели на экран. После этого можно проводить анализ полученных отчетов.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

ГЛАВА 2. РАЗРАБОТКА МАТЕМАТИЧЕСКОЙ МОДЕЛИ И ЕЕ РЕШЕНИЕ

2.1. Постановка  транспортной задачи о назначениях

Пусть имеется 5 работников, которые могут выполнять 5 работ. Время выполнения i –м работником  j – й  работы приведено в таблице 2.1(1). Требуется поручить каждому из работников выполнение одной работы, чтобы минимизировать в данном случае суммарное время выполнения всех работ.

Таблица 2.1(1)

Условия задачи

Работник	Время выполнения работы, час
	Работа 1	Работа 2	Работа 3	Работа 4	Работа 5
1.Воробьев 2.Синицын 3.Галкин 4.Сорокин 5.Орлов	25 25 30 27 29	16 17 15 20 19	15 18 20 22 17	14 23 19 25 32	13 15 14 12 10

 

 

 

 

 

 

 

 

 

 

 

2.2. Решение  транспортной задачи о назначениях  «Венгерским методом»

1) Формулируем  задачу в виде транспортной  таблицы:

Таблица 2.2(1)

Матрица A

25	16	15	14	13
25	17	18	23	15
30	15	20	19	14
27	20	22	25	12
29	19	17	32	10

 

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

Таблица 2.2(2)

Матрица B

12	3	2	1	0
10	2	3	8	0
16	1	6	5	0
15	8	10	13	0
19	9	7	22	0

 

3) Находим в  каждом столбце минимальный элемент  и вычитаем его из всех элементов  данного столбца.

 

 

 

 

 

 

Таблица 2.2(3)

Матрица C

2	2	0	0	0
0	1	1	7	0
6	0	4	4	0
5	7	8	12	0
9	8	5	21	0

 

4) Находим строку (столбец) с нулевым элементом и делаем назначение в клетку этого элемента.

Таблица 2.2(4)

Матрица D

2	2	0	0	0
0	1	1	7	0
6	0	4	4	0
5	7	8	12	0
9	8	5	21	0

 

Выделенные  нули это сделанное назначение. Полученное решение (выделенные нули) недопустимо, т.к. на 4-ю работу никто не назначен.

5) Так как решение недопустимо, следовательно, проводим модификацию матрицы. Вычеркиваем строки и столбцы с возможно большим количеством нулевых элементов (вычеркнутые строки окрашены в серый цвет). Получаем сокращенную матрицу (Таблица 2.2(5)):

 

Таблица 2.2(5)

Матрица E

2	2	0	0	0
0	1	1	7	0
6	0	4	4	0
5	7	8	12	0
9	8	5	21	0

 

Минимальный элемент  сокращенной матрицы = 4, вычитаем его из всех оставшихся элементов. Затем складываем минимальный элемент с элементами, расположенными на пересечениях вычеркнутых строк и столбцов (Таблица 2.2(6)).

Таблица 2.2(6)

Матрица F

2	6	0	0	4
0	5	1	7	4
2	0	0	0	0
1	7	4	8	0
5	8	1	17	0

 

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

7) В данной  матрице находим строку (столбец) с нулевым элементом и делаем назначение в клетку этого элемента (аналогично с пунктом 4).

Таблица 2.2(7)

Матрица G

2	6	0	0	4
0	5	1	7	4
2	0	0	0	0
1	7	4	8	0
5	8	1	17	0

 

8) Полученное решение (выделенные нули) недопустимо, т.к. на 4-ю работу никто не назначен. Следовательно, (возвращаемся к пункту 5) проводим модификацию, вычеркиваем строки и столбцы с возможно большим количеством нулевых элементов (вычеркнутые строки окрашены в серый цвет). Получаем сокращенную матрицу (Таблица 2.2(8)).