Scientific journal
Modern high technologies
ISSN 1812-7320
"Перечень" ВАК
ИФ РИНЦ = 0,940

THE THEOREM ON MANAGING OF GAS FLOWS IN CLOSED THE GAS-TRANSPORT SYSTEM WITH ADDITIONAL METRIC CONDITIONS AND REVERSIBLE PIPELINES

Snezhin A.N. 1 Petrov S.V. 1
1 Company «Gazprom development»
3374 KB
The most actual and daunting problem facing computer complexes, decisive streaming tasks, is a task on the distribution of flows. After input of restrictions throughput and control actions this task by definition to becomes task of flows control, which includes several types of streaming tasks – transport tasks, the task of determining the existence of flow, the tasks of the search for a generalized flow, etc. In the article «Algorithm for optimal distribution of gas flows in closed the gas-transport system» was submitted by the original mathematical model and realizing her method for calculating the optimal allocation of gas flows in difficult close system of gas pipelines with out taking into account values GMS. In it also has been presented the theorem about the decision on a reversible arcs received during the development of a method. In present article a proof of the put forward theorem and the detailed solution of the task managing distribution of gas flows with reversible arcs and taking into account values of GMS.
mathematical model; theorem; proof; the distribution of gas flows; reversible gas pipeline; Gas measuring station (GMS); Gas-transport system (GTS; technically possible productivity (TPP)

Наиболее актуальной и сложной проблемой, стоящей перед потоковыми комплексами является задача о распределении потоков. При вводе ограничений пропускной способности и управляющих воздействий эта задача по определению [1, 4] становиться задачей управления потоками, включающая в себя сразу несколько типов потоковых задач – транспортные задачи, задачи определения существования потока, задачи о поиске обобщенного потока и пр. В ходе поиска решения одной из таких задач – задачи распределения потоков газа в сложной системе газопроводов с учетом пропускной способности и управляющих воздействий, был разработан новый оригинальный метод решения задачи управления потоками, позволяющий находить решение с учетом условий, возникающих в реально действующих потоковых системах. В статье «Алгоритм управления распределением потоков газа в замкнутой газотранспортной системе»была представлена оригинальная математическая модель и реализующий ее метод расчета оптимального распределения потоков газа в сложной замкнутой системе газопроводов без учета значений ГИС. Также в ней была представлена полученная в ходе разработки метода теорема о решении на реверсивных дугах. В настоящей статье приводится доказательство выдвинутой теоремы и разбирается решение задачи управления распределением потока газа с реверсивными дугами и с учетом значений ГИС.

Основные определения и доказательство теоремы

Напомним постановку задачи для газотранспортной системы без реверсивных дуг. Пусть символ ij обозначает дугу с началом i и концом j. Обозначим через xij переменную величину газового потока в начале дуги ij. По определению для нереверсивной дуги величина xij всегда неотрицательна. Это значит, что газ течёт по дуге из начала i в конец j. Пусть gij есть поступление/распределение на дуге ij. Причём, для величины gij – используем знак « + », если на дуге поступление – приток, и знак «–», если на дуге распределение – отток. Будем считать, что поступление/распределение происходит на середине дуги. Это предположение является важным для описанного метода решения задачи. С учётом сделанных обозначений поток с середины до конца дуги равен xij + gij. Пусть cij – это длина газопровода, который соединяет вершину i с вершиной j. Тогда целевая функция, которая является по сути ТТР, будет иметь следующий вид:

Eqn30.wmf (1)

Здесь и в дальнейшем берутся только те индексы i и j, для которых существуют дуги.

В постановку задачи линейного программирования также входит условие баланса в узлах:

Eqn31.wmf (2)

где j номер узла газотранспортной системы; fj – поступление/распределение в узле j (« + » отток, «–» приток)и условие положительности знака потока на дуге в случае отсутствия реверсивных дуг:

xij ≥ 0. (3)

Сформулируем основной результат, доказательство которого будет приведено ниже:

Теорема. Решение, полученное при условии, что разрешается дополнительно хотя бы одна реверсивная дуга, заведомо даёт результат подсчета ТТР не хуже, чем при отсутствии разрешения на реверс этой дуги, либо позволяет решить задачу, у которой не было решения, при изначально заданных условиях.

Замечание: Предполагаем далее, что имеется хотя бы 1 дуга, следовательно, не менее 2 узлов.

Доказательство теоремы разобьём на несколько утверждений и лемму.

Лемма. Пусть имеется две задачи линейного программирования в стандартной форме (см. [2]) у которых различаются только целевые функции. Первая целевая функция имеет вид:

Eqn32.wmf (4)

вторая имеет вид:

Eqn33.wmf (5)

где v есть произвольная действительная константа. Тогда решение Eqn34.wmf первой задачи, на котором достигается min линейной формы (4) является решением второй задачи и на нем целевая функция (5) также достигаем min.

Доказательство. Если Eqn34_1.wmf оптимальное решение первой задачи, тогда оно удовлетворяет всем условиям и ограничениям и верно равенство:

Eqn35.wmf (6)

Это значит, что для любого допустимого решения x′ имеем:

Eqn36.wmf (7)

Пусть Eqn37.wmf есть решение второй задачи, тогда

Eqn38.wmf (8)

следовательно,

Eqn39.wmf

по определению минимума для второй задачи. Отсюда получаем, что

Eqn40.wmf.

С другой стороны из формулы (7) следует, что

Eqn41.wmf.

Учитывая эти два неравенства, получаем:

Eqn42.wmf.

Поэтому

Eqn43.wmf.

Т.е. Eqn34.wmf является решением второй задачи. Доказательство леммы завершено.

Формула (1) фактически означает, что при подсчёте ТТР поток не меняется при прохождении по дуге. Запишем новую целевую функцию, с учётом того, что дойдя до середины дуги, величина потока меняется.

Eqn44.wmf (9)

Утверждение 1. При одинаковом векторе ограничений, матрице коэффициентов задачи линейного программирования и фиксированных поступлений/распределений на дугах gij, если найден min линейной формы (1), то на нем линейная форма (9) принимает минимальное значение.

Доказательство. Преобразуем формулу (9)

Eqn45.wmf (10)

где Eqn46.wmf – есть константа. Условие Леммы выполняется, что завершает доказательство утверждения 1.

Пусть дуга ij объявлена реверсивной. Добавим (в центре дуги) новую вершину с новым номером k = k(ij). С учетом введенной точки дугу ij заменим на 4 новые дуги ik, kj, ki, jk. Будем считать, что поступление или распределение газа gij на дуге ij переходит в поступление или распределение газа fk в узле k = k(ij), то есть

Eqn47.wmf.

Определим новые переменные, которые могут принимать любые действительные значения Eqn48.wmf и Eqn49.wmf. Значение переменной Eqn50.wmf – поток на первой половине дуги ij, значение переменной Eqn51.wmf – поток на второй половине дуги ij. Учитывая знаки переменных Eqn51.wmf, Eqn50.wmf, получаем 4 варианта потока газа на реверсивной дуге (рис. 1).

Для нереверсивных дуг Eqn52.wmf и Eqn53.wmf. Длины новых 4 дуг положим 1/2 старой:

Eqn54.wmf

pic_11.tif

Рис. 1. Возможные направления потоков газа на реверсивной дуге (на рисунке i – началогазопровода, j – конец газопровода):а – поток идет от начала к концу; б – поток идет от конца к началу (реверс); в – встречный поток (реверс на конце); г – разнонаправленный поток (реверс на начале – газопровод становиться донором за счет запаса газа)

Для целевой функции ТТР в случае отрицательных значений на «половинках» дуг формула расчёта включает модули величин, так как ТТР не зависит от направления течения потока:

Eqn55.wmf (11)

Обозначим через i0j0 реверсивную дугу, тогда учитывая, что xij ≥ 0, xij + gij ≥ 0 и свойство |a – b| ≤ |a + b|, если a, b ≥ 0, имеем оценку:

Eqn56.wmf (12)

Для дальнейшего рассмотрения будем предполагать, что решение задачи без реверсивных дуг существует. Обозначим его Eqn57.wmf, а значение целевой функции на нем через min.

Утверждение 2. Для задачи с объявленной реверсивной дугой i0j0 существует поток Eqn58.wmf, на котором целевая функция задачи с реверсом равна min целевой функции задачи без реверса.

Доказательство. По построению имеем:

Eqn59.wmf (13)

поскольку все поступления и распределения перенесены на центр дуги. На нереверсивных дугах оставим старые значения потока Eqn57.wmf. На новых дугах, полученных в результате добавления реверса, зададим следующие значения потока газа:

Eqn60.wmf Eqn61.wmf

Eqn62.wmf Eqn63.wmf (14)

Подставим эти значения в последнее равенство оценки (12):

Eqn64.wmf (15)

Используя условие (13) можно записать:

Eqn65.wmf (16)

Учитывая (13)–(16) имеем:

Eqn66.wmf (17)

Поэтому в задаче с реверсом есть поток, на котором достигается min задачи без реверса.

Утверждение 3. Для задачи с объявленной реверсивной дугой i0j0 построенный поток Eqn58.wmf, есть допустимое решение новой задачи линейного программирования.

Доказательство. Рассмотрим, как меняется система уравнений баланса в узлах для задачи с добавленной реверсивной дугой.

Появляется новое уравнение условия баланса для узла с номером k:

Eqn67.wmf (18)

где k = k(i0j0), a Eqn68.wmf (см. рис. 1). Учитывая условия (11) можно записать уравнение (18) в виде:

Eqn69.wmf (19)

Проверим, что поток с условиями (13)-(14) удовлетворяет уравнению (19). Для этого просто подставим заданные значения в обе части уравнения и получим равенство:

Eqn70.wmf (20)

Уравнение условие баланса (2) в узле i0 для нереверсивной дуги i0j0 имеет вид:

Eqn71.wmf (21)

При добавлении признака реверса уравнение (2) в узле i0 приобретает вид:

Eqn72.wmf (22)

Проверим, что поток с условиями (12)-(13) удовлетворяет уравнению (22). Подставим значения потока в обе части уравнения (22):

Eqn73.wmf (23)

Eqn74.wmf (24)

Учитывая равенства (21), (23), (24), получаем, что указанный поток удовлетворяет уравнению (22). Аналогично для конца дуги j0 имеем уравнение баланса вида (2)

Eqn75.wmf (25)

При добавлении признака реверса уравнение (2) в узле j0 приобретает вид:

Eqn76.wmf (26)

Проверим, что поток с условиями (13)-(14) удовлетворяет уравнению (26). Действуя аналогично, получаем:

Eqn77.wmf (27)

Eqn78.wmf (28)

Учитывая равенства (25), (27), (28), получаем, что указанный поток удовлетворяет уравнению (26). Остальные условия (уравнения) выполняются автоматически, так как по построению данного решения оно удовлетворяет тем уравнениям, которые не менялись.

Объединив вместе Утверждения 2 и 3, получаем.

Утверждение 4. Для задачи с объявленной реверсивной дугой i0j0, построенный поток Eqn58.wmf есть допустимое решение новой задачи. Значение новой целевой функции на нем совпадает с min целевой функции задачи без реверса.

Обозначим новую целевую функцию для задачи с реверсивной дугой:

Eqn79.wmf (29)

Оптимальное решение Eqn80.wmf задачи с реверсом, очевидно, удовлетворяет условию:

Eqn81.wmf (30)

Утверждение 5. Для любого решения Eqn82.wmf задачи с реверсом дуги i0j0 верно, что решение в новых переменных Eqn50.wmf и Eqn51.wmf является допустимым решением задачи, где поток на дуге i0j0 разделён на два с одним из направлений как на рис. 1 (а-г).

Доказательство. Проверим, что это верно для всех вершин, кроме i0 и j0. Для этого уравнения вида (2) преобразуем следующим образом:

Eqn83.wmf (31)

Проверим согласование потока в середине дуги i0j0. Это следует из преобразования равенства (18)

Eqn84.wmf (32)

Проверим согласование потока в вершине i0. Для этого преобразуем уравнение (20)

Eqn85.wmf (33)

Осталось проверить согласование потока в вершине j0. Аналогичным образом преобразуем уравнение (26)

Eqn86.wmf (34)

Равенства (31)–(34) показывают, что поток, выраженный в новых переменных Eqn50.wmf и Eqn51.wmf, удовлетворяет всем требуемым условиям.

Доказательство Теоремы. Рассмотрим Случай 1, когда решение задачи (1–3) без реверсивных дуг существует, обозначим это решение символом Eqn57.wmf, а значение целевой функции на этом решении через MIN. Пусть дуге i0j0 присвоен признак реверса. Согласно Утверждению 4 существует поток Eqn58.wmf – допустимое решение задачи с реверсом. Значение новой целевой функции на этом потоке совпадает с MIN целевой функции задачи без реверса:

Eqn87.wmf

У задачи с реверсом есть оптимальное решение Eqn80.wmf, для которого выполнено неравенство (30) Eqn88.wmf Следовательно, получаем:

Eqn89.wmf (35)

Для задачи с реверсом в новых переменных Eqn50.wmf, Eqn51.wmf в целевую функцию (11) входят модули величин потоков:

Eqn90.wmf

Комбинируя вместе неравенство (12), (16), (29), получаем, что:

Eqn91.wmf (36)

где величины Eqn92.wmf, Eqn93.wmf вычислены по решению Eqn80.wmf. Из неравенств (36) и (37) так же очевидно следует, что:

Eqn94.wmf (37)

То есть новое решение не хуже решения без реверса. Кроме того, согласно Утверждению 5 решение Eqn92.wmf, Eqn93.wmf является допустимым решением задачи, где поток на дуге i0j0 разделён на два. Таким образом, все ограничения соблюдены, и Теорема 1 доказана для первого случая при добавлении реверса на 1 дугу. Случай 2, когда изначальная задача не имела решения, а после добавления реверса на дугу решение появилось, показан на рис. 2, где приведен один из возможных вариантов данного случая.

Если по условию задачи признак реверса получают несколько дуг, то проводя аналогичные рассуждения можно доказать все утверждения, где в формулировке будут несколько дуг с реверсом. Если дуги с реверсом не имеют общих вершин, то добавляются новые уравнения и доказательства проводятся по той же схеме.

pic_12.tif

Рис. 2. Пример решение задачи с введением условия реверса дуги:а – дуга не реверсивная – решения нет; б – введение реверса дуги дает решение задачи

Пусть также есть реверсивные дуги i0v0 и v0t0 с общей вершиной v0. Обозначим через k1 = k1(v0t0) середину дуги i0v0 и через k2 = k2(v0t0) середину дуги v0t0. Покажем для этого случая схему доказательства на примере Утверждения 5. Уравнение баланса (2) в узле v0 для случая без реверса

Eqn95.wmf (38)

При добавлении признаков реверса уравнение (2) в узле v0 приобретает вид:

Eqn96.wmf (39)

Проверим согласование потока в узле v0, преобразуя равенство (39)

Eqn97.wmf

Eqn98.wmf (40)

Eqn99.wmf

Eqn100.wmf

Теорема доказана.

Осталось заметить, что если в узле сходятся несколько (больше 2) реверсивных дуг, то записывая условие баланса в этом узле и аналогично группируя члены уравнений или неравенств, получаем требуемые утверждения во всех возможных случаях.

Описание метода подключения ГИС для газотранспортной системы

Рассмотрим, для начала, газотранспортную систему без реверсивных дуг. Пусть на некоторых дугах имеются газо-измерительные станции – ГИС. В результате проведения замеров на дугах могут быть либо точные данные потока газа, либо значение в диапазоне. Задача: найти оптимальное по заданному критерию распределение газа с учетом новых условий замеров на ГИС. Определим вектор {gmsTij}, который для некоторых дуг, где есть ГИС, равен 1, а остальные координаты равны 0. Идея решения в том, что ставятся ограничения на значения переменных, которые моделируют поток. Рассмотрим два случая.

Случай A. Значение потока на дуге имеет постоянное (не отрицательное) значение, обозначается gmsij. В виде формул это можно записать так:

xij = + gmsij. (41)

Используя описанное выше соответствие индексов T, имеем

T: gmsij = gmsT(ij) → gmsl;

T: gmsTij = gmsTT(ij) → gmsTl. (42)

Поэтому условие на ГИС можно задать так:

Eqn101.wmf (43)

где li есть некоторое подмножество множества номеров дуг.

Пусть число дуг с ГИС равно Z. Тогда i = 1, 2, ..., Z. И вектор длины n:

Eqn102.wmf (44)

где единицы стоят на местах с номерами li, и n – число дуг.

Равенства для нашего метода следует заменить на два неравенства:

Eqn103.wmf Eqn104.wmf (45)

По условию задачи ГИС могут быть в начале или в конце дуги. Вектор GIEl обозначает, где находится ГИС: в начале дуги – координата равна 0 или в конце дуги – координата равна 1. Математически это можно записать так:

1) ГИС в начале дуги: Eqn105_1.wmf

