Гасников А.В., Кленов С.Л., Нурминский Е.А., Холодов Я.А., Шамрай Н.Б. Введение в математическое моделирование транспортных потоков

Подождите немного. Документ загружается.

348

Задача 16. Пусть в условиях задачи 11 кратчайший путь ровно

один. Требуется найти путь, который будет являться вторым по величи-

не длины (времени прохождения).

Задача 17. В городе были построены дороги, соединяющие неко-

торые перекрестки (вершины графа транспортной сети). Длина каждой

дороги известна. Строителям для отчета требуется найти кратчайшие

пути между каждой парой перекрестков.

а) Оцените сложность алгоритма и время работы соответствующей

программы (1000 перекрестков), если разрешается пользоваться только

алгоритмом Дейкстры поиска кратчайшего расстояния (правда, много

раз).

б) Предложите более быстрый алгоритм (например, алгоритм Флой-

да–Уоршола) и также оцените его время работы при тех же условиях.

в) В каком смысле поиск кратчайших путей (алгоритмом Флойда)

эквивалентен вычислению в идемпотентном полуполе (см. п. 2.1.3 гла-

вы 2) некоторой степени (укажите какой степени и предложите эффек-

тивный способ возведения в эту степень) матрицы, заполненной длина-

ми всевозможных ребер–дорог? Как действовать, если какие-то верши-

ны не соединены ребром?

Задача 18. Сопоставим каждому перекрестку (вершине графа

транспортной сети) некоторое число – потенциал

и определим новое

расстояние (время прохождения) между перекрестками

ij ij j i

New Old P P  

где

Old

– «старое» расстояние между вершинами

а) Докажите, что кратчайший путь в графе с «новыми» расстояниями

совпадает с кратчайшим путем в графе со «старыми» расстояниями.

б) Какие потенциалы нужно расставить в вершины, чтобы алгоритм

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

рассмотренных вершин «лишние» вершины, т.е. не лежащие на крат-

чайшем пути?

Задача 19. В городе были выделены несколько перекрестков

(вершин графа транспортной сети) и были подсчитаны все расстояния

от выделенных перекрестков до всех остальных.

а) Как, используя эту информацию, оценить снизу кратчайшее рас-

стояние между любыми двумя перекрестками (вершинами)?

349

б) Какие перекрестки (вершины) мы должны выделить (их количест-

во заранее оговорено), чтобы оценка из п. а) была более точной?

Часть 5. Максимальный поток

Задача 20 (О максимальном потоке). Будем считать, что из

пункта А в пункта Б едет (возможно, через другие пункты) непрерыв-

ный поток автомобилей величиной X автомобилей в единицу времени.

Также будем считать, что у каждой дороги, соединяющей два пункта,

пропускная способность ограничена числом

машин в единицу вре-

мени. Необходимо найти, какой максимальный поток можно запустить

из пункта А в пункт Б с учетом пропускных способностей дорог.

а) Запишите эту задачу, как задачу линейного программирования,

напишите двойственную к ней задачу.

Указание. Считайте граф ориентированным. Используйте мат-

рицу инциденций графа.

б) Пусть

– неотрицательные целые числа. Покажите, что в опти-

мальном решении задачи поток, проходящий через каждую дорогу, бу-

дет также целым.

Указание. Используйте вид матрицы инциденций графа (в каж-

дом столбце только два числа не равны нулю; эти числа: 1 и минус 1).

в) Как при доказательстве целочисленности решения (см. пункт б))

можно использовать теорему Гофмана–Краскала [6] о том, что полиэдр,

задаваемый ограничениями вида

Ax b



0x 



с абсолютно унимоду-

лярной матрицей

и произвольным вектором



(таким, что система

Ax b



0x 



совместна), имеет все вершины с целочисленными ком-

понентами?

Замечание. Отметим, что по теореме Пуанкаре [5], матрица ин-

циденций произвольного ориентированного графа абсолютно унимоду-

лярна, т.е. определитель любой еѐ квадратной подматрицы равняется

одному из трех чисел: минус 1, 0, 1.

г) Оцените сложность алгоритма Форда–Фалкерсона (

– неотри-

цательные целые числа) и время работы соответствующей программы

