Материал: Проектное управление в строительстве. Баркалов С.А., Бурков В.Н

MECHANISMS OF EVALUATION TEST OF VARIOUS WAYS OF MANAGEMENT

OF THE COMPLEX TECHNICAL SYSTEMS

S.A. Barkalov, A.V. Belousov, Z.B. Tutarishev

Barkalov Sergey Alekseyevich, Voronezh state technical university, Doctor of Engineering, professor, head of the department of management,

Russia, Voronezh, e-mail: sabarkalov@mail.ru, ph.: +7-473-276-40-07

Belousov Alexey Vadimovich, Voronezh state technical university, undergraduate of department of management,

Russia, Voronezh, e-mail: belousov@vgasu.vrn.ru, ph.: +7-473-276-40-07

Tutarishev Zaur Baturbievich, Voronezh state technical university, graduate student of department of management,

Russia, Voronezh, e-mail: upr_stroy_kaf@vgasu.vrn.ru, ph.: +7-473-276-40-07

Аdstract. In this article the ways of feedback control which gained distribution in many technical systems are considered. A priori (prior to functioning) the time schedule control and the basic, or planned trajectory of driving of an object corresponding to it are calculated. The resulting management is formed as the sum of the program and adjusting components which is formed in the course of functioning on the basis of the current information on the revolting influences and on object deviations from a planned trajectory. Formation of the adjusting component is made under any simple law of regulation while for the choice of a program component the difficult optimizing tasks can be solved.

Keywords: task, quality, model, system, management, improvement, functioning

References

1.S.A. Barkalov, V.E. Belousov, N.Yu. Kalinina, T.V. Nasonova. M.A. Fomina, A.V. Leksashov. Model operation of a system of assessment of competences of management of the faculty of higher education institution. The XXI International conference on the soft calculations and measurements (SCM-2018). The collection of reports in 2 volumes. St. Petersburg. On May 23-25, 2018 SPb.: СПбГЭТУ "LETI", SCM'2018 on May 23-25, 2018 T1. - Page 355 – 358.

2.V.E. Belousov. Algorithms of obtaining ordered rules of preference in problems of a decision making when scheduling production programs [Text] / V.E. Belousov, K.I. Nizhegorodov, I.S. Plough//the Scientific VGTU Publishing house magazine "Upravleniye Stroitelstvom", Voronezh, 2019. - No. 1 (14). - Page 105-111.

3.V.E. Belousov. The resource and time analysis in problems of scheduling of the structural enterprises. [Text] / V.E. Belousov, S.A. Barkalov, K.A. Nizhegorodov//Materials of XVI All-Russian school conference of young scientists "Management of larger systems" Tambov (11-13.09.2019), TGTU Publishing house, Tambov, 2019. – T.1. - Page 98-101.

90

УДК 519.714.3

АЛГОРИТМЫ ПОТОКОВОЙ ОПТИМИЗАЦИИ НА СЕТЯХ ПРИ РЕАЛИЗАЦИИ СЛОЖНЫХ ПРОЕКТОВ

А.М. Ходунов

Ходунов Антон Михайлович*, Воронежский государственный технический университет, аспирант кафедры управления,

Россия, г. Воронеж, sbarkalov@nm.ru; 8-473-276-40-07

Рассматриваются основные постановки задач, связанные с потоками в сетях и возможные алгоритмы их решения. Подчеркивается, что достаточно часто возникает задача нахождения не единственного пути из всех возможных путей, задаваемых графом, а определения общего распределения некой физической сущности по всей сети с некоторым критерием. К таким задачам сводится задача распределения продуктового потока, задача распределения транспортного трафика, информационных потоков и т.п. Возможно применение подобного представления и при распределении объемов строительно-монтажных работ, подлежащих выполнению

Ключевые слова: потоки в сетях, максимальный поток, поток минимальной стоимости, алгоритм Форда-Фалкерсона, предпоток, контур отрицательной длины, потенциал вершины

