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

На правах рукописи

Степанов Евгений Олегович

Задачи геометрической теории меры в моделях

оптимизации транспортных сетей и потоков Специальность 06.13.17 — теоретические основы информатики

Автореферат

диссертации на соискание ученой степени доктора физико-математических наук

Санкт-Петербург — 2006

Работа выполнена в Санкт-Петербургском Государственном Университете Информационных Технологий, Механики и Оптики

Официальные оппоненты: доктор физико-математических наук

B.C. Козякин

доктор физико-математических наук, профессор В.М. Тихомиров доктор физико-математических наук, профессор В.Г. Осмоловский Ведущая организация: Санкт-Петербургское отделение Математического Института им. В.А. Стеклова РАН

Защита состоится / { 2006 г. в ¿1 часов на заседании

диссертационного совета Д 002.077.01 в Институте проблем передачи информации РАН по адресу: 127994, г. Москва, Большой Каретный переулок, д. 19.

С диссертацией можно ознакомиться в библиотеке Института проблем передачи информации РАН по адресу: 127994, г. Москва, Большой Каретный переулок, д. 19.

Автореферат разослан "лГ/" Oty 2006 г.

Ученый секретарь диссертационного совета доктор физико-математических наук ' j _И.И. ЦИТОВИЧ

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ Актуальной проблемой в области оптимизации транспортных сетей является формулировка и исследование моделей, не предполагающих априорного знания топологии оптимизируемых сетей. В диссертации рассматриваются математические модели задач такого рода, а именно, задач оптимизации транспортных сетей и потоков произвольной природы, в которых заданными являются распределения источников и стоков, но не топология сети. К таким задачам, исследуемым в диссертации, относятся

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

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

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

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

исследователями, в том числе Л. Канторовичем, М. Весктапп'ом, Т. Puu, F. Morgan'ом.

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

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

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

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

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

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

Теоретическая и практическая значимость. Работа носит

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

Ä

сетей, основанных на задачах Монжа-Канторовича оптимального ■ переноса массы. Кроме того, эти результаты полезны при численном исследовании предложенных в работе оптимизационных моделей.

Апробация работы. Основные результаты диссертации докладывались и обсуждались

- на семинарах по математической физике Петербургского отделения Математического Института им. Стеклова РАН под , руководством O.A. Ладыженской и H.H. Уральцевой, 2002, 2003,

2005 гг.

- на семинаре по маломерной математике Петербургского отделения Математического Института им. Стеклова РАН,

2006 г.

- на семинарах Института Проблем Передачи Информации РАН,

2002, 2005, 2006 гг.

- на семинаре института Вейерштрасса (Weicrstrasa Institute for Applied Analysis and Stochastik), г. Берлин, Германия, 2005 г.

- на семинаре по функционально-дифференциальным уравнениям в научно-исследовательском институте математики г. Ариэль, Израиль, под руководством проф, М.Е. Драхлина, 2002 г.

- на семинарах математического факультета Тохниона, г. Хайфа, Израиль и Университета г. Беер-Шева, Израиль, 2002 г.

- на конференциях "Gíornate di Lavoro sul Calcolo dell Variazioni e Teoría Geométrica della Misura", г. Левико, Италия, 2001, 2002,

2003, 2004, 2005 гг.

- на международной школе-конференции "Nonlinear Analysis and Calculus of Variations" (г. Пиза, Италия, 2005 г.)

- на международных симпозиумах "Mathematical Models and Methods in the Study of Traffic Plow" (г. Феррара, Италия, 2003 г. и г. Врешиа, Италия, 2006 г.) и 'Masa Transport Problems, Shape Optimization and Weak Geometrical Structures" (г. Пиза, Италия, 2001 г.)

- на международной конференции "Advances in Partial Differential Equations", г. Феррара, Италия, 2003 г.

- на семинарах кафедр математики университетов г. Лечче, г. Пиза, политехнических институтов г. Вари и г. Милан, Италия, 2001, 2002, 2003, 2004, 2005, 2006 гг.

Публикации. Основные результаты диссертации опубликованы в монографии [1] и работах (2] — [10].

Структура и объем работы. Диссертация состоит из введения, шести глав, заключения и списка литературы, включающего 81 наименование. Общий объем работы составляет 347 страниц машинописного текста.

СОДЕРЖАНИЕ РАБОТЫ

Во введении обоснована актуальность выбранного направления исследования, дан краткий обзор литературы по теме диссертации и приведена аннотация результатов диссертации.

В главе 1 рассматриваются следующие задачи.

задача 1. Пусть задана положительная борелевская мера <р с компактным носителем в 2?". Найти множество £ор( с к", минимизирующее функционал среднего расстояния Е,Р, определямый формулой

[ А{¿\вг(х,Е))с1ф)> JW^

среди всех замкнутых связных множеств Е с Ж", удовлетворяющих ограничению на длину < I (число I > О предполагается

заданным). Здесь А: 1К+ —► — заданная неубывающая функция.