для поиска максимального потока (количество пунктов – 1000).

д) Сойдется ли за конечное время к оптимальному решению алго-

ритм Форда–Фалкерсона, если

– неотрицательные вещественные

числа?

е) Модифицируйте алгоритм Форда–Фалкерсона для решения задачи

350

максимального потока при неотрицательных вещественных

(напри-

мер, алгоритмы Эдмонса–Карпа и Диница), оцените их сложность и

время работы (количество вершин – 1000).

ж) Оцените пространственную и временную сложность алгоритма

Карзанова нахождения максимального потока.

В чем заключаются

преимущества алгоритма Карзанова, например, над алгоритмом Форда–

Фалкерсона?

Задача 21. В контексте предыдущей задачи будем считать, что

суммарный поток машин через вершину также ограничен.

Как эту задачу свести к задаче 20 поиска максимального потока?

Задача 22. Во вражеской стране некоторые города соединены

прямыми дорогами. Партизаны хотят сорвать перевозку оружия от го-

рода А до города Б: для этого им нужно взорвать минимальное количе-

ство дорог так, чтобы от города А стало бы нельзя доехать до города Б.

а) Предложите алгоритм нахождения дорог, которые предполагается

взорвать (минимальный разрез) и оцените его время работы (количество

вершин – 1000).

б) Докажите, что количество взорванных дорог равняется макси-

мальному потоку из вершины А в вершину Б (веса всех ребер – 1).

Задача 23. Чиновник хочет проинспектировать все дороги горо-

да. Для этого он составил маршрут, проходящий по каждой дороге хотя

бы один раз. Будем считать, что чиновнику нужна единица времени,

чтобы проинспектировать одну дорогу (проезжая дорогу несколько раз,

он еѐ соответствующее число раз и инспектирует). Необходимо найти

минимальное время, нужное чиновнику для инспекции всех дорог (как

минимум по разу).

Как свести эту задачу к задаче 20 о максимальном потоке?

Указание. Когда в графе нельзя найти Эйлеров цикл? Какие реб-

ра нужно сделать двойными, чтобы Эйлеров цикл нашелся?

Задача 24. Некоторые объекты (подмножество вершин) в городе

назовем стратегически-важными. Найдите минимальное по суммарной

длине подмножество дорог, таких, что из каждого стратегически-

Описание этого алгоритма имеется, например, в лекции М. Г. Фуругяна, прочитанной

студентам второго курса ФУПМ МФТИ весной 2009 г.,

http://www.intuit.ru/department/algorithms/algomodex/2/.

351

важного объекта до каждого стратегически важного можно добраться

по дорогам из выбранного множества.

а) Частным случаем каких вышеупомянутых задач является данная

задача? Что известно про сложность решения частных случаев?

б) Докажите NP-полноту этой задачи путем сведения к ней задачи

3-SAT о выполнимости булевых формул в 3-конъюнктивной нормаль-

ной форме.

Замечание. Условие задачи 3-SAT см. в книге [16].

Задача 25 (Транспортная задача). Имеется

производителей и

потребителей некоторого товара, расположенных в узлах транспорт-

ной сети. Пусть

x 

обозначает количество продукта, перевозимого

из i-го узла в j-й,

c 

– стоимость перевозки,

a 

– объѐм произ-

водства в i-м узле,

b 

– суммарную потребность – в j-м (при этом







). Поставим задачу о составлении плана перевозок миними-

зирующего общую стоимость перевозок от производителей к потреби-

телям:

1. 1

min

ij ij







ij i





ij j





а) Напишите двойственную задачу к вышеприведенной задаче.

б) Дополнительно введя сток и исток и пользуясь матрицей инци-

денций, запишите задачу нахождения максимального потока минималь-

ной стоимости и двойственную к ней.

в) Рассматривая эту задачу как задачу линейного программирования,

получите оценку для времени работы известных вам алгоритмов в наи-

худшем случае и в среднем. Примите

500mn

Задача 26. Рассматривается та же самая транспортная задача с

целыми неотрицательными параметрами

a 

1, ,in 

;

b 

1, ,jm 

а) Покажите, что решения

задачи в классе неотрицательных дей-

ствительных чисел будут целыми.

Указание. Запишите задачу нахождения максимального потока

минимальной стоимости (см. задачу 25 б)), затем воспользуйтесь теоре-

мой Гофмана–Краскала (см. задачу 20 в)).

б) Как нужно модифицировать алгоритм Форда–Фалкерсона нахож-

352

дения максимального потока для решения транспортной задачи? Оце-

ните время работы получившегося алгоритма при

500mn

в) Сойдется ли за конечное время модифицированный алгоритм из

пункта а), если параметры задачи могут быть не целыми?

Замечание. Вообще говоря, нахождение целочисленных реше-

ний, как правило, значительно усложняет алгоритм, иногда делая зада-

чу, решаемую за полиномиальное время, NP-трудной (например, в зада-

че размещения производства, см. [15]). Однако приведенная задача как

раз является исключением из этого правила.

Задача 27. Пусть есть граф со взвешенными ребрами, причем ве-

са ребер могут быть отрицательными числами.

а) Как в данном графе найти цикл, сумма длин ребер которого отри-

цательна?

б) Как нахождение таких циклов использовать при решении транс-

портной задачи 24?

в) Оцените время работы полученной программы при

500mn

Часть 6. Построение оптимальной транспортной сети

Задача 28 (П. П. Бобрик, 2000). Распределение мест проживания

населения по городу, имеющему форму квадрата со стороной

км и не

имеющего дорог, равномерное. Условное распределение мест работы

жителей (при условии, что зафиксировано место жительства) также

равномерное (и, как следствие, не зависит от места жительства). Руко-

водство города решило построить сеть дорог в виде квадратной решѐтки

со стороной квадратной ячейки, равной

a A n

. Известно, что затрата-

ми на строительство сети дорог можно пренебречь по сравнению с по-

следующими суммарными затратами на еѐ поддержание. Пусть

–

стоимость поддержания 1 км дороги (в одну сторону) в течение 1 года,

– стоимость 1 часа, потраченного одним человеком в дороге. Число

жителей в городе

. Каждый человек

300Q 

раз в год направляется

из дома на работу и обратно с работы домой. Скорость движения чело-

века не по дороге

км/ч, скорость движения человека по дороге

км/ч (

vV 

), время, потраченное на прохождение одного перекрѐстка,

есть

0t 

мин.

а) Постройте целевую функцию, отвечающую за эффективность по-

строенной транспортной сети.

б) Какое значение

«оптимально» выбрать руководству города?

353

Задача 29. В условиях предыдущей задачи было решено постро-

ить радиально-кольцевую систему дорог, состоящую из

колец и

радиусов.

а) Постройте целевую функцию, отвечающую за эффективность по-

строенной транспортной сети.

б) При каких условиях эта сеть окажется эффективней оптимальной

квадратной сети из предыдущей задачи?

Задача 30. В условиях задачи 28 был предложен альтернативный

план транспортной сети – регулярная сеть дорог, с элементарной «ячей-

кой» в виде правильного (равностороннего) треугольника со стороной b

(из расчета, что длина сети совпадает с «квадратной»). При этом оказа-

лось, что время, потраченное на прохождение перекрестка в вершине

графа транспортной сети,





, пропорционально степени

этой

вершины. Определить, при каком значении



эффективность сетей

совпадает (если такое



существует).

Задача 31 (А. П. Буслаев, 2001). В литературе имеется довольно

большое количество различных характеристик графов транспортных

сетей. Интересной задачей является исследование этих макрохарактери-

стик на различных типах случайных графов. Например, во второй части

монографии [23] вводятся такие показатели «хорошести» графа транс-

портной сети (отметим, что терминология пока не устоялась, поэтому в

других местах аналогичные термины могут иметь иное содержание):

 









– надежность,

где

– число вершин в графе



– число связных компонент в

графе



, полученном из исходного графа

путем случайного и неза-

висимого разыгрывания его ребер (с вероятностью

0p 

ребро остав-

ляют и с вероятностью

1 p

ребро стирают),



– математическое

ожидание с.в.



;

 