Теория графов зародилась, как область знаний, отражающая «игру гения» при решении отдельных игровых задач. Этим условиям удовлетворяет знаменитая задача о кенигсбергских мостах, получившая в трудах Эйлера элегантное решение в 1736 году. Следующая задача по теории графов была сформулирована более чем через сто лет английским ученым Гамильтоном, и также носила игровой характер. К сожалению, эта задача не имела столь простого и красивого решения, как задача Эйлера, но дала толчок, правда в более поздние времена, для развития приближенных алгоритмов ее решения.

Примерно такой же характер носит и знаменитая теорема о четырех красках, сформулированная еще в 1852 году и доказанная только в 1976 году.

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

Во второй половине XIX век начали стремительно развиваться электротехника и органическая химия. Задачи, свойственные этим отраслям научных знаний уже вполне конкретно требовали применения аппарата, подобного уже существующей теории графов. В результате такого симбиоза Г. Кирхгоф получил достаточно удобное описание электрических цепей. Дальнейшее распространение практического применения теории графов связано с работами английского математика А. Кэли, сумевшего разработать приемлемый аппарат визуализации органических соединений. Его работа заложила основы применения математического аппарата теории графов к проблемам химической кинетики.

Дальнейшее развитие теории графов тесно связано с представлением некой коммуникационной сети в виде графа и возможностью передачи по такой сети какого-то продукта, то есть моделирование продуктопроводов. Как обычно, основная потребность в соответствующей теоретической разработке была порождена военными проблемами. В ходе Второй мировой войны перед США встала задача одновременного логистического обеспечения двух театров военных действий, находящихся практически в противоположных концах света: европейского и тихоокеанского. Математическим изучением проблем, стоящих

© Ходунов А.М., 2020

91

перед планировщиками предстоящих боевых действий, занимался математик Джордж Бернард Данциг.

Результаты его работ позволили в 1951 году описать задачу о максимальном потоке в наиболее общем виде. Но работоспособный алгоритм решения этой задачи был предложен Л. Фордом и Д. Фалкерсоном только в 1955 году и получил название алгоритм расстановки пометок. Но в последнее время его часто называют по именам создателей. В последствии этот алгоритм неоднократно подвергался модификациям: последнее успешное изменение было зарегистрировано в 2010 году.

Таким образом, задача о максимальном потоке является основой целого раздела современной теории графов, поэтому рассмотрим более подробно ее базовые понятия. Для примера рассматривается простая сеть, приведенная на рис. 1 и взятая из классической монографии [1], состоящая из четырех вершин и шести дуг.

В сети имеется один источник – это начальная вершина сети x0 и один сток (конечная вершина заданной сети) z. Около каждой дуги приведены через запятую два значения: пропускная способность данной дуги cij и величина потока по этой дуге φ(xi, xj).

Поток в любой сети должен удовлетворять следующим свойствам:

1. Поток по дуге не должен превышать ее пропускной способности, то есть φ(xi, xj) ≤

cij.

2. Свойство кососимметричности.

φ(xi, xj) = – φ(xj, xi),

то есть поток по дуге может протекать в обе стороны, при этом величина потока в противоположном направлении принимает отрицательное значение. Из этого свойства следует, что в представленной сети отсутствуют петли, то есть φ(xi, xi) = 0, для любой вершины xi.

x1

1,1 3,0

z

1,1

3,0

x2

Рис. 1. Простая сеть

3. Свойство сохранения потока. Поток не должен нигде накапливаться и нигде не создаваться за исключением начальной (источник) и конечной вершины (сток) заданной сети. Формальное условие в этом случае выглядит следующим образом

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

При этом Ф является величиной потока на конечных дугах.

92

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

Формальная запись задачи о максиальном потоке будет иметь следующий вид: необходимо найти максимум функции следующего вида

Анализируя формальную постановку задачи (1) – (3) приходим к заключению о том, что все функции описывающий исходные условия задачи будут линейными, а, следовательно, и сама задача будет относится к классу задач линейного программирования, которая может быть решена стандартными методами. Но есть и другой подход, базирующийся на теории графов, отличающийся большей наглядностью и практичностью. Поэтому остановимся именно на этом подходе.

