Задачи геометрической теории меры в моделях оптимизации транспортных сетей и потоков тема диссертации и автореферата по ВАК РФ 05.13.17, доктор физико-математических наук Степанов, Евгений Олегович

• Степанов, Евгений Олегович
• доктор физико-математических наук
• 2006

Оглавление диссертации доктор физико-математических наук Степанов, Евгений Олегович

Введение

Основные обозначения

Глава 1. Качественные свойства ирригационных сетей

1. Существование решений

2. Некоторые численные результаты

3. Связные пространства

4. Метрические свойства связных множеств конечной длииы

5. Некоторые вспомогательные утверждения

6. Длина оптимальных сетей

7. Местоположение оптимальных сетей

8. Регулярность по Альфорсу и равномерная спрямляемость

Глава 2. Геометрия оптимальных ирригационных сетей

1. Некоторые полезные сведения из топологии

2. Отсутствие петель

3. Концевые точки и точки ветвления

4. Характеризация точек ветвления с помощью средней кривизны

Глава 3. Транспортные сети

1. Задача Монжа-Канторовича с условием Дирихле

2. Выбор оптимальной транспортной сети

3. Сведение задачи к минимизации функционала среднего расстояния

2 Оглавление

Глава 4. Общая задача оптимизации транспортных сетей

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

2. Эквивалентная формулировка транспортной задачи

3. Вспомогательные леммы

4. Ослабленная формулировка задачи

5. Свойства ослабленных решений

6. Существование классических решений

Глава 5. Модели с использованием транспортных плотностей

1. Основные факты о потоках

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

3. Подпотоки евклидовых потоков

4. Вогнутые функционалы па евклидовых потоках

5. Вспомогательные леммы

6. Потоки и транспортные меры

7. Оценки масс евклидовых потоков

8. Эквивалентная формулировка задачи в частном случае

9. Качественные свойства оптимальных потоков

10. Существование решений

Глава б. Оптимальные ценовые политики для транспортных сетей

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

2. Существование решений

3. Качественные свойства оптимальных ценовых политик

4. Некоторые примеры

Введение диссертации (часть автореферата) на тему «Задачи геометрической теории меры в моделях оптимизации транспортных сетей и потоков»

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

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

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

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

С весьма общей точки зрения такого рода задачи относятся к весьма обширному классу задач экономического расчета наилучшего использования ресурсов [11]. Оптимизация во всех рассматриваемых задачах производится с целью минимизации совокупных затрат на пользование сетью (т.е., например, совокупных затрат населения на ежедневные перемещения по городу в задачах городского планирования или совокупной стоимости пересылки данных в телекоммуникационных сетях) при заданных ограничениях (обычно это ограничения бюджетного характера на стоимость создания и эксплуатации сети), а также, в задачах определения оптимальной ценовой политики, с учетом интересов компании-владельца транспортной сети (т.е. с целью максимизации его прибыли при учете интересов населения). Сходные задачи оптимизации размещения центров предоставления услуг, а также некоторые подобные задачи в дискретных постановках рассматривались многими исследователями (см., например, работы [1, 2, 3, 4, 5, 6, 7, 28, 66, 75, 76]).

В настоящей работе предложены различные математические модели указанных задач, от допускающих достаточно простую формулировку до весьма сложных, отличающихся степенью учета различных факторов, влияющих на принятие решения. Рассматриваемые модели пригодны для проектирования и анализа широкого класса сетей, в том числе городских транспортных и хозяйственно-коммуникационных (телефонных, электрических, газовых и трубопроводных) сетей, автодорожных и железнодорожных сетей, а также телекоммуникационных сетей (см., например, работы [30, 58, 60], в которых предлагались различные сходные модели в дискретных постановках). Кроме того, подобные оптимизационные модели возникают и в задачах самой разной природы, не обязательно относящихся к урбанистике или экономике, в частности, в задачах обработки изображений [50], математической статистики [51, 52], задачах оптимальной ирригации [16, 29, 36, 44, 61, 70], при аппроксимации решений классической задачи коммивояжера (так называемая "задача ленивого коммивояжера". [68]). "Ядром" всех этих моделей являются различные варианты "непрерывной" (т.е. недискретной) постановки задачи Монжа-Канторовича оптимального переноса массы, допускающей в качестве входных данных произвольные меры, не обязательно являющиеся дискретными (см., например, работы [9,10,19, 24, 43, 53, 54, 56, 57, 72, 77]). Использование именно таких постановок значительно упрощает возможность исследования качественных свойств решений соответствующих задач в весьма общей ситуации (когда параметры задач могут быть произвольны).

