Systems. Methods. Technologies 1 (37) 2018

Системы Методы Технологии. В.А. Иванников. Анализ и разработка … 2018 № 1 (37) с. 126-129 127 Введение Для расчета региональных транспортных схем с учетом сетевых направлений грузопотоков необходимо унифицировать описание последних. Это связано с тем, что применяемые формы описания схем грузопотоков лесоматериалов часто содержат формулировки, не под- дающиеся однозначной формализации. Наиболее целесообразно решение данной задачи на сети с «удлиненными» дугами или с запретами на мат- рице, так как реализация алгоритма при этом всегда при- водит к конечному результату. Однако получаемое реше- ние может содержать встречные перевозки на отдельных участках или запрещенные корреспонденции на матри- це, окончательные выводы по которым могут быть сде- ланы лишь на основе тщательного анализа [1, 2]. Математическая формализация рассматриваемой задачи, включающая две ее разновидности, обуслов- ленные особенностями описания общесетевых схем, заключается в следующем [3, 4]. Постановка и решение задачи. Модель транспорт- ной сети для решения рассматриваемой задачи описы- вается следующим образом [5; 6]. Задан конечный связный граф, изображающий схему железных дорог: ( ) ( ) rV VG , , ≡υ = , где υ ,V — множества соответственно вершин сети и ориентированных ребер (участков), соединяющих вер- шины графа; r — отображение множества V самого на себя. Отдельный полигон сети представляется в виде под- графа G ′ графа G , который может быть определен так: ( ) ( ) . , , , , И И V V rV ИV G ⊂′′ ⊂′′ ′′ ′′ ≡′′ ′′ =′′ (2) ( ) . V r r ′∩υ=υ′ При этом элементами множества V ′ являются все пункты полигона и стыковые пункты с соседними по- лигонами, а элементами множества И ′ — упорядо- ченные пары ( j ;i υυ ). Если кратчайший путь между какими-либо пункта- ми включает участки других полигонов, то следует расширить множество И " и соответственно отображе- ние r" , включив в них условные дуги между выходны- ми и входными пунктами полигона на данном пути. Иначе, если кратчайший путь из i υ′ в j υ′ проходит за пределы полигона через 1 i υ ′′ и входит через 1 j υ ′ , будем считать, что: ( ) 1 1 1 1 i r j ,И j , i υ ′′ ′′∈ υ ′′ ′′ ∈ υ ′′ υ ′′ . (3) Общесетевые схемы нормальных направлений гру- зопотоков (СННГ) на сети представляются как некото- рые ориентированные графы  G без контуров, яв- ляющиеся по отношению к графу G частичными гра- фами, содержащими все его вершины и только часть его дуг: ( ) U U UV G ⊂ = ∆ ∆ ∆ , , . (4) На полигоне дороги сетевая СННГ изображается в виде частичного графа  G ′′ , определяемого соотноше- нием: ( ) ( ) ( ) И U U UVG UVG UVG ∩ =′ ′ ′ ′ ∩ =′ ′ ′ ∆ ∆ ∆ ∆ ∆ ∆ , , , . (5) Для формирования расчетной транспортной сети построим граф * ∆′′ G , обратный графу ∆ ′′ G , и ориенти- рованный граф следующим образом: ( ) ( ) * 1 * 1 * ; , ; , ∆ ∆ ∆ ′′ −′′ =′′ ′′ ′′ =′′ ′′ ′′ =′′ UUU UV G UV G z z z (6) где * ∆ ′ U — множество дуг, противоположных дугам множества ∆ ′ И . Тогда сеть для расчета на выделенном полигоне мо- жет быть изображена в виде графа zG ′′ , дугам которого поставлены в соответствие некоторые положительные числа (расстояние, время, издержки и т. п.) [7, 8]. Что- бы обеспечить выполнение вычислительных процедур на ЭВМ с выдачей конечных результатов, выделим в множестве U ′ подмножества ∆ ′′ И и * ∆ ′ U и поставим в соответствие дугам графа G некоторые положитель- ные числа из соотношения: ( ) ( ) ( )     ′ ∈′ ′ ≥ ∈′ ′ =′ ∆ * , max , UИИf M ИИИf Uf z (7) Для математической постановки однопродуктовой транспортной задачи по полученной сети зададим на множестве U ′′ функции ( ) Иd ′′ пропускных способ- ностей по дугам данного груза, а на множестве V ′′ определим функции ( ) υ ′′ ia производства и потребле- ния. Последние принимают значения ( ) J i ia ′∈ в пунк- тах производства и ( ) J j jb ′∈ — в пунктах потребле- ния. Здесь J,J ′ ′ — множества индексов соответствен- но пунктов производства и потребления [9]. Тогда рас- сматриваемая задача формируется следующим образом. В области Z , определяемой ограничениями: 1) ( ) ( )      ∈ ′∈ − ′∈ =′ −′ ∑ ∑ +′∈′ −′∈′ ; ,0 , , , , t r r ИИ ИИ r J r J rb J ra Иr ИX r r (8) 2) ( ) ( ) UИ Иd ИX ′ ∈′ ′ ≤′ ≤ , 0 , (9) где +′′ −′′ rИ, rИ — множества исходящих и соответст- венно входящих дуг вершины ( ) U rr ′′ = ,1 ; tJ — мно- жество индексов транзитных пунктов, задана целевая функция ( ) ( ) . ИxF ′ Требуется найти такой поток ( ) ИX ′ , чтобы было справедливо равенство: