Решение энтропийно-регуляризованной транспортной задачи при малом параметре регуляризации (1187428), страница 8
Текст из файла (страница 8)
Считаем, что такая информация (статистика) по вчерашнему дню общедоступна. Исходя из этойинформации каждый житель, оценивающий минуту своего времени в pрублей, оценивает (экстраполируя ситуацию вчерашнего дня на день сегодняшний, за неимением точной информации о xk+1 ) свои затраты от62двух возможных альтернатив: Ap xk – личный транспорт и Bp – общественный транспорт. Мы считаем всех жителей рациональными, поэтомуиз двух альтернатив, каждый житель выбирает ту, которая приносит емунаименьшие затраты. Таким образом, происходит формирование xk+1 .Из описанного выше ясно, что жители города в (k + 1)-й день, оценивающие единицу своего времени в p xk < p ≤ pmax рублей, предпочтутв этот день личный автомобиль, а жители, оценивающие единицу своеговремени в 1 ≤ p < p xk рублей предпочтут в этот день общественный транспорт. Таким образом, в (k + 1)-й день доля xk+1 = x p xkжителей города использует (выберет) личный автомобиль.Для того чтобы сформулировать основной результат, сделаем одноупрощающее предположение, которое позволит представить этот результат в более наглядной форме.
Будем считать, что в зависимости x (p) =p−η параметр η = 1. Тогда, если4γ < a − b1 ,(79)то x (p ( · )) – сжимающее преобразование отрезка [0, 1] в себя. Легко понять, что условия (75) – (79) совместны.Теорема 1. При η = 1 в условиях (75) – (79) описанная выше динамика сходится (вне зависимости от x0 ) со скоростью геометрическойпрогрессии к неподвижной точке: xk −→ x∗ , которая определяетсяk→∞как единственная точка пересечения графиков x (p) p (x) на плоскости(p, x) .Доказательство. Сформулированное в теореме 1 утверждение сразу следует из принципа неподвижной точки для сжимающих операторов [18]. Однако намного полезнее представляется продемонстрироватьдоказательство рисунком, проясняющим, как происходит «нащупывание» равновесия.63Рис. 11: Итерационный процесс поиска равновесияЭтот рисунок можно проинтерпретировать следующим образом.
Вначальный момент x0 доля жителей города воспользовались личным автомобилем. На следующий день всем известно x0 , исходя из этого числа, каждый оценивает каким образом ему сегодня добираться до работы (и обратно). В результате автомобилем транспортом воспользуется x1 = x p x0 доля жителей города. Аналогично на следующийдень личным транспортом воспользуется x2 = x p x1 , на следующийx3 = x p x2 и т.д. Из рис. 1 видно, что такой итерационный процессбудет сходящимся к корню уравнения x = x (p (x)), что можно пониматькак точку пересечения графиков функции x (p) и p (x). Легко проверить,64что если на рис. 1 выбрать x0 левее x∗ , то сходимость также будет иметьместо.6.3Численные экспериментыМоделировался город численностью 1000 человек. Жители оценивают свое время целое число рублей p ∈ [1, 10].
Для распределения ЦипфаПарето был выбран параметр η = 2.Доля людей, выбравших личный транспорт в день номер 0, генерируется случайно. Эксперимент останавливается, если в сходящемся процессе доля людей, выбраших автомобильную поездку, изменяется менее, чемна 0.001 (1 человек). Для каждого набора парметров эксперимент проводился 1000 раз. Ниже, в результатах эксперимента приведены усредненные значения количества дней схождения вышеописанной динамики.65Таблица1Результаты экспериментовПараметрыT0 = 70, b2 = 75,γ=3T0 = 70, b2 = 75,γ=3T0 = 67, b2 = 75,γ=3T0 = 67, b2 = 75,cγ = 3T0 = 60, b2 = 75,γ=3b1aЧисло дней50603.0251603.5552604.1050652.7040603.1341503.4040552.6942552.7450606.81516013.5549604.8050653.0640506.84415013.9540553.0942553.4140702.6445703.1750704.1853707.49При таких параметрах процесс «нащупывания» равновесия сходилсяв среднем (случайно выбиралась точка x0 ∈ [0, 1]) за 3 – 4 дня (итерации).
Были также проведены численные эксперименты и при других значениях параметров. При самых неблагоприятных значениях, используемых в численных экспериментах, сходимость была в среднем за 14 дней.Таким образом, получено модельное подтверждение известного из опыта факта, что выход (нащупывание) равновесия осуществляется крайнебыстро (двух недель всегда хватает).
При этом стоит обратить внима66ние, что казалось бы незначительное повышение платы за общественныйтранспорт заставляет жителей «колебаться», дольше выходить на равновесие.ЗаключениеВ данной работе была предложена модификация адаптивного методаподобных треугольников (ASTM) для решения задачи ЭЛП с балансовыми ограничениями. Проведен сравнительный анализ быстродействия алгоритмов Синкхорна (балансировки) и различных вариантов ASTM дляразных входных данных (равномерное распределение, «полуравномерное» распределение, изображения из датасета MNIST), который выявилпревосходство ASTM. Также исследованы особенности работы ASTM ипроизведен обзор приложений, в которых может быть применен данныйметод (например, скаляризация).
Все выводы подкреплены экспериментами. Кроме того, проведен обзор четырёхстадийной модели поиска равновесного распределения потоков и подробно исследован четвёртый блокмодели (расщепление потоков по способу передвижения). Предложенамодель расщепления, и описан итерационный процесс эволюции траспортной сети.67Список литературы[1] А. В. Гасников, С. Л.
Кленов, Е. А. Нурминский, Я. А. Холодов, Н. Б.Шамрай Введение в математическое моделирование транспортныхпотоков.М.: МЦНМО, 2013, 428 с.[2] Гасников А.В., Блинкин М.Я., Омельченко С.С., Усик И.В. Эволюционный вывод простейшей модели бимодального расщепления спросана городские передвижения. // ТРУДЫ МФТИ. — 2015.
— Том 8, №1[3] Гасников А.В., Гасникова Е.В., Нестеров Ю.Е., Чернов А.В. Обэффективных численных методах решения задач энтропийнолинейного программирования // ЖВМ и МФ. 2016. Т. 56. No 4. С.523–534. arXiv:1410.7719[4] Franklin J., Lorenz J. On the scaling of multidimensional matrices //Linear Algebra and its applications. 1989. V. 114. P. 717–735.[5] В. И. Швецов, Математическое моделирование транспортных потоков.M.: Автоматика и телемеханика, 2003, выпуск 11, 46 с.[6] A. G. Wilson, A statistical theory of spatial distributions models.Transpn. Res. 1967, V. 1. P. 253-270.[7] Sandholm W., Population games and Evolutionary dynamics.
EconomicLearning and Social Evolution.MIT Press; Cambridge, 2010[8] Гасников А.В., Гасникова Е.В., Мендель М.А., Чепурченко К.В. Эволюционные выводы энтропийной модели расчета матрицы корреспонденций.Математическое моделирование. Т. 28. 2016[9] Nesterov Y. Smooth minimization of non-smooth function // Math.Program. Ser. A. 2005. V. 103. No 1. P.
127–152.68[10] Нестеров Ю.Е. Введение в выпуклую оптимизацию. М.: МЦНМО,2010[11] A. Ben-Tal, A. Nemirovski. Lectures on Modern Convex Optimization(Lecture Notes). // Personal web-page of A. Nemirovski, 2015.[12] А.В. Гасников Эффективные численные методы поиска равновесийв больших транспортных сетях arXiv:1607.03142[13] Л.
В. Канторович О перемещении масс, Зап. научн. сем. ПОМИ,2004, том 312, 11–14[14] Гасников А.В., Дорн Ю.В., Нестеров Ю.Е, Шпирко С.В. О трехстадийной версии модели стационарной динамики транспортныхпотоков // Математическое моделирование. 2014. Т. 26:6. C. 34–70.arXiv:1405.7630[15] Filippo Santambrogio Optimal Transport for Applied Mathematicians// Springer 2015[16] Ortuzar J.D., Willumsen L.G. Modelling transport. JohnWilley andSons, 2011.[17] Dafermos S., Sparrow F.
The Traffic Assignment Problem for a GeneralNetwork // J. of Res. of the National Bureau of Standards. 1969. V. 73B.P. 91–118.[18] Канторович Л.В., Акилов Г.П. Функциональный анализ. М.: Наука,1984.69.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
