Содержание к диссертации
Введение
ГЛАВА 1 Потоковые задачи в транспортных сетях в четких условиях 11
1.1 Основные понятия теории потоков 11
1.2 Описание методики расчета пропускных способностей дуг транспортной сети .12 1.2.1 Факторы, ведущие к постановкам потоковых задач в нечетких условиях .14
1.3 Нечеткая логика как основной инструмент оперирования неопределенностью 15
1.4 Потоковые задачи в транспортных сетях 21
1.4.1 Нахождение максимального потока в транспортной сети .21
1.4.2 Нахождение максимального потока в транспортной сети с учетом ненулевых нижних потоковых границ 23
1.4.3 Нахождение потока минимальной стоимости в транспортной сети .24
1.4.4 Нахождение потока минимальной стоимости в транспортной сети с учетом ненулевых нижних потоковых границ 27
1.5 Потоковые задачи в динамических транспортных сетях 28
1.5.1 Нахождение максимального потока в динамической транспортной сети с учетом нулевых и ненулевых нижних потоковых границ 29
1.5.2 Нахождение потока минимальной стоимости в динамической транспортной сети с учетом нулевых и ненулевых нижних потоковых границ 31
1.6 Выводы по главе 1 33
ГЛАВА 2 Нахождение максимального потока и потока минимальной стоимости в транспортной сети в нечетких условиях 34
2.1 Нахождение максимального потока в транспортной сети с нечеткими пропускными способностями .34
2.2 Методика выполнения арифметических операций над нечеткими числами 37
2.3 Нахождение максимального потока в транспортной сети с учетом ненулевых нижних и верхних потоковых границ, представленных в нечетком виде .40
2.4 Нахождение потока минимальной стоимости в транспортной сети с нечеткими пропускными способностями и стоимостями 47 2.4.1 Метод потенциалов для нахождения потока минимальной стоимости в транспортной сети с нечеткими пропускными способностями и стоимостями 50
2.5 Нахождение потока минимальной стоимости в транспортной сети с учетом нечетких ненулевых нижних, верхних границ потоков и стоимостей 63
2.6 Выводы по главе 2 81
ГЛАВА 3 Решение потоковых задач в динамических транспортных сетях с нечеткими нижними, верхними границами потоков и стоимостями ..83
3.1 Определение нечеткой динамической транспортной сети 83
3.2 Нахождение максимального потока в динамической транспортной сети с нечеткими пропускными способностями, зависящими от времени 85
3.3 Нахождение максимального потока в динамической транспортной сети с учетом нечетких ненулевых нижних и верхних потоковых границ, изменяющихся во времени .90
3.4 Нахождение потока минимальной стоимости в динамической транспортной сети с зависящими от времени пропускными способностями и стоимостями, заданными в нечетком виде .110
3.5 Нахождение потока минимальной стоимости в динамической транспортной сети с учетом нечетких ненулевых нижних, верхних потоковых границ и стоимостей, зависящих от времени .133
3.6 Выводы по главе 3 144
ГЛАВА 4 Разработка программного модуля, реализующего решение потоковых задач в транспортных сетях в нечетких условиях 146
4.1 Функциональное назначение разработанного программного модуля .146
4.2 Описание логической структуры программного модуля 149
4.3 Подготовка входных данных с использованием ГИС ObjectLand .152
4.4 Оценка временной сложности 152
4.5 Выводы по главе 4 153
Заключение .154
Список используемых источников .156
- Нечеткая логика как основной инструмент оперирования неопределенностью
- Методика выполнения арифметических операций над нечеткими числами
- Нахождение максимального потока в динамической транспортной сети с учетом нечетких ненулевых нижних и верхних потоковых границ, изменяющихся во времени
- Описание логической структуры программного модуля
Нечеткая логика как основной инструмент оперирования неопределенностью
Как было упомянуто выше, потоковые задачи, возникающие при исследовании транспортных сетей, являются актуальными в силу широты их практического применения. Рассмотрим понятие транспортной сети, представленное в определении 1.1.
Согласно [4] транспортной сетью называют конечный связный ориентированный граф G = (X, A) без петель, где X – множество вершин, которое представляет собой множество узлов, например, перекрестков транспортной сети или станций, A – множество дуг, т.е. участков дорог, соединяющих узлы xi ,xj X , где (i, j =1,...,n) . Каждой дуге (xi ,xj ) A данного графа поставлено в соответствие некоторое неотрицательное число uij , называемое пропускной способностью этой дуги, и существуют две вершины: источник x0 =s , в который не входит ни одна дуга, и сток xn =t, из которого не выходит ни одной дуги.
В задачах определения потока минимальной стоимости на дугах сети задается также параметр cij , определяющий стоимость перевозки единицы потока по дуге (xi , xj ). Рассмотрим понятие пропускной способности дуг транспортной сети, представленное в Уравнение (1.1) является уравнением сохранения потока, которое показывает, что количество потока, втекающее в любую вершину х. кроме источника и стока, равно количеству потока, вытекающему из вершины х., кроме источника и стока. Ограничение на дуговые потоки указаны в уравнении (1.2).
Итак, параметром, накладывающим ограничение на потоки, текущие по дугам транспортной сети, являются пропускные способности. Пропускная способность дороги (участка дороги) определяет максимальное количество транспортных средств, которое может пропустить рассматриваемая дорога (ее участок) вообще или в единицу времени. По сути, пропускные способности являются основополагающим параметром при решении потоковых задач, ведь именно от правильности их задания зависит корректность решения. Следовательно, необходимо обратиться к методикам определения пропускных способностей на примере автомобильных дорог [34].
Пропускная способность дороги зависит от большого числа факторов: дорожных условий (ширины проезжей части, продольного уклона, радиуса кривых в плане, расстояния видимости и др.), состава потока автомобилей, наличия средств регулирования, погодно-климатических условий, возможности маневрирования автомобилей по ширине проезжей части, психофизиологических особенностей водителей и конструкции автомобилей. Изменение из этих факторов приводит к существенным колебаниям пропускной способности в течение суток, месяца, сезона и года. При частом расположении помех на дороге происходят значительные колебания скорости, приводящие к появлению большого числа автомобилей, движущихся в группах, а также снижению средней скорости всего потока [5].
Пропускные способности принято подразделять на теоретические, практические и расчетные. Под теоретической пропускной способностью uтеор понимают пропускную способность дороги или ее участка в условиях постоянных интервалов между автомобилями, однородного состава транспортных средств (например, в случае, если состав автомобилей состоит только из легковых автомобилей). Если рассматривается автомобильная магистраль, то теоретическая пропускная способность ее полосы составляет 2900 легковых авт/ч.
Практическая пропускная способность uпракт представляет собой параметр, обеспечиваемый в реальных дорожных условиях. Выделяют два ее типа: максимальную практическую umax и практическую в реальных дорожных условиях uпракт . Под максимальной практической пропускной способностью понимают пропускную способность участка дороги в эталонных условиях [5].
Практическая пропускная способность в конкретных дорожных условиях соответствует участкам с худшими дорожными условиями по сравнению с эталонным участком.
Расчетная пропускная способность uрасч определяет экономически обоснованное количество транспортных средств, которое может пройти по рассматриваемой дороге (ее участку) в конкретных дорожных условиях и при конкретной организации движения. Расчетная пропускная способность может быть вычислена, как: uрасч =knuтеор, (1.3) где п – коэффициент перехода от теоретической пропускной способности к расчетной, k который определяется в зависимости от вида дороги, категории дорог и рельефа в (1.3).
В реальных вычислениях пропускной способности помимо вышеуказанной формулы (1.3) может быть использована формула для расчета практической пропускной способности в реальных дорожных условиях: uпракт =Bumax. (1.4) В (1.4) umax – константа, зависящая от количества полос на дороге. Коэффициент B представляет итоговый коэффициент снижения пропускной способности, равный произведению частных коэффициентов 1...15 . Коэффициенты являются постоянными для определенных значений признаков. Например, коэффициент 1 представляет собой табличную зависимость между количеством полос на дороге, шириной полос или проезжей части, 2 зависит от ширины обочины, 3 представляет собой зависимость между расстоянием от кромки проезжей части до препятствия и шириной полосы движения (наличием боковых помех), 4 показывает взаимосвязь между количеством автопоездов в потоке в % и количеством легковых и средних грузовых автомобилей в %, 5 представляет собой коэффициент, показывающий взаимосвязь между продольным уклоном в %, длиной подъема и количеством автомобильных поездов в потоке в %, коэффициент 6 зависит от расстояния видимости в м., 7 зависит от радиуса кривой в плане, 8 представляет собой коэффициент, отражающий ограничение скорости знаком, коэффициент 9 является зависимым от трех параметров: числа автомобилей, поворачивающих налево в %, типа пересечения и ширины проезжей части основной дороги, коэффициент 10 зависит от укрепления обочины, 11 зависит от вида покрытия дороги, 12 меняет свое значение при наличии бензозаправочных станций, площадок отдыха с полным отделением от основной дороги и наличием специальной полосы для въезда или тех же атрибутов при наличии или отсутствии отгона, 13 зависит от вида разметки, 14 зависит от ограничения скорости (аналогично 8 ) и наличия указателей полос движения, 15 выявляет взаимосвязь между числом автобусов в потоке в % и числом легковых автомобилей в потоке в %.
Методика выполнения арифметических операций над нечеткими числами
В модели (2.9)-(2.11) cij – стоимость перевозки единицы потока по дуге (xi , xj ); –
заданное нечеткое значение потока, стоимость перевозки которого необходимо минимизировать.
Как было описано в первой главе диссертации, для решения данной задачи в четких условиях применяются алгоритмы Басакера-Гоуэна [33] последовательного поиска кратчайших путей, алгоритм Клейна выявления и удаления циклов отрицательного веса и пр. Поскольку областью рассмотрения являются транспортные сети, исходные стоимости перевозок потока неотрицательны, значит, исходный граф не будет содержать циклов отрицательной стоимости, следовательно, на первом шаге алгоритма поиска потока минимальной стоимости нецелесообразно применять алгоритм Клейна. Также стоит отметить, что для выявления циклов отрицательной стоимости традиционно применяется алгоритм Флойда-Воршелла [64], оперирующий путями от каждой вершины к каждой, что не эффективно в нашем случае, т.к. достаточно найти расстояние от источника к стоку. Следовательно, для поиска потока минимальной стоимости следует рассматривать алгоритм Басакера-Гоуэна и его модификации.
В алгоритме поиска потока минимальной стоимости Басакера-Гоуэна осуществляется поиск цепи наименьшей стоимости и передача по ней максимального потока, учитывая пропускные способности входящих в этот путь дуг. Поскольку поиск цепи наименьшей стоимости эквивалентен поиску кратчайшего пути в графе (в данном случае стоимость эквивалентна длине пути), встает вопрос о выборе оптимального алгоритма поиска кратчайшего пути в графе.
Существует большое количество алгоритмов поиска кратчайшего пути. Среди них выделяют алгоритмы Дейкстры [103], Беллмана-Форда [104-105], Флойда-Воршелла [64], Левита [24], Джонсона [106]. Традиционно для поиска кратчайших путей (путей наименьшей стоимости) используют алгоритм Дейкстры [103], предложенный Э. Дейкстрой в 1959 г., он ищет кратчайший путь от заданной вершины ко всем остальным вершинам графа. В процессе работы алгоритма поддерживаются три множества: вершины, расстояние до которых уже вычислено (но, возможно, не окончательно); вершины, расстояние до которых вычисляется; вершины, расстояние до которых еще не вычислялось [23]. Временная эффективность алгоритма Дейкстры зависит от структур данных, используемых для реализации очереди с приоритетами и представления входного графа. В общем случае он имеет время работы O(X 2) [24]. Алгоритм Левита [22] также ищет кратчайший путь от заданной вершины ко всем остальным вершинам графа. Время его работы в худшем случае экспоненциально, но на практике обычно показывает время работы O(Alog X) . В процессе его работы поддерживаются те же три множества вершин. При этом вершины, входящие в первое множество делятся на два упорядоченных множества — основную и приоритетную очередь. Каждой вершине сопоставляется неотрицательное значение длины кратчайшего из известных на данный момент путей в нее из начальной вершины. Недостатком метода Левита является необходимость повторной обработки вершин, а достоинством - лучшее время работы на графах, построенных на реальных транспортных сетях. Но оба метода поиска кратчайшей цепи не применяются для графов с отрицательными длинами дуг (стоимостям перевозок). В общем случае алгоритм Левита может быть применен для таких графов, но необходимость учитывать такие дуги значительно усложняет алгоритм.
Метод Форда-Беллмана [104-105] ищет кратчайший путь из одной вершины к остальным за время 0(ХА) и может быть использован для графов с отрицательными длинами пути (стоимостями перевозок). Особенность алгоритма состоит в том, что он также определяет наличие циклов отрицательного веса, которые могут существовать, если исходный граф имеет дуги отрицательной длины (стоимости).
Алгоритм Флойда-Воршелла [64] ищет кратчайшие пути между всеми парами вершин графа за время 0(Х3). Метод может быть применен для графов с отрицательными длинами пути (стоимостями). Он также используется для выявления циклов отрицательной стоимости (например, в алгоритме поиска потока минимальной стоимости Клейна). Данный алгоритм позволяет найти лишь кратчайшие расстояния между вершинами без сохранения самих путей. Алгоритм Джонсона [106] ищет кратчайшие пути между всеми парами вершин графа за время 0(X2logX + XA) в общем случае. Может применяться для графов с отрицательными длинами путей (стоимостями). Алгоритм заключается в применении алгоритма Дейкстры для поиска кратчайшего пути предварительно изменяя веса ребер, избавляясь, таким образом, от отрицательных длин (стоимостей). Новые веса вводятся с использованием метода Беллмана-Форда.
В алгоритме поиска потока минимальной стоимости мы ищем кратчайший путь в нечеткой остаточной сети. Таким образом, в ней появятся ребра, имеющие отрицательную стоимость, так как в случае пускания потока по дуге (х.,х.) є А, имеющей стоимость перевозки су, в нечеткой остаточной сети появляется помимо прямого ребра обратное ребро (pcf ,xf) є А 1, имеющее отрицательную стоимость —с... Следовательно, мы не можем применять эффективный алгоритм поиска пути минимальной стоимости Дейкстры. Поэтому для поиска потока минимальной стоимости целесообразно применять либо алгоритм, предложенный Басакером-Гоуэном, где на этапе поиска кратчайшей цепи используется алгоритм Форда, позволяющий оперировать отрицательными параметрами стоимостей, либо алгоритм, сводящий отрицательные числа к неотрицательным.
Метод, позволяющий перейти от отрицательных чисел к неотрицательным, основан на введении потенциалов для каждой из вершин графа. Более эффективным для поиска заданного потока минимальной стоимости является алгоритмы Эдмондса-Карпа [45] и Томизавы [107], преобразующие отрицательные стоимости перевозок с помощью потенциалов вершин в неотрицательные. Идея метода в том, что на каждом шаге построения нечеткой остаточной сети стоимости перевозок пересчитываются, исходя из значений потенциалов, приписанных вершинам графа так, чтобы они были неотрицательными. В свою очередь, потенциалы вершин задаются с помощью нахождения длин кратчайших путей от источника к конкретной вершине, где под длиной пути понимаем стоимость его прохождения. Итак, рассмотрим основные определения нахождение потока минимальной стоимости в транспортной сети с нечеткими пропускными способностями и стоимостями
Нахождение максимального потока в динамической транспортной сети с учетом нечетких ненулевых нижних и верхних потоковых границ, изменяющихся во времени
Задачи, рассмотренные в первой главе диссертации, предполагали мгновенное прохождение потока по дугам транспортной сети. В данной главе будут рассматриваться динамические транспортные сети, то есть такие, в которых поток затрачивает некоторое время при прохождении по дугам сети. Данные задачи возникают при планировании транспортных перевозок, экономическом планировании, строительстве и эвакуации зданий. Методы решения потоковых задач в динамических транспортных сетях, в частности, задачи нахождения потока минимальной стоимости в динамической сети, используются для решения проблемы загрязнения воздуха машинами, связывая пропускную способность дуги с максимально допустимым уровнем загрязнения воздуха, который, в свою очередь, зависит от числа машин, которое может пропустить конкретный участок пути [110]. Данные задачи должны быть рассмотрены с учетом сложного характера факторов внешней среды, которые вносят неопределенность в постановки задач. Актуальность описанных задач, а также подобных задач с учетом ненулевых нижних потоковых границ, отражающих экономическую обоснованность перевозки, состоит в том, что алгоритмы их решения позволяют находить максимально возможный объем перевозки между выбранными пунктами на карте дорог и выбирать оптимальные маршруты для перевозки с дальнейшей передачей по ним потока с учетом ограниченного времени перевозки и меняющихся во времени параметров транспортной сети в условиях неопределенности.
Задача нахождения максимального динамического потока имеет два основных метода решения: с помощью «развернутого во времени графа», предложенного авторами Форд и Фалкерсон, и с помощью применения алгоритма поиска потока минимальной стоимости, полагая время прохождения потока по дуге - ее стоимостью и применяя алгоритм поиска кратчайших путей [111]. Согласно [1, 112] «развернутый во времени» статический граф, соответствующий исходному динамическому графу, строится «растягиванием во времени» исходного динамического графа за заданное количество временных интервалов путем создания отдельной копии каждой вершины xiєX в каждый рассматриваемый момент времени в є T .
Несмотря на компактность второго подхода, большее распространение получил способ, оперирующий «развернутым во времени» графом. Это справедливо в силу того, что алгоритм, основанный на декомпозиции потока, не позволяет учесть динамическую структуру транспортной сети в полной мере (учитывается лишь время прохождения потока по дугам), в то время как пропускные способности дуг и параметры времени задаются константами. Это позволило нам назвать модель, предложенную Фордом-Фалкерсоном, «стационарно-динамической» [34]. В реальных постановках задач параметр времени отправления потока является решающим, поскольку он влияет на пропускные способности дуг сети, а также на время в пути. Например, в утренние часы (момент отправления 1) дороги не загружены, пропускная способность дорог высокая, а значит время прохождения потока по дугам небольшое. В вечерние часы (момент отправления 2) дороги загружены, следовательно, их пропускные способности малы, а время прохождения потока большое. Таким образом, мы приходим к рассмотрению потоковых задач в динамических транспортных сетях, т.е. таких, параметры которых могут меняться во времени. Учтем также нечеткий характер пропускных способностей дуг транспортных сетей, рассмотренный в первой главе диссертации. Следовательно, необходимо разработать алгоритмы нахождения потоков в нечетких динамических транспортных сетях.
Перед рассмотрением основных потоковых задач, возникающих в транспортных сетях, представленных в виде нечетких ориентированных графов, необходимо дать определения нечеткой «стационарно-динамической» (определение 3.1) и динамической транспортных сетей (определение 3.2) [34]. Определение 3.1 Нечеткой стационарно-динамической транспортной сетью называется [34] транспортная сеть, представленная в виде нечеткого ориентированного графа G = (X,A), где X = {x1,x2,...,xn} - множество вершин, Таким образом, рассматриваемые в данной главе диссертационной работы задачи будут опираться на понятие динамической транспортной сети в отличие от «стационарно-динамической», рассматриваемой в классической литературе по динамическим потокам. Так как рассматриваемые далее задачи помимо нечетких параметров будут содержать параметр времени прохождения потока по дугам сети, представленный четко, приходим к решению таких задач в условиях частичной неопределенности.
Нахождение максимального потока в динамической транспортной сети с нечеткими пропускными способностями, зависящими от времени
Рассмотрим задачу определения максимального потока в динамической транспортной сети, представленной нечетким ориентированным графом. Особенность данной постановки задачи заключается в том, что пропускные способности дуг сети представляют собой нечеткие числа. Также как и пропускные способности, параметры времени прохождения потока по дугам сети зависят от момента отправления потока, следовательно, мы приходим к следующей постановке задачи [113]:
С помощью «растягивания во времени» исходного нечеткого динамического графа введем «развернутый во времени» статический нечеткий граф, что отражено в правиле 3.1, представленном в [113]. Для нахождения в построенном графе максимального потока, построим нечеткую остаточную сеть согласно правилу 3.2, введенному в [113]. Будем искать максимальный поток в нечеткой остаточной сети, соответствующей статическому «развернутому во времени» графу с помощью алгоритма Эдмондса-Карпа, модифицированного для применения нечетких чисел.
Правило 3.1 построения «развернутого во времени» нечеткого графа для нахождения максимального потока в динамической транспортной сети с нечеткими пропускными способностями [113]
Переходим от заданного нечеткого динамического графа G = (X, A) к «развернутому во времени» на p интервалов нечеткому статическому графу G с помощью «растягивания во времени» исходного динамического графа за заданное количество временных интервалов путем создания отдельной копии каждой вершины xi є X в каждый рассматриваемый момент времени 9єT. Пусть Gp=(Xp,Ap) представляет собой «развернутый во времени» граф исходного динамического графа. Множество вершин X графа G задается как Xp={(xi,9):(xi,9)єXхT}. Множество дуг A p ставит в соответствие дугам (xi,xj) є A исходного динамического графа дуги, идущие из каждой пары «вершина-время» (x ,9) є X в каждую пару «вершина-время» вида (x 3 = 9 + тij(9)), где xjєГ(xi) и 9 + тij(9) p. Пропускные способности дуг u(xi,xj ,9,3), соединяющие пары «вершина-время» (xi,0) с (xj ,Э) в Gp, равны u ij(9). Параметры времени прохождения потока т( xi,xj,9,3), соединяющие пары вершин (xi,9) с (x ,3) в G , равны исходным в динамическом графе
Описание логической структуры программного модуля
Необходимо разработать алгоритм решения задачи определения максимального потока минимальной стоимости в динамической транспортной сети в условиях частичной неопределенности. Для этого введем правило 3.9 построения нечеткой остаточной сети в «развернутом во времени» графе, сформулированное в [29].
Правило 3.9 построения нечеткой остаточной сети в «развернутом во времени» графе в динамической для нахождения максимального потока минимальной стоимости транспортной сети с нечеткими зависящими от времени пропускными способностями и стоимостями, заданными в нечетком виде
Нечеткая остаточная транспортная сеть Gp = {Xp,Ap) строится по «развернутой во времени» сети G = (X A ) в зависимости от величин потоков (xi,x ,0,3 = 0 + Тij(0)), идущих по последней следующим образом: каждая дуга в остаточной нечеткой сети Gp, соединяющая пару «вершина-время» (xf ,0) с парой «вершина-время» {x ,3) по которой поток %(xi,x ,0,S) отправляется в момент времени 0 є T имеет нечеткую остаточную
Алгоритм решения задачи нахождения максимального потока минимальной стоимости в динамической транспортной сети с зависящими от времени пропускными способностями и стоимостями, заданными в нечетком виде
Рассмотрим формальный алгоритм решения задачи нахождения максимального потока минимальной стоимости в динамической транспортной сети в условиях частичной неопределенности [29], представленный моделью (3.24)-(3.28).
Этап 1. Перейти от заданного нечеткого динамического графа G к «растянутому во времени» нечеткому статическому графу G согласно «растягиванию во времени» исходного динамического графа за заданное количество временных интервалов путем создания отдельной копии каждой хг є X в каждый рассматриваемый момент времени 9 є Т согласно правилу 3.7.
Необходимо вычислить максимальный поток, имеющий минимальную стоимость, вытекающий из группы источников во все моменты времени и втекающих в группу стоков во все моменты времени не позднее р. Для этого вводим искусственный источник s и сток и Ї и соединяем S дугами с каждым истинным источником, а/с каждым истинным стоком. Фиктивные дуги, идущие от искусственных вершин, имеют бесконечную пропускную способность.
Этап 6. Если найден максимальный поток в графе Gp (xt,xp6,S) + 8%y.P =v(p) минимальной стоимости c( (xj,x ,в,3) + 8 хР ) из искусственного источника s в искусственный сток і, определяемый множеством путей Р, переходим к первоначальному динамическому графу G следующим образом: отбрасываем искусственные вершины s , Ї и дуги, соединяющие их с другими вершинами. Таким образом, в исходном динамическом графе получен максимальный поток значения у(р), эквивалентный потоку из источников (начальная вершина исходного графа, растянутая нар интервалов) в стоки (конечная вершина, растянутая нар интервалов) в графе Gp после удаления фиктивных вершин, а каждый путь, соединяющий вершины (s,0) и (t,g = 6 + zst(6)),g є Т, по которому идет поток (s,t,0,g), соответствует потоку q st (в) стоимости c( st (в)). Численный пример, реализующий работу алгоритма нахождения максимального потока минимальной стоимости в динамической транспортной сети в условиях частичной неопределенности, представлен в Приложении А.
Нахождение потока минимальной стоимости в динамической транспортной сети с учетом нечетких ненулевых нижних, верхних потоковых границ и стоимостей, зависящих от времени Рассмотрим ситуацию, когда необходимо перевезти заданное количество единиц потока из источника в сток в транспортной сети в нечетких условиях с учетом времени прохождения потока по дугам графа, зависимости параметров сети от момента отправления потока, а также заданных минимальных значений рентабельности перевозок, выраженных нижними потоковыми границами. Тогда, мы приходим к постановке задачи нахождения потока минимальной стоимости с учетом нижних границ потоков в динамической нечеткой транспортной сети [116].
Так как данная задача рассматривалась в литературе в четких условиях, а также в условиях стационарно-динамических графов, возникла необходимость разработки алгоритма решения задачи нахождения потока минимальной стоимости в нечеткой транспортной сети с учетом верхних и ненулевых нижних потоковых границ, а также параметров времени прохождения потока по дугам сети, зависящим от момента отправления потока.
Таким образом, сначала введем правило 3.10 перехода к «развернутому во времени» графу, соответствующему исходному, сформулированное в [116].
Правило 3.10 построения «развернутого во времени» нечеткого графа, соответствующего исходному динамическому графу, для нахождения потока минимальной стоимости в динамической транспортной сети с учетом нечетких ненулевых нижних, верхних потоковых границ и стоимостей перевозок, зависящих от времени
Пусть Gp=(Xp,Ap) представляет собой «развернутый во времени» граф исходного динамического графа. Множество вершин Xp графа Gp задается как Xp={(xi,9):(xi,9)єXхT}. Множество дуг A p ставит в соответствие дугам (xi,xj) є A исходного динамического графа дуги, идущие из каждой пары «вершина-время» (x ,9) є X в каждую пару «вершина-время» вида (x 3 = 9 + тij(9)), где xjєГ(xi) и 9 + тij(9) p.
Правило 3.11 перехода от «развернутого во времени» нечеткого графа к соответствующему нечеткому графу без нижних потоковых границ для решения задачи нахождения потока минимальной стоимости в динамической транспортной сети с учетом нечетких ненулевых нижних, верхних потоковых границ и стоимостей перевозок, зависящих от времени
Перейдем от «развернутого во времени» нечеткого графа G =(X A ), имеющего ненулевые нижние потоковые границы, к нечеткому графу G = (X A ) без нижних границ потоков. Для этого вводим в граф G искусственные источник s и сток t , дуги, соединяющие пары «вершина-время» (t,У9єT) c (s,V9eT) с верхней границей потока