Задача 2. Пусть задано компактное множество М с К". Найти множество 2 — ]Сор1 С минимизирующее функционал максимального расстояния Рм, определяемый формулой

^(Е) := гсшхсМБ^Х, Е),

ХёМ

среди всех замкнутых связных множеств Е с К", удовлетворяющих ограничению на длину 7-^1(Е) < I (число I > 0 предполагается заданным).

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

Наконец, рассматривается также следующая задача, в известном смысле двойственная задаче 2.

задача 3. Пусть задано компактное множество М с к" и число г > 0. Найти компактное свзное множество еорь с к",

минимизирующее функционал длины И1 (13) среди всех замкнутых связных Е е К", удовлетворяющих ограничению ^м(Е) < г.

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

В главе 1 сформулированы общие теоремы о существовании решений поставленных задач, а также о наиболее простых качественных свойствах таких решений. В частности, в следующей теореме приведены основные качественные свойства решений задачи 1, доказанные в главе 1. Для ее формулировки рассмотрим следующие условия на функцию А\ • («1) А липшицева на интервале [0,(11атсо8ирруз], т.е. найдется'такая константа Л > 0, что

\А(х) - А[у)\ < Л|а; — у\

для любых ж, у 6 [0, сИаш вирр ; (огг) для любого с > 0 существует такая константа А = А(с) > 0, что

для любых х, у е [с,сиатсо8ирру>], В частности, функция А инъективна (иначе говоря, строго возрастающая, поскольку мы предполагали функцию А неубывающей) на интервале [0, (Натаирруз].

Теорема 1. Пусть о задаче 1 функция А строго возрастающая, а мера ¡р удовлетворяет условию "Н1 (вирр <р) > I (в частности, оно выполнено всегда, если <р <С Сп, или, в более общем случае, если размерность меры меры <р больше единицы). Тогда 7^1(ЕОр0 = I- Если, кроме того, ^ е где р г= 4/3 при п = 2 или р — п/(п — 1) при

п> 2 (напомним, что носитель меры предполагается компактным), а функция А удовлетворяет условиям (сц) и (с^), то множество Еор{ с сонирр <р, и является регулярным по Альфорсу в том смысле, что для любого х 6 Еорг и г < сИат £0(Л выполняются оценки

сг<Н1{ЪС\ВТ{х))<Сг с константами с > 0 и С > 0, не зависящими ни от х, ни от г > 0.

s

Стоит отметить, что свойство регулярности по Альфорсу существенно сильнее простой спрямляемости (последняя фактически гарантирована для множества Eopt в силу присутствующего в формулировке задачи требования связности и конечности длины этого множества): известно, что для замкнутых связных одномерных множеств оно эквивалентно более сильному свойству равномерной спрямляемости, изученному в работах G. David и S. Semmes.

Аналогичные свойства доказаны в главе 1 и для решений задачи 2. Доказывается также утверждение об эквивалентности задач 2 и 3. 1

В главе 2 изучаются основные топологические и геометрические свойства решений задач 1 и 2. Для формулировки соответствующих результатов напомним следующие классические определения.

ОПРЕДЕЛЕНИЕ 2. Пусть Е — топологическое пространство. Будем говорить, что порядок точки х 6 Е не превосходит п, и писать

ord^S* < п,

где п — кардинал, если для любого е > 0 существует открытая окрестность U С Е, х € U, удовлетворяющая условиям diam (U) < е и фди < п, где # обозначает мощность множества.

Порядок точки х £ Е будем называть равным п и писать

ordxT. = n,

если п — наименьший кардинал, для которого ord^T, < п.

Если ordx'E > 3, то х называется точкой ветвления Е, а если ordxЕ = 1, то х называется концевой точкой Е.

В следующей теореме приведены основные качественные свойства решений задачи 1, доказанные в главе 2.

ТЕОРЕМА 3. Пусть в задаче 1 функция А удовлетворяет условиям (ai) и (аг) (см. формулировку теоремы 1), а мера ip удовлетворяет условию "H1 (supp ip) > I (в частности, оно выполнено всегда, если <р -С Сп, или, в более общем случае, если размерность меры меры <р больше единицы). Тогда EDpt не содержит никакой простой замкнутой кривой. В частности, если п = 2, то множество К2 \ Eopt связно. Если, кроме того, п — 2, а ^ 6 //(К"), где р = 4/3 (напомним,

* Приведенные результаты о задаче 2 в дальнейшем развиты в работе Н. Miranda, Е. Paolini, Е. Stepanov. On one~diaen3lonal continua uniformly approximating planar sets. // Calculus of Variations and Partial Differential Equations. 2006 В частности, в этой работе для двумерного случая п ~ 2 доказана теорема о структуре решений задачи 2.

что носитель меры <р предполагается компактным), то выполняются следующие дополнительные свойства

• ordx^opt is 3 для всех х € Sopt, то есть все точки ветвления S0pt являются тройными точками. Более того, число концевых точек и точек ветвления Eopt конечно.

• Обобщенная средняя кривизна И множества Eopt, определяемая как векторнозначная обобщенная функция, удовлетворяющая условию ........ v ^ •• ■ ...........— '

< Х,Н >•.— f dixP^XdU1 для любого X,S Cß0{Rn,К"),

i/Eop* * * * "Y '

является мерой Радона, причем Н{{х}) = 0 для любой точки ветвления х S Sopt. Данное свойство -можно рассматривать как слабую форму утверждения о том, что всякая точка ветвления оптимального множества является "регулярным трехточием", т.е. точкой, из которой выходят ровно три ветви под углами, равными ISO градусам.

В главе 2 приводятся также и более общие утверждения о топологических и геометрических свойствах решений задач 1 и 2, а также об их частичной регулярности.

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

Рассмотрим для примера интерпретацию соответствующей модели в терминах задач городского планирования. А именно, пусть плотность населения в некоторой географической зоне (например, городе) задана конечной неотрицательной борелевской мерой <р+ с компактным носителем в R". Необходимо найти оптимальную транспортую сеть (сеть маршрутного городского транспорта и/или метро), которая обеспечивала бы наилучший доступ населения к центрам обслуживания (магазинам, кинотеатрам и т.п.) и рабочим местам, плотность которых

задана конечной неотрицательной борелевской мерой с компактным носителем в К". Искомая транспортная сеть моделируется замкнутым связным множеством £ С Ж". Пусть неубывающая функция А: К+ —» Е"1 задает эффективную стоимость (в терминах материальных затрат, а также затрат времени и усилий) перемещения каждого жителя без помощи транспортной сети, так что затраты на проезд расстояния I без использования транспортной сети составляют А(£).

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

(1) (^т)1-®" \ Е = \ Е>

где тг*: К" х К" —> К" - проекции на первую и вторую копии Ж" соответственно, т.е. ^(т+.а;-) г*. Если меры у* сосредоточены вне Е, и <р+(Мг') = <£>"(]{£"), то условие (1) означает, что все жители должны в результате перемещения достичь соответствующие рабочие места (магазины, центры оказания услуг населению). Однако имеет смысл и ситуация 9з+(К") ф В последнем случае некоторые

из жителей останавливаются в своем перемещении (или начинают движение) на Е. Так, в предельном случае р" = Ов рассматриваемой нами модели отсутствуют рабочие места (магазины и т.п.), так что единственной целью жителей является достижение транспортной сети Е с минимальными затратами.

Полную стоимость /е перемещения населения в соответствии с транспортным планом 7 легко выразить формулой

А{йх:{х,у))(1'у(х>у)1

где функция в И" определяется формулой

£2е(х, у) := «¿(ж, у) А (йй (ж, Е) 4- (Нб1 {у, Е)).

Иными словами, житель, начинающий движение из точки х, для достижения точки у будет выбирать наиболее удобный ему маршрут из двух вариантов: первый вариант — поездка без использования транспортной сети (при этом ему приходится проехать за плату расстояние 6,{х,у)), а второй - поездка с использованием транспортной сети (при этом ему приходится проехать за плату расстояние с!^ (х, Е) +

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

Обобщенная задача Монжа-Канторовичя. об оптимальном переносе массы с условием Дирихле на Е формулируется следующим образом: найти оптимальный транспортный план 7^, минимизирующий функционал среди всех допустимых транспортных планов

(т.е. конечных неотрицательных борелевских мер 7 в К" х К", удовлетворяющих (1). Будем в дальнейшем обозначать А/А'(<р+,<р~,£) как сам}' задачу Монжа-Канторовича об оптимальном переносе массы с условием Дирихле на Е, так и соответствующее ее решению 7^ минимальное значение функционала Iе. В случае Е = 0 будем для простоты писать МК(р+ ,<р~).

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

Задача 4. Найти множество с н , минимизирующее

функционал МК((р+,(р~,•) среди веет замкнутых связных множеств Е с К", удовлетворяющих ограничению на длину "Н^Е) < I (число I > 0 предполагается заданным). Меры <р+, <р~, а также неубывающая функция А: Ж+ —* К+ предполагаются заданными.

Основным результатом главы 3 является результат о сведении задачи 4 к задаче 1.

ТЕОРЕМА 4. Для задачи 4 существует такая неотрицательная борелевская мера ц> на К" (зависящая от >р+, (р~ и А), что любое решение задачи 4 является и решением задачи 1. При этом <р < (р±> и если 1р+ <р~, то <р ф 0.

Стоит отметить, что любое решение задачи 1 является, очевидно, и решением задачи 4 с ¡р* := <р, <р~ :— 0.

При помощи теоремы 4 и результатов глав 1 и 2, в главе 3 сформулированы результаты о качественных свойствах решений задачи 4.

В главе 4 рассматривается более общая по сравнению с главой 3 модель оптимизации транспортной сети без предположения о пренебрежимой малости затрат на перемещение по сети и без предположения связности сети.

Будем считать, что ■ соответствующие затраты задаются неотрицательной функцией В: R+ —♦ R+ (так, что B(t) — затраты на перемещение по сети на расстояние Ь). Функцию А: R+ —+ определяющую затраты на перемещение без использования транспортной сети (так, что A(t) - затраты на перемещение без использования сети на расстояние t), будем считать непрерывной. В обозначениях главы 3, если спрямляемая кривая в с К", соединяющая точки х S К" и у G R", интерпретируется как маршрут движения пассажира из тачки х 6 R" в точку у € №п, то величины Н1{в \ S) и Н'(й П S), где Н1 - одномерная мера Хаусдорфа, обозначают, соответственно, расстояние, которое пассажир может проехать без использования транспортной сети и с ее использованием. При этом каждый житель при планировании поездки может выбрать то расстояние Ls(B,6), на которое он будет использовать транспортную сеть £ при выборе маршрута движения 0, но так, что Le(J5,0) < H1 (О П Е). ТЪгда полные затраты на поездку одного пассажира по маршруту в можно выразить числом

ЫВ,в) А(«1(в) - Ьъ(В,в)) Ц- B(LS(B,<?)),

Естественно считать, что выбор Ls(B, 0) осуществляется из следующих соображений. Если пассажир решил использовать транспортную сеть на расстояние I, то его затраты определяются числом

д(1) := А(П1{9) -1) + В{1).

Поэтому в качестве Le(B, 0) для него имеет смысл выбирать из интервала [О, П £]) так, чтобы затраты g были минимальными. Такой выбор, вообще говоря, не всегда возможен (если функция g не является хотя бы полунепрерывной снизу), однако соответствующая точная нижняя грань всегда достигается для полунепрерывной снизу оболочки д~ функции д, определяемая по формуле

д-{1) = А(Н1(в)-1) + В-{1)>

где В~ - полунепрерывная снизу оболочка функции В. Таким образом, в качестве Ья(В, в) достаточно выбирать любую точку минимума д~ на интервале [O,7il(0 П Е)]. Поскольку таких точек минимума может быть несколько, то имеет смысл ввести для определенности следующее допущение: если минимальную стоимость поездки по заданному маршруту 0 можно получить при различных значениях расстояния I, на которые используется проектируемая транспортная

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

(2) LS(B, в) тах{/ е Argmmiswl(i)nE) А(Н\в) -£) + £Г(0}

(очевидно, что соответствующий максимум достижим). Следует подчеркнул», что данное предположение в главе 4 имеет смысл только для определенности, т.к. при выборе другого значения Ls(B, в) из точек минимума функции д~ на интервале [0, "Н1(в П £)] значение затрат не меняется.

Очевидно, что каждый житель, при выборе маршрута свой поездки из пункта х в пункт у решает задачу оптимизации индивидуальных затрат äs(B, •), так что его фактические затраты выражаются числом de,nix, у), определяемым по формуле

¿в>ф, V) := inf в) : в 6 9,0(0) = г, 0(1) = у} ,

где 9 обозначает множество всех спрямляемых кривых.

Как и в главе 3, будем описывать ежедневные перемещения населения при помощи транспортного плана -у, т.е. конечной неотрицательной борелевской меры на М" X R", удовлетворяющей ограничению на маргиналы

(3) тг<#7 = tpi, i = 0,1.

Предполагая, что население в целом стремится уменьшить свои совокупные затраты, выбирая соответствующий транспортный план, мы получаем, что совокупные расходы населения на поездки задаются минимумом функционала Монжаг Канторовича 1в,п> определяемого по формуле

7):=/ dBlE(x,y)d'y(x,y),

среди всех допустимых транспортных планов. Будем в дальнейшем обозначать этот минимум MK(<p+t tp~t S, В), а именно,

МАГ(«р+, v?-, Е, В) := inf {/в,е(т) '• 7 допустимый транспортный план} .

Стоит отметить, что соответствующий оптимальный транспортный план 7opt (реализующий минимум) зависит от всех параметров задачи, в том числе от В и от Е.

Пусть Н: —» - заданная неубывающая штрафная функция, отражающая затраты на постройку транспортной сети в зависимости от ее длины, так что Н{Н1{Т)) имеет смысл затрат на постройку сети длиной Wl(E). Теперь можно сформулировать общую задачу

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

ЗАДАЧА 5. Найти множество Еор1 с К", минимизирующее функционал

Е ь-» МК{<р+, <р~, Е, В) + Н(Н1 (Е))

среди всех борелевских (соотв. замкнутых связных) множеств Е С К". Меры <р+, ср~. а также, неубывающая функция А: К+ —> Е+ предполагаются заданными.

В частном случае

где число / > 0 задано, вышеприведенная задача соответствует задаче с ограничением на длину Т0(Т,) < I.

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

ТЕОРЕМА 5. Если в задаче 5 (без априорного требования связности оптимального множества) функции А и В вогнуты, до данная задача имеет решение.

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

В главе 4 также приведена эквивалентная формулировка задачи 5, полезная в приложениях, основанная Pia описании перемещения населения не в терминах транспортного плана 7, а в терминах транспортной меры г\ — конечной неотрицательной борелевской меры на пространстве 0 всех спрямляемых путей (с естественной топологией равномерной сходимости), удовлетворяющей условию на маргиналы

где отображения рг: В —> Ж" определены по формуле р,{9) в (г), г = 0,1. В частности, теорема 5 доказывается на основе анализа такой эквивалентной формулировки. Использование транспортной меры вместо транспортного плана удобно тем, что транспортная мера содержит информацию не только о начальных и конечных точках маршрутов перемещения, но и о самих маршрутах поездок.

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

В главе 5 рассматривается постановка задачи оптимизации транспортных сетей в терминах транспортных потоков. В формулировке этой задачи используется математический аппарат теории потоков Федерера-Флеминга. Предложенная модель является развитием более простых моделей, предлагавшихся ранее для телекоммуникационных сетей, трубопроводов, дренажных и ирригационных сетей, а также сетей автострад, а в одном частном случае является развитием классической задачи построения минимальной штейнеровской сети.

Пусть Л, В б К+, а, ß, 5 б [0,1]. Будем моделировать поток жителей, перемещающихся без использования проектируемой

^Приведенные результаты в дальнейшем развиты в работе G. Buttazzo, A. Pratelli, S. Solimini, £. Stepanov. Mass -transportation and urban planning problems. // Dipartimanto dl Materaatica, Umversltä dl Pisa. 2005. 81c. В частности, в этой работе доказано, что если функция И вогнута (соотв. строго погнута), то среди решений задачи 5 найдется по крайней мере оюто, имеющее не более чем счетное число связных компонент, хотя н не обязательно являющееся замкнутым (соотв все решения задачи 5 можно считать, не ограничивая общности, имеющими пе более чем счетное число связных компонент), хотя для произвольной функции Я реотепие задачи 5 может содержать более чем счетное число связных компонепт В этой же работе доказан и результат о естественной регулярности решегшй задачи 5 для случая, когда функция А линейна, В — 0, а Я произвольна.

транспортной сети, одномерным евклидовым потоком (flat chain) Т, а поток жителей, перемещающихся с использованием транспортной сети, одномерным евклидовым потоком (flat chain) S. Константу А будем считать стоимостью перемещения без использования проектируемой транспортной сети, а константу В - с использованием транспортной сети. Тогда число

W(T,S) := АМа(Т) + BM0(S),

где MQ обозначает а-массу потока, задает совокупную стоимость перемещения населения. Пусть Я: Е+ —» Ё+ - заданная неубывающая штрафная функция, отрюкающая затраты на постройку транспортной сети, обслуживающей поток S, в зависимости от ¿-массы этого потока, так что H(Ms(S)) имеет смысл затрат на постройку сети для обслуживания потока массой М^(S). Теперь можно сформулировать обшую задачу оптимизации транспортной сети в терминах потоков.

задача 6. Найти пару одномерных потоков (flat chain) (T0pi,S0pt), минимизирующих функционал

&(T,S) = W(T,S) + H(Ms(S))

среди всех пар одномерных потоков (flat chain) конечной массы, удовлетворяющих условию

8(T + S)r*v+-<p~.

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

В главе 5 показано, что в частном случае а = /3 = 1, 5 ~ О задача 6 эквивалентна задаче б для ситуации, когда функции А и В линейны. В общем же случае она независима от задачи б, и позволяет при манипуляции параметрами моделировать большую или меньшую "коллективность" поведения населения (т.е. склонность к выбору одинаковых маршрутов), и, соответственно, большую или меньшую пропускную способность различных участков сети (заметим, что в моделях, рассматриваемых в предыдущих главах, пропускная способность всех участков проектируемой транспортной сети одинакова).

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

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

ТЕОРЕМА 6. Пусть А > 0, а е [0,1], В > О, функция Н: [0,+оо) [О,+оо) строго возрастает, строго вогнута и неограничена, S £ [0, с*). Пусть также /3 € [0, а], причем А > В, если /3 = а. Наконец, предположим, что tp*2 — конечные положительные меры Бореля с компактным носителем в R", удовлетворяющие условию </з+(К") = (,o-(Rn).

Предположим, что задача 6 имеет решение, т.е. существует пара вещественных одномерных евклидовых потоков (Topt,Sopi), минимизирующая функционал

S) = АМа(Т) + BM?(S) + H(Ms(S))

среди всех пар (Т, S) вещественных одномерных евклидовых потоков конечной массы, удовлетворяющих условию

д{Т + S) = <р+ — <р~.

Тогда любая такая оптимальная пара (Topt, Sopt) обладает следующими свойствами.

(i) Sopt — спрямляемый поток, представимый в виде Snpt = ^urtP^optJ» где Eopt — компактное счетно (Н1,1)-спрямляемое множество, а плотность является полунепрерывной сверху функцией, удовлетворяющей условию infxgr:Qpt 0sop, (х) = _&а> 0.

^Приведенные результаты о задаче б в дальнейшем развиты в работе Е. Paolini» Е. Stepanov. Op-timal transportation networks an flat chains. // Interfaces and Free Boundaries. 2006.

(ii) Потоки Topi и S0pt дизъюнктны в том смысле, что меры

и (¿Sop, взаимно сингулярны. Кроме того, 8ир1еяп|0Гор,(а?) 6q, где ОтьР% — плотность Тор%. Если а < 1, то поток Торt является спрямляемым.

(iii) Поток To^t + £ор1 ацикличен.

Существование решения гарантировано, например, если а < 1, либо если а = Р= 1,6 = 0 (в последнем случае функция Н не обязательно должна быть вогнутой).

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

Для формулировки соответствующих моделей рассмотрим сначала случай, когда выбираемый населением транспортный план 7 заранее известен. Иначе говоря, изменение ценовой политики не влияет на выбор жителями целей их поездок (хотя может влиять на выбор маршрутов). Такая ситуация возможна при рассмотрении краткосрочной реакции населения на изменение цен. Естественно считать, что при заданной ценовой политике В каждый житель выбирает маршрут поездки в из пункта х в пункт у так, чтобы минимизировать общую стоимость поездки ^(-S, в), иначе говоря, его маршрут принадлежит множеству Qb(x,v) геодезических линий метрики £fjj,s(v)i соединяющих точки х я у. В дальнейшем, в полном соответствии с преположением о выборе расстояния Ьъ, сделанном в главе 4, вводится следующее разумное допущение: каждый житель при выборе расстояния, на которое. использовать транспортную сеть при поездке из пункта х в пункт у, выбирает такое его значение, которое обеспечивает максимальное использование транспортной сети при равных совокупных затратах пассажира, иначе говоря, выбирается расстояние

(4) ЫВ,х,у) sup Ls(B,0).

0e<3s(x,v)

В этом случае доход владельца сети определяется формулой

ЛхП

ПхП

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

Поскольку все рассмотренные величины зависят от В~, а не от В, то целесообразно в дальнейшем рассматривать задачу об отимизации ценовой политики В в классе В невозраетшощих полунепрерывных снизу функций В: Е£+ —► удовлетворяющих условию В{0) = 0 (последнее условие естественно, т.к. собственник транспортной сети не имеет права взимать плату с тех, кто не использует сеть).

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

задача 7. При заданном транспортном плане -у найти оптимальную ценовую политику В 6 В, максимизирующую Сг(-, 7) в

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

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

Горс(В) := А^хшп {/д1е('>) : 7 допустимый транспортный план}. Доход владельца сети определяется формулой

т.е. так, чтобы его минимум мог достигаться только при выборе 7 из Гар^В). Мы можем сформулировать теперь следующую задачу.

В.

..7)!_{в£л>.

если 7 € Гор4(В), иначе,

задача 8. Найти оптимальную ценовую политику В 6 В, максимизирующую функционал О в В,

Решение такой задачи соответствует ценовой политике, наилучшим образом удовлетворяющей компанию, заинтересованную и долгосрочной прибыли, так как в долгосрочной перспективе изменения ценовой политике может приводить к полному изменения поведения населения, включающему в себя не только возможное изменение маршрутов движения (что учитывалось и в задаче 7), но и возможное изменение целей поездок (что учитывается только в задаче 8),

Очевидно, что задача 8 допускает теоретико-игровую интерпретацию. Действительно, она может рассматриваться как задача определения специальной точки равновесия по Нэшу в следующей некооперативной игре: игроками являются "население" и "компания-владелец транспортной сети", причем стратегиями населения являются транспортные планы, а стратегиями компании-владельца сети -функции В е В. Функцией выигрыша населения в этой игре является функционал /д.е, а функцией выигрыша компании-владельца сети -функционал Ст.

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

В следующей теореме приведены основные качественные свойства минимальных решений задач 7 и 8, доказанные в главе 6. Для ее формулировки необходимо ввести некоторые обозначения. Пусть из а -модуль непрерывности функции А на [0, А], где

Л := сНат (вирр <р+ и вирр <р~) + ^(72),

а именно,

шл{1) := вир{|Л(и) - А(ь)| : |м - ь\ < 1,0 < и < А, 0 < V < А}

для всех I < А. Будем также обозначать для удобства шл{1) а>д(А) при г> А.

теорема 7. Пусть В - минимальное решение задачи 8 (соотв. задачи 7 с заданным транспортным планом 'у). Тогда

В{и)-В{ь)<шА{\и-и\)

для всех и, v £ 2". В частности, функция В непрерывна. Кроме того, если функция А субаддитивна, т.е.

А(и + v) < А(и) + А(г>) для всех и, v € то В (и) < А(и) для всех и 6 [O.W^E)].

Наконец, для некоторых модельных задач в главе 6 найдены явные решения.

В заключении приведены основные результаты работы.

РЕЗУЛЬТАТЫ РАБОТЫ

В диссертации получены следующие основные результаты:

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

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

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

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

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

Список литературы

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

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

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

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

5. G, Buttazzo, A. Pratelli, Е, Stepanov, Optimal pricing policies for public transportation networks.// SIAM Journal on Optimization. 2006, Vol, 16. No. 3, Pp. 826-853.

6. Q, Buttazzo, E, Stepanov. Minimization problems for average distance functional // Calculus of Variations; Topics from the Mathematical Heritage of Ennio De Glorgi, D, Pallara (ed.). Quadern! di Matematica, 2004. Vol. 14. Pp. 47-83.

7. G. Buttazzo, E. Stepanov, Optimal transportation networks as free Dirichlet regions for the Monge-Kantorovich problem.// Annall délia Scuola Normale Superior di Pisa Classe di Sclenze. 2003, Vol. II. No, 4, Pp, 631-678,

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

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

10. 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.

Центр распределенных издательских систем ИТМО. Санкт-Петербург, Саблинская 14.Твл: (812) 238-85-38

Подписано х печати Заказ/4" Л Объем 1 п.л. Тираж 100 экз.

Введение

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

Глава 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

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

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.