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

Такая проверка осуществляется путем сканирования вершин, начиная от анализируемой, для которой было нарушено условие вида λi≥di, двигаясь по направлению к начальной вершине. В процессе сканирования подвергаются проверке ребра для которых выполняется соотношение вида λj – λi = lij. При этом каждое ребро анализируется только один раз. Такое движение приводит теоретически к двум результатам: достигается начальная вершина и проверяется совпадает ли расстояние от вершины i до начальной вершины с полученной величиной λi или нет. Если совпадает, то процесс решения продолжается, так как контура отрицательной длины нет. Если же начальная вершина не достигнута, то получили контур отрицательной длины.

К недостаткам алгоритма следует отнести необходимость предварительного выбора величин di, так как именно от этого будет зависеть трудоемкость алгоритма, потому что именно величина di будет определять число проверок на наличие контура.

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

Алгоритмов вычисления кратчайших расстояний в графах достаточно много: алгоритм для графов с правильной нумерацией вершин, алгоритм Форда, алгоритм Дейкстры. В данном случае, учитывая, что веса ребер могут быть согласно формуле (4) отрицательными, наиболее подходящим может быть алгоритм Беллмана-Форда. Вычислительная сложность которого несколько выше: O(VE), чем алгоритма Дейкстры – O(VlogV), но зато он позволяет работать с отрицательными весами ребер, что является основным преимуществом в данном случае

Последовательность операций, выполняемых алгоритмом Беллмана – Форда следующая:

Предварительный шаг. Каждой вершине присваивается расстояние до исходной вершины графа равное бесконечности. Начальной вершине присваивается ноль. То есть 0 = 0, все остальные вершины помечаются индексами i =+ .

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

j – i >lij,

то необходимо рассчитать новое значение индекса конечной вершины j по формуле 'j = i

+lij.

2 шаг. Проверяем, имеются ли в данном графе контуры отрицательной длины. Для этой цели вычисляем для каждого ребра (i, j) соотношение вида

j – i < lij,

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

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

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

100

Основная идея алгоритма основана на случайном выборе ребер, подлежащих стягиванию. Стягивание ребра осуществляется за счет объединения двух вершин, связанных с выбранным ребром, в одну. За счет этой операции происходит уменьшение ребер в нем. Если случайным образом в графе выбрано ребро (u, v), то есть объединяются вершины u и v за счет удаления вершины v, то каждое ребро, инцидентное вершине v, будет заменяться на ребро (u, x). При такой операции преобразованный граф не будет содержать контуров.

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

К недостаткам алгоритма можно отнести необходимость на каждой итерации подсчитывать мощность полученного разреза.

Дальнейшее обобщение задач о потоке в сетях связано с отождествлением графа с некой электрической цепью, в которой ребра – это проводники характеризуемые или сопротивление R, или проводимостью, которая определяется как обратная величина сопротивления, то есть G=1/R, а вершины графа – это соединения проводников. Так как величина тока между узлами в электрической сети всегда пропорциональна разности потенциалов этих узлов, то возникает естественное желание ввести аналогичные величины, характеризующие каждую вершину в графе. Не мудрствуя лукаво эти характеристики так же назвали потенциалами вершин и обозначили qi.

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

дуг иными словами полустепень исхода для этих дуг равна нулю, то естьdi =0. Для каждой

вершины, которая не является стоком задается величина qi которая называется потенциалом вершины. Все вершины, для которых qi>0, являются источниками в рассматриваемой сети. Таким образом, получаем сеть с множеством источников и стоков.

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

qi xl , xj xi, xj ,

где V– и V+ – множество дуг, входящих в вершину и выходящих из вершины соответственно.

Вданной постановке задачи поток в сети не во все моменты времени будет удовлетворять условиям сбалансированности. Исследуются условия стабилизации потока и скорость сходимости процесса.

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

приписывается вес, который на произвольном шаге в момент времени t для дуги (i, j) будет

обозначаться как φtij Причем, в общем случае пропускные способности одного и того же ребра в разных направлениях не одинаковы, то есть φtij ≠ φtji.

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

101

заданы вес дуг φ0ij, которые могут меняться с стечением времени. Начальное распределение весов должно удовлетворять условию

∑φ0ij = qi . xl V-

Что означает, что суммарная величина весовых коэффициентов, входящих в рассматриваемую вершину i, должна равняться величине ресурса, которым располагает данная вершина qi.

Для каждой дуги изначально определена функция весовых коэффициентов cij (φtij, φtji). По известным значениям весовых коэффициентов φtij в момент времени t осуществляется нахождение весовых коэффициентов для следующего момента времени, то есть величин φtij+1

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

maxcij ijt 1, ijt →min,

j V-

∑ijt 1 qi , j V-

ijt 1 0, i, j E.

Решение данной задачи естественно будет зависеть от вида задаваемых функций cij (φtij, φtji). Для некоторых частных случаев были получены соответствующие результаты.

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

Библиографический список

1.Баркалов С.А. Формирование производственной программы строительного предприятия [Текст] / Баркалов С.А., Курочка П.Н., Золотарев Д.Н. // Экономика и менеджмент систем управления / Научно-практический журнал, № 1.1(19) 2016. – с. 110-119.