2) ГИС в конце дуги: Eqn105.wmf

Тогда

1) Eqn103.wmf Eqn104.wmf

2) Eqn106.wmf Eqn107.wmf

В матричном виде:

Eqn108.wmf или Eqn109.wmf (46)

где Eqn110.wmf – матрица размера 2×n и li столбец не нулевой,

Eqn111.wmf

или

Eqn113.wmf

Обозначим через Dgms матрицу размера (2∙Z)×n вида

Eqn114.wmf

а через Eqn115.wmf – обозначим вектор

Eqn116.wmf,

где y ∈ {b, e}.

Случай B. Значение (положительное) потока на дуге задаётся значением и диапазоном, обозначается Devij . В виде формул это можно записать так:

0 ≤ + gmsij – Devij∙gmsij ≤ xij ≤ + gmsij + Devij∙gmsij. (47)

В этом случае задано, что 0 ≤ Devij ≤ 1.

Используя описанное выше соответствие индексов T, имеем

T: Devij = DevTij → Devl. (48)

Поэтому условие на ГИС можно задать следующим образом:

Eqn118.wmf

Eqn119.wmf (49)

Для нашего метода неравенства:

Eqn118.wmf

Eqn120.wmf (50)

3) ГИС в начале дуги:

Eqn121.wmf

