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

2-й шаг. В плане перевозок

строим "разгрузочный" цикл, начиная с элемента , при этом на нечетном местах этого цикла , при этом считаем стоящим на первом месте.

В данном случае в "разгрузочный" цикл входят элементы

Перемещая по этому циклу число получим новый план перевозок, равный

Так как перевозка

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

Таковым будет цикл, состоящий из

Перемещая по этому циклу получим новое решение. Как результат такого перемещения и тем самым вновь переходим к 1-ому этапу.

1-ый этап. Наибольшим элементом

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

2-ый этап. На этом этапе необходимо было бы "разгрузить" элемент

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

Тема 5. Задача оптимального назначения на авиарейсы

Авиалиния, работающая в течение всей недели, имеет расписание рейсов, приведенное в таблице 5.1.

Поставлена следующая задача. Где должны базироваться экипажи (в пунктах А и/или В) и какие рейсы они должны обслуживать, чтобы суммарное время, которое все экипажи теряют на ожидание обратного рейса, было бы минимальным, но при этом необходимо учесть, что время ожидания каждой бригады должно быть больше 4 часов и меньше 24 часов.

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

Таблица 5.1

Пункт А ® пункт В			Пункт В ® пункт А
№ рейса	Отправление	Прибытие	№ рейса	Отправление	Прибытие
1	06.00	12.00	101	05.30	11.30
2	07.30	13.30	102	09.00	15.00
3	11.30	17.30	103	15.00	21.00
4	19.00	01.00	104	18.30	00.30
5	00.30	06.30	105	00.00	06.00

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

Предположим, например, что экипаж базируется (живет) в А и обслуживает рейс 3 в направлении В и рейс 102 в противоположном направлении. Этот экипаж должен ждать в пункте В 15.5 часа (от 17.30 до 09.00). Составим путем аналогичных расчетов две матрицы, оформленные в виде таблиц 5.2 и 5.3, элементы которых отражают величины потерянного времени, считая в первом случае, что все экипажи живут в пункте А, а во втором, что все они живут в пункте В. В таблице 5.2. элемент

время ожидания при обслуживании рейса под номером (вылет из пункта проживания А) и обслуживание рейса, номер которого определяется как (возвращение в пункт проживания А из пункта В). В таблице 5.3 элемент время ожидания при обслуживании рейса под номером (вылет из пункта проживания В) и обслуживание рейса, номер которого определяется как (возвращение в пункт проживания В из пункта А).

Таблица 5.2

Все экипажи живут в пункте А

17.5	21	3	6.5	12
16	19.5	1.5	5	10.5
12	15.5	21.5	1	6.5
4.5	8	14	17.5	23
23	2.5	8.5	12	17.5

Таблица 5.3

Все экипажи живут в пункте B

18.5	15	9	5.5	0
20	16.5	10.5	7	1.5
0	20.5	14.5	11	5.5
7.5	4	22	18.5	13
13	9.5	3.5	0	18.5

Составим теперь на основе этих двух таблиц третью (таблица 5.4.), каждый элемент которой будет являться меньшим из чисел, занимающих соответствующие клетки в двух исходных таблицах. При этом мы не будем принимать во внимание числа, которые не превосходят четырех, учитывая потребности экипажа в отдыхе. Например, если нам представится выбор между числами (1, 101; место жительства в пункте А) и (101, 1; место жительства в пункте B), то выбрать следует (1, 101), которое дает нам ожидание в 17,5 часа вместо 18,5 часа. Напротив из (3, 102; место жительство в пункте А) и (102,3; место жительства в пункте B) мы выбираем (3, 102), хотя этому варианту и соответствует меньшее время, т.к. вариант (102,3) оставляет на отдых меньше 4 часов и поэтому неприемлем. Отметим, что время ожидания свыше 24 часов мы предусмотрительно не учитывали в наших таблицах.