К простейшим из рассматриваемых моделей оптимизации транспортных сетей относятся задачи нахождения минимума функционала среднего расстояния

6 ВВЕДЕНИЕ на множестве всех замкнутых связных множеств Е С Мп, удовлетворяющих ограничению па длину Н1(Е) < I. Здесь множество Е представляет искомую транспортную сеть (заранее предполагаемую замкнутой и связной), а конечная борелевская мера </?, моделирующая распределение населения в заданной местности, функция А: R+ —» R+, представляющая затраты каждого жителя на проезд без использования сети (так что число A(t) задает затраты на проезд расстояния t) и число I > 0, определяемое бюджетными ограничениями на постройку и эксплуатацию сети, предполагаются заданными. Транспортная сеть, таким образом, проектируется исходя из соображений минимизации полных затрат населения па достижение сети из мест проживания. Аналогичный характер и смысл имеет и задача минимизации функционала максимального расстояния

Fa/(E) := maxdist (х, Е), хем на множестве всех замкнутых связных множеств Е С К", удовлетворяющих ограничению на длину ?^(Е) < /, а также в известной мере двойственная последней задача минимизации функционала длины Н](Е) на множестве всех замкнутых связных множеств Е С R", удовлетворяющих ограничению Fm{Е) < г (последняя задача имеет смысл, например, как поиск конфигурации трубопровода минимальной длины, подходящего к каждому дому на расстояние, не превышающее г). В этих задачах заданным предполагается компактное множество М С М", моделирующее расположение населения, а также число I > О (соотв. г > 0).

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

ВВЕДЕНИЕ 7 ограничению #Е < /с, где А; — заданное натуральное число, посвящена обширная литература — это так называемые задачи оптимального размещения точек (optimal location problem, A;-median % problem для случая минимизации функционала среднего расстояния и ^-center problem для случая минимизации функционала максимального расстояния). Такие задачи могут интерпретироваться, например, как задача нахождения оптимального местоположения к сервисных центров (магазинов, складов и т.п.) с учетом заданной плотности населения ц) или только мест проживания населения. Различные разновидности таких задач встречаются в самых разных областях математики, в т.ч. и в столь, на первый взгляд, не имеющих между собой ничего общего ее разделах, как теория управления [34] и теория кодирования информации (поскольку они естественным образом связаны с задачами плотной упаковки [21]). В силу чрезвычайной обширности литературы на эту тему сошлемся лишь на монографии [1, 2, 3] и обзоры [66, 75, 76]. Стоит также отметить, что в случае к = 1 эти задачи сводятся к "непрерывной" (т.е. не обязательно дискретной) задаче Ферма-Вебера [55] о нахождении "медианы" заданного распределения ip. Для случая меры сосредоточенной в трех точках, эта задача восходит к Ферма, а ее решение было дано Торричелли. Часто обобщенной задачей Ферма-Вебера называют задачу размещения точек и для произвольного к. Этот же случай (к = 1 и дискретной меры tp) имеет и другое известное обобщение — задачу нахождения минимального связного графа (штейнеровского дерева), соединяющего заданные точки (на которых сосредоточена мера у?) [8].

8 ВВЕДЕНИЕ