4) ГИС в конце дуги:

Eqn122.wmf

Тогда

3) Eqn123.wmf

Eqn124.wmf

4) Eqn125.wmf

Eqn126.wmf

В матричном виде получаем:

Eqn127.wmf или Eqn128.wmf (51)

где

Eqn129.wmf

или

Eqn130.wmf

Обозначим через Dggms матрицу размера (2∙Z)×n вида:

Eqn131.wmf

а через Eqn132.wmf – обозначим вектор

Eqn133.wmf,

где y ∈ {b, e}.

Теперь можно поставить задачу линейного программирования, которая учитывает метрические характеристики потока, задавая матрицу

Eqn134.wmf,

вектор

Eqn135.wmf

и вектор линейной формы Eqn136.wmf.

Перейдем к рассмотрению случая с реверсивными дугами. Нам придётся учитывать знак потока дуги. Знак « + » означает, что поток течёт из начала в конец, знак «–» поток течёт из конца в начало. Также будем учитывать ГИС в начале или конце. Суть метода – поставить ограничения на новые дуги, чтобы потоки на дуге с реверсом совпадали с потоком на новых дугах, то есть моделируется поток на реверсивной дуге.

Случай A. Знак потока « + ». Поток совпадает с начальным направлением. Пусть l принимает значения номеров всех дуг.

