Разработка имитационной модели транспортной сети
МИНИСТЕРСТВО ОБРАЗОВАНИЯ РЕСПУБЛИКИ БЕЛАРУСЬ
Учреждение образования "Гомельский государственный университет имени Франциска Скорины"
Математический факультет
Кафедра МПУ
Разработка имитационной модели транспортной сети
Курсовая работа
Исполнитель
студентка группы ПМ-44
Бутакова О.В.
Научный руководитель
доцент кафедры МПУ Сукач Е.И.
Гомель 2007
Содержание
Введение
1. Имитационное моделирование для рациональной организации транспортных потоков
1.1 Актуальность использования имитационной модели для исследования потоков в железнодорожной сети
1.2 Описание модели железнодорожной сети
1.3 Алгоритм Форда-Фалкерсона для нахождения максимального потока в сети
1.4 Метод Монте-Карло
2. Имитационная моделЬ железнодорожной сети
2.1 Формализация модели железнодорожной сети
2.2 Алгоритм работы модели железнодорожной сети
2.3 Решение тестовых задач с помощью имитационной модели
Заключение
Список использованных источников
Приложение
Листинг программы
Введение
По причине увеличения транспортных потоков в железнодорожной сети актуальной является проблема их рациональной организации. Однако с учетом влияния различных факторов, таких как загруженность участка дороги, состояния дороги, наличия внутренних потоков, данная задача не может быть решена с помощью аналитических моделей, основанных на графовых моделях.
Поэтому актуальна разработка компьютерных моделей, позволяющих учесть все перечисленные случайные факторы, и рационально организовать потоки в железнодорожной сети.
Для реализации курсовой работы необходимо решить следующие частные задачи:
актуальность использования имитационной модели для исследования потоков транспортной сети;
составление списков входных и выходных параметров имитационной модели железнодорожной транспортной сети;
разработка и реализация алгоритма имитационной модели;
решение тестовых задач с помощью имитационной.
В первой главе представлены: теоретический материал для разработки имитационной модели железнодорожной сети, ее актуальность, алгоритм Форда-Фалкерсона, метод Монте-Карло.
Во второй главе представлены формализация имитационной модель, описание водных и выходных значений, блок-схема алгоритма, тестирование модели и в приложении листинг программы.
1. Имитационное моделирование для рациональной организации транспортных потоков
1.1 Актуальность использования имитационной модели для исследования потоков в железнодорожной сети
В наше время за счёт резкого увеличения числа транспортных средств в сетях дорог существенно возросли требования к рациональной организации транспортных потоков. Сама сеть дорог может быть представлена в виде графа, состоящего из узлов и дуг. Каждое ребро графа, соответствующее участку дороги, характеризуется длиной, пропускной способностью и стоимостью проезда по нему единицы транспортного средства. На пропускную способность ветви графа влияет скорость передвижения единицы транспорта, которая в свою очередь зависит от многих факторов, среди которых наиболее важными являются загруженность участков пути, состояние дорожного покрытия, условия внешней среды. Загруженность на различных участках дороги бывает различной и зависит от наличия внутренних транспортных потоков на данном участке, которые могут рассматриваться как помехи при передвижении транспортной единицы из начального пункта сети в конечный пункт. Состояние дороги определяется её изношенностью, условиями эксплуатации, влиянием погодных условий. Параметры внешней среды изменяются в зависимости от времени года, времени суток и подвержены влиянию погодных воздействий. Значения факторов, определяющих рациональную организацию транспортных потоков в сети, изменяются во времени. Наличие внутренних транспортных потоков на каждом участке сети носит вероятностный характер. Отдельные участки транспортной сети изменяют своё состояние (изнашиваются) с разной интенсивностью. Параметры внешней среды периодически изменяются. При управлении следует учитывать, что в реальной транспортной сети перечисленные факторы являются взаимосвязанными.
При управлении потоками в транспортной сети, как правило, находят оптимальное распределение транспортного потока по ветвям сети, оценивают максимальный поток в сети и находят кратчайший путь между заданными входом и выходом, выявляют узкие места в сети с целью их своевременной ликвидации. Одновременно с этими задачами оценивают суммарные затраты транспортных средств при их движении из начального пункта в конечный.
Наличие случайных факторов, влияющих на состояние транспортной сети, не позволяет решать перечисленные задачи с использованием известного аппарата, основанного на аналитических моделях, называемых графовыми моделями. Особенно большие трудности у исследователей вызывает определение узких мест в сети при наличии транспортных потоков относящихся к различным направлениям и вероятностных внутренних потоков на отдельных участках сети, которые могут приводить к увеличению числа аварий и возникновению “пробок".
Исходя из выше изложенного, в качестве выхода из положения исследователи вынуждены прибегать к имитационному моделированию транспортных потоков в сети дорог с учетом случайных факторов.
1.2 Описание модели железнодорожной сети
Структуру транспортных потоков в железнодорожной сети можно представить в виде графа Gh, где h-вариант организации транспортных потоков в железнодорожной сети. Перевозки в сети реализуются в соответствии со следующими параметрами, определяемыми матрицами:
;
;
;
,
(1. 1)
где c>ij>>
>- пропускные способности ветвей
графа G>h>,
соединяющих узел i с
узлом j; l>ij>
- расстояния между узлами i
и j;
- начальный поток по ветви ij;
q>ij>
- стоимость единицы пути движения
транспортного средства по ветви ij.
Определёно множество входов в сеть
,
и множество выходов из сети
,
в одном направлении. В сети кроме
транзитных потоков существуют внутренние
транспортные потоки на отдельных
отрезках дороги в одну и другую сторону,
которые снижают пропускные способности
ветвей графа G>h>.
Величины внутренних транспортных
потоков для ij-ых
участков определяются функциями
распределения
.
Пропускные способности ветвей ij
графа G>h>
с учётом внутренних потоков изменяются
и представляют собой случайные величины,
определяемые с помощью функций
распределения
.
В каждом узле железнодорожной сети
происходят процессы формирования-расформирования
составов. Длительность этих процессов,
как правило, носит вероятностный характер
и описывается функциями распределения.
Функции распределения для каждого i-ого
узла сети задаются матрицей
,
где каждый элемент матрицы есть
функция распределения времени на
формирование-расформирование в i-ом
узле для состава, пришедшего с узла k
и следующего в узел j.
Матрица имеет вид:
где w- общее количество входящих-исходящих дуг для узла i. Время на формирование-расформирование составов местного назначения принимается равным нулю.
Максимальный поток между узлами распределяется по ветвям сети, где k-номер итерации алгоритма Форда-Фалкерсона при определении максимального значения потока. Показатель затрат движения транспортных средств вдоль ветви ij графа G>h> может быть задан одной из функций:
,
(1.2)
где
весовые коэффициенты важности
соответственно расстояния (
),
времени (
),
стоимости (
)
движения по ветвям сети. Величина
есть среднее значение времени, затраченное
транзитными составами на
формирование-расформирование в i-ом
узле. Оно определяется по формуле:
,
(1.3)
где
- значение времени на формирование-расформирование,
полученное по функции распределения
.
Поскольку при движении транспортных
средств по сети G>h>
необходимо стремиться к минимизации
этих затрат, то в качестве показателя
“выгоды" максимального потока берётся
общая характеристика затрат, которая
вычисляется по матрице распределений
максимального потока по всем ветвям ij
графа G>h>:
(1.4)
Таким образом, формула (1.4) определяет величину затрат при перемещении транспортного средства в сети G>h> в условиях максимального потока. С одной стороны поток необходимо максимизировать, а с другой стороны показатель “выгоды" должен быть минимальным.
Наличие внутренних транспортных потоков в G>h> обусловливает вероятностный характер пропускных способностей на многих ветвях графа G>h>. Недетерминированное время формирования и расформирования составов влияет случайным образом на время передвижения транзитных составов из пункта отправления в пункт назначения по пути, содержащим этот узел. Указанные особенности не позволяют использовать для поиска максимального потока в сети алгоритм Форда-Фалкерсона. Поэтому актуально использование имитационной модели, основанной на сочетании процедуры Монте-Карло и теоремы Форда-Фалкерсона. Таким образом, ставятся задачи определения с помощью имитационной модели максимального потока в заданном направлении между множеством узлов входов в сеть и множеством узлов выходов, а так же поиска узких мест в сети G>h> при перемещении транспорта в заданном направлении, устранение которых позволит достичь оптимальной организации потоков в сети. При поиске интегрального максимального потока в сети необходимо выполнение следующих условий: для каждого сочетания входа и выхода имеется максимальный поток, интегральная функция затрат имеет минимальное значение.
1.3 Алгоритм Форда-Фалкерсона для нахождения максимального потока в сети
Алгоритм решения задач нахождения
максимального потока в железнодорожной
сети основан на теореме Форда-Фалкерсона:
в любой транспортной сети максимальный
поток равен минимальной пропускной
способности. Если поток максимален, то
найдется такое сечение, пропускная
способность которого равна мощности
потока. Доказывается эта теорема
применением алгоритма Форд-Фалкерсона.
Согласно этому алгоритму, начиная с
некоторого начального неполного потока,
по итеративному алгоритму можно получить
полный поток, если прибавлять к различным
значениям потоков
пути
минимальное из чисел
,
которые вычислены по этому пути. После
такой операции путь
уже будет содержать хотя бы одну
ненасыщенную дугу. Если таким же образом
поступить с другими путями
,
то, в конце концов, получим полный поток.
Поэтому алгоритм определения максимального
потока состоит из следующих шагов:
Строим начальный поток
;
проверяем, попал ли узел
в множество узлов
,
которые достижимы по ненасыщенным
ребрам из
.
Если узел
не попал, то считают, что построенный
поток максимален, и алгоритм расчета
останавливается;
если узел
попал во множество
,
то выделяют путь
,
состоящий из ненасыщенных ребер и
ведущий грузы из
в
;
увеличивают поток через каждое ребро
этого пути на величину
;
строят новый поток
и переходят к шагу 2.
Обычно сеть задается матрицей пропускной
способностей
всех ребер сети
.
Задавая
,
затем вычисляют на k-м
шаге матрицу значений потоков на дугах
.
Строят матрицу разностей
.
В этой матрице насыщенным ребрам при
потоке
будут соответствовать нулевые элементы,
ненасыщенным - ненулевые элементы.
Поэтому вычисление матрицы
достаточно как для построения множества
узлов по которым вещество из
достигает по ненасыщенным ребрам до
,
так и для построения последовательности
ненасыщенных ребер.
Технология составления этих списков следующая:
сначала составляют список узлов, в каждый из которых ведет ненасыщенное ребро из вершины i;
далее для каждого i-го узла составляют свой список узлов, в каждый из которых из i-го узла ведет ненасыщенное ребро (за исключением тех узлов, которые уже вошли в ранее составленные списки) и так далее.
Этот процесс выписывания списков
заканчивается в двух случаев. Либо
появиться узел
,
что означает продолжение работы
алгоритма, либо в список выписанных
узлов не попал узел
,
что означает конец расчетов.
1.4 Метод Монте-Карло
Пусть требуется разыграть дискретную случайную величину X, т. е получить последовательность её возможных значений x>i>, зная закон распределения X:
|
X |
x>1> |
x>2> |
… |
x>n> |
|
p |
p>1> |
p>2> |
… |
p>n> |
Рисунок 1.1 - Распределение случайной величины X
Обозначим через R непрерывную
случайную величину, распределённую
равномерно в интервале (0,1), а через r>j>,
- её возможные значения, т.е. случайные
числа.
Разобьём интервал 0 R <1 на оси Оr точками с координатами p>1>, p>1>+ p>2, >p>1>+ p>2>+ p>3,...>, p>1 >+ p>2> +…+ p>n>>-1> на n частичных интервалов ∆>1>, ∆>2,...>,> >∆>n>>, >длины которых p>1,> p>2>,…, p>n>> >соответственно. Таким образом, |∆>i>|= p>i>> (>1), где i=1, 2, …,n.
Теорема: если каждому случайному числу r>j> (0 r>j> <1), которое попало в интервал ∆>i,> ставить в соответствие возможное значение x>i>>,> то разыгрываемая величина будет иметь заданный закон распределения:
Так как при попадании случайного числа r>j>> >в частичный интервал ∆>i >разыгрываемая величина принимает возможное значение x>i>>,> а таких интервалов всего n, то разыгрываемая величина имеет те же возможные значения, что и X, а именно x>1,> x>2,...>, x>n>. Вероятность попадания случайной величины R в интервал ∆>i >равна его длине, а в силу |∆>i>|= p>i>, получим, что вероятность попадания R в интервал ∆>i >равна p>i>>. >Следовательно, вероятность того, что разыгрываемая величина примет возможное значение x>i>>, >также равна p>i>. Таким образом разыгрываемая величина имеет заданный закон распределения как показано на рисунке 1.1
Правило: для того чтобы разыграть дискретную случайную величину, заданную законом распределения (2) нужно:
1) разбить интервал (0;
2) оси на Or на n частичных интервалов:
∆>1 >= (0; p>1>), ∆>2>= (p>1>; p>1> +p>2>),...,> >∆>n>= (p>1> +p>2> +…+p>n>>-1>;
3) выбрать случайное число r>j>> (>например, из таблицы случайных чисел). Если r>j>> >попало в частичный интервал ∆>i>>,> то разыгрываемая случайная величина приняла возможное значение x>i>>.>
2. Имитационная моделЬ железнодорожной сети
2.1 Формализация модели железнодорожной сети
Рассмотрим железнодорожную сеть:
Рисунок 2.1.1 - Граф железнодорожной сети
Узлы - это города, через которые проходит сеть дорог. Дуги - это участки пути, соединяющие соответствующие города. Каждая дуга имеет свою пропускную способность. В сети кроме транзитных потоков существуют внутренние транспортные потоки, которые значительно снижают пропускную способность участка сети дорог. В каждом узле происходят процессы формирования и расформирования составов.
Пусть имеется один узел отправления и один узел назначения. Требуется определить с учётом структуры сети и имеющихся параметров максимальный поток в сети с минимальными затратами всех ресурсов. Таким образом, ставится задача определения с помощью имитационной модели максимального потока между начальным и конечным узлом графа, поиск узких мест в сети, устранение которых позволит достичь оптимальной организации потоков в железнодорожной сети.
Эта задача решается следующим образом. Для получения усредненных характеристик максимального потока и его “выгоды" необходимо провести N прогонов.
На первой итерации применения процедуры Монте-Карло вероятностная задача поиска максимального потока в сети превращается в классическую. При этом определяются компоненты матрицы пропускных способностей путём вычисления c>ijl>=c>ij>-v>ijl>, где v>ijl> определяется по функции распределения H>ij> (v) путём нахождения единичного жребия третьего типа.
При учёте влияния внутренних потоков на пропускные ситуации в сети возможны следующие ситуации:
внутренних потоков нет на участке дороги;
внутренние потоки влияют на пропускную
способность участка таким образом, что
она уменьшается, но остаётся больше
либо равна значению потока на этом
участке, т.е.
,
где
- пропускная способность сети изменённая
с учётом внутренних потоков (при этом
алгоритм Форда-Фалкерсона работает и
находится максимальный поток и его
распределение по ветвям сети);
внутренние потоки влияют на пропускную
способность участка таким образом, что
она уменьшается и становится меньше
значения потока на этом участке, т.е.
,
где
- пропускная способность сети изменённая
с учётом внутренних потоков (в этих
условиях алгоритм Форда Фалкерсона не
работает и данная ситуация говорит о
возникновении “пробки" в сети на
этом участке).
Для каждого i-го узла сети
с учётом заданных функций распределения
времён формирования-расформирования
вычисляется среднее время нахождения
в i-ом узле транспортной
единицы. В качестве начального потока
выбираются значения матрицы
.
На k-ой итерации (k - номер итерации в алгоритме Форда-Фалкерсона) с помощью алгоритма Форда-Фалкерсона, используя изменённую матрицу пропускных способностей определяется само распределение потока по сети и его значение потока. По формулам (1.2), (1.3), и (1.4) с учётом распределения потоков, определяется обобщённый показатель “выгоды" этого потока. Значения потока, матрица значений распределения потока по ветвям и показатель “выгоды" запоминаются в базе данных модели (БДМ). Модифицируется номер итерации процедуры Монте-Карло (l=l+1) и все расчёты повторяются сначала.
По завершении N итераций этих расчётов в БДМ модели сформированы следующие выборки: выборка матриц распределения потока по ветвям сети, то есть для каждого элемента матрицы распределений потока имеется своя выборка; выборка значений максимального потока; выборка интегральных показателей “выгоды" потока.
По этим выборкам объема N формируются средние значения, а именно:
;
;
Все эти значения должны быть вычислены и представлены пользователю по завершении работы программы.
Для поиска узких мест в G>h> с начальным пунктом Z и конечным пунктом Y проведём покомпонентное вычитание из этой матрицы соответствующих значений матрицы пропускных способностей С>h>>::>
В тех местах, где элементы этой матрицы будет иметь отрицательное значение, находятся “узкие места" в G>h>. На величину этой разности пропускные способности с>ij> должны быть увеличены для того, чтобы граф G>h> обеспечивал максимальный поток транзитных маршрутов в направлении из точки Z в точку Y.
Таким образом, по завершении работы программы, также должны быть получены следующие значения: матрица, характеризующая узкие места в сети, и рекомендуемая матрица пропускной способности для данной сети дорог.
Алгоритм работы модели основан на сочетании процедуры Монте-Карло и теоремы Форда-Фалкерсона и применением единичного жребия третьего типа.
2.2 Алгоритм работы модели железнодорожной сети
Алгоритм работы модели железнодорожной сети представлен на рисунке 2.2 Для работы программного обеспечения необходимо задать следующие входные значения:
- матрица пропускной способности сети;
- матрица расстояния между узлами;
- матрица стоимости единицы пути;
- функция распределения времени на
формирование и расформирование составов;
- вектор времени на формирование и
расформирование составов;
- количество прогонов программы.
Рассмотрим работу модели на первом прогоне (i=1). Программное обеспечение учитывает, что в сети кроме транзитных потоков существуют внутренние транспортные потоки. Эти внутренние потоки влияют на пропускную способность сети. Таким образом, на каждом прогоне изменяется матрица пропускных способностей c [i,j] путем разыгрывания единичного жребия третьего типа.
С помощью алгоритма Форда-Фалкерсона вычисляется максимальный поток maxpotok, распределение потока в сети f [i,j], и по формулам (1.2), (1.3) и (1.4) определяется обобщённый показатель “выгоды" этого потока Ф>zy>. Все эти значения запоминаются в базе данных ЭВМ.
Если i<=pr, то программа продолжает первоначальные вычисления. В противном случае (если i>pr) вычисляется следующие средние значения: максимальный поток maxpotok, распределение потоков f [i,j] и обобщённый показатель “выгоды" Ф>zy>> >на каждом прогоне. Далее определяются узкие места в сети. Для этого вычисляются значения: f>ср> [i,j] -c [i,j] и в тех местах, где матрица принимает отрицательные значения на величину этой разницы увеличиваются пропускные способности матрицы c [i,j] для обеспечения рациональной организации потоков железнодорожной сети.
После завершения работы программы новая матрица пропускных способностей c [i,j], будет обеспечивать максимальный поток транзитных маршрутов в железнодорожной сети в направлении из начального пункта в конечный.
Рисунок 2.2 - Блок-схема реализованного программного обеспечения
2.3 Решение тестовых задач с помощью имитационной модели
Модель железнодорожной транспортной сети, представленная в данной курсовой работе, предоставляет следующие возможности:
поиск максимального потока и усредненного потока в сети железнодорожных дорог различным количеством узлов (N<100);
поиск узких мест и оптимальная организация потоков в сети дорог.
Интерфейс реализован на языке Borland Delphi 7.0. На рисунке 2.3 представлен интерфейс программного обеспечения.
Рисунок 2.3 - Интерфейс программного обеспечения
Рассмотрим функционирование модели на следующем примере. Для работы программы можно использовать либо данные, которые представлены в файле 11. txt, либо ввести свои необходимые значения которые в дальнейшем можно сохранить в txt-файле. Данные вводятся при запуске программы.
При задании произвольных значений входных данных пользователь должен учитывать, что если задать стоимость единицы пути либо дину дуги, не существующей дороги, то программа выдаст предупреждение о неправильном вводе начальных данных.
Файл 11. txt содержит следующие значения:
Матрица пропускной способности:
Вектор вероятности:
Время задержки транспорта:
Матрица стоимости пути единицы пути:
Матрица длины дороги:
Коэффициенты важности:
Количество прогонов: 10
Если необходимо создать текстовый файл с новыми данными, то нужно прописать необходимые значения и нажать на кнопку “Запись в файл". Эти значения записываются txt-файл и при дальнейшей работе с ними нужно нажать на кнопку “Чтение из файла". На рисунке 2.4 представлен пример заполнения входных значений. Когда все значения заполнены, нажимаем на кнопку “Вычислить". При этом появляется форма, указанная на рисунке 2.5
Рисунок 2.4- Пример ввода данных.
Таким образом, на форме представлены следующие результаты работы программы: матрица размером 2х10, в первом столбце которой представлены значения максимальных потоков на каждом прогоне, во втором - значения обобщенных показателей “выгоды"; среднее значение показателей выгоды и максимальных потоков, полученных на каждом прогоне; матрица усредненного потока.
Рисунок 2.5- Полученный результат
Для просмотра полученной матрицы пропускных способностей необходимо нажать на кнопку “Жми сюда”. Появляется форма, которая указана на рисунке 2.6
Таким образом при выполнении программы с начальными данными, расположенными в текстовом файле 11. txt мы получим следующие результаты:
Матрица усредненного потока всей сети:
Среднее значение выгоды: 0,82
Среднее значение потока: 7
Новая пропускная способность:
Полученная новая матрица пропускных способностей, будет обеспечивать максимальный поток транзитных маршрутов в железнодорожной сети в направлении из начального пункта в конечный для данной сети дорог.
Рисунок 2.6- Рекомендуемая пропускная способность
Заключение
В ходе реализации курсовой работы были выполнены все поставленные задачи и разработана имитационная модель транспортной сети с учетом одного входа и одного выхода в сети.
Таким образом, были решены следующие частные задачи:
актуальность использования имитационной модели для исследования потоков транспортной сети;
составление списков входных и выходных параметров имитационной модели железнодорожной транспортной сети;
разработка и реализация алгоритма имитационной модели;
решение тестовых задач с помощью имитационной.
Таким образом, был разобран материал по данной курсовой работе и выявлена актуальность разработки имитационной модели транспортной сети и выполнено программное обеспечение, реализующее работу модели железнодорожной сети. Данная модель разработана для случая одного входа и одного выход в сеть и нуждается в дополнительной модификации программы, что будет выполнено в следующей курсовой работе.
Список использованных источников
Максимей И.В. Имитационное моделирование на ЭВМ. - М.: Радио и связь, 1988. - 232 с.
Технология системного моделирования / Под общ. ред. С.В. Емельянова. - М.: Машиностроение; Берлин: Техник, 1988. - 520 с.
Задачи и модели ИСО. Ч.3. Технология имитации на ЭВМ и принятие решений: Уч. пособие / И.В. Максимей, В.Д. Левчук, С.П. Жогаль, В.Н. Подобедов. - Гомель: БелГУТ, 1999. - 150 с.
Левчук В.Д. Базовая схема формализации системы моделирования MICIC4 // Проблемы программирования. - 2005. - № 1. - С.85-96.
Приложение
Листинг программы
unit Unit1;
interface
uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, Grids, StdCtrls, ExtCtrls, jpeg;
type
TForm1 = class (TForm)
GroupBox1: TGroupBox;
Panel1: TPanel;
Panel2: TPanel;
VertexPrompt: TLabel;
VertexCount: TEdit;
Button1: TButton;
Button2: TButton;
Capofedge: TStringGrid;
GroupBox3: TGroupBox;
StringGrid1: TStringGrid;
GroupBox4: TGroupBox;
StringGrid2: TStringGrid;
Edit1: TEdit;
Button3: TButton;
Memo1: TMemo;
Button4: TButton;
OpenDialog1: TOpenDialog;
SaveDialog1: TSaveDialog;
Label1: TLabel;
StringGrid3: TStringGrid;
GroupBox5: TGroupBox;
Label2: TLabel;
Edit2: TEdit;
StringGrid4: TStringGrid;
StringGrid5: TStringGrid;
Label3: TLabel;
Label4: TLabel;
Edit3: TEdit;
Label5: TLabel;
Label6: TLabel;
Label7: TLabel;
Edit4: TEdit;
Label8: TLabel;
Edit5: TEdit;
Label9: TLabel;
Panel3: TPanel;
Image1: TImage;
Label10: TLabel;
Label11: TLabel;
Label12: TLabel;
Edit6: TEdit;
Label13: TLabel;
Edit7: TEdit;
Label14: TLabel;
Label15: TLabel;
Label16: TLabel;
Button5: TButton;
Label17: TLabel;
procedure Button2Click (Sender: TObject);
procedure Button1Click (Sender: TObject);
procedure VertexCountChange (Sender: TObject);
procedure Button3Click (Sender: TObject);
procedure Button4Click (Sender: TObject);
procedure Edit2Change (Sender: TObject);
procedure Button5Click (Sender: TObject);
private
{ Private declarations }
public
{ Public declarations }
end;
Const
N1=100;
l=MAXINT;
var
Form1: TForm1;
n: integer;
kol2,op,rr,nn,mi,tool,kon: integer;
j1,l6,w, i,z,j,ko,H2,H3,sum,ss,maxpotok,j3,k3,kk,potok,o,ll,kol1,pp,p1,j2,kol,t: integer;
c: array [1. N1,1. N1] of integer;
c1: array [1. N1,1. N1] of real;
c2: array [1. N1,1. N1] of real;
tt: array [1. .50,1. .50] of real;
fij: array [1. .50,1. .50] of real;
yij: array [1. .50,1. .50] of real;
y1i: array [1. .50,1. .50] of real;
xij: array [1. .10,1. .50] of real;
fij1: array [1.20,1.20] of real;
ttt: array [1.20,1.20] of real;
dij: array [1.20] of real;
Fi: array [1.20] of real;
lhh: array [1.20,1.20] of real;
hij: array [1.20] of real;
hi: array [1.20] of integer;
potokvr: array [1.20] of integer;
d11,d22,d33,z1,l5,mm,ten,w1,t1,kol3,lop,bpp,loop,ten1,bred1,bred2: real;
lh: array [1. N1,1. N1] of integer;
qh: array [1. N1,1. N1] of integer;
f: array [1. N1,1. N1] of integer;
const
size = N1 + 2;
type
queue = record
a: array [0. size-1] of integer;
head, tail: integer;
end;
var
p: array [1. N1] of integer; // номер предыдущей вершины
v: array [1. N1] of boolean; // посещенность
q: queue;
implementation
{$R *. dfm}
procedure init_queue (var q: queue); // инициализировать очередь
begin
with q do
begin
tail: = 0;
head: = 0;
end;
end;
function is_queue_empty (const q: queue): boolean; // Проверка пустоты
begin
is_queue_empty: = q. tail = q. head;
end;
procedure push (var q: queue; x: integer); // Положить элемент в очередь
begin
with q do
begin
a [tail]: = x;
tail: = (tail + 1) mod size;
end;
end;
function pop (var q: queue): integer; // Достать из очереди
begin
with q do
begin
pop: = a [head] ;
head: = (head + 1) mod size;
end;
end;
// Метод Форда-Фалкерсона
function mff (xo, xn: integer): boolean;
var
i, j: integer;
begin
fillchar (v, sizeof (v), false); { обнуляем массив посещений }
init_queue (q); { инициализируем очередь }
push (q, xo); { заталкиваем в очередь исток }
v [xo]: = true; { посетили исток }
p [xo]: = - 1; { у истока нет предка }
while not is_queue_empty (q) do { пока очередь не пуста }
begin
i: = pop (q); { достаем вершину из очереди }
for j: = 1 to n do { перебираем все вершины }
if not v [j] and { вершина не посещена }
(c [i, j] -f [i, j] > 0) then { ребро i->j ненасыщенное }
begin
v [j]: = true; { посетили вершину j }
push (q, j); { положили веришину j в очередь }
p [j]: = i; { i предок j }
end;
end;
mff: = v [xn] ; { дошли ли до стока }
end;
{ min: минимум из двух вещественных чисел }
function min (a, b: integer): integer;
begin
if a > b then min: = b else min: = a;
end;
// максимальное значение потока }
procedure maxpotok1 (xo, xn: integer);
var
k: integer;
d,d1,potok: integer;
begin
kk: =0;
repeat
begin
if c [1,j3] <>0 then
begin
kk: =kk+1;
j3: =j3+1;
end
else j3: =j3+1;
end;
until j3>n;
fillchar (f, sizeof (f), 0); // обнуляем gjnjr
potok: = 0;
while mff (xo, xn) do // Пока существует путь от xo в xn}
begin
d: = l;
d1: = l; // ребро в этом пути с минимальной
k: = xn; // пропускной способностью
while k <> xo do
begin
d: = min (d,c [p [k], k] -f [p [k], k]);
d1: = min (d1,c [p [k], k] -f [p [k], k]);
k: = p [k] ;
end;
k: = xn; // идем по найденому пути от xo к xn
while k <> xo do
begin
f [p [k], k]: = f [p [k], k] + d; // увеличиваем по прямым ребрам
f [k, p [k]]: = f [k, p [k]] - d; // уменьшаем по обратным ребрам
k: = p [k] ;
end;
j3: =1;
potok: = potok + d1;
// увеличиваем поток
if k3<>kk then k3: =k3+1 else
begin
i: =1; j2: =1;
for j1: =1+t to n+t do
begin
for j: =1 to n do
begin
tt [j1,j2]: =f [i,j] ;
if j2<=n then j2: =j2+1;
if j2>n then j2: =1;
end;
if i<n then i: =i+1; end;
t: =t+n;
potokvr [z]: =potok;
z: =z+1;
// строим lhh
kol2: =0;
for i: =1 to n do
for j: =1 to n do
kol2: =kol2+lh [i,j] ;
for i: =1 to n do
for j: =1 to n do
lhh [i,j]: =lh [i,j] /kol2;
// построили матрицу lhh
// дополнительная часть программы
{razigrivaem}
p1: =1;
for i: =1 to n do
begin
sum: =0;
ko: =0; t1: =0;
for j: =1 to n do
if f [i,j] >0 then
begin
w1: =Random;
for w: =1 to ll do
begin
if w1<hij [w] +t1 then begin
ss: =f [i,j] *hi [w] ;
sum: =sum+ss;
ko: =ko+f [i,j] ;
break;
end
else t1: =hij [w] +t1;
end;
end; if ko=0 then ko: =1;
dij [p1]: =sum/ko; p1: =p1+1;
end;
for i: =1 to n do
for j: =1 to n do
begin
yij [i,j]: =d11*lhh [i,j] ;
fij1 [i,j]: =0;
end;
{umnozit matr na vek}
i: =0;
while op<=n do
begin
rr: =1;
i: =i+1;
while rr<=n do
begin
mm: =0;
for j: =1 to n do mm: =mm+qh [i,j] *lh [j,rr] ;
ttt [op,rr]: =mm; rr: =rr+1;
end;
op: =op+1;
end;
lop: =0;
for i: =1 to n do
for j: =1 to n do
lop: =lop+ttt [i,j] ;
for i: =1 to n do
for j: =1 to n do
ttt [i,j]: =d33* (ttt [i,j] /lop);
for i: =1 to n do
for j: =1 to n do
if f [i,j] >0 then begin
fij1 [i,j]: =lh [i,j] /f [i,j] +dij [i] ;
kol3: =kol3+fij1 [i,j] ;
end;
for i: =1 to n do
for j: =1 to n do
begin
fij1 [i,j]: = (fij1 [i,j] /kol3) *d22;
end;
{vischitivaem vse fij*}
for i: =1 to n do
for j: =1 to n do
begin
fij [i,j]: =ttt [i,j] +fij1 [i,j] +yij [i,j] ;
end;
{nahodim F=sumfij*}
lop: =0;
for i: =1 to n do
for j: =1 to n do
lop: =lop+fij [i,j] ;
Fi [mi]: =lop;
mi: =mi+1;
// конец дополнительной части
end; end;
maxpotok: =potok; // возвращаем максимальный поток
end;
procedure TForm1. Button2Click (Sender: TObject);
begin
Form1. Close;
end;
procedure TForm1. Button1Click (Sender: TObject);
var i,j,fcost: integer;
begin
Label10. Visible: =false;
Label11. Visible: =true;
Label12. Visible: =true;
Edit6. Visible: =true;
Label13. Visible: =true; Label14. Visible: =false;
Label15. Visible: =true;
Label17. Visible: =true; Button5. Visible: =true;
Edit7. Visible: =true;
Panel3. Visible: =true;
Image1. Visible: =true;
d11: =strtofloat (Edit3. text);
d22: =strtofloat (Edit4. text);
d33: =strtofloat (Edit5. text);
GroupBox3. Visible: =false;
Label1. Visible: =true;
Edit1. Visible: =true;
n: =strtoint (VertexCount. text);
ll: =strtoint (Edit2. text);
for i: =1 to n do
for j: =1 to n do begin
c [j, i]: =StrToInt (CapOfEdge. Cells [i,j]);
end;
for i: =1 to n do
for j: =1 to n do begin
qh [j, i]: =StrToInt (StringGrid3. Cells [i,j]);
end;
for i: =1 to n do
for j: =1 to n do begin
lh [j, i]: =StrToInt (StringGrid1. Cells [i,j]);
end;
for i: =1 to ll do
hij [i]: =StrToFloat (StringGrid4. Cells [i-1,0]);
for i: =1 to ll do
hi [i]: =StrToInt (StringGrid5. Cells [i-1,0]);
maxpotok1 (1,n);
// ср. поток
for i: =1 to mi-1 do
ten: =ten+potokvr [i] ;
ten1: =trunc (ten/ (mi-1));
// ср. выгода
for i: =1 to mi-1 do
loop: =loop+Fi [i] ;
loop: =loop/ (mi-1);
// матрица всех потоков
j1: =0; j2: =0;
for i: =1 to t do
begin
j: =1; j2: =j2+1; j3: =1;
while j<=n do
begin
bpp: =0;
for H2: =0 to mi do
bpp: =bpp+tt [i+n*H2,j] ;
yij [j2,j3]: =bpp/ (mi-1);
j3: =j3+1; j: =j+1;
end; end;
// усредненная матрица всех потоков
for i: =1 to n do
for j: =1 to n do
begin
y1i [i,j]: =round (yij [i,j]);
end;
i: =1; bred1: =0;
begin
for j: =1 to n do
bred1: =bred1+y1i [i,j] ;
if bred1>ten1 then begin
j: =1;
while j<=n do
begin
if (yij [i,j] -trunc (yij [i,j]) >=0.5) and (yij [i,j] -trunc (yij [i,j]) <1)
then begin y1i [i,j]: =y1i [i,j] -1; break; end
else j: =j+1; end;
end;
if bred1<ten1 then begin j: =1;
while j<=n do
begin
if (yij [i,j] -trunc (yij [i,j]) >=0.5) and (yij [i,j] -trunc (yij [i,j]) <1)
then begin y1i [i,j]: =y1i [i,j] +1; break; end
else j: =j+1
end; end;
for j: =1 to n do
y1i [j, i]: =-1*y1i [i,j] ;
end;
i: =n; bred1: =0;
begin
for j: =1 to n do
bred1: =bred1+y1i [i,j] ;
bred1: =-1*bred1;
if bred1>ten1 then begin
j: =1;
while j<=n do
begin
if (yij [i,j] -trunc (yij [i,j]) >=0.5) and (yij [i,j] -trunc (yij [i,j]) <1)
then begin y1i [i,j]: =y1i [i,j] +1; break; end
else j: =j+1;
end; end;
if bred1<ten1 then begin j: =1;
while j<=n do
begin
if (yij [i,j] -trunc (yij [i,j]) >=0.5) and (yij [i,j] -trunc (yij [i,j]) <1)
then begin y1i [i,j]: =y1i [i,j] -1; break; end
else j: =j+1
end; end;
for j: =1 to n do
y1i [j, i]: =-1*y1i [i,j] ;
end;
kon: =0;
while kon<=n-1 do
begin
bred2: =0;
i: =2+kon;
for j: =1 to n do
bred2: =bred2+y1i [i,j] ;
begin
if bred2>0 then begin j: =2+kon;
while j<=n-1 do
begin
if (yij [i,j] -trunc (yij [i,j]) >=0.5) and (yij [i,j] -trunc (yij [i,j]) <1)
then begin y1i [i,j]: =y1i [i,j] -1; break; end
else j: =j+1
end; end;
if bred2<0 then begin j: =2+kon;
while j<=n-1 do
begin
if (yij [i,j] -trunc (yij [i,j]) >=0.5) and (yij [i,j] -trunc (yij [i,j]) <1)
then begin y1i [i,j]: =y1i [i,j] +1; break; end
else j: =j+1
end; end;
for j: =2+kon to n-1 do
y1i [j, i]: =-1*y1i [i,j] ;
end;
kon: =kon+1;
end;
// поиск узких мест в сети дорог
for i: =1 to n do
for j: =1 to n do
c1 [i,j]: =y1i [i,j] -c [i,j] ;
for i: =1 to n do
for j: =1 to n do
CapOfEdge. Cells [j, i]: =floattostr (y1i [i,j]);
for i: =1 to n do
for j: =1 to n do
StringGrid3. Cells [j, i]: =Floattostr (c1 [i,j]);
edit1. text: =floattostr (loop);
edit6. text: =floattostr (ten1);
edit7. text: =floattostr (maxpotok);
loop: =0; ten1: =0;
end;
procedure TForm1. VertexCountChange (Sender: TObject);
var i,j: integer;
begin
z: =1; mi: =1;
t: =0; ss: =0;
kk: =0; k3: =1;
kol: =0; kol1: =0;
ko: =0; sum: =0;
l5: =0; l5: =0;
pp: =1; o: =1;
op: =1;
// hij [1]: =0.2; hij [2]: =0.3; hij [3]: =0.5; d33: =0.25;
// hi [1]: =4; hi [2]: =5; hi [3]: =3; d11: =0.25; d22: =0.5;
l6: =0;
if VertexCount. Text<>'' then begin
CapOfEdge. ColCount: =StrToInt (VertexCount. Text) +1;
CapOfEdge. RowCount: =StrToInt (VertexCount. Text) +1;
StringGrid3. ColCount: =StrToInt (VertexCount. Text) +1;
StringGrid3. RowCount: =StrToInt (VertexCount. Text) +1;
StringGrid1. ColCount: =StrToInt (VertexCount. Text) +1;
StringGrid1. RowCount: =StrToInt (VertexCount. Text) +1;
n: =StrToInt (VertexCount. Text);
for i: =1 to n do begin
CapOfEdge. Cells [0, i]: ='x'+IntToStr (i);
CapOfEdge. Cells [i,0]: ='x'+IntToStr (i);
end;
for i: =1 to n do
for j: =1 to n do begin
CapOfEdge. Cells [i,j]: ='0';
end;
for i: =1 to n do begin
StringGrid3. Cells [0, i]: ='x'+IntToStr (i);
StringGrid3. Cells [i,0]: ='x'+IntToStr (i);
end;
for i: =1 to n do
for j: =1 to n do begin
StringGrid3. Cells [i,j]: ='0';
end;
for i: =1 to n do begin
StringGrid1. Cells [0, i]: ='x'+IntToStr (i);
StringGrid1. Cells [i,0]: ='x'+IntToStr (i);
end;
for i: =1 to n do
for j: =1 to n do begin
StringGrid1. Cells [i,j]: ='0';
end;
end;
end;
procedure TForm1. Button3Click (Sender: TObject);
var f: textfile; i,j,n: integer; s: string;
Begin
opendialog1. filter: ='текстовые файлы|*. txt|';
if opendialog1. execute and fileexists (opendialog1. filename)
then begin
assignfile (f,opendialog1. filename);
reset (f);
readln (f,n);
for i: =1 to n do
for j: =1 to n do begin readln (f,s);
stringgrid3. cells [j-1, i-1]: =s;
end;
for i: =1 to n do
for j: =1 to n do begin readln (f,s);
stringgrid1. cells [j-1, i-1]: =s;
end;
for i: =1 to n do
for j: =1 to n do begin readln (f,s);
Capofedge. cells [j-1, i-1]: =s;
end;
for i: =1 to n do begin readln (f,s);
stringgrid4. cells [i-1,0]: =s;
end;
for i: =1 to n do begin readln (f,s);
stringgrid5. cells [i-1,0]: =s;
end;
readln (f,s); edit3. Text: =s;
readln (f,s); edit4. Text: =s;
readln (f,s); edit5. Text: =s;
closefile (f);
end;
end;
procedure TForm1. Button4Click (Sender: TObject);
var f: textfile; i,j,n: integer;
Begin
savedialog1. filter: ='текстовые файлы|*. txt|';
n: =strtoint (VertexCount. text) +1;
ll: =strtoint (Edit2. text);
if savedialog1. execute then begin
assignfile (f,savedialog1. filename);
rewrite (f);
writeln (f,n);
for i: =1 to n do
for j: =1 to n do
writeln (f,stringgrid3. cells [j-1, i-1]);
for i: =1 to n do
for j: =1 to n do
writeln (f,stringgrid1. cells [j-1, i-1]);
for i: =1 to n do
for j: =1 to n do
writeln (f,Capofedge. cells [j-1, i-1]);
for i: =1 to n do
writeln (f,stringgrid4. cells [i-1,0]);
for i: =1 to n do
writeln (f,stringgrid5. cells [i-1,0]);
writeln (f,edit3. text);
writeln (f,edit4. text);
writeln (f,edit5. text);
closefile (f);
end;
end;
procedure TForm1. Edit2Change (Sender: TObject);
begin
ll: =StrToInt (Edit2. Text);
StringGrid4. ColCount: =StrToInt (Edit2. Text);
StringGrid5. ColCount: =StrToInt (Edit2. Text);
end;
procedure TForm1. Button5Click (Sender: TObject);
begin
StringGrid3. Visible: =false;
Label11. Visible: =false;
GroupBox4. Visible: =false;
for i: =1 to n do
for j: =1 to n do
if c1 [i,j] <0 then c2 [i,j]: =c [i,j] + (-1) *c1 [i,j] ;
for i: =1 to n do
for j: =1 to n do
CapOfEdge. Cells [j, i]: =floattostr (c2 [i,j]);
for i: =1 to n do
for j: =1 to n do
end;