Методы анализа сетей. Филлипс. Гарсиа-Диас (1981) (1186150), страница 21
Текст из файла (страница 21)
Рнс. х.за. Промежуточное решение. Построенный полный маршрут является оптимальным, если его длина не превосходит длины любого маршрута, соответствующего другим звеньям дерева. Однако нижняя граница для узла (1, 4), равная 58, меньше длины построенного маршрута, равной 63. Следовательно, необходимо исследовать подмножество маршрутов, которые не содержат звено (1, 4). Матрица Р на данном этапе будет совпадать со старой матрицей Р, кото- Глава 2 Таблица 2.2Д Окончательная матрица решеннй С; А; вт рую мы имели до этапа ветвления из узла (1, 4).
Однако, для того чтобы исключить все маршруты, содержащие звено (1, 4) значение элемента 4, матрицы 0 мы принимаем равным оо. В нашем примере соответствующая матрица совпадает с мат- 48 ~ ~Все 1 С 73 Рне. 2.36. Возврат. 121 Детермипироеиккме потоки е сетях рицей 1е, приведенной в табл. 2.14, если элемент е1ы=16 заменить на 44— - оо. Далее с этой новой матрицей выполняются описанные выше процедуры ветвления и построения границ. Полученное при этом дерево изображается на рис. 2.3б. Дан- 4З< / Нее 1 <тэ маршруты Рис. 2.37. Оптимальное решение.
ная процедура анализа предыдущих промежуточных точек ветвления, которые могли бы определить более короткий маршрут, называется возвратом, Проводя аналогичные вычисления, построим разбиение подмножества маршрутов, содержащих звено (б, 3). Полученное при этом дерево изображено на рис. 2.37. 122 г г Заметим, что нижняя граница первоначального маршрута, содержащего звено (1, 4), теперь является наименьшей.
Следовательно, этот маршрут должен быть оптимальным. Оптимальный маршрут состоит из следующих звеньев, или пар городов: (4, 3), (6, 2), (3, 5), (5, 6), (2, 1) и (1, 4). Он является ориентированным циклом, длина которого равна 63. 2хь4. ЗАКЛЮЧИТЕЛЬНЫЕ ЗАМЕЧАНИЯ Следует отметить, что задача коммивояжера является комбинаторной задачей, поскольку число возможных маршрутов экспоненциально зависит от числа городов. Данная задача принадлежит классу так называемых А7Р-полных задач. Было показано, что многочисленный класс комбинаторных задач яв-.
ляется классом эквивалентных задач, где эквивалентность понимается в том смысле, что либо все они могут быть решены с помощью алгоритмов, имеющих полиномиальную сложность вычислений, либо ни одна из них не может быть решена с помощью таких алгоритмов (см. разд. 2.7). Данная группа задач образует класс УР-полных задач. И наконец, задача коммивояжера не может быть непосредственно сформулирована и решена как задача линейного программирования. Она относится к классу потоковых задач в силу исторически сложившейся связи между методами их решения и в силу ее графического представления как задачи об оптимальном маршруте. Ряд задач, представляющих собой разновидность задачи коммивояжера, был поставлен и решен с целью исследовать маршруты движения людей или перевозки товаров.
Однако рассмотрение этих прикладных задач отодвигает на второй план одну важную особенность задачи коммивояжера. Основное различие между задачей коммивояжера и другими задачами о кратчайшем пути заключается в том, что в первой из них требуется существование ориентированного цикла, в который ровно один раз входят все узлы (города или километровые столбы) сети. Другие важные приложения задачи коммивояжера связаны с определением нагрузки учителей, составлением 'хвинии х1чньободз х1чньикееб ен юдеб нинзнкоп1чн кинезипзеб а также с нахождением последовательности выполнения операций на универсальном станке.
Кроме того, на практике встречаются задачи, связанные с составлением расписания работы станков на некотором предприятии, нахождением оптимальной последовательности переключения их скоростей и определением порядка их обслуживания. 19З Дете минировонньи потоки в оетнк 2.9.5. ОПИСАНИЕ ПРОГРАММЫ, РЕАЛИЗУЮЩЕЙ АЛГОРИТМ РЕШЕНИЯ ЗАДАЧИ КОММИВОЯЖЕРА Назначение: данная программа позволяет находить оптимальное решение задачи коммивояжера.
Локализация: подпрограмма ТцАЬА1. в пакете сетевой оптимизации. Ограничения: программа позволяет обрабатывать сети, содержащие до 50 узлов и 50 дуг. Размеры сети можно увеличить, изменив границы массивов в операторах размерности, записанных в подпрограмме ТКАБА1. и основной программе. Входные данные: Набор 1. Одна карта с именем алгоритма ТЯРц в формате (А4). Набор 2. Одна карта с числом узлов и числом дуг в сети в формате (2110).
Набор 3. Общее число карт в данном наборе равно числу дуг в сети. С каждой карты считываются следующие значения: 1) номер начального узла дуги; 2) номер конечного узла дуги; 3) длина дуги. Формат (4Х, 16, 110, Р10.2). Набор 4. Данный набор состоит из одной карты, содержащей слово 'РЕ)Ч(З' в формате (А4), которая указывает конец задачи. Набор 5.
Данный набор состоит из одной карты, содержащей слово 'ЕХ1Т' в формате (А4), которая указывает конец входных данных. Составные части программы. Программа состоит из следующих подпрограмм и функций: подпрограмма Т1(АВА(. (ввод- вывод, построение дерева, возврат, отсечение путей); функция М11ЧС01 (редукция столбца); функция Н1(к)ЯО% (редукция строки); подпрограмма РКТКХЗ (печать начального решения). Используемые переменные: 1 — начальный узел дуги, 3— конечный узел дуги, УА1. — длина дуги. Используемый метод: данный алгоритм основан на методе «ветвей и границ», описанном Литтлом и др. Литература: 1411. 2.9.6.
СОСТАВЛЕНИЕ МАРШРУТА ЗАРУБЕЖНОГО ПУТЕШЕСТВИЯ Выиграв третий приз в ирландской лотерее, один дипломник Техасского университета решил, что после пяти лет непрерывной учебы на инженерно-технологическом факультете настало время вырваться из дома и посмотреть на жизнь в других стра- 124 Глава 2 Таблица 2.22. Ирландская лотерея КолледжИа Стейаен Акапулько Гонолулу Токио Гонконг Лондон Сидней Рии !90 210 680 690 460 !90 — 380 760 790 б!О 2!О 380 — 890 900 340 680 760 890 — 480 760 690 790 900 480 — 890 460 6!О 340 760 890 780 670 4!О 5!О 490 720 750 450 600 250 560 600 нах.
Он выбрал семь мест, наиболее интересных для посешения в рождественские каникулы. В местном бюро путешествий он получил информацию о стоимости проезда самолетом в каж- РЕШЕНИЕ ЗАДАЧИ КОММИВОЯЖЕРА МЕТОДОМ ВЕТВЕИ И'ГРАНИЦ; "'ИСХОДНАЯ МАТРИЦА"' 1 99999999 2 19 3 21 4 68 5 69 6 46 7 78 8 75 1 46 2 61 3 34 4 76 5 89 6 99999999 7 72 8 60 Копледле Сгейаен Акапулько Гонолулу Токио Гонконг Лондон Сидней Рии 19 99999999 38 76 79 61 67 45 78 67 4! 51 49 72 99999999 50 21 38 99999999 89 90 34 41 60 75 45 60 25 56 60 50 99999999 68 76 89 99999999 48 76 51 25 780 750 670 450 4!О 600 5!О 250 490 560 720 600 — 500 500 69 79 90 48 99999999 89 49 56 125 Двтврминированнмв потоки в сетях "ДОПУСТИМОЕ РЕШЕНИЕ" 307 1 2 8 4 5 7 3 б ОПТИМАЛЬНОЕ РЕШЕНИЕ ЗОТ ИЗУЗЛА1 ВУЗЕЛ2 РАССТОЯНИЕ19 ИЗУЗЛА2 ВУЗЕЛ8 РАССТОЯНИЕ45 ИЗУЗЛА8 ВУЗЕЛ4 РАССТОЯНИЕ25 ИЗУЗЛА4 ВУЗЕЛ5 РАССТОЯНИЕ48 ИЗУЗЛА5 ВУЗЕЛ7 РАССТОЯНИЕ49 ИЗУЗЛА7 ВУЗЕЛЗ РАССТОЯНИЕ41 ИЗ УЗЛА 3 В УЗЕЛ 6 РАССТОЯНИЕ 34 ИЗУЗЛА6 ВУЗЕЛ1 РАССТОЯНИЕ46 дый из городов, которые он собирался посетить, н стоимость проезда из одного города в другой.
Соответствующие цены (в долл.) приведены в табл, 2.22. Поскольку плата за проезд из одного города в другой равна плате за проезд в обратном направлении, то матрица стоимостей является симметричной. Перед тем как заказать билеты на самолет, он решилопределить наиболее дешевый маршрут объезда всех выбранных им городов. Это не представляло для него трудностей, поскольку он знал алгоритм решения задачи коммивояжера. Соответствующая задача коммивояжера была решена с помощью программы, описанной в разд. 2.9.5.
Самым дешевым маршрутом для посещения выбранных им городов оказался маршрут Колледж-Стейшен — Лондон — Гонолулу — Сидней— Гонконг — Токио — Рим — Акапулько и снова Колледж-Стейшен. Общая стоимость за проезд при этом равна 3070 долл. 2.10. ТРАНСПОРТНАЯ ЗАДАЧА В стандартной постановке данной задачи заданы т пунктов снабжения, из которых продукт может транспортироваться в каждый из и пунктов потребления.
Производительность с'-го источника снабжения равна аь а потребление 1'-го стока равно Ьь Параметры ол и Ь| являются фиксированными в заданном периоде планирования. Предполагается, что стоимость транспортировки единицы продукта из пункта 1 в пункт 7' не зависит от объема перевозимого груза и равна сп. Требуется для заданного периода планирования найти такую схему транспортиповки продукта, при которой общие транспортные затраты мн- 126 Глава 2 нимальиы. Здесь предполагается, что учет ведется по одному виду продукции.
Однако в гл. 5 мы докажем, что многопродуктовые транспортные задачи сводятся к однопродуктовым задачам. Основными понятиями, необходимыми для формулирования транспортной задачи, являются понятия стоимости транспортировки единицы продукта, производительности пунктов снабжения и спроса пунктов потребления. Рис. 2.38 дает графическую интерпретацию данной задачи. ь, а, а2 Производительность пунктов снабжения Спрос пунктов потребпения Рис. 2.38.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