Если дуга в старой нумерации не реверсивная, тогда используя «старую» матрицу шифратор найдем двойной номер ij = ij(l) и в «новой» матрице смежности в ячейке с номером ij берём значение r. После этого присваиваем Eqn137.wmf Eqn138.wmf Eqn139.wmf В итоге перебираем n – M «старых» дуг, и n – M новых дуг.

Если дуга в старой нумерации суть реверсивная, тогда используя двойной номер ij = ij(l) по матрице «биекции» находим номер k = k(ij) фиктивной вершины.

Случай A. 1. ГИС в начале дуги.

В «новой» матрице смежности из ячеек с номерами ik, kj, jk, ki берём последовательно значения и присваиваем

Eqn140.wmf Eqn141.wmf

Eqn142.wmf Eqn143.wmf

Eqn144.wmf Eqn145.wmf

Eqn146.wmf Eqn147.wmf

Eqn148.wmf Eqn149.wmf

Eqn150.wmf Eqn151.wmf (52)

Случай A 2. ГИС в конце дуги.

Eqn152.wmf Eqn153.wmf

Eqn154.wmf Eqn155.wmf

Eqn156.wmf Eqn157.wmf

Eqn158.wmf Eqn159.wmf

Eqn160.wmf Eqn161.wmf

Eqn162.wmf Eqn163.wmf (53)