– устойчивость,

где



– размер (число вершин) максимальной связной компоненты в

графе



;

354

 

G p ij

i j i

rt p E











– доступность,

где



– длина кратчайшего пути в графе



, ведущего из вершины

в вершину

(доопределим





(i – мнимая единица), если из вер-

шины

нельзя добраться по графу



в вершину

а) Исследуйте качественно зависимость приведенных показателей от

для графов транспортной сети со структурой задачи 28 и 30 (считай-

те, что

1N 

б) Сравните эффективность транспортных сетей задач 28 и 30 с по-

мощью приведенных показателей.

в) (гигантская компонента; см. приложение А. М. Райгородско-

го) Покажите, что если взять в качестве

полный граф на

верши-

нах, то

 

G G N p



(модель Эрдѐша–Реньи) и для любого

1c 

най-

дѐтся такое





, что

 

P s c N





 

Задача 32 (показатель качества графа транспортной сети;

Уотс–Строгатц, 1998)*. Рассматривается такой ориентированный

взвешенный граф транспортной сети, что из любой его вершины можно

добраться по ребрам (с учетом ориентации ребер) в любую другую.

Обозначим через

– длину кратчайшего пути по рассматриваемому

графу транспортной сети из вершины

в вершину

. Показателем ка-

чества исследуемого графа назовем величину:

 

i j V i j

e n n d











где

 

1,...,Vn

– множество вершин графа. Оцените значение этого

показателя для графа транспортной сети из задачи 28, считая

1n 

Задача 33 (нахождение минимума функционала среднего рас-

стояния; Е. О. Степанов, 2005)**. На множестве всех замкнутых связ-

ных множеств



хаусдорфовой размерности 1 (

 

H   

), удов-

летворяющих ограничению на длину,

 

Hl

, требуется найти реше-

ние



следующей задачи:

355

   

 

dist , min

F A x d x



  

   







где

 





– мера, отвечающая распределению населения в окрестности

точки с координатой



, число

 

задает затраты жителя на проезд

на расстояние

. Транспортная сеть



, таким образом, проектируется

исходя из соображений минимизации полных затрат населения на дос-

тижение сети из мест проживания. Покажите, что при весьма общих

условиях решение



этой задачи существует, не содержит петель, име-

ет конечное число концевых точек и точек ветвления, а также обладает

некоторыми свойствами регулярности (см. раздел, посвященный задаче

Штейнера). Предложите эффективный способ численного поиска



Литература

К частям 1, 3:

1. Hwang F. K., Richards D., Winter P. The Steiner tree problem. Elsevier

Science Publishers, 1992.

2. Гордеев Э. Н., Тарасцов О. Г. Задача Штейнера. Обзор // Дискрет-

ная математика. 1993. Т. 5. № 2. С. 3–28. http://www.mathnet.ru/

3. Иванов А. О., Тужилин А. А. Теория экстремальных сетей. Москва–

Ижевск: Институт компьютерных исследований, 2003.

4. Протасов В. Ю. Максимумы и минимумы в геометрии. № 31.

М.: МЦНМО, Библиотечка «Математическое просвещение», 2005.

http://www.mccme.ru/mmmf-lectures/books/books/book.31.pdf

К частям 2, 4, 5:

5. Берж К. Теория графов и ее приложения. М.: ИЛ, 1962.

6. Гвишиани А. Д., Гурвич В. А. Динамические задачи классификации

и выпуклое программирование в приложениях. М.: Наука, 1992.

7. Stoer Mechthild, Wagner Frank A Simple Min-Cut Algorithm // Jour-

nal of the ACM. 1997. V. 44. № 4. P. 585–591.

8. Разборов А. А. О сложности вычислений // Матем. просв. 1999.

№ 3. http://www.mccme.ru/free-books/matpros4.html

Обратим внимание, что на этом электронном ресурсе открыт свободный доступ к пол-

ным текстам статей ряда ведущих российских научных журналов (Успехи математических

наук, Математический сборник, Математические заметки, Функциональный анализ, Из-

вестия РАН, Дискретная математика, Математическое моделирование, Журнал вычисли-

тельной математики и математической физики и др.).

