Построение матрицы корреспонденций для транспортной сети г.Владивостока
Автор работы: Пользователь скрыл имя, 27 Октября 2012 в 22:02, дипломная работа
Краткое описание
Основная цель данной работы состоит в построении матрицы трудовых
корреспонденции для транспортной сети г.Владивостока.
Для достижения поставленной цели необходимо выполнить следующие
задачи:
1. Изучить мировой и российский опыт решения транспортной проблемы.
2. Изучить гравитационные модели и их модификации.
3. Изучить энтропийные модели.
4. Провести условное деление территории г.Владивостока на сегменты.
5. Построить матрицу отправления и матрицу прибытия.
6. Построить матрицу трудовых корреспонденций для транспортной сети
г.Владивостока.
Содержание работы
Введение
2
1 Опыт решения транспортной проблемы
5
2 Математические модели определения корреспонденций
8
2.1 Гравитационные модели . . . . . . . . . . . . . . . . . . . . . .
9
2.2 Энтропийные модели . . . . . . . . . . . . . . . . . . . . . . . . 14
2.3 Моделирование самоорганизующихся потоков . . . . . . . . . 17
2.4 Алгоритмы построения матрицы корреспонденций . . . . . . . 20
3 Матрица корреспонденций для г.Владивостока
22
3.1 Деление территории г.Владивостока на сегменты . . . . . . . . 22
3.2 Подготовка данных . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.3 Построение матрицы корреспонденций . . . . . . . . . . . . . . 28
3.4 Проверка полученных результатов . . . . . . . . . . . . . . . . 31
Заключение
35
Список литературы
37
Приложение 1
39
Приложение 2
40
Приложение 3
41
Приложение 4
43
Приложение 5
44
Содержимое работы - 1 файл
ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ
ГОУ ВПО ДАЛЬНЕВОСТОЧНЫЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
ИНСТИТУТ МАТЕМАТИКИ И КОМПЬЮТЕРНЫХ НАУК
КАФЕДРА МАТЕМАТИЧЕСКИХ МЕТОДОВ В ЭКОНОМИКЕ
Построение матрицы корреспонденций для
транспортной сети г.Владивостока
Дипломная работа
студентки группы 255 А
Чалой Е.В.
Научный руководитель
Шамрай Н.Б.
к.ф.-м.н., ст.преп.
Владивосток
2009
Содержание
Введение
2
1 Опыт решения транспортной проблемы
5
2 Математические модели определения корреспонденций
8
2.1 Гравитационные модели . . . . . . . . . . . . . . . . . . . . . .
9
2.2 Энтропийные модели . . . . . . . . . . . . . . . . . . . . . . . . 14
2.3 Моделирование самоорганизующихся потоков . . . . . . . . . 17
2.4 Алгоритмы построения матрицы корреспонденций . . . . . . . 20
3 Матрица корреспонденций для г.Владивостока
22
3.1 Деление территории г.Владивостока на сегменты . . . . . . . . 22
3.2 Подготовка данных . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.3 Построение матрицы корреспонденций . . . . . . . . . . . . . . 28
3.4 Проверка полученных результатов . . . . . . . . . . . . . . . . 31
Заключение
35
Список литературы
37
Приложение 1
39
Приложение 2
40
Приложение 3
41
Приложение 4
43
Приложение 5
44
1
Введение
Транспортные системы городов и их ареалы являются одним из важных
факторов, который влияет на социально-экономическое развитие страны.
Совершенствование транспортной сети повышает качество жизни горожан,
увеличивает рост занятости, укрепляет бюджет города, развивает бизнес и
привлекает инвестиции.
Дороги являются "каркасом" страны (города), с помощью которого
соединяются между собой все части страны (города). Поэтому в
идеальной модели рыночной экономики улично-дорожные сети, в частности
и городские, должны обеспечивать высокую мобильность людей и
беспрепятственную перевозку товаров, так как состояние транспортной сети
напрямую влияет на состояние экономики в целом.
Экономическими эффектами от улучшения улично-дорожной сети
являются рост доходов транспортных предприятий, снижение аварийности
и удешевление эксплуатации транспортных средств. Перечисленные
эффекты можно назвать прямыми. Но, кроме прямых эффектов, от
улучшения качества дорог существуют и косвенные. К косвенным эффектам
относятся рост производства, в результате удешевления перевозок,
экономия времени населения и улучшения его здоровья, за счет снижения
числа ДТП.
Для России, как и для всех других стран мира, состояния дорог
оказывают влияние на экономические процессы. На сегодняшний день,
в России состояние дорожно-транспортной системы является одним из
факторов, которые тормозят развитие экономики страны.
Приморский край, особенно г.Владивосток, также столкнулся
с транспортной проблемой. Число транспорта в г.Владивостоке
неизбежно увеличивается. Эти процессы происходят быстрее, чем
муниципалитет успевает построить новые объездные дороги и увеличить
пропускную способность старых. Это привило к возникновению пробок,
затруднительному передвижению, ухудшению экологии и ухудшению
условий для нормального развития предприятий города.
Для решения возникшей проблемы существует много способов, которые
являются весьма дорогостоящими. Примерами решений транспортной
проблемы являются ограничение въезда в центр города, организация
перехватывающих парковок, ограничение владения личным транспортом и
строительство платных дорог.
В мировом опыте уже существуют удачно реализованные проекты такого
плана. Например, в Лондоне и Риме организован платный въезда в центр
2
города, что позволило "разгрузить" центр. В США весьма распространенны
перехватывающие парковки, что позволяет уменьшить число автомобилей
в городе. В Италии хорошо развита сеть платных дорог.
Но также существует и негативный опыт. Примером может являться
строительство платных дорог в странах Восточной Европы и строительство
перехватывающих парковок в Москве. Поэтому, перед тем как
инвестировать деньги в данную область, необходимо иметь четкое
представление, как и о уровни загрузки всех элементов в существующей
транспортной сети, так и о загрузки в планируемой сети. Если этого
не делать, то могут, увеличатся риски инвестиций и вероятность того,
что предпринятые меры не только не улучшат ситуацию на дорогах, а,
наоборот, ухудшат.
Для определения потоков и загрузки элементов сети сегодня существует
много математических моделей. Но основной проблемой в большинстве
данных моделей является необходимость информации о передвигающихся
по городу индивидуумах. Эта информация представляется в виде матрицы
корреспонденций.
Получить необходимую информацию о пассажиропотоке можно при
помощи натурных замеров. В дополнении к натурным замерам, для
получения более точной и обширной информации, начиная с 30 - х
годов прошлого века начали использовать матрицы корреспонденций,
построенные с помощью математических моделей, в частности, с помощью
гравитационных моделей.
Модифицированные гравитационные модели, а также энтропийные
модели, которые используются сегодня, позволяют определить матрицу
трудовых корреспонденций в городской транспортной системе, матрицы
пассажирских корреспонденций по всем видам направлений.
Если матрица корреспонденций построена, то на её основе можно:
– составить наиболее точное расписание движения общественного
транспорта;
– определить загрузки элементов улично-дорожной сети;
– определить главные пассажирообразующие пункты;
– оценить количество перевозимых пассажиров по типам пассажиров, по
видам транспорта, маршрутам и направлениям;
– оценить интенсивность пассажиропотоков между различными
пунктами.
3
В данной работе попытаемся построить матрицу трудовых
корреспонденций для транспортной сети г.Владивостока без проведения
натурных замеров пассажиропотоков, используя только наиболее
изученные методы формирования матрицы корреспонденций. В первой
главе дипломного исследования сделаем мировой и российский обзор
путей решения транспортной проблемы. Рассмотрим положительный и
негативный опыт разных стран в борьбе с городскими пробками.
Во второй главе сделаем обзор наиболее распространенных
математических моделей, используемых для построения матриц
корреспонденций, и их классификацию. Подробно опишем гравитационные
и энтропийные методы, а также их различные модификации.
В последней главе дипломной работы рассмотрим применение,
описанных в главе 2, моделей построение матриц корреспонденций для
транспортной сети города Владивостока. Подробно опишем методы
построения матрицы притяжения, матрицы отправления и матрицы
временных затрат. Проведем сравнительный анализ полученных расчетным
путем данных с данными обследований, которые были собраны в результате
прохождения производственной практики.
Основная цель данной работы состоит в построении матрицы трудовых
корреспонденции для транспортной сети г.Владивостока.
Для достижения поставленной цели необходимо выполнить следующие
задачи:
1. Изучить мировой и российский опыт решения транспортной проблемы.
2. Изучить гравитационные модели и их модификации.
3. Изучить энтропийные модели.
4. Провести условное деление территории г.Владивостока на сегменты.
5. Построить матрицу отправления и матрицу прибытия.
6. Построить матрицу трудовых корреспонденций для транспортной сети
г.Владивостока.
4
1 Опыт решения транспортной проблемы
В качестве макроэкономической функции дорожного комплекса можно
выделить его способность стимулировать экономический рост. Но, для
использования этой способности в полной мере необходима качественная
и разветвленная сеть автодорог.
Для создания такой сети в России необходим крупномасштабный
государственный заказ на дорожное строительство, что требует больших
вложений. Частичной альтернативой может являться инвестирование
строительства дорог предпринимательским сектором. Но тогда возникает
вопрос как окупить затраты конкретного инвестора?
Одним из путей решения этой проблемы может служить строительство
дублирующих, наиболее загруженных, участков магистрали, проезд, по
которым, в последствие, будет платным. В качестве положительного
примера, где используются платные дороги, можно привести Италию, где
существует единая сеть платных автомагистралей, которая управляется
одним крупным концессионным обществом.
В качестве еще одного удачного примера внедрения системы платных
дорог может являться строительство сети платных дорог в черте города
Мельбурн. Данный метод, в свое время, достаточно ощутимо помог решить
проблему городских пробок.
Существует и негативный опыт строительства платных дорог. Примером
является строительство автострады М-1 в Венгрии, которую практически
никто не использует из-за непомерно высоких тарифов. На сегодняшний
день, платные дороги также существуют и в США, Испании, Португалии,
Франции, Китае.
Другим примером, решения транспортной проблемы является платный
въезд в центр города. В этом случае водитель делает выбор заплатить ему
и передвигаться дальше по центральной зоне города на своей машине или
оставить машину и воспользоваться общественным транспортом. Данное
правило распространяется и на жителей платной зоны, только стоимость
въезда в данную часть города для них составляет 10% от тарифа. Данный
метод в 2003 году был введен в Лондоне и, благодаря этому способу,
количество машин в центре города уменьшилось на 10-15%, при этом
нагрузки на метро и другой общественный транспорт существенно не
увеличились.
Данная методика борьбы с пробками в городе используется и в Риме.
Здесь существует четыре зоны ограниченного движения, и по статистике
интенсивность движения в этих зонах снизилась до 20%. Нагрузка же на
5
общественный транспорт при этом увеличилась всего на 6%.
Похожей методикой, направленной на ограничение въезда в центр
города и, тем самым, на разгрузку основных центральных магистралей,
является организация перехватывающих парковок. В этом случае никто
не фиксирует въезд автомобилиста в центр города, и никто не требует
заплатить за это. Для России эти факторы являются плюсом с
психологической и юридической сторон.
Работа перехватывающих парковок организовывается следующим
образом. Водитель может оставить свою машину на специальной парковке
при въезде в центр города, или проехать в центр, и оставить машину на
парковке там, но за существенно большую плату, и только на определенное
время.
Опыт использования системы перехватывающих парковок показывает,
что введение этой системы существенно помогает уменьшить загрузки на
дорогах центральной части города. Число пользователей составляет 30-
50% от всех автовладельцев, а в Бостоне этот показатель достигает 75%.
Наибольшее количество перехватывающих парковок эксплуатируются в
крупных городах США, ФРГ, Франция, Швейцария.
Существует и негативный опыт использования перехватывающих
парковок. Строительство парковок такого направления в Москве и в Санкт-
Петербурге. Это связанно с тем, что парковки располагаются слишком
близко к центру города. Поэтому, во-первых, даже в случае массового
использования перехватывающих парковок пробки, до места расположения
парковок, никак не уменьшаться. Во-вторых, люди, простоявшие в пробках
в периферийных зонах, не видят смысла оставлять свои машины и
добираться до места иным средством передвижения, когда они находятся
близко к цели своего пути.
Также к причинам, по которым перехватывающие парковки не
пользуются популярностью, является то, что в центре есть большое
количество мест, где можно бесплатно оставить свой автомобиль на весь
день.
Еще одним примером неудачной транспортной политики является
пример Афин, где в 1982 году было введена система, по которой в
четный день могут передвигаться по дорогам машины номера, у которых
заканчиваются на четное число, а в нечетные - наоборот. В результате
власти добились совершенно противоположного эффекта. Теперь в Афинах
около 44% семей владеют двумя машинами, а около 17% тремя. Вторая
и третья машина чаще всего старая, списанная в Западной Европе, что
ухудшает экологию города.
6
Существует еще один метод решения транспортных проблем - единая
интеллектуальная система управления движением в городе. Данная система
непрерывно собирает информацию о загруженности дорог, скорости
потоков, авариях и условиях для движения машин. Собранная информация
обрабатывается и затем выдается в радиоэфир, онлайн на интернет-ресурсы
и дорожные указатели-табло, становясь, дополнительным средством
навигации для водителей, а также используется для регулирования
движения. Этот метод борьбы с пробками активно используется в Сеуле.
Интеллектуальная система управления движением в городе хоть и
помогает уменьшить число ДТП на дорогах, но не привела к значительному
уменьшению числа пробок в городе.
Существуют и другие методы по решению транспортной проблемы:
полосы с резервным движением (данный метод реализован в Вашингтоне),
создание выделенных полос для общественного транспорта (используется
в Париже), искусственное ограничение автомобилей (применяется в
Сингапуре). Но эти методы также не привели к ожидаемым результатам.
Поэтому транспортная проблема для этих городов так и осталась не
решенной.
Из описанного выше опыта решения транспортной проблемы можно
сделать следующие выводы:
– перед, введением любого метода по регулированию транспорта
необходимо определить объемы использования дорожными сетями;
– необходимо делать прогнозы загрузок всех элементов транспортной сети
включая планируемыми изменениям в сети и без них.
В транспортной теории уже существуют методологии определения таких
параметров. Для применения этих методологий на практике необходимо
знать полную матрицу корреспонденций по условным зонам города.
Доминирующую роль в нагрузке на улично-дорожную сеть в городах
составляют пассажирские перевозки. Поэтому в первую очередь необходимо
строить пассажирскую матрицу корреспонденций.
7
2 Математические
модели
определения
корреспонденций
Количественной
характеристикой
передвигающихся
по
городу
индивидуумов является матрица корреспонденций, элементы которой
определяют объем потока между каждой парой "точек". Под "точками"
будем понимать условные зоны, которые были получены путём деления
рассматриваемой области (например, города) некоторым подходящим
образом.
Можно выделить четыре класса расчета корреспонденций [1]:
Класс 1 К этому классу относятся нормативные, чаще всего линейные
модели,
с
критериальной
функцией
технико-экономического
содержания, которые отвечают на вопрос "Как должно быть?". К
классу 1 могут быть отнесены задачи планирования железнодорожных
грузовых перевозок, иногда задачи вне- и внутригородских перевозок.
Класс 2 Модели данного класса статистические - от простейших
однофакторных до динамических многофакторных. Особое место
среди них занимают гравитационные модели. Модели в данном классе,
а также в классах 3 и 4 отвечают на вопрос "Как есть?".
Задачи класса 2 возникают при планировании пассажирских
перевозок на железнодорожном транспорте (в пригородных и дальних
сообщениях), воздушном и морском транспорте, автомобильном
внегородском (в регионе), а также при планировании грузовых
перевозок в тех случаях, когда прикрепление поставщиков к
потребителю не может быть заданно на перспективу. К этому же
классу можно отнести задачи прогнозирования объёмов перевозок
на заданных направлениях, которые возникают при перспективном
планировании железнодорожных и морских грузовых перевозок.
Класс 3 Для решения задач класса 3 также используются статистические
модели и прежде всего гравитационные, но модифицированные,
усложнённые по сравнению с моделями класса 2. Усложнение
гравитационных моделей выражается в виде дополнительных условий,
которые обеспечивают балансировку матрицы корреспонденций.
Задачи этого класса включают задачи определения трудовых
корреспонденций в городских транспортных системах, когда рабочие
места, их ёмкость и размещение потенциальных кадров на территории
города выявлены и установлены априори.
8
Класс 4 Модели данного класса энтропийные. Они представляются
в форме нелинейной оптимизационной задачи математического
программирования,
причём
их
целевая
функция
носит
"термодинамический"
характер
и
включает
вероятностные
характеристики коллективного поведения. Определяющую роль
играют не детерминированные факторы поведения индивидуумов, а
закономерности коллективного поведения.
К задачам данного класса относится задача формирования
пассажирских корреспонденций в городских транспортных системах по
всем видам поездок: трудовым, культурно - бытовым, рекреационным.
В задачах класса 1 процесс формирования корреспонденций может
быть центрально управляемый, то есть "центр" планирует распределение
(направления и объемы транспортировки), которое было бы наиболее
выгодно, например, с точки зрения минимизации затрат. Затем "центр" для
каждой из уже известных корреспонденций принимает решение с помощью
критерия технико-экономического содержания о маршруте следования.
В задачах класса 4 невозможно жесткое управление формированием
корреспонденций и установка обязательных маршрут следования из одного
"центра". Это происходит потому, что пассажирские корреспонденции
формируются в городе под влиянием множества случайных факторов.
Каждый пассажир выбирает сам вид транспорта и маршрутов следования,
которые могут внезапно измениться. Поэтому возможно лишь косвенное
влияние "центра" на организацию потоков в сети, например на выбор
маршрута следования путем изменения технико-экономических параметров
некоторых элементов сети или выполнения определенных мер по
организации движения и так далее. Но, в данной работе будем предполагать,
что топология сети и технико-экономические параметры элементов сети
неизменны.
Дипломная работа посвящена построению трудовой матрицы
корреспонденции для транспортной сети г.Владивостока. Поэтому
остановимся на более подробном изучении гравитационных моделей,
модифицированных гравитационных моделей и энтропийных моделей.
2.1 Гравитационные модели
Простейшие гравитационные модели начали использовать для решения
задач планирования городских транспортных систем ещё с 30-х годов
20 века. В настоящее время для расчета корреспонденций вместо
9
гравитационных моделей используются энтропийные, а гравитационная
модель может быть использована только для задач, в которых
потребительское поле имеет ярко выраженную дискретную структуру.
Гравитационная модель разработана по аналогии с ньютоновским
законом, который связывает силу притяжения F
ij
между двумя массами
m
i
и m
j
, расположенными друг от друга на расстоянии d
ij
F
ij
= ζ
m
i
m
j
d
2
ij
,
где ζ – некоторая константа.
Аналогично закону Ньютона, транспортная гравитационная модель
связывает интенсивность потока T
ij
между полным числом отправления из
i зоны Q
i
и прибытий в j зону D
j
и затратами на передвижение между
зонами i и j c
ij
.
T
ij
= k
Q
i
D
j
c
2
ij
, i = 1,...,N, j = 1,...,M,
(1)
где N – общее количество зон отправления, M – общее количество зон
прибытия, k – некоторая константа, а затраты на передвижение выступают
в качестве "расстояния". Величина c
ij
– может быть рассмотрена как
расстояние между двумя зонами i и j, или как стоимость прохождения
расстояния между данными зонами.
Согласно уравнению (1) величина T
ij
пропорциональна Q
i
и D
j
и
обратно пропорциональна квадрату "расстояния" между ними c
ij
. Но у
этого уравнения имеется один очень большой недостаток: если увеличить
задаваемые значения Q
i
и D
j
в два раза, то число поездов в соответствии
с уравнением увеличится в четыре раза, хотя на самом деле оно только
удвоится.
Для устранения этого очевидного недостатка необходимо дописать
следующие ограничения, которые связанны с балансом въезда и выезда:
N
∑
i
T
ij
= D
j
, ∀i = 1,...,N,
(2)
M
∑
j
T
ij
= Q
i
, ∀j = 1,...M,
(3)
T
ij
≥ 0, ∀i = 1,...,N, ∀j = 1,...M.
(4)
10
Уравнение (2) означает, что суммарный поток (сумма числа поездок),
который выехал из всех зон i = 1,...,N в зону j должны быть равен
потоку, который прибыл в зону j. Уравнениe (3) означает, что суммарный
поток, который выехал обратно из всех зон j = 1,...,M в зону i должен
совпадать с числом прибывших в зону i. Суммарное количество выехавших
должно быть равно суммарному количеству прибывших, то есть должно
обязательно выполняться следующее условие
N
∑
i
Q
i
=
N
∑
j
D
j
Потоки при этом
не должны быть отрицательными.
Гравитационная модель (1) с ограничениями (2) - (4) является первой
модифицированной гравитационной моделью.
При моделировании, например, трудовых поездок в городе,
пассажиропоток T
ij
между известными вектором отправления Q
i
и
прибытия D
j
можно рассчитать по следующей формуле:
T
ij
= A
i
B
j
Q
i
D
j
f(c
ij
), i = 1,...,N, j = 1,...,M,
(5)
где
A
i
=
M
∑
j
B
j
D
j
f(c
ij
)
(−1)
, i = 1,...,N,
(6)
B
j
=
N
∑
i
A
i
Q
i
f(c
ij
)
(−1)
, j = 1,...,M,
(7)
f(c
ij
) = −αc
ij
exp
αc
ij
, i = 1,...,N, j = 1,...,M
где f(c
ij
)– функция, которая зависит от стоимости поездки. В качестве
f(c
ij
) можно использовать среднее время передвижения t
ij
, которое
считается заданным при решении задачи. Среднее время передвижения
является более или менее стабильным показателем транспортной системы
в каждом городе и может быть спрогнозировано.
Коэффициенты A
i
и B
j
определяются из условий (2) и (3)
соответственно. Уравнение (6) можно получить, проведя следующие
преобразования:
A
i
Q
i
M
∑
j
B
j
D
j
f(c
ij
) = Q
i
, i = 1,...,N,
A
i
M
∑
j
B
j
D
j
f(c
ij
) = 1, i = 1,...,N,
11
A
i
=
M
∑
j
B
j
D
j
f(c
ij
)
(−1)
, i = 1,...,N.
Аналогично уравнению (6), находится уравнение (7).
Если к ограничениям (6) и (7) добавить ограничение на T
ij
N
∑
i
M
∑
j
T
ij
c
ij
= C,
(8)
где C – полные затраты на передвижение, то наиболее вероятным
распределением будет матрица {T
ij
}, максимизирующая энтропию
lnW({T
ij
}) = lnT! −
∑
i
∑
j
lnT
ij
!,
где T – полное число поездок при ограничениях (6), (7) и (8), W({T
ij
}) –
полное число состояний системы, соответствующих распределению {T
ij
}. В
этом случае функция, зависящая от стоимости поездки, равна
f(c
ij
) = exp(−βc
ij
).
(9)
Величина C в (8) обычно не известна, и поэтому это уравнение на
практике не решается относительно β. Параметр β определяется методами
калибровки. Чем больше параметр β, тем меньше средняя длина поездки.
Этот факт связан с величиной C в уравнении (8). Если C увеличивается,
то увеличиваются и затраты на передвижение, и средняя длина поездки, а
β при этом уменьшается.
Тогда A
i
=
[
M
∑
j
B
j
D
j
exp(−βc
ij
)
]
(−1)
можно понимать как некий
конкурирующий член, который сокращает большинство поездок вследствие
роста привлекательности одной зоны. Также его можно использовать
как меру доступности. Аналогичную роль играют величины B
j
=
[
N
∑
i
A
i
Q
i
exp(−βc
ij
)
]
(−1)
, которые связанны с изменениями Q
i
.
Нахождение матрицы корреспонденций при помощи описанной выше
модели даст хорошие результаты только в том случае, если поездки будут
классифицированы по типам поездки и по типу передвижения.
Введем несколько типов пассажиров и несколько типов коммуникаций.
Выделим типы пассажиров по доступности различных наборов
коммуникаций. Например, владельцы автомобилей имеют доступ как
к личному автотранспорту, так и к общественному, а остальные люди могут
передвигаться, используя только общественный транспорт. Если деление по
признаку наличия автомобиля не проводится, то это приведет к моделям, в
12
которых пассажиры, не имеющие автомобилей, совершают автомобильные
поездки, либо заставит проводить отдельные распределения поездок
для различных групп пассажиров, а следовательно, и прогнозировать
привлекательность поездок для каждой группы в отдельности. Таким
образом, разделение всех пассажиров на тех, кто владеет личным
транспортном и тех, кто нет, является минимально необходимым. Полезно
также разделять людей по различным уровням дохода или по различным
социальным группам.
Рассмотрим множество типов пользователей транспортной сети R. На
этом множестве выделим множество типов коммуникаций M(r), которые
доступны пассажирам r ∈ R типа. Один тип коммуникаций, который
доступен пассажирам r типа обозначим за k ∈ M(r) обозначает множество
всех коммуникаций, которые являются, доступны между зонами i и j для
пассажиров r типа обозначим через M
ij
(r). Будем полагать, что между
всеми существующими зонами доступны все типы коммуникаций.
Определим следующие величины:
T
kr
ij
- интенсивность потока между i и j, совершаемого пассажирами r типа
на транспортном средстве k;
Q
r
i
- число отправлений из зоны i, совершаемых пассажирами r типа;
c
k
ij
- цена поездки из зоны i в зону j на k виде транспорта.
Остальные переменные определяются аналогично главе 1.2.
Тогда можно записать [2]
T
kr
ij
= A
r
i
B
j
Q
r
i
exp(−β
r
c
k
ij
),
(10)
где
A
r
i
=
M
∑
j
M(r)
∑
k
B
j
D
j
exp(−β
r
c
k
ij
)
(−1)
и
B
j
=
N
∑
i
R
∑
r
A
r
i
Q
r
i
exp(−β
r
c
k
ij
)
(−1)
.
Уравнение (10) описывает несколько гравитационных моделей для каждой
k − r группы. Связь между ними осуществляется через B
j
, так как это
выражение включает в себя все k и r.
Если для описания населения достаточно одного типа пассажира, то
можно провести агрегирование по r. Если провести агрегирование по
k, то получим ситуацию с одним типом коммуникаций. Если провести
агрегирование по k и по r, то получим исходную гравитационную модель
(5) при условии (9).
13
Предположим, что вместо стоимости проезда, представленной в виде c
k
ij
,
заданны величины C
k
ij
, которые описывают стоимость проезда из зоны i в
зону j для r типа пассажира. Величина C
r
ij
составляется из c
k
ij
, доступного
пассажирам r типа. Тогда получаем [2]
M(r)
∑
k
T
kr
ij
= A
r
i
B
j
Q
r
i
exp(−β
r
C
r
ij
),
(11)
где
A
r
i
=
M
∑
j
M(r)
∑
k
B
j
D
j
exp(−β
r
C
r
ij
)
(−1)
и
B
j
=
N
∑
i
R
∑
r
A
r
i
Q
r
i
exp(−β
r
C
r
ij
)
(−1)
.
Описанные выше гравитационные модели и их модификации при
формировании транспортных пар (i,j) не учитывают индивидуальные
предпочтения. Поэтому энтропийные модели, в которых вместо средних
величин характеристик передвижения вводятся условия об априорном
предпочтении формирования транспортных пар (i,j), формируют более
близкие, по вероятности, распределения корреспонденций к реальной
транспортной системе, которая сложится при учете предпочтений.
2.2 Энтропийные модели
Энтропийные модели базируются на принципе максимума взвешенной
энтропии рассматриваемой дескриптивной системы. Суть этого принципа
заключается в том, что реальному распределению потока на сети, которые
генерируются в результате самоорганизации, ставится в соответствие
распределение
потоков
(которые
удовлетворяют
транспортным
ограничениям), которое может быть получено в результате максимизации
некоторой энтропийной функции, которая параметрически зависит
от состояния системы, априори желательного для всех ее элементов
(взвешенная энтропия).
Рассмотрим физическую систему, как макросистему. В ней можно
выделить макроуровень и микроуровень. Макроуровень характеризуется
такими параметрами, как энергия, температура и так далее. Значения
этих параметров и общее состояние системы определяются взаимодействием
огромного количества частиц микроуровня, где взаимодействие между
всеми частицами носит случайный характер. По второму закону
термодинамики замкнутая физическая система стремится к достижению
14
устойчивого равновесного состояния, которое будет характеризоваться
максимумом энтропии этой системы.
Проведем аналогию со статистической физикой. В качестве некоторой
макросистемы рассмотрим пассажирские перевозки. В этом случае,
макроуровень будет характеризоваться суммарными транспортными
расходами, капитальными вложениями и так далее, а частицами
микроуровня будут являться пользователи сети. Взаимодействие частиц
на микроуровне носит случайный характер, так как в основе их
взаимодействия лежат такие факторы, как воля и желание, причем
количество индивидуумов в системе велико. Получаем, что при
моделировании пассажирских, особенно городских, перевозок можно
использовать методы статистической физики, связанные с измерением
энтропийной системы.
Наибольшая важность этой модели заключается в том, что в ней
формализуется гипотезы о равновесном и независимом поведении элементов
системы при формировании ее состояний. При наличии такой гипотезы,
наиболее вероятным является то состояние системы, при котором ее
неопределенность, измеряемая величиной энтропии, максимальна.
Максимизация взвешенной энтропии означает, что в системе ищется не
просто равновесное состояние, а состояние, которое близко по вероятности
к тому, которое сложилось бы в реальной транспортной системе при учете
индивидуальных предпочтений. Априорные индивидуальные предпочтения
в энтропийных моделях могут быть заданны, например, в виде функции
распределения вероятности α
ij
, где под α
ij
понимается вероятность того,
что индивидуум из зоны отправления i поедет в зону прибытия j .
Примером первых моделей этого направления может служить модель[3]:
min
T
ij
(
N
∑
i
M
∑
j
T
ij
c
ij
+ β
N
∑
i
M
∑
j
lnT
ij
)
(12)
M
∑
j
T
ij
= Q
i
;
N
∑
i
T
ij
= D
j
;
(13)
T
ij
≥ 0.
(14)
Здесь за T
ij
обозначена корреспонденция из зоны i в зону j. Под β
понимается средневзвешенная стоимость проезда. Через c
ij
обозначена
стоимость проезда единицы потока из сегмента i в сегмент j. Количество
поездок из зоны i будем обозначать через Q
i
. Количество поездок в зону j
через D
j
.
15
Формулу (12) можно преобразовать к следующему виду:
max
T
ij
N
∑
i
M
∑
j
T
ij
ln
T
0
ij
T
ij
(15)
T
0
ij
= exp
−
c
ij
β
,
где T
0
ij
обозначает распределение корреспонденции, которое образуется в
системе при отсутствии ограничений.
Другой пример энтропийной модели имеет следующий вид [1]
max
T
ij
N
∑
i
M
∑
j
T
ij
ln
α
ij
T
ij
(16)
M
∑
j
T
ij
= Q
i
;
(17)
N
∑
i
T
ij
= D
j
;
(18)
T
ij
≥ 0.
(19)
Величины α
ij
определяются исходя из функций распределения поездок,
например по времени, или удобству сообщений.
Модель (16) − (19) можно расширить следующим способом.
Предположим, что каждый человек может воспользоваться одним из
двух видов транспорта (например, железнодорожным или автобусом).
Тогда модель (16) будет записана в следующем виде [3]:
max
T
k
ij
N
∑
i
M
∑
j
2
∑
k
T
k
ij
ln
α
k
ij
T
k
ij
(20)
N
∑
i
M
∑
j
T
k
ij
= Y
k
, k = 1,2;
M
∑
j
2
∑
k
T
k
ij
= Q
i
, i = 1,...N;
N
∑
i
2
∑
k
T
k
ij
= D
j
, j = 1,...M.
Здесь α
k
ij
– вероятность того, что пользователь сети поедет из зоны i в зону
j и выберет k вид транспорта. Под Y
k
понимается суммарное количество
16
поездок по сети на k виде транспорте. Величины α
k
ij
определяются как
значения некоторых функций от времени поездки из зоны i в зону j
на k виде транспорта, которые являются специально построенными по
результатам статистических обследований.
Для определения потоков по всем звеньям транспортной сети города
используются модели самоорганизующихся потоков. В этих моделях потоки
по сети могут находиться одновременно с матрицей корреспонденций.
Но, на практике, чаще всего используют модели, в которых потоки
определяются по построенной заранее матрице корреспонденций. В моделях
самоорганизующихся потоков, как и в моделях построения матриц
корреспонденций, учитывается, что индивидуумы сами выбирают маршрут
следования.
2.3 Моделирование самоорганизующихся потоков
Задачи самоорганизации потоков могут возникать в транспортных сетях,
потребительское поле для которых имеет различную структуру, то есть
является сильно или слабо дискретным. Примером модели данного класса
являться следующая модель [3]:
min
T
ij
x
ij
∑
i
∑
j
(
∑
p
∑
u
c
u
γ
ij
up
x
ij
up
) + υT
ij
lnT
ij
(21)
∑
i
∑
j
∑
p
γ
ij
up
x
ij
p
≤ b
u
;
∑
p
x
ij
p
= y
ij
, ∀i,j;
∑
i
T
ij
= Q
i
;
∑
j
T
ij
= D
j
;
x
ij
p
≥ 0,T
ij
≥ 0,
где x
ij
pu
– часть потока на дуге u маршрута p, который порождается
корреспонденцией пользователей сети T
ij
, которые едут из зоны i в зонуj,
γ
ij
up
= 1, если дуга u входит в p маршрут, 0 - в противном случае. Под b
u
понимается ограничение на пропускную способность дуги u.
Модель (21) является примером моделей, в которых одновременно
с поиском потоков на звеньях транспортной сети, определяются
корреспонденции между условными зонами. Целевой функционал данной
модели носит смешанный характер: он содержит слагаемые энтропийного
17
и технико-экономического типа. Однако, в силу своей сложности, эта
модель не получила широкого распространения в практике пассажирского
прогнозирования.
Более известными являются модели определения пассажиропотоков, в
которых матрица корреспонденций задается. Большинство моделей такого
типа основываются на построении кратчайшего пути, для нахождения
которого осуществляется расценка дуг в соответствии с принятыми в модели
гипотезами о приоритетах и предпочтениях маршрутов.
По способу оценки затрат на дугах можно выделить два направления:
1. Модели, в которых корреспонденции распределяются по кратчайшим
путям (обычно в смысле времени передвижения).
В моделях этого типа гипотеза о выборе кратчайшего пути
рассматривается изолированно от других поведенческих гипотез, то
есть считается, что каждый человек выбирает маршрут независимо
от того, как организуются на сети потоки. При этом характеристики
дуг сети (таких как "длина"), которые необходимы для нахождения
кратчайших путей, рассчитываются априори из ранее определенной
статистической информации о времени поездки, о складывающихся
ранее элементах загрузок сети и так далее.
2. Модели, в которых затраты на дугах существенно зависят от их
загрузок.
В моделях данного типа учитывается, что каждый индивидуум
выбирает маршрут в зависимости от ситуации, которая складывается
на всех дугах сети. Поэтому кратчайший путь может меняться
в процессе наложения его на сеть, что связанно с изменениями,
которые складываются на элементах транспортной сети. Такие модели
самоорганизации потоков базируются на втором принципе Вардропа
[3]: самоорганизующиеся потоки стремятся так распределиться по
сети, чтобы достичь положения, в котором ни один пользователь
сети не может уменьшить время своей поездки в результате
изменения маршрута. Это положение называется равновесным,
а соответствующие ему потоки - равновесными, поэтому часто
модели данного типа называют моделями отыскания равновесного
потокораспределения в сети.
Величина потоков на элементах сети определяются в результате
решения оптимизационной задачи с нелинейным функционалом,
параметры которой подбираются специальным образом на основе
18
анализа распределений времени, дальности поездок и другой
статистической информации.
Примером моделей второго типа являются модели скалярной
оптимизации со специальной критериальной функцией и линейными
ограничениями транспортного типа. В данных моделях равновесные
потоки могут быть найдено с достаточной точностью. Примером модели
скалярной оптимизации со специальной критериальной функцией и
линейными ограничениями может являться следующая модель [3]:
min
x
ij
∑
i
∑
j
x
ij
∫
0
S
ij
(x)dx
(22)
∑
k
T
kpq
= D
pq
, ∀(p,q);
(23)
x
ij
=
∑
p
∑
q
∑
k
δ
ij,k,pq
T
k,p,q
,∀i,j;
(24)
δ
ij,k,pq
=
1, если дуга (i,j) ∈ маршруту k для корреспонденции из p в q,
0, в остальных случаях;
T
k,p,q
≥ 0,
Под x
ij
здесь будем понимать искомый поток по дуге, которая соединяет
вершину i и вершину j; под T
kpq
– корреспонденции из условной зоны p в
условную зону q по маршруту k; D
pq
– корреспонденция из условной зоны
p в условную зону q; S
ij
(x) – функция дифференциальных затрат на дуге
(i,j).
Функцию дифференциальных затрат S
ij
можно рассчитать по
следующей формуле:
S
ij
(x
ij
) = d
ij
δ + α
x
ij
n
ij
− γ
+
α
2
x
ij
n
ij
− γ
2
+ β
1/2
,
где под d
ij
понимается длина дуги (i,j); под n
ij
– число полос на
автомобильной дороге соединяющей вершину i и вершину j; x
ij
– искомый
поток по дуге (i,j); α,β,γ,δ – параметры функции данной дуги, которые
определяются по данным статистических исследований.
Основная трудность при отыскании самоорганизующихся потоков по
моделям, в которых затраты на дугах существенно зависят от их
загрузок, заключается в построении хорошей критериальной функции
дифференциальных затрат S
ij
(x
ij
).
Для расчета модели самоорганизующихся потоков используется метод
пошагового распределения [1].
19
2.4 Алгоритмы построения матрицы корреспонденций
Для построения матрицы корреспонденций, с помощью гравитационной
моделью (5) или энтропийной (15), с ограничениями (13)-(14), были
разработаны специальные алгоритмы. Рассмотрим более подробно каждый
из алгоритмов.
Алгоритм
построения
матрицы
корреспонденций
гравитационным методом [5]:
Шаг 1 Полагаем n = 1 и строим матрицу распределения корреспонденций
по следующей формуле T
1
ij
= Q
i
D
j
f(c
ij
)
[
∑
j
D
j
f(c
ij
)
]
−1
.
Шаг 2 Полагаем S
n
j
=
∑
j
T
n
ij
.
Шаг 3 Если
∑
i
T
n
ij
= D
j
, то алгоритм прекращает свою работу. Матрица T
n
является искомой матрицей корреспонденций на транспортной сети. В
противном случае, полагаем n = n + 1 и переходим к шагу 4.
Шаг 4 Если S
n
j
> D
j
, то T
n
ij
= T
n−1
ij
D
j
(S
j
)
−1
. Если S
n
j
≤ D
j
, то T
n
ij
= T
n−1
ij
.
Шаг 5 Находим Q
n−1
i
= Q
i
−
∑
j
T
n
ij
.
Шаг 6 Находим R
n−1
j
= D
j
−
∑
i
T
n
ij
и полагаем n = n + 1.
Шаг 7 Пересчитываем матрицу корреспонденций по следующей формуле
T
n
ij
= T
n−1
ij
+ Q
n−2
i
D
n−2
j
f(c
ij
)
[
∑
j
R
n−2
j
f(c
ij
)
]
−1
и переходим к шагу 2.
В результате работы описанного алгоритма получаем матрицу
распределения корреспонденций на транспортной сети T
n
ij
, которая будет
являться решением гравитационной модели (5).
Функция f(c
ij
) является функцией, которая зависит от стоимости
проезда или от среднего времени передвижения. Далее в наших расчетах
будем считать, что f(c
ij
) - функция, зависящая от времени передвижения,
и вычислять по формуле f(c
ij
) = exp
−βV
ij
, где β - коэффициент
калибровки, который определяет чувствительность "корреспонденций" к
фактору дальности; V
ij
- время, которое затрачивается на передвижение
из условной зоны i в условную зону j. Типичным значением для трудовых
поездок является β = 0.065 [7]. Поэтому в дальнейшем будем считать, что
коэффициент калибровки задан и равен β = 0.065.
Алгоритм построения матрицы корреспонденций энтропийным методом
основан на методе балансировки, где на каждой итерации этого алгоритма
20
выполняется баланс попеременно относительно строк или столбцов, а
через некоторое число итераций эта процедура приводит к полностью
сбалансированной матрице корреспонденций.
Если в качестве начального распределения брать некоторое начальное
распределение T
0
ij
, то предельная матрица доставляет максимум следующей
функции [6]:
∑
i
∑
j
T
ij
ln
T
0
ij
T
ij
=
∑
i
∑
j
T
ij
lnT
0
ij
−
∑
i
∑
j
T
ij
lnT
ij
.
Алгоритм построения матрицы корреспонденций энтропийным
методом [6]:
Шаг 1 В качестве начального приближения выбираем матрицу временных
затрат, T
0
= exp
−V
, и полагаем s = 0.
Шаг 2 Умножая столбцы матрицы T
s
на коэффициент, добиваемся
выполнения
N
∑
j
T
s
ij
= Q
i
,∀i = 1,...,M.
Шаг 3 Обозначаем полученную матрицу за T
s+1
и полагаем s = s + 1.
Шаг 4 Если условие
M
∑
i
T
s
ij
= D
j
,∀j = 1,...,N. выполняется, то алгоритм
прекращает свою работу. Иначе, переходим к шагу 5.
Шаг 5 Умножая строки матрицы T
s
на коэффициент, добиваемся
выполнения условия
M
∑
i
T
s
ij
= D
j
,∀j = 1,..,N.
Шаг 6 Обозначаем полученную матрицу за T
s+1
, полагаем s = s + 1 и
переходим к шагу 2.
Полученная, в результате работы алгоритма, матрица T
s
будет искомой
матрицей корреспонденций, а индекс s будет показывать число итераций,
за которое было найдено решение.
21
3 Матрица корреспонденций для г.Владивостока
3.1 Деление территории г.Владивостока на сегменты
Для расчета матрицы корреспонденций любым, из описанных в главе
1, методом необходимо определить вектор отправления Q и вектор
прибытия D. Для этого нужно знать условные зоны (сегменты), из
которых люди поедут (например, на работу), и условные зоны, в которые
они будут приезжать (например, рабочие места). В рамках данной
работы введем следующее определение условной зоны. Под условной зоной
(сегментом) далее будем понимать квадрат размерность 800 × 800 метров,
расположенный на территории города Владивостока (рис. 1).
Рис. 1: Пример одного сегмента г.Владивостока
Используя электронную карту города Владивостока [8] поделим
территорию города на условные зоны при помощи прямоугольной сетки
с шагом 800 метров (рис. 2). Получаем матрицу размерностью 22 × 30,
которая описывает всю территорию г.Владивостока. Масштаб рисунка 2
равен 1:99600.
В качестве "точек" отправления и "точек" прибытия возьмем все
условные зоны, которые получились в результате наложения сетки на
территорию г.Владивостока, то есть каждый сегмент города будет являться
и "точкой" отправления и "точкой" прибытия. Следовательно, матрица
отправления и матрица прибытия будут иметь размерность 22 × 30.
22
Рис. 2: г.Владивосток с наложением сетки
Элементы соответствующие сегментам, где никто не живет и не работает,
будем брать равными 0. Из рисунка 2 видно, что обе матрицы разреженные
и, следовательно, матрица корреспонденций тоже будет разреженной.
Так как для нахождения матрицы корреспонденции, используя
описанные в главе 1 модели, будет удобнее работать с векторами, то после
того как матрицы отправления и прибытия будут построены будем их
"вытягивать" в вектор-столбец и вектор-строку соответственно.
Для простоты, далее матрицу отправления будем называть
матрицей жилых массивов, а соответствующий ей вектор - вектором
отправления. Матрицу прибытия будем называть матрицей притяжения, а
соответствующий ей вектор - вектор прибытия.
3.2 Подготовка данных
Для построения матрицы трудовой корреспонденции необходимо знать:
• вектор отправления;
• вектор прибытия;
• вектор затрат.
Для определения вектора отправления построим матрицу жилых
массивов для трудовой корреспонденции. Матрицей жилых массивов
23
для трудовой корреспонденции является матрица, которая состоит из
посчитанного в каждом (i,j) сегменте проживающего экономически
активного населения. Для построения матрицы жилых массивов, которая
будет отображать число проживающих в каждом сегменте экономически
активного населения, подсчитаем сначала матрицу жилых массивов,
которая отображает все население.
Население в каждой условной зоне будем подсчитывать следующим
образом. С помощью детализированной до домов электронной карты
г.Владивостока [8] подсчитаем "вручную" в каждой зоне (i,j) число жилых
домов разной этажности (рис. 3).
Рис. 3: Пример определения этажности дома
Зная количество жилых домов разной этажности, которые находятся
в сегменте (i,j), умножим их на соответствующее число проживающих
людей в доме данной этажности и затем просуммируем. Зависимость числа
проживающих в жилом доме людей от числа этажей в данном доме
представлена в таблице 1.
Матрица, которая получилась в результате описанного подсчета,
приведена в приложении 1. Элемент (j,i) в матрице жилых массивов
соответствует числу людей, которое проживает в условной зоне (i,j)
рисунка 2. Таким образом, получена полная картина числа людей
проживающих в каждом из 660 сегментов на рисунке.
В результате подсчетов, число живущих на территории г.Владивостока
получилось равным 587768. Численность постоянного населения
г.Владивостока в 2008 году равнялось 578800 человек [14]. Ошибка в
подсчетах по общему количеству проживающих людей равна 8968, что не
превышает 1.5% от всех проживающих на территории города, суммарная
24
Таблица 1: Зависимость числа проживающих от этажности дома
Число этажей в доме Число проживающих людей
частные дома
2
одноэтажные
10
двухэтажные
30
трехэтажные
45
четырехэтажные
96
пятиэтажные
150
шестиэтажные
180
семиэтажные
224
восьмиэтажные
280
девятиэтажные
315
десятиэтажные
320
одиннадцатиэтажные
352
двенадцатиэтажные
384
тринадцатиэтажные
312
четырнадцатиэтажные
336
пятнадцатиэтажные
360
шестнадцатиэтажные
384
семнадцатиэтажные
408
двадцати шестиэтажные
624
ошибка отклонений по районам составила 5%. Следовательно, подсчитанная
"вручную" матрица является достоверной и может быть использована для
дальнейших расчетов.
Матрицу жилых массивов для трудовой корреспонденции получим
путем умножения матрицы жилых массивов на процент занятых в
экономике людей. Для получения распределения живущих на территории
г.Владивостока студентов и школьников по сегментам умножим матрицу
жилых массивов на процент учащихся. Данные о процентном распределение
населения возьмем из статистического ежегодника "Форпост у океана -
Владивосток"[9].
На территории г.Владивостока, кроме жителей города, работают
люди с п.Трудового и о.Русского. Поэтому для построения матрицы
корреспонденции для транспортной сети г.Владивостока необходимо учесть
поток рабочей силы из сельских населенных пунктов. Для их включения
в трудовую корреспонденцию будем суммировать число проживающих
работников в г.Владивостоке и число работников, которые едут из сельских
населенных пунктов, в тех сегментах, в которых есть основные въезды
в город: автодорожное сообщение с городом происходит в сегменте
(22,21); морское - в сегменте (6,6); железнодорожное - в сегментах
(13,8),(11,8),(9,8) и в (6,5).
25
В п.Трудовое проживает 19500 человек. Из проживающего на территории
поселка населения 61% - трудовые ресурсы [14]. В данную категорию людей
могут входить студенты, работники, которые работают на территории
п.Трудовое, работники, которые работают в г.Владивостоке. Данная
работа посвящена построению матрицы трудовых корреспонденций для
г.Владивостока, поэтому необходимо учитывать только то население,
которое поедут работать из п.Трудовое в г.Владивосток. В силу
того, что данная информация отсутствует, предположим, что из
п.Трудовое в г.Владивосток поедет работать 60% трудоспособного
населения. Транспортное сообщение с г.Владивостоком - автобусное и
железнодорожное. Будем полагать, что половина поедет на автобусах
и на легковых автомобилях, другая воспользуется пригородными
электропоездами.
На о.Русском число работающих равняется 1027 [14]. Предположим, что
они все работают в г.Владивостоке. Транспортное сообщение с городом
только морское. Полученное дополнительное число работников прибавим
к соответствующим сегментам и получим матрицу жилых массивов для
рабочей корреспонденции. Полученную матрицу "вытянем" в вектор-
столбец, который и будет в дальнейшем использован для расчета трудовой
корреспонденции.
Для нахождения вектора прибытия, определим места притяжения
населения и их емкость:
– больницы и больничные учреждения;
– учебные заведения;
– средние и крупные предприятия;
– малые предприятия.
Информация о больницах и больничных учреждениях, расположенных
на территории города Владивостока, а также о числе занятых в данной
сфере людей взята из статистических сборников "Здравоохранение и
социальное обеспечение в Приморском крае"[10], "Труд и занятость
населения во Владивостоке"[11] и "Рынок труда Владивостока"[12].
Данные об учебных заведениях и занятых в этой сфере людей взята из
аналитической записки "О состоянии образования во Владивостоке"[13].
Информация о малых, средних и крупных предприятиях - из "Труд и
занятость населения во Владивостоке"[11], "Рынок труда Владивостока"[12]
и на официальном сайте администрации г.Владивостока [14].
26
Данные по количеству учащихся в средних учебных заведениях, средне -
специальных учебных заведениях и высших учебных заведениях были взяты
на официальном сайте администрации г.Владивостока [14].
Полученная в результате обработки всей вышеперечисленной
информации матрица представлена в приложении 2.
Аналогично матрице жилых массивов, элемент матрицы притяжения
(j,i) соответствует числу людей, которые притягиваются в условную
зону (i,j) рисунка 2. Таким образом, получена полная картина числа
притяжений для каждого из 660 сегментов рисунка 2.
Полученную матрицу притяжения "вытянем" в вектор-строку, который
и будет в дальнейшем использован для расчета трудовой корреспонденции.
Последний столбец матрицы жилых массивов и матрицы притяжения
нулевой. Поэтому, без потери общности, можно его откинуть, что сократит
число сегментов, и, следовательно, сократит размеры векторов и уменьшит
число переменных в задаче.
На рис. 4 визуально представлены матрица отправления и матрица
прибытия. Зеленым цветом обозначаются сегменты, из которых население
отправляется на работу, синим - сегменты, в которые прибывают, серым
и белым цветами - пустые сегменты. Из рисунка видно, что почти все
условные зоны города являются местами отправки и прибытия
Рис. 4: Матрицы отправления и прибытия
27
В качестве вектора затрат на передвижение из зоны i в зону j возьмем
временные затраты. Вектор временных затрат, для простоты посчитаем
сначала в виде матрицы размерностью 22 × 29, а затем "вытянем"
полученную матрицу в вектор.
Матрицу временных затрат будем вычислять по следующей формуле:
V
ij
= d
ij
∗ s
ij
,
где s
ij
– скорость передвижения индивидуума в транспортной сети из
условной зоны i в зону j, d
ij
– расстояние от сегмента i до сегмента j.
Скорость передвижения индивидуума будем брать равной 4км./ч., если он
передвигается внутри условной зоны и 30км./ч., если он едет из условной
зоны i в условную зону j, где i = j.
По построению матрицы города известно, что расстояние между
двумя близлежащими сегментами равняется 800м. Расстояние внутри
каждого сегмента будем брать равным 400м. Тогда получаем, что матрица
расстояний будет симметричной, с диагональными элементами равными 0.4.
Элементы верхней треугольной матрицы будем рассчитывать следующим
образом:
– расстояние от сегмента (i,j) до сегмента (i,k) по формуле 0.8 ∗ (j −
k)км.;
– расстояние от сегмента (i,j) до сегмента (l,k) по формуле
√
0.8
k−j
+ 0.8
i−l
км.
Аналогичным образом рассчитывается и нижняя треугольная матрица.
Зная матрицы отправления, прибытия и временных затрат можно
посчитать матрицу трудовых корреспонденций, с помощью энтропийной
модели (15), (13)-(14) и гравитационной (5) , которые были описаны в главе
1.1 и 1.2 соответственно.
3.3 Построение матрицы корреспонденций
Для построения трудовой матрицы корреспонденций воспользуемся
гравитационной моделью (5):
T
ij
= A
i
B
j
Q
i
D
j
f(c
ij
), i = 1,...,N, j = 1,...,M,
где
A
i
=
M
∑
j
B
j
D
j
f(c
ij
)
(−1)
, i = 1,...,N,
28
B
j
=
N
∑
i
A
i
Q
i
f(c
ij
)
(−1)
, j = 1,...,M,
f(c
ij
) = exp
−βV
ij
, i = 1,...,N, j = 1,...,M
Также рассчитаем матрицу трудовых корреспонденций энтропийным
методом (15), (13)-(14):
max
T
ij
N
∑
i
M
∑
j
T
ij
ln
T
0
ij
T
ij
M
∑
j
T
ij
= Q
i
;
N
∑
i
T
ij
= D
j
;
T
ij
≥ 0,
где T
0
ij
= exp
−
c
ij
β
.
Матрица отправления Q имеет размерность 638 × 1, матрица прибытия
D−1×638. Следовательно, наша задача будет иметь размерность 638×638,
а число переменных в ней равняется 407044. Число ограничений на не
отрицательность также равняться 407044, а число ограничений задачи
равняется 1276. Полученную задачу с большим количеством переменных и
ограничений с помощью пакетов, в частности с помощью пакета MINOS,
решить не удалось. Поэтому для построения матрицы корреспонденций
гравитационным и энтропийным методами воспользуемся специальными
алгоритмами, которые были описаны в главе 1.4.
Как можно заметить, даже для сравнительно небольшого города
Владивостока, у которого начальная матрица, описывающая территорию,
имеет размерность 22 × 29, число переменных, полученных в решении
задачи, уже равняется 407044, что очень велико. Таким образом,
гравитационный и энтропийный методы, используемые для построения
матрицы корреспонденции, квадратично увеличивают число переменных в
задаче, и их число равняется (n ∗ m)
2
, где m × n – размерность матрицы,
описывающей город.
В приложении 3 представлены коды программ, написанные на octave,
которые реализуют специальные методы, которые описаны в главе 1.4.
На рис. 5 изображен график сходимости: голубым цветом изображена
сходимость гравитационного метода, желтым - энтропийного. Из рисунка
видно, что скорость сходимости энтропийного метода выше, и допустимое
решение находится за меньшее количество итераций.
Полученные в результате работ программ матрицы трудовых
корреспонденций приложены к дипломной работе на электронном носителе.
Максимальная абсолютная ошибка между двумя полученными матрицами
29
1
2
3
4
5
6
7
8
9
10
0
5
10
15
20
25
30
35
40
45
50
55
60
Рис. 5: График сходимости
равняется 44, что говорит о точности полученного решения. На данном
носителе записаны две папки. В соответствии с названием в папке находится
матрица трудовых корреспонденций для транспортной сети г.Владивостока,
которая была получена либо с помощью энтропийной, либо с помощью
гравитационной модели.
В каждой из этих папок расположены также две папки: "матрицы
корреспонденций из сегментов" и "матрицы корреспонденций в условные
зоны". В папке "матрицы корреспонденций из сегментов" находятся 638
матриц трудовых корреспонденций из всех условных зон г.Владивостока.
Название каждого из файлов, находящихся в папке, соответствует сегменту
на рис.2. Матрицы, записанные внутри этих файлов, являются матрицами
корреспонденций из соответствующего названию сегмента во все условные
зоны г.Владивостока. В папке "матрицы корреспонденций в условные
зоны" записаны 638 матриц трудовых корреспонденций во все сегменты
г.Владивостока. Название каждого их файлов соответствует сегменту на
рис.2. Матрицы, записанные внутри этих файлов, являются матрицами
корреспонденций в соответствующий названию сегмент из всех условных
зон г.Владивостока.
В приложении 4 представлены матрица корреспонденций из всех
условных зон г.Владивостока в сегмент (8,8). На рис. 6 проиллюстрирована
данная матрица корреспонденций из всех условных зон в сегмент (8,8).
На данном рисунке красным цветом выделена условная зона (8,8), в
которую притягиваются работники; спектром от синего до светло - зеленого,
выделены зоны, из которых едут на работу в сегмент (8,8) более 100 человек
30
Рис. 6: Пример корреспонденций в одну зону
более 100 человек в порядке возрастания.
Аналогичный анализ, по количеству человек, которые поедут из одной
условной зоны в другие, можно сделать для всех 1276 матриц трудовых
корреспонденций. Также зная матрицы трудовых корреспонденций, с
помощью описанных в главе 1 моделей самоорганизующихся потоков,
можно рассчитать потоки по сетям.
3.4 Проверка полученных результатов
В ходе выполнения данной дипломной работы была получена матрица
трудовой корреспонденции. Полученный результат нельзя проверить
теоретическим способом. Поэтому были сделаны натурные замеры потоков
автотранспорта на различных сечениях элементов улично - дорожной сети
г.Владивостока в утреннее время суток.
В качестве проверяемых районов были выбраны Первомайский и
Фрунзенский. В Первомайском районе не расположены места массового
притяжения людей для культурно - бытовых или рекреационных целей.
Поэтому основной поток, который будет ехать в Первомайский район, это
будет трудовой поток.
Во Фрунзенском районе расположено меньше мест притяжения людей,
31
Рис. 7: Пример корреспонденций из одной условной зоны
таких как больницы, учебные заведения и торговые центры. Поэтому
поток в данный район в основном будет состоять из трудового потока.
Предположим, что трудовой поток едет в течение четырех часов, с 7.30
до 11.30 часов утра.
Натурные замеры проводились на улице Спортивная, Пограничная и
Алеутская (см. рис. 8). На данном рисунке голубым цветом выделены
районы в сторону которых, натурным методом, замерялся поток, красным
цветом – точки, на которых данные замеры производились. Замер
проводились в будний день, в течение часа с 8.30 - 9.30 утра, по
направлениям в рассматриваемый район.
Улица Спортивная является единственной улицей, которая соединяет все
районы г.Владивостока с Первомайским. Другого въезда в район или выезда
из него нет.
В Первомайском районе 59338 рабочих мест. По рассчитанной матрице
корреспонденции из остальных районов города в Первомайский на работу
едут 40697 человека. Обеспеченность населения собственными легковыми
автомобилями в в.Владивостоке составляет 336 автомобиля на 1000 жителей
[9]. Следовательно, мимо контрольного поста, где проводились замеры,
должно было проехать 12209 легковых автомобилей за 4 часа или, в среднем,
32
Рис. 8: Граф г.Владивостока с выделением некоторых районов
3053 – за час.
Для определения потока в район Эгершельда, проводились замеры в двух
контрольных точках: на улицах Алеутская и Посьетская. По рассчитанной
матрице корреспонденций в данную часть города на работу едут 43953
человека. Следовательно, суммарный поток, который должен был проехать
мимо контрольных пунктов, должен был составить 3296 легковых машин.
В таблице 2 дано сравнение расчетных потоков с соответствующими
данными обследований.
Таблица 2: Сравнение расчетных данных и данных обследований
Направление Данные обслед. Расчет. данные Откл. в %
в Первомайский
район
2672
3054
14
во Фрунзенский
район
2924
3296
12.7
В процессе сборки эмпирических данных, также было подсчитано число
общественного транспорта. Количество людей, которое проехало за час
в общественном транспорте оценить нельзя, но можно приблизительно
посчитать количество людей, которые поедут в Первомайский район на
данном виде транспорта. Даже, если предположить, что в одной легковой
машине поедет только один водитель, то в среднем получаем, что в одном
автобусе в Первомайский район поедет 72 человека, а во Фрунзенский –
33
91 человек, что не превышает максимальной вместимости автобуса в 100
человек.
Расхождение расчетных данных с данными обследований можно
объяснить тем, что в качестве начальной матрицы распределения была
выбрана матрица временных затрат. Временные затраты, были рассчитаны
из расстояний между условными зонами, которые являются стабильными
показателями. Но, функция затрат, зависящая только от временных
издержек, не дает более реалистичных результатов.
Построение функции затрат, которая максимально бы соответствовала
реальной ситуации, является основной сложностью в данных моделях.
Важной особенностью является то, что функция затрат зависит от
результатов загрузки транспортной сети. А потоки на улично - дорожной
сети зависят от матрицы корреспонденций.
Также можно выделить тот факт, что нет более подробной
статистической информации о распределении легковых автомобилей в
собственности, как по возрастным группам, так и по районам города. Этот
факт отрицательно сказывается на проверке полученных распределений,
путем теоретических расчетов, с полученными эмпирическими данными.
34
Заключение
В процессе выполнения данной работы были изучены:
– мировой и российский опыт в решении транспортных проблем;
– гравитационные модели и их модификации;
– энтропийные модели;
– модели самоорганизующихся потоков.
В рамках данной работы были посчитаны матрица отправления
и матрица притяжения. Эти матрицы, как и матрица трудовых
корреспонденций, являются входными для большинства транспортных
моделей, поэтому полученные в ходе выполнения данной дипломной работы
матрицы Q и D могут быть использованы в дальнейшем для транспортных
моделей, применимых к г.Владивостоку.
В ходе выполнения данной работы также был изучены и
реализованы на языке octave специальные алгоритмы для решения
гравитационной и энтропийной моделей. С помощью этих алгоритмов
были построены матрицы трудовых корреспонденций для транспортной
сети г.Владивостока. Максимально абсолютная разница между двумя
решениями равняется 44, что говорит о точности полученных результатов.
Для более удобного и легкого чтения матрицы, она была разбита на
638 матриц корреспонденций из (i,j) сегмента во все условные зоны
г.Владивостока, и на 638 матриц корреспонденций в (i,j) условную зону
из всех сегментов. Таким образом, в результате данной работы были
получены матрицы трудовых корреспонденций, связывающие все условные
зоны г.Владивостока между собой.
В ходе выполнения работы, было выявлено, что для сравнительно
небольшого г.Владивостока число переменных в решении задачи очень
велико. Используемые для построения матрицы корреспонденций методы
квадратично увеличивают число переменных по сравнению с начальным
их количеством. Этот недостаток не является существенным, если решать
эти задачи с помощью специально разработанных алгоритмов, но пакеты
программ даже задачу для г.Владивостока уже не решают.
Полученные значения были сравнены с реальными потоками по дорогам
г.Владивостока. Было выявлено, что полученные значения превышают
эмпирически показатели. Данный результат позволяет сделать следующий
вывод. Для получения более точных и реалистичных показателей
35
необходимо строить "хорошую" функцию временных затрат, которая
зависела бы от таких показателей как:
– комплексное время, затрачиваемое индивидуумом на путь следования,
– затраты на передвижение до пункта следования;
– плата за стоянку.
Полученный результат дипломной работы далее может использоваться
для расчетов эффективности долгосрочных инвестиций в решение
транспортных проблем, что позволит установить оправдают ли будущие
выгоды, понесенные затраты. Также может использоваться в качестве
дополнительной информации для определения ценовой политики,
например, в случае строительства платных дорог или перехватывающих
парковок.
36
Список литературы
[1] Васильева Е.В., Игудин Р.В., Лившиц В.Н. Оптимизация планирования
и управления транспортными системами. – М: Транспорт, 1987.
[2] Вильсон А.Дж. Энтропийные методы моделирования сложных систем.
– М: Наука, 1978.
[3] Васильева Е.В., Левит Б.Ю., Лившиц В.Н. Нелинейные транспортные
задачи на сетях. – М: Финансы и статистика, 1981.
[4] Шелейховский Г.В. Композиция городского плана как проблема
транспорта. – М: Государственный институт проектирования городов
ГИПРОГОР, 1946.
[5] Arrowsmith G. A behavioural approach to obtaining a double constrained
trip distribution model. – Operation Research Quarterly, 1973, vol.24, №1.
[6] Романовский И.В., Ампилова Н.Б., Петренко Е.И. О максимизации
энтропии при линейных ограничениях. [электронный ресурс] // Режим
доступа: htpp://www.pub.math.spbu.ru [Дата обращения: 29 марта
2009г.]
[7] Алиев А.С., Стрельников А.И., Швецов В.И., Шершевский Ю.З.
Моделирование транспортных потоков в крупном городе с применением
к Московской агломерации. – М: Журнал Автоматика и Телемеханика,
2005, №11, с. 113 - 125.
[8] Официальный сайт Примор АГП [электронный ресурс] // Режим
доступа:
htpp://www.personal.primorye.ru/primagp/default.htm
[Дата обращения: 6 февраля 2009г.]
[9] Форпост у океана - Владивосток (статистический ежегодник с
исторической справкой). - Владивосток: Издательство Примстат, 2008.
[10] Здравоохранение и социальное обеспечение в Приморском крае
(статистический сборник). - Владивосток: Издательство Примстат,
2008.
[11] Труд и занятость населения во Владивостоке (статистический сборник).
- Владивосток: Издательство Примстат, 2008.
[12] Рынок
труда
Владивостока
(статистический
бюллетень).
-
Владивосток: Издательство Примстат, 2009.
37
[13] О состоянии образования во Владивостоке (аналитическая записка). -
Владивосток: Издательство Примстат, 2009.
[14] Паспорт города [электронный ресурс] // Режим доступа:
htpp://www.vlc.ru [Дата обращения: 15 марта 2009г.]
38
П
р
и
л
о
ж
е
н
и
е
1
Т
а
б
л
и
ц
а
2
:
М
а
т
р
и
ц
а
ж
и
л
ы
х
м
а
с
с
и
в
о
в
1
2
3
4
5
6
7
8
9
1
0
1
1
1
2
1
3
1
4
1
5
1
6
1
7
1
8
1
9
2
0
2
1
2
2
1
3
0
7
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
2
9
0
4
5
5
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
3
0
7
1
6
4
5
3
8
1
6
0
8
2
3
9
6
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
4
0
0
1
2
3
9
1
4
7
5
2
7
8
2
1
0
6
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
5
0
0
1
9
0
0
5
7
9
0
7
3
0
6
4
1
1
9
6
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
6
0
9
1
4
1
3
9
6
5
9
1
9
0
2
4
2
7
1
1
6
8
7
2
8
4
2
6
6
8
9
0
0
0
0
0
0
0
0
0
0
0
0
0
7
6
3
7
3
1
2
7
2
8
7
8
6
0
1
4
0
2
3
7
3
2
6
0
9
9
9
9
8
1
1
4
1
7
0
1
4
6
0
0
0
4
0
0
0
0
0
0
0
0
0
8
0
2
5
2
7
5
8
3
4
7
3
8
5
3
2
2
2
9
7
0
5
0
4
5
1
0
7
5
4
5
0
3
5
5
5
1
1
7
0
9
0
1
6
6
8
3
2
4
5
1
3
4
8
4
7
8
0
0
0
0
0
0
0
9
4
5
3
2
8
7
9
2
7
2
8
3
1
0
1
8
0
5
1
6
4
9
1
3
9
1
1
4
3
1
4
9
2
7
7
7
9
1
1
4
9
0
1
0
8
5
8
4
4
8
6
1
5
2
6
5
1
5
3
9
4
5
2
4
2
4
0
0
0
0
0
1
0
2
0
3
2
0
2
3
9
9
8
8
4
7
8
9
4
1
1
2
7
5
9
6
9
9
8
1
6
0
1
4
2
4
3
2
8
7
1
8
7
4
2
8
7
6
6
6
8
2
4
2
2
0
2
8
1
3
6
5
1
4
2
7
4
0
0
0
0
1
1
2
5
0
1
0
3
7
2
4
1
1
4
3
9
8
8
2
8
1
2
0
6
3
7
9
8
0
8
9
4
8
1
7
0
1
6
2
9
6
7
5
8
2
0
2
7
8
6
4
5
7
7
1
5
0
1
7
6
9
8
8
2
9
6
0
0
0
1
2
4
7
0
0
9
8
8
7
7
2
0
8
5
5
9
5
8
7
2
7
7
9
7
5
8
8
6
0
6
9
3
8
4
0
0
0
8
2
6
8
6
5
4
0
6
7
3
9
3
7
6
2
8
0
0
0
1
3
9
0
7
2
5
8
5
4
2
2
5
5
7
9
4
1
0
1
1
0
1
7
8
0
2
5
9
8
5
9
5
1
0
0
0
0
0
0
0
0
2
2
4
5
1
2
3
0
5
0
0
1
4
0
4
5
6
3
8
6
7
6
1
1
0
3
2
0
0
0
0
3
9
2
1
5
4
5
6
3
0
0
0
0
0
0
0
3
0
1
8
7
2
8
4
0
0
1
5
0
6
0
0
9
6
4
8
0
4
0
0
0
7
6
9
0
5
7
1
4
0
0
0
0
0
0
0
1
4
9
1
0
2
2
0
1
6
0
0
0
0
0
0
0
0
1
3
2
0
0
0
0
0
0
0
0
0
0
0
3
4
2
0
1
7
0
0
0
0
0
0
0
0
4
0
0
0
0
0
0
0
0
0
0
0
0
7
7
5
2
2
1
8
0
0
0
0
0
2
0
4
6
0
0
0
0
0
0
0
0
0
0
0
0
5
4
1
1
9
2
5
8
1
9
0
0
0
0
1
0
1
4
0
2
5
5
0
0
0
0
0
0
0
0
0
0
0
0
3
6
1
0
2
3
2
9
2
0
0
0
0
0
0
0
2
7
2
0
1
0
0
0
0
0
0
0
0
0
1
0
1
6
8
5
6
2
2
2
6
3
3
2
2
1
0
0
0
0
0
0
0
3
6
0
0
0
0
0
0
0
0
0
0
0
3
3
1
3
6
2
3
7
9
2
2
0
0
0
0
0
0
0
4
8
0
0
0
0
0
0
0
0
0
0
0
0
0
9
2
2
3
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
6
1
4
2
4
0
0
0
0
0
0
0
0
0
0
1
1
0
0
0
0
0
0
0
0
0
0
0
1
0
2
5
0
0
0
0
0
0
0
0
0
0
0
4
0
0
0
0
0
0
0
0
0
0
0
2
6
0
0
0
0
0
0
0
0
0
0
0
4
6
1
9
3
0
0
0
0
0
0
0
0
0
2
7
0
0
0
0
0
0
0
0
0
0
0
0
0
0
6
0
0
0
3
8
5
6
0
0
0
0
0
2
8
0
0
0
0
0
0
0
0
0
0
0
0
0
1
6
1
6
4
2
7
0
0
0
0
0
0
0
2
9
0
0
0
0
0
0
0
0
0
0
0
0
0
0
2
4
4
3
1
6
6
0
0
0
0
0
39
П
р
и
л
о
ж
е
н
и
е
2
Т
а
б
л
и
ц
а
3
:
М
а
т
р
и
ц
а
п
р
и
т
я
ж
е
н
и
я
1
2
3
4
5
6
7
8
9
1
0
1
1
1
2
1
3
1
4
1
5
1
6
1
7
1
8
1
9
2
0
2
1
2
2
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
2
0
7
5
7
9
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
3
0
4
2
4
3
8
4
4
0
4
1
5
4
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
4
0
0
4
1
3
4
4
1
5
3
4
8
2
5
2
4
2
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
5
0
0
8
1
5
0
5
1
5
0
8
7
2
9
7
6
1
7
4
1
3
4
0
0
0
0
0
0
0
0
0
0
0
0
0
0
6
0
7
8
8
1
1
9
2
1
3
8
4
7
8
8
9
6
4
2
9
7
1
9
9
4
0
0
5
3
9
1
0
0
0
0
0
0
0
0
0
0
0
0
0
7
0
1
6
1
2
2
7
3
2
1
7
9
7
8
1
5
2
0
8
1
3
7
6
9
6
8
5
6
7
8
4
8
0
0
0
0
7
9
0
0
0
0
0
0
0
0
0
8
0
1
3
5
4
1
3
7
4
2
0
6
5
7
8
8
4
2
0
5
3
5
1
1
4
9
8
1
2
2
9
4
2
3
5
1
3
8
2
9
1
2
1
3
2
1
0
0
1
2
6
3
9
5
7
0
0
0
0
0
0
0
9
0
1
3
5
4
2
9
0
5
1
4
0
0
1
6
6
2
3
7
0
7
3
8
2
9
5
0
5
0
2
1
0
5
2
2
3
0
2
1
9
1
2
3
8
7
1
7
2
8
2
1
1
2
1
3
5
0
1
3
1
5
8
3
2
0
0
0
0
0
1
0
0
7
8
8
2
0
9
3
1
4
1
8
1
4
8
4
3
1
1
2
3
8
5
7
4
1
1
6
1
7
2
5
1
7
2
5
1
4
4
4
3
7
3
1
2
6
5
5
2
2
2
1
9
5
7
1
6
9
5
3
2
6
6
3
1
5
8
0
0
0
0
1
1
0
0
1
3
8
7
2
4
1
3
4
7
4
1
5
6
3
6
2
6
8
2
3
0
0
3
1
7
2
5
9
8
7
1
4
0
6
1
4
0
6
2
5
4
9
2
5
2
4
0
0
0
0
1
4
4
5
0
0
0
1
2
0
7
8
8
1
3
8
7
2
6
5
7
3
5
9
9
3
3
5
6
3
1
7
1
1
9
0
8
9
8
7
1
7
2
5
0
0
1
7
5
5
2
0
0
0
0
0
1
2
0
7
8
3
2
0
0
1
3
0
8
0
8
1
6
8
0
2
5
3
7
3
1
6
6
3
1
2
9
2
5
7
1
0
1
6
8
6
9
8
7
0
0
0
0
7
1
9
0
0
1
2
0
7
1
2
0
7
9
8
5
0
0
1
4
0
1
0
9
1
1
9
3
7
2
5
9
8
3
0
7
1
3
0
7
1
0
0
1
0
0
2
9
8
7
0
0
0
0
0
0
0
0
0
1
2
1
0
9
4
0
0
1
5
0
7
8
8
2
1
3
7
2
5
9
8
1
8
8
9
0
0
0
1
0
8
3
0
9
8
7
0
0
0
0
0
0
0
0
0
1
0
8
2
0
1
6
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
8
1
2
0
7
9
5
7
1
7
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
7
0
8
1
0
8
2
1
8
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
2
0
7
1
0
8
2
1
9
0
0
0
0
0
0
1
8
9
5
1
1
8
2
0
0
0
0
0
0
0
0
0
0
0
0
0
1
5
6
4
2
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
2
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
2
0
7
2
2
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
2
3
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
2
4
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
2
5
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
2
6
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
2
7
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
2
8
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
2
0
7
1
2
0
7
0
0
0
0
0
0
2
9
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
2
0
7
1
9
4
6
1
2
0
7
0
0
0
0
0
40
Приложение 3
Код программы алгоритма нахождения матрицы корреспонденций
гравитационным методом.
source(’dat1’);
V=e. (-0.065*vrem_zat);
[m,n]=size(V);
s=(Q*V’)’;
for i=1:m
T1(i,:)=D(i).*Q.*V(i,:)/s(i);
endfor
while 1
S=sum(T1);
if max(abs(S-Q))<1e-10
save otvet_gr T1
break;
endif
for j=1:n
if S(j)>Q(j)
T2(:,j)=T1(:,j)*Q(j)/S(j);
elseif S(j)<=Q(j)
T2(:,j)=T1(:,j);
endif
endfor
Q1=D - sum(T1’)’;
R1=Q - sum(T1);
s=(R1*V’)’;
for i=1:m
T3(i,:)=T2(i,:)+Q1(i).*R1.*V(i,:)/s(i);
endfor T1=T3;
p+=1;
endwile
41
Код программы алгоритма нахождения матрицы корреспонденций
энтропийным методом.
source (’dat’);
T = e. (-vrem_zat);
[m,n]=size(T)
s=0;
while 1
k12 = ones(1,n);
for i=1:m
if D(i)!=0
k1(i,1)=sum(T(i,:))/D(i);
T1(i,:) = T(i,:)/k1(i);
elseif D(i) == 0
T1(i,:)=0;
endif
endfor
T=T1;
if max(max(abs(sum(T)-Q)))<1e-11
save otvet_entr T
break;
endif
for j=1:n
if Q(j)!=0
k2(1,j)=sum(T(:,j))/Q(j);
T2(:,j) = T(:,j)/k2(j);
elseif Q(j) == 0
T2(:,j) = 0;
endif
endfor
T=T2;
s+=1;
endwile
42
П
р
и
л
о
ж
е
н
и
е
4
Т
а
б
л
и
ц
а
4
:
М
а
т
р
и
ц
а
к
о
р
р
е
с
п
о
н
д
е
н
ц
и
й
в
с
е
г
м
е
н
т
(
8
,
8
)
1
2
3
4
5
6
7
8
9
1
0
1
1
1
2
1
3
1
4
1
5
1
6
1
7
1
8
1
9
2
0
2
1
2
2
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
2
1
4
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
3
0
7
4
1
1
9
2
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
4
0
0
1
1
1
7
2
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
5
0
0
1
0
3
9
5
4
4
6
2
0
0
0
0
0
0
0
0
0
0
0
0
0
0
6
0
8
1
3
6
5
0
1
9
1
2
7
9
4
2
0
0
0
0
0
0
0
0
0
0
0
0
0
7
0
3
5
2
6
8
4
8
3
1
6
3
1
6
1
0
1
1
0
0
0
0
0
0
0
0
0
0
0
0
8
0
2
3
5
8
7
5
1
2
6
4
8
6
4
3
9
5
5
3
9
1
3
3
4
1
1
6
0
0
0
0
0
0
0
0
9
0
3
1
1
1
1
8
0
1
4
7
8
0
1
7
4
7
3
6
1
9
0
4
6
1
2
8
1
4
0
5
6
0
0
0
0
0
0
1
0
0
3
2
8
7
9
6
1
3
3
7
5
2
4
1
2
0
4
7
6
4
7
6
6
8
1
8
1
5
2
0
0
0
0
1
1
2
0
4
3
9
6
6
5
1
4
1
5
2
3
8
1
0
1
6
5
2
2
6
3
7
1
1
0
0
1
0
0
0
1
2
0
6
1
1
4
5
6
4
4
1
0
0
4
1
4
8
7
0
0
0
0
6
8
0
0
3
8
0
0
0
1
3
0
7
9
6
1
9
7
9
1
2
2
2
9
6
1
0
0
0
0
0
0
0
0
0
4
2
3
0
0
1
4
0
4
5
9
4
0
2
0
0
0
4
8
4
0
0
0
0
0
0
0
2
2
0
0
1
5
0
6
1
0
1
0
0
0
0
0
7
0
4
0
0
0
0
0
0
0
1
0
0
0
1
6
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
1
7
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
8
0
1
8
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
2
1
9
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
1
3
2
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
8
2
4
3
2
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
3
3
4
2
2
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
2
3
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
2
4
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
2
5
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
2
6
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
2
7
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
3
6
0
0
0
2
8
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
3
0
0
0
0
0
0
2
9
0
0
0
0
0
0
0
0
0
0
0
0
0
0
2
3
0
0
0
0
0
0
43
П
р
и
л
о
ж
е
н
и
е
5
Т
а
б
л
и
ц
а
5
:
М
а
т
р
р
и
ц
а
к
о
р
р
е
с
п
о
н
д
е
н
ц
и
й
и
з
с
е
г
м
е
н
т
а
(
4
,
1
1
)
1
2
3
4
5
6
7
8
9
1
0
1
1
1
2
1
3
1
4
1
5
1
6
1
7
1
8
1
9
2
0
2
1
2
2
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
2
0
5
6
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
3
0
3
0
1
3
5
6
8
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
4
0
0
7
1
6
4
1
5
4
6
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
5
0
0
1
5
0
2
2
1
7
8
1
4
5
7
0
2
0
0
0
0
0
0
0
0
0
0
2
3
0
0
0
6
0
7
2
3
1
7
5
2
0
7
1
7
8
1
6
3
1
1
6
0
0
0
0
0
0
0
0
0
0
0
0
0
7
0
1
8
5
4
1
9
7
4
6
6
5
1
2
4
2
0
1
0
0
0
0
2
2
0
0
0
0
0
0
0
0
8
0
1
7
2
8
1
7
9
9
5
5
7
9
6
5
9
5
4
1
0
1
3
4
5
4
3
6
2
7
0
0
0
0
0
0
0
9
0
1
9
4
9
8
2
3
8
5
5
8
1
0
3
5
4
5
1
5
8
6
7
4
5
6
1
3
8
3
5
2
3
0
0
0
0
0
1
0
0
1
2
3
3
4
2
4
6
0
5
5
8
9
4
4
4
0
3
9
1
0
4
7
0
6
4
2
7
4
5
9
4
9
0
0
0
0
0
1
1
0
0
2
0
2
6
8
5
1
0
5
3
6
6
8
3
8
2
3
3
8
3
8
6
8
7
4
0
0
0
0
3
9
0
0
0
1
2
0
1
4
1
8
7
6
9
6
0
4
3
4
5
2
1
4
0
0
0
4
7
0
0
0
0
0
3
3
0
0
0
1
3
0
1
5
2
0
1
4
6
4
5
3
3
6
0
3
7
2
3
0
0
0
0
1
8
0
0
3
3
3
3
2
7
0
0
1
4
0
2
1
1
9
2
2
6
5
4
8
0
0
2
2
2
4
0
0
0
0
0
0
0
0
0
3
4
2
5
0
1
5
0
1
5
1
7
2
8
4
1
0
0
0
2
3
0
2
7
0
0
0
0
0
0
0
0
0
2
8
0
1
6
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
3
3
1
2
6
1
7
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
4
5
2
9
1
8
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
3
2
2
9
1
9
0
0
0
0
0
0
4
2
2
5
0
0
0
0
0
0
0
0
0
0
0
0
0
4
3
2
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
2
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
3
3
2
2
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
2
3
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
2
4
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
2
5
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
2
6
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
2
7
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
2
8
0
0
0
0
0
0
0
0
0
0
0
0
0
0
3
5
3
1
0
0
0
0
0
0
2
9
0
0
0
0
0
0
0
0
0
0
0
0
0
0
3
5
5
1
3
3
0
0
0
0
0
44
Информация о работе Построение матрицы корреспонденций для транспортной сети г.Владивостока