Случай AA. Знак потока может быть и « + » и «» на реверсивных дугах. Знак потока « + ». Совпадает с начальным направлением. Знак потока «». Поток течёт в противоположную сторону от начального направления. (Если знак « + » этот случай описан выше.)

Случай AA. 1. ГИС в начале дуги. Знак потока «» на реверсивной дуге.

Eqn164.wmf Eqn165.wmf

Eqn166.wmf Eqn167.wmf

Eqn168.wmf Eqn169.wmf

Eqn170.wmf Eqn171.wmf

Eqn172.wmf Eqn173.wmf

Eqn174.wmf Eqn175.wmf (54)

Случай AA. 2. ГИС в конце дуги. Знак потока «» на реверсивной дуге.

Eqn176.wmf Eqn177.wmf

Eqn178.wmf Eqn179.wmf

Eqn180.wmf Eqn181.wmf

Eqn182.wmf Eqn183.wmf

Eqn184.wmf Eqn185.wmf

Eqn186.wmf Eqn187.wmf (55)

Случай B. Знак потока « + ». Поток совпадает с начальным направлением. Значение ГИС может учитываться в диапазоне.

Случай B. 1. ГИС в начале дуги. Нижняя граница диапазона больше 0.

Eqn188.wmf Eqn189.wmf