Приведенные задачи минимизации функционалов среднего или максимального расстояний па классе одномерных множеств или подобные им задачи иногда называют задачами ирригации, поскольку их легко интерпретировать как задачи поиска оптимальной "системы каналов" S, наилучшим образом, с учетом ограничения на длину, подводящих воду ко всем растениям некоторого "поля" (с учетом или без учета плотности "растений на поле5') [41, 61, 70]. Общие результаты о существовании решений этих задач, а также качественные геометрические и топологические свойства последних изучаются в главах 1 и 2. В частности, будет показано, что соответствующие решения при естественных предположениях на данные задачи не содержат петель (простых замкнутых кривых), имеют конечное число концевых точек и точек ветвления и обладают некоторыми свойствами регулярности, а также будут охарактеризованы некоторые топологические и геометрические свойства точек ветвления этих решений. Кроме того, в главе 1 приводятся некоторые результаты численного моделирования соответствующих оптимальных сетей.

В главе 3 рассматривается задача построения оптимальной связной транспортной сети в предположении пренебрежимости затрат на перемещение по сети по сравнению с затратами на перемещение без ее использования. Данными задачи являются распределение источников (например, плотность населения в некоторой местности), задаваемая конечной неотрицательной борелевской мерой с компактным носителем в Rn, и распределение стоков (например, плотность центров обслуживания населения — магазинов, кинотеатров и т.п., и рабочих мест), задаваемая конечной неотрицательной борелевской мерой цГ

ВВЕДЕНИЕ 9 с компактным носителем в Е", а также неубывающая функция A: R+ —> Ё+ задающая эффективную стоимость (например, в терминах материальных затрат, а также затрат времени и усилий) перемещения каждого без помощи транспортной сети, так что затраты на проезд расстояния t без использования транспортной сети составляют A(t). Задача состоит в нахождении оптимальной транспортной сети (сети маршрутного городского транспорта и/или метро), которая обеспечивала бы наилучший доступ населения к центрам обслуживания (магазинам, кинотеатрам и т.п.) и рабочим местам. Искомая транспортная сеть моделируется замкнутым связным множеством S с Rn. Рассматриваемая в главе 3 строгая постановка соответствующей оптимизационной задачи, основанная на модели Монжа-Канторовича оптимального переноса массы и па предположении пренебрежимой малости затрат на перемещение с использованием сети пригодна также для оптимизации компьютерных сетей. Отмстим, что в отличие от работы [62], где предлагается основанная на похожих идеях модель оптимизации телекомуникационной сети с заранее заданной топологией (оптимизируются только отдельные параметры сети), в рассматриваемых в настоящей работе моделях топология сети заранее неизвестна. Наконец, в [35, 41] показано, что эта модель возникает и в некоторых задачах оптимизации формы в электродинамике.

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

10 ВВЕДЕНИЕ

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

В главе 5 рассматривается постановка задачи оптимизации транспортных сетей в терминах транспортных потоков. В формулировке этой задачи используется математический аппарат теории потоков Федерера-Флеминга, которая оказывается весьма естественной для описания моделей оптимизации транспортных сетей и потоков. Предложенная модель является развитием более простых моделей, предлагавшихся ранее для телекоммуникационных сетей [58], трубопроводов [30], дренажных и ирригационных сетей, а также сетей автострад [29, 44, 60, 61, 79, 80, 81], а в одном частном случае является развитием классической задачи построения минимальной штейнеровской сети [8]. В основе всех таких моделей находятся специальные разновидности задачи оптимального переноса массы,

ВВЕДЕНИЕ И сформулированные в терминах потоков и представляющие собой по сути дела "одномерные" версии различных геометрических вариационных задач типа задачи Плато [20, 22, 23, 49, 65, 73]. В этой главе не рассматривается вопрос существования решений соответствующей задачи в общей постановке, а лишь доказываются общие результаты о качественных свойствах решений. Кроме того, показывается, что в важном частном случае рассматриваемая в этой главе задача сводится к задаче, рассматриваемой в главе 4 в предположении линейности затрат на перемещение с использованием и без использования сети. Тем самым доказываются и некоторые качественные свойства решений последней задачи (такие как замкнутость множества, моделирующего транспортную сеть), существование которых уже доказано в главе 4, в достаточно распространенном и практически важном частном случае. Для иллюстрации развитой техники доказывается существование решений поставленной задачи в некоторых важных частных случаях.

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

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

Основные обозначения

Нк к-мерная мера Хаусдорфа в Еп

Л} одномерная мера Хаусдорфа в R" (длина) мощность (число элементов) множества

Сп мера Лебега в R"

1 е характеристическая функция множества Е