Для этой цели рассмотрим произвольную дугу, в произвольном графе (k; l), приведенную на рис. 2. Для каждой дуги в графе задается пропускная способность ckl и поток по этой дуге φkl. Алгоритм, предложенный в [Форд] основан на идее последовательного перебора всех вершин графа начиная с начальной, которая по данному алгоритму изначально имеет индекс равный 0 и расстановки пометок у тех вершин, которые позволяют пропустить поток по инцидентному ему ребру.

ckl; φkl

k l

Рис. 2. Произвольная дуга в произвольном графе

При этом возможны следующие случаи:

1.если выполняется условие φkl < ckl, то есть величина потока через рассматриваемую дугу меньше (дуга ненасыщена), ее пропускная способность, то вершина l помечается положительным индексом +k;

2.если выполняется условие φkl = ckl, то есть величина потока через рассматриваемую дугу равна, ее пропускная способность (дуга насыщена), то вершина l не помечается вообще;

3.если выполняется условие φlk > 0, то есть поток через рассматриваемую дугу проходит и его величину можно уменьшить, то вершина l помечается положительным индексом +k;

4.если выполняется условие φlk = 0, то есть поток через рассматриваемую дугу отсутствует и, следовательно, его нельзя уменьшить, то вершина l не помечается вообще;

Если в процессе расстановки пометок была достигнута конечная вершина, сток, то в литературе такая ситуация называется «прорывом», то есть в процессе расстановки пометок нам удалось «прорваться от источника к стоку. Это означает, что существующий поток в рассматриваемой сети можно будет увеличить. Возникает закономерный вопрос на сколько?

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

93

= min(hmin, ckl – φkl),

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

После этого увеличиваем поток по дугам, стираем все пометки у вершин, оставляя только пометку у начальной вершины, истока, и начинаем новую итерацию.

Наконец на определенной итерации возникает ситуация, когда мы не можем достичь конечной вершины графа, то есть стока. Это означает, что прорыв оказывается невозможен. На этом решение задачи заканчивается, так как возникшая ситуация характеризует положение, когда дальнейшее увеличение потока в рассматриваемой сети невозможно. Максимальный поток получен.

У предложенного алгоритма есть одна весьма неприятная особенность: его справедливость доказана только для случая, когда пропускные способности дуг ckl являются целыми числами. В том случае, когда это не так, как показали авторы алгоритма, процедура вычислений может оказаться бесконечной или же давать решение, не удовлетворяющее условиями максимальности. Иначе говоря, на анализируемой сети будет иметься поток, величина которого больше, чем получен по алгоритму. Но принимая во внимание, то обстоятельство, что задача о максимальном потоке является в общем случае задачей линейного программирования, алгоритмы которого устойчиво работают с действительными числами, следует сделать вывод, что должны существовать и алгоритмы нахождения максимального потока при нецелых значениях пропускных способностей дуг.

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

Шаг 1. Из исходной сети удаляются все насыщенные дуги, то есть дуги, поток по которым равен пропускной способности дуги, таким образом каждой удаляемой дуги должно выполняться условие вида φij = cij. На первой итерации решения такие дуги, как правило, отсутствуют, так как по условиям решения начальный поток по дугам принимается, обычно равным нулю, то есть φij = 0.

Шаг 2. На оставшейся сети при помощи традиционного алгоритма ФордаФалкерсона, находим путь, позволяющий увеличить поток в сети и увеличиваем его и переходим к шагу 1. В том случае, когда увеличивающего пути в сети нет, переходим к шагу

3.

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

Алгоритм Форда-Фалкерсона предполагает выполнение на каждом шаге всех свойств потока, что не всегда бывает удобно. Рассмотрим алгоритм проталкивания предпотока, предложенного в 1986 году А. Гольдбергом и Р. Тарьяном. В данном случае на первой стадии алгоритма допускается нарушение свойства сохранения потока по вершинам, то есть поток может накапливаться в вершинах и такие вершины в алгоритме получили название активных. На заключительной стадии алгоритма, используя свойство кососимметричности, накопившийся в вершинах сети избыток потока возвращается обратно в источник.

Ключевым понятием алгоритма является понятие предпотока, который является функцией f(xi, xj), заданной на множестве действительных чисел и удовлетворяющей следующим свойствам:

1. Выполняется условие ограничения пропускной способности дуги f(xi, xj) ≤ cij.

2. Свойство кососимметричности:

94