Eqn190.wmf Eqn191.wmf

Eqn192.wmf Eqn193.wmf

Eqn194.wmf Eqn195.wmf

Eqn196.wmf Eqn197.wmf

Eqn198.wmf Eqn199.wmf

Eqn200.wmf Eqn201.wmf

Eqn202.wmf Eqn203.wmf (56)

Случай B 2. ГИС в конце дуги. Нижняя граница диапазона больше 0.

Eqn204.wmf Eqn205.wmf

Eqn206.wmf Eqn207.wmf

Eqn208.wmf Eqn209.wmf

Eqn210.wmf Eqn211.wmf

Eqn212.wmf Eqn213.wmf

Eqn214.wmf Eqn215.wmf

Eqn216.wmf Eqn217.wmf

Eqn218.wmf Eqn219.wmf (57)

Случай BB. Знак потока может быть и « + » и «» на реверсивных дугах.

Знак потока « + ». Поток совпадает с начальным направлением. Знак потока «». Поток течёт в другую сторону от начального направления. Если знак « + » этот случай описан выше.

Случай BB 1. ГИС в начале дуги. Знак потока «» на реверсивной дуге. Нижняя граница диапазона больше 0 по модулю.

Eqn220.wmf Eqn221.wmf

Eqn222.wmf Eqn223.wmf

Eqn224.wmf Eqn225.wmf

Eqn226.wmf Eqn227.wmf

Eqn228.wmf Eqn229.wmf

Eqn230.wmf Eqn231.wmf

Eqn232.wmf Eqn233.wmf

Eqn234.wmf Eqn235.wmf (58)

Случай BB 2. ГИС в конце дуги. Знак потока «» на реверсивной дуге. Нижняя граница диапазона больше 0 по модулю.

Eqn236.wmf Eqn237.wmf

Eqn238.wmf Eqn239.wmf

Eqn240.wmf Eqn241.wmf

Eqn242.wmf Eqn243.wmf

Eqn244.wmf Eqn245.wmf

Eqn246.wmf Eqn247.wmf

Eqn248.wmf Eqn249.wmf

Eqn250.wmf Eqn251.wmf (59)

В результате, заданы все n + 3∙M∙(n + M) значений для векторов Eqn252.wmf Eqn253.wmf Eqn254.wmf Eqn255.wmf и задача сведена к предыдущему случаю, где нет реверса.

Постановка задачи линейного программирования для решения симплекс методом завершена.

Заключение

Метод, изложенный в данной работе, позволяет производить постановку разных потоковых задач в зависимости от топологии рассматриваемой газотранспортной системы и граничных условий. В статье обоснована возможность постановки задачи для решения симплекс методом [2, 3] с добавлением признака дуги и с учетом замеров реально проходящего газа через газопроводы. Разработанный метод многовариантен и позволяет оперативно решать наиболее актуальные задачи потоковых комплексов.

Выражаем благодарность В.М. Простокишину за внимание к работе и конструктивное обсуждение.