2.Баркалов С.А. Распределение ресурсов типа мощности на основе обобщения задачи

оредакторе [Текст]/ С.А. Баркалов, П.Н. Курочка, Т.А. Аверина, Д.Н. Золотарев // Вестник Южно-Уральского государственного университета. Серия: Компьютерные технологии, управление, радиоэлектроника, т. 17, №2, 2017. – с. 134 – 140.

3.Новиков Д.А., Бреер В.В., Рогаткин А.Д. Управление толпой: математические модели порогового коллективного поведения. М.: ЛЕНАНД, 2016. – 168 с.

4.Губанов Д.А., Новиков Д.А., Чхартишвили А.Г. Социальные сети. Модели информационного влияния, управления и противоборства. М.: Изд-во физ.-мат. лит-ры, 2010

– 228 с.

5.Курочка П.Н. Оценка надежности организационных структур произвольного вида, задающихся планарным графом / П.Н. Курочка, В.Г. Тельных // Научный вестник Воронеж. гос. арх.-строит. ун-та. Строительство и архитектура. – 2011. – № 3 (23). - С. 134–141.

102

6.Форд Л.Р., Фалкерсон Д.Р. Потоки в сетях: Пер. с англ. – М.: Мир, 1966 – 276 с.

7.Ху Т. Целочисленное программирование и потоки в сетях. – М.: Мир, 1974. – 520 с.

NETWORK OPTIMIZATION ALGORITHMS FOR NETWORKS

IN THE IMPLEMENTATION OF COMPLEX PROJECTS

A.M. Khodunov

Khodunov Anton Mikhailovich *, Voronezh State Technical University, graduate student of the Department of Management,

Russia, Voronezh, e-mail: sbarkalov@nm.ru, tel. 8-473-276-40-07

The main problem statements related to flows in networks and possible algorithms for their solution are considered. It is emphasized that quite often there is a problem of finding not a single path from all possible paths set by the graph, but determining the General distribution of a certain physical entity over the entire network with a certain criterion. These tasks include the distribution of product flow, the distribution of transport traffic, information flows, and so on. it is Possible to use this representation when distributing the volume of construction and installation work to be performed

Keywords: flows in networks, maximum flow, minimum cost flow, Ford-Fulkerson algorithm, preflow, negative length contour, vertex potential

References

1.Barkalov S. A. Formation of the production program of the construction enterprise [Text]

/Barkalov S. A., Kurochka P. N., Zolotarev D. N. / / Economics and management of management systems / Scientific and practical journal, no. 1.1 (19) 2016. - pp. 110-119.

2.Barkalov S. A., Kurochka P. N., Averina T. A., Zolotarev D. N., Distribution of resources of the power type based on generalization of the information about the editor [Text]. Vestnik of the South Ural state University. Series: Computer technologies, control, radio electronics, vol. 17, no. 2, 2017. – p. 134 – 140.

3.Novikov D. A., Breer V. V., Rogatkin A.D. crowd Control: mathematical models of threshold collective behavior. Moscow: LENAND, 2016. - 168 p.

4.Gubanov D. A., Novikov D. A., Chkhartishvili A. G. Social networks. Models of informational influence, management, and confrontation. Moscow: Publishing house of physics. litry, 2010-228 p.

5.Kurochka P. N. Assessment of the reliability of organizational structures of any kind, set by a planar graph / P. N. Kurochka, V. G. Telnykh / / Scientific Bulletin of Voronezh. state arch.- builds. UN-TA. Construction and architecture. - 2011. - No. 3 (23). - Pp. 134-141.

6.Ford, L. R., Fulkerson, D. R. Flows in networks: TRANS. – M.: Mir, 1966 – p. 276

7.Hu T. Integer programming and threads in networks. - Moscow: Mir, 1974. – 520 p.

103

НАУЧНЫЕ РАБОТЫ СТУДЕНТОВ И МАГИСТРАНТОВ

УДК 005.64

ЭТАПЫ ПРИМЕНЕНИЯ МЕТОДА ЭКСПЕРТНЫХ ОЦЕНОК В ОПРЕДЕЛЕНИИ УРОВНЯ УПРАВЛЕНИЯ КАЧЕСТВОМ СТРОИТЕЛЬНОГО ПРОЕКТА

Е.В. Баутина, О.И. Харитонова, Е.А. Агапонова

Баутина Елена Владимировна, Воронежский государственный технический университет, кандидат технических наук, доцент кафедры управления,

Россия, г. Воронеж, e-mail: bautina_elena@mail.ru, тел.: +7-910-249-22-93

Харитонова Ольга Ивановна, Воронежский государственный технический университет, старший преподаватель кафедры «Системы управления и информационные технологии в строительстве»,

Россия, г. Воронеж, e-mail: haritonova_o_i@mail.ru, тел.: +79507526537

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

Россия, г. Воронеж, e-mail: agaponova.ekaterina@mail.ru, тел.: +7-961-614-69-90

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

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

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

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

© Баутина Е.В., Харитонова О.И., Агапонова Е.А., 2020

104