AM В наибольшее из А и В где А ж В - числа, функции или меры) А А В наименьшее из А и В где А и В - числа, функции или меры) Вт(х) открытый шар радиуса г с центром в х

Вт{х) замкнутый шар радиуса г с центром в х

D замыкание множества D со D выпуклая оболочка множества D со" D замкнутая выпуклая оболочка множества D diam D диаметр множества D | • | евклидова метрика в R" dist (х, Е) расстояние от точки х до множества Е dji(А, В) расстояние Хаусдорфа между множествами А и В supp </? носитель меры ip мера, полученная из при помощи отображения / ^ плотность (производная Радона-Никодима) меры ^ относительно меры ц

14 ОСНОВНЫЕ ОБОЗНАЧЕНИЯ

1/(П) пространство Лебега р-суммируемых функций на Q

Wk,p(Vt) пространство Соболева функций на Q с р-суммирусмыми обобщенным производными порядка до к включительно Q*k(ip,x) верхняя fc-мерная плотность меры ip в точке a;Gln нижняя к-мерная плотность меры ip в точке жбЕ" O/cip, х) ^-мерная плотность меры tp в точке х £ Мп 0£(S, х) верхняя /с-мерная плотность множества Е в точке xGl" 0ь(Е, х) нижняя ^-мерная плотность множества Е в точке х £ Мп 0fc(E, х) /с-мерная плотность множества Е в точке х £ Мп sc~I релаксация (полунепрерывная снизу оболочка) функционала I

Г" lim„ Iu Г~-предел последовательности функционалов Iv Г+ lim„ Iv Г+-предел последовательности функционалов Argmin I Множество точек минимума функционала I Argmax I Множество точек максимума функционала I F: X -о Y многозначное отображение F из X в У Graph F график отображения F Ма(Т) а-масса потока Т

М(Т) масса (1-масса) потока Т дТ граница потока Т