356

9. Смейл С. О проблемах вычислительной сложности // Матем. просв.

2000. № 4. http://www.mccme.ru/free-books/matpros5.html

10. Schrijver Alexander On the history of the transportation and maximum

flow problems // Math. Program., Ser B. 2002. V. 91. P. 437–445.

http://oai.cwi.nl/oai/asset/10084/10084A.pdf

11. Вялый М. Н. Линейные неравенства и комбинаторика. М.: МЦНМО,

Летняя школа «Современная математика», 2003.

http://www.mccme.ru/free-books/dubna/vyalyi.pdf

12. Зыков А. А. Основы теории графов. М.: Вуз. книга, 2004.

13. Diestel R. Graph Theory. Electronic Edition, NY: Springer, 2005.

14. Goldberg A. V., Harrelson C. SODA '05 Proceedings of the sixteenth

annual ACM-SIAM symposium on discrete algorithms. USA Society

for Industrial and Applied Mathematics Philadelphia. 2005. P. 156–165.

15. Кормен Т. Х., Лейзерсон Ч. И., Ривест Р. Л., Штайн К. Алгоритмы:

Построение и анализ. М.: Вильямс, 2005.

16. Кузюрин Н. Н., Фомин С. А. Эффективные алгоритмы и сложность

вычислений. М.: МФТИ, 2007.

http://discopal.ispras.ru/ru.lectures-mipt.htm

17. Емеличев В. А., Мельников О. И., Сарванов В. И., Тышкевич Р. И.

Лекции по теории графов. М.: УРСС, 2009.

18. Annual IEEE Symposium on Foundations of Computer Science, 1 – 51.

http://theory.stanford.edu/focs2010/

19. http://e-maxx.ru/algo/; http://www.machinelearning.ru/

20. Шень А. Х. Программирование: теоремы и задачи. М.: МЦНМО,

2011.

К части 6:

21. Стенбринк П. А. Оптимизация транспортных сетей. М.: Транспорт,

1981.

22. Бобрик П. П. Cравнение эффективностей треугольной и квадратич-

ной регулярных транспортных сетей // Транспорт: наука, техника,

управление. М.: Изд-во ВИНИТИ, 2000. № 7.

23. Луканин В. Н., Буслаев А. П., Трофимов Ю. В., Яшина М. В. Авто-

транспортные потоки и окружающая среда. Ч. 1, 2. М.: ИНФРА-М,

1998, 2001.

24. Latora V., Marchiori M. Efficient behavior of small-world networks //

Phys. Rev. Letters. 2001. V. 87. № 19.

http://www.w3.org/People/Massimo/papers/2001/efficiency_prl_01.pdf

25. Степанов Е. О. Математические модели оптимизации транспорт-

ных сетей. Санкт-Петербург: СПбГУ ИТМО, 2005.

357

Преобразования запрещенных маневров

(от Яндекс-пробки)

А. И. Верещагин, В. Б. Гольдштейн, И. И. Колесниченко,

М. В. Левин, Андрей А. Петров

Постановка задачи

При нахождении маршрутов проезда по городу важно учитывать

не только взаимное расположение дорог, но и правила дорожного дви-

жения. Картографические компании собирают информацию о располо-

жении дорог и дорожных знаках. Эта информация предоставляется от-

дельно, однако для маршрутизации обязана учитываться вместе. Граф

дорог состоит из перекрестков и улиц их соединяющих. Встречаются

улицы с односторонним и двусторонним движением, а также улицы, по

которым проезд машин запрещен вовсе. Однако из-за запрещающих

знаков на некоторые улицы можно выехать не всегда. Простейшим

примером служит запрещенный левый поворот. Несмотря на то, что по

улицам AMB и CMD разрешен проезд в обоих направлениях, нельзя

проехать по ним последовательно. То есть проезд по пути AMC и BMD

запрещен. Обобщая этот пример, назовем запрещенным маневром по-

следовательность дорог, проезд по которым от начала и до конца за-

прещен. Запрещенные маневры могут состоять как из двух ребер (за-

прет левого поворота), так и из 4–5 дорог (сложный выезд на трассу).

Рис. 1