Методические указания по курсовой работе для студентов специальности 22. 02 Автоматизированные системы (стр. 11 из 13)

Таблица 5.4

17,5	15	9	5,5	12
16	16,5	10,5	5	10,5
12	15.5	14.5	11	5,5
4.5	8	14	17.5	13
13	9,5	8,5	12	17,5

Назовем назначением факт приписания экипажа одному из рейсов (скажем (102,1) (3,102), (104,2) и т.д.). Понятно, что каждый экипаж может быть назначен лишь на один прямой и один обратный рейс. Тем самым, любое возможное решение задачи о назначениях может быть представлено таблицей, элементами которой являются числа 0 и 1, причем в каждой строке и в каждом столбце имеется только одна единица, отмечающая выбранное значение. В таблице 5.5 приведен пример возможного решения.

Таблица 5.5

0	1	0	0	0
1	0	0	0	0
0	0	0	0	1
0	0	1	0	0
0	0	0	1	0

Решение, описываемое таблицей 5.5 соответствует, как можно установить рассматривая и предыдущие таблицы, рейсам (2,101), (102,1), (5,103), (104,3), (105,4), т.е. при таком варианте трем экипажам следует базироваться в пункте А, а двум - в пункте B. Суммарные потери времени будут составлять

15 + 16 + 5,5 + 14 + 12 = 62,5 часа.

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

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

Процесс решения расчленяется на шесть этапов.

ЭТАП 1. ПОЛУЧЕНИЕ НУЛЕЙ

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

а столбцы - Сделав эти предварительные замечания, перейдем к таблице 5.6, которая является копией таблицы 5.3.

Таблица 5.6.

17,5	15	9	5,5	12
16	16,5	10,5	5	10,5
12	15.5	14.5	11	5,5
4.5	8	14	17,5	13
13	9,5	8,5	12	17,5

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

где для рассматриваемого случая

Описанный вариант позволяет получить хотя бы один нуль в каждом столбце. В нашем примере (таблица 5.6) нам следует вычесть 4.5 из всех элементов первого столбца, 8 из всех элементов второго столбца и т.д. Таким образом мы получим числа

которые составляют следующую таблицу.

Таблица 5.7

1	2	3	4	5
1	13	7	0,5	0,5	6,5
2	11,5	8,5	2	0	5
3	7,5	7,5	6	6	0
4	0	0	5,5	12,5	7,5
5	8,5	1,5	0	7	12

ЭТАП 2. ПОИСК ОПТИМАЛЬНОГО РЕШЕНИЯ

При помощи нулевых значений

попытаемся сконструировать решение, для которого суммарное время потерь (или в нулевых условиях других задач, суммарные затраты) имело бы нулевое значение. Если это возможно, то мы нашли оптимальное решение. В противном случае мы переходим к третьему этапу.

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

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

В рассматриваемом примере вначале подчеркнут двойной чертой элемент

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

Следовательно, необходим переход к следующему, третьему этапу.

Таблица 5.7а

1	2	3	4	5
1	13	7	0,5	0,5	6,5
2	11.5	8,5	2	0	5
3	7,5	7,5	6	6	0
4	0	0	5,5	12,5	7,5
5	8,5	1,5	0	7	12

ЭТАП 3. ПОИСКИ МИНИМАЛЬНОГО НАБОРА СТРОК И СТОЛБЦОВ, СОДЕРЖАЩИХ ВСЕ НУЛИ