0[EJ поток, ассоциированный с (Нк, А;)-спрямляемым множеством Е и плотностью 9 (ориентация не указана)

Заключение диссертации по теме «Теоретические основы информатики», Степанов, Евгений Олегович

ЗАКЛЮЧЕНИЕ 337

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

Список литературы диссертационного исследования доктор физико-математических наук Степанов, Евгений Олегович, 2006 год

1. Бахтин А.Е., Колоколов А.А., Коробкова З.В. Дискретные задами производственно-транспортного типа. // Новосибирск: Наука. 1978. 167 с.

2. Береснев B.JL, Гимади Э.Х., Дементьев В.Т. Экстремальные задачи стандартизации. // Новосибирск: Наука, 1978. 335 с.

3. Емеличев В.А., Ковалев М.М., Кравцов М.К. Многогранники, графы, оптимизация. // М.: Наука. 1981. 344 с.

4. Заблоцкая О.А. L-разбиение многогранника задачи стандартизации. // Моделирование и оптимизация систем сложной структуры. Омск: ОмГУ, 1987. С. 151-154.

5. Забудский Г.Г. Об оценках стоимости связывающей сети в некоторых задачах размещения. // Дискретная оптимизация и анализ сложных систем. Новосибирск: ВЦ СО АН СССР, 1989. С. 10 25.

6. Забудский Г.Г. Задачи оптимального размещения взаимосвязанных объектов на линии. // Методы решения и анализа задач дискретной оптимизации. Омск: ОмГУ, 1992. С. 5 24.

7. Забудский Г.Г. Алгоритм решения одной задачи оптимального линейного упорядоченения. // Известия вузов. Математика. 1997. N 12. С. 73-78.

8. Иванов А.О., Тужилин А.А. Теория экстремальных сетей. / Монография. М.: Научно-издательский центр "Регулярная и хаотическая динамика", 2004. 424 с.340 Литература

9. Канторович JI.B. О перемещении масс. // Докл. АН СССР. 1942. Т. 37. Вып. 7-8. С. 227-229.

10. Канторович JT.B. Об одной проблеме Монжа. // Успехи матем. наук. 1948. Т. 3. Вып. 2. С. 225-226.

11. И. Канторович JI.B. Экономический расчет наилучшего использования ресурсов. / Монография. М.: Изд-во АН СССР, 1960. 347 с.

12. Куратовский К. Топология, том 2. // М.: Мир, 1969. 623 с.

13. Паолини Э., Степанов Е.О. Качественные свойства множеств, минимизирующих функционалы максимального и среднего расстояния в Rn. // Проблемы математического анализа. 2004. Вып. 28. С. 105-122.

14. Петросян J1.A., Зенкевич Н.А., Семина Е.А. Теория игр. // М.: Высшая школа. 1998. 304 с.

15. Смирнов С.К. Разложение соленоидальиых векторных зарядов на элементарные соленоиды и структура одномерных нормальных потоков. // Алгебра и анализ. 1993. Т. 5. Вып. 4. С. 206-238.

16. Степанов Е.О. Частичная геометрическая регулярность некоторых оптимальных связных транспортных сетей. // Проблемы математического анализа. 2005. Вып. 31. С. 129-157.

17. Степанов Е.О. Математические модели оптимизации транспортных сетей и потоков. / Монография. СПб: СПбГУ ИТМО. 2005. 244 с.

18. Степанов Е.О. Об одной модели оптимизации транспортных потоков. // Проблемы математического анализа. 2006. Вып. 32. С. 21-43.

19. Судаков В.Н. Геометрические проблемы теории бесконечномерных вероятностных распределений. // Труды АН СССР.,1. Литература 341

20. Математический институт им. В.А. Стеклова. Т. 141. Л.:Наука, 1976. 191 с.

21. Федерер Г. Геометрическая теория меры. // М.:Наука, 1987. 761 с.

22. Фейеш Тот Л. Расположения на плоскости, на сфере и в пространстве. / Монография. М.:Физматлит. 1958. 364 с.

23. Фоменко А.Т. Геометрические вариационные задачи. Современные проблемы математики. // Итоги науки и техники. М.:Наука, 1973. Т. 1. С. 39-59.

24. Фоменко А.Т. Многомерные вариационные методы в топологии экстремалей. // Успехи матем. наук. 1981. Т. 36. Вып. 6. С. 105-135.

25. L. Ambrosio. Lecture notes on optimal transport problems. // Mathematical aspects of evolving interfaces, Lecture Notes in Mathematics, Springer-Verlag. 2003. Vol. 1812. Pp. 1-52.

26. L. Ambrosio, N. Fusco, D. Pallara. Functions of bounded variation and free discontinuity problems. // Oxford mathematical monographs. Oxford University Press, Oxford. 2000. 434c.

27. L. Ambrosio, P. Tilli. Topics on analysis in metric spaces. // Oxford Lecture Series in Mathematics and its Applications. Oxford University Press, Oxford. 2004. Vol. 25.

28. V. Bangert. Minimal measures and minimizing closed normal one-currents. // Geom. Funct. Anal. 1999. Vol. 9. No 3. Pp. 413-427.

29. M. Beckmann, T. Puu. Spatial economics: density, potential and flow. // Elsevier Science Ltd. 1985.

30. M. Bernot, V. Caselles, J.-M. Morel. Traffic plans. // Publicacions Matematiques. 2005. Vol. 49. No 2. Pp. 417-451.342 Литература

31. S. Bhaskaran, F. J. M. Salzborn. Optimal design of gas pipeline networks. // J. Oper. Res. Society. 1979. Vol. 30. Pp. 1047-1060.

32. G. ВоисЫМё, G. Buttazzo, I. Fragala. Mean curvature of a measure and related variational problems. // Ann. Scuola Norm. Sup. CI. Sci. 1997. Vol. 25. No 4. Pp. 179-196.

33. A. Braides, A. Defranceschi. Homogenization of multiple integrals. // Oxford lecture series in mathematics and its applications. Clarendon Press, Oxford. 1998. Vol 12.

34. Y. Brenier. The dual least action problem for an ideal, incompressible fluid. // Arch. Rational Mech. Anal. 1993. Vol. 122. No 4. Pp. 323-351.

35. F. Bullo, D. Liberzon. Quantized control via locational optimization. // IEEE Trans. Automat. Control. 2006. Vol. 51. No 1. Pp. 2-13.

36. G. Buttazzo, G. ВоисЫМё. Characterization of optimal shapes and masses through Monge-Kantorovich equation. //J. European Math. Soc. 2001. Vol. 3. Pp. 139-168.

37. G. Buttazzo, E. Oudet, E. Stepanov. Optimal transportation problems with free Dirichlet regions. // Progress in Nonlinear Diff. Equations and their Applications. Birkhauser. 2002. Vol. 51. Pp. 41-65.

38. G. Buttazzo, A. Pratelli, S. Solimini, E. Stepanov. Mass transportation and urban planning problems. // Preprint, Dipartimento di Matematica, Universita di Pisa. 2005.

39. G. Buttazzo, A. Pratelli, E. Stepanov. Optimal pricing policies for public transportation networks. // SIAM J. Optim. 2006. Vol. 16. No. 3. Pp. 826853.1. Литература 343

40. G. Buttazzo, E. Stepanov. On regularity of transport density in the Monge-Kantorovich problem. // SIAM J. Control Optim. 2003. Vol. 42. No 3. Pp. 1044-1055.

41. G. Buttazzo, E. Stepanov. Optimal transportation networks as free Dirichlet regions for the Monge-Kantorovich problem. // Ann. Scuola Norm. Sup. CI. Sci. 2003. Vol. II. No 4. Pp. 631-678.

42. G. Buttazzo, E. Stepanov. Transport density in Monge-Kantorovich problems with Dirichlet conditions. // Discrete and Continuous Dynamical Systems-A. 2005. Vol. 12. No 4. Pp. 607-628.

43. L. Caffarelli, M. Feldman, R.J. McCann. Constructing optimal maps for Monge's transport problem as a limit of strictly convex costs. // J. Amer. Math. Soc. 2002. Vol. 15. Pp. 1-206.

44. V. Caselles, J.-M. Morel. Irrigation. // Progress in Nonlinear Diff. Equations and their Applications. Birkhauser. 2002. Vol. 51. Pp. 81-90.

45. C. Castaing, M. Valadier. Convex analysis and measurable multifunc-tions. // Lecture notes in mathematics. Springer-Verlag, Berlin. 1977. Vol. 580.

46. G. David, S. Semmes. Analysis of and on uniformly rectifiable sets. // Math. Surveys Monographs. Amer. Math. Soc., Providence, RI. 1993. Vol. 38.344 Литература

47. L. De Pascale, A. Pratelli. Regularity properties for Monge transport density and for solutions of some shape optimization problems. // Calc. Var. Partial Diff. Equations. 2002. Vol. 14. No 3. Pp. 249-274.

48. L. De Pascale, A. Pratelli. Sharp summability for Monge transport density via interpolation. // ESAIM Control Optim. Calc. Var. 2004. Vol. 10. No 4. Pp. 549-552.

49. T. De Pauw, R. Hardt. Size minimization and approximating problems. // Calc. Var. Partial Diff. Equations. 2003. Vol. 17. No 4. Pp. 405-442.

50. T. DeRose, T. Duchamp, H. Hoppe, J. McDonald, W. Stutzle. Fitting of surfaces to scattered data. // Proceedings of Curves and Surfaces in Computer Vision and Graphics 3, SPIE Proceedings. 1992. Vol. 1830. Pp. 212-220.

51. T. Duchamp, W. Stutzle. Extremal properties of principal curves in the plane. // Annals of Statistics. 1996. Vol. 109. No 4. Pp. 1511-1520.

52. L.C. Evans. Partial differential equations and Monge-Kantorovich mass transfer. // Cambridge MA, Current Developments in Mathematics. 1997. Pp. 65-126.

53. L.C. Evans, W. Gangbo. Differential equations methods for the Monge-Kantorovich mass transfer problem. // Memoirs of the A.M.S. 1999. Vol. 137. No 653.

54. S.P. Fekete, J.S.B. Mitchell, K. Beurer. On the continuous Fermat-Wcber problem. // Oper. Research. 2005. Vol. 53. No 1. Pp. 61-76.1. Литература 345

55. М. Feldman, R. J. McCann. Uniqueness and transport density in Monge's mass transportation problem. // Calc. Var. Partial Diff. Equations. 2002. Vol 15. No 1. Pp. 81-113.

56. W. Gangbo, R. J. McCann. The geometry of optimal transportation. // Acta Math. 1996. Vol. 177. No 2. Pp. 113-161.

57. E. N. Gilbert. Minimum cost communication networks. // Bell System Tech. J. 1967. Vol. 46. Pp. 2209-2227.

58. B. Kawohl, L. Tartar, 0. Pironneau, J.-P. Zolesio. Optimal Shape Design. // Springer-Verlag, Berlin. 2001.

59. D. H. Lee. Low cost drainage networks. // Networks. 1976. Vol. 6. Pp. 351-371.

60. F. Maddalena, S. Solimini, J.-M. Morel. A variational model of irrigation patterns. // Interfaces and Free Boundaries. 2003. Vol. 5. No 4. Pp. 391415.

61. A. Marigo, B. Piccoli. Optimal distribution coefficients for packets traffic on a telecommunication network. // Proceedings IEEE CDC-ECC, Sevelli, Spain. 2005.

62. P. Mattila. Geometry of sets and measures in Euclidean spaces. // Cambridge studies in advanced mathematics. Vol. 44. Cambridge University Press, Cambridge. 1995. 343 c.

63. M. Miranda, E. Paolini, E. Stepanov. On one-dimensional continua uniformly approximating planar sets. // Calc. Var. Partial Diff. Equations. 2006.

64. F. Morgan. Geometric measure theory. A Beginner's guide. Academic Press. 1987.346 Литература

65. F. Morgan, R. Bolton. Hexagonal economic regions solve the location problem, // Amer. Math. Monthly. 2001. Vol. 109. No 2. Pp. 165-172.

66. E. Paolini, E. Stepanov. Optimal transportation networks as flat chains. // Interfaces and Free Boundaries. 2006.

67. P. Pollak. Lazy travelling salesman problem. // Master's thesis, The Technion-Israel Institute of Technology, Haifa, 2002.

68. A. Pratelli. Equivalence between some definitions for the optimal mass transport problem and for the transport density on manifolds. // Ann. Mat. Рига Appl. 2005. Vol. 184. No 2. Pp. 215-238.

69. S. J. N. Mosconi, P. Tilli. Г-convergence for the irrigation problem. // Journal of Convex Analysis. 2005. Vol. 12. No 1. Pp. 145-158.

70. F. Santambrogio, P. Tilli. Blow-up of optimal sets in the irrigation probem. // Journal of Geometric Analysis. 2005. Vol. 15. No 2. Pp. 343362.

71. S.T. Rachev, L. Riischendorf. Mass transportation problems. Vol. I. Theory, Vol. II. Applications. Probability and its Applications. Springer-Verlag, Berlin, 1998.

72. L. Simon. Lectures on geometric measure theory. // Proceedings of the Centre for Mathematical Analysis, Australian National University. Australian National University, Centre for Mathematical Analysis, Canberra. 1983.

73. S.M. Srivastava. A course on Borel sets. // Graduate texts in mathematics. Springer-Verlag, New York. 1998. Vol. 180.

74. A. Suzuki, Z. Drezner. The p-center location. // Location science. 1996. Vol. 4. No 1-2. Pp. 69-82.1. Литература 347

75. A. Suzuki, A. Okabe. Using Voronoi diagrams. // Facility location: a survey of applications and methods (Z. Drezner, editor), Springer series in operations research, Springer Verlag. 1995. Pp. 103-118.

76. C. Villani. Topics in optimal transportation. // Graduate studies in mathematics. Vol. 58. American Math. Soc., Providence, RI. 2003.

77. B. White. Rectifiablity of flat chains. // Annals of Math. 1999. Vol. 150. Pp. 165-184.

78. Q. Xia. Optimal paths related to transport problems. // Communications in Contemporary Math. 2003. Vol. 5. No 2. Pp. 251-279.

79. Q. Xia. Boundary regularity of optimal transport paths. // Preprint. 2004. http://www.ma.utexas.edu/~qlxia/.

80. Q. Xia. Interior regularity of optimal transport paths. // Calc. Var. Partial Diff. Equations. 2004. Vol. 20. No 3. Pp. 283-299.