О ПРИМЕНЕНИИ СЕТЕВОЙ МОДЕЛИ ДЛЯ АНАЛИЗА ПЛАНИРУЕМОГО ПРОЕКТА

АННОТАЦИЯ

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

ABSTRACT

The purpose of the article is to develop a concept for modeling a planned set of works that, by revealing alternative implementation options based on a certain criterion, identifies the best one. For this purpose, a stochastic network model was put forward, which included a set of interconnected tasks that were characterized by the cost of implementation and the probability of completion. An algorithm is proposed for constructing the best project in terms of cost, time, and a combination of both indicators. Using the constructed network, an analysis and forecast of alternative options for implementing the planned set of interconnected processes was carried out.

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

Keywords: stochastic networks, alternative subnetworks, solution duration, solution probability, solution search, ordering of alternative solutions.

Введение

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

Материалы и методы исследования.

На рисунке 1 каждая вершина относится к определенному типу, вершины 2 и 5 являются дизъюнктивными, вершина 1-конъюнктивна, вершины 3,4,6,7,8 – унарны. Построенная стохастическая сеть позволяет определить альтернативные варианты реализации множества процессов (работ) без знания специальных методов расчёта. Число возможных вариантов 3: {a,b,c,d,e,f};{ a,b,g,h,j,e,f}; {a,b,g,m,n,f}. С точки зрения теории вероятностей каждый из этих вариантов сетевых графиков можно рассматривать как случайное событие [1,2].

Рисунок 1. Стохастическая сетевая модель

Построенные сетевые графики обладают следующими особенностями: 1) миноранта и мажоранта сетевых графиков G_i совпадают с минорантой и мажорантой заданной исходной стохастической сети; 2) ни один из графиков не содержит дизъюнктивных вершин; 3) согласно теории вероятностей, каждый из них является случайным событием. Рассмотрим следующие параметры на стохастической сети: 1) t(x_i,x_j) –продолжительность  задания с номером (x_i,x_j); 2) p(x_i,x_j)– вероятность (частота) появления задания с номером (x_i,x_j). На основе этих данных можно вычислить продолжительность и вероятность каждого сетевого графика. Из литературы [3,4] известны следующие: 1) продолжительность каждого сетевого графика равна продолжительности максимального (критического) пути из входящих в него путей, соединяющих миноранту с мажорантой; - вероятность появления каждого сетевого графика равна произведению вероятностей появления входящих в него заданий. Обозначим стохастическую сеть как G=(X, A), где X — множество вершин, а A -множество дуг. Сетевые графики являются случайными событиями и образуют некоторое множество M={G₁,...,G_q}. Обозначим продолжительность и вероятность произвольного графика G_j через T(G_j) и P(G_j), соответственно, где j=1,2,3, графики отличаются друг от друга значениями этих параметров. Это определяет превосходство графиков друг над другом. Например, оптимальный с точки зрения времени считается график с номером j₀, продолжительность которого оценивается по формуле: , оптимальным  с точки зрения вероятности является график, для которого: . Следовательно, актуально сравнение альтернативных сетевых графиков между собой по рассматриваемым параметрам. Сравнение целесообразно реализовать методом упорядочивания графиков по заданным параметрам. Условные оценки времени работ a,b,c,…представлены в следующей таблице:

Пусть T(i) – продолжительность критического пути сетевого графика с началом в вершине i и концом в s=9, Q_i – множество дуг сетевого графика с началом в вершине i и концом в s=9.

Задача 1. Упорядочивание альтернативных решений по возрастанию их продолжительности.

Для построения подходящего алгоритма сортировки альтернативных решений по возрастанию их продолжительности целесообразно построить её древовидное преобразование (рис.2).  Соответствующее преобразование обозначим через О, построенное дерево через D: D=(Y,B), здесь Y обозначение множества вершин, В-множества дуг на дереве. Отображение О для каждого графика G_j сопоставляет взаимо однозначно ровно одно поддерево D_j:, j=1,2,3.

Рисунок 2. Древовидное преобразование сети, изображенной на рис.1

На рис. 2 вершины построенного дерева обозначены как, т.е. образ вершины на дереве показан спереди, а  прообраз  показан в скобках.  Построение явного дерева D=(Y, B) в процессе рекуррентных вычислений  обусловлено необходимостью того, что удаление кое-каких элементов  из дерева после каждого построения  поддерева D_i не вызывает  препятствий для определения следующего поддерева D_i+1, но в сети сделать это невозможно.

Таким образом, требуется построить такие образы, , что:

 ()

В результате вычислений снизу вверх строится решение  с минимальным временем [1,2]. Для выявления очередного решения  из дерева  удаляются все ненужные элементы, которые на рисунке 2 обозначены черточками,  и т.д.

Задача 2. Упорядочивание альтернативных решений по убыванию их  вероятности.

Требуется определить множество графиков , для которых выполняются неравенства:

Аналогично задаче 2, построим образ заданной стохастической сети в виде стохастического дерева. Обозначим вероятность дерева D_i как P(D_i). Таким образом, задача 2 сводится к следующей задаче:

Требуется построить такие поддеревья   для которых выполняются неравенства: 

.

Методы упорядочивания альтернативных решений подробно изложены в работах [1,2]. При программировании алгоритма сортировки альтернативных решений преобразование сети  на явное дерево может занять много памяти компьютера. Для экономии памяти нет необходимости строить явное дерево, и предпочтительнее строить неявное дерево [5]. Последнее дерево строится поэтапно, как необходимое поддерево явного дерева, по мере необходимости, и используется для последующих вычислений [1,3]. На рис.3 представлены результаты построения альтернативных решений с применением неявного дерева. На неявном дереве для определения перспективной вершины и ее раскрытия применяется оценочная функция по формуле P(i)= P₁(i)⋅P₂(i), где P₁(i) – функция построенная на основе апостериорной информации от начальной вершины до текущей, т.е. вершины с номером i, P₂(i) - функция построенная на основе априорной информации от текущей вершины до мажоранты и оценивает верхнюю границу реального значения вероятности, но от шага к шагу эта оценка подходит к реальной оценке [2,3]. Каждый раз в результате выявления очередного решения с наибольшей вероятностью из текущего дерева выбираются элементы ,  и, удаляются элементы, и .

Рисунок 3. Первый этап сортировки альтернативных решений

На рисунке 3. удалённые элементы отмечены двойными черточками.

Таблица 1.

Результаты упорядочивания альтернативных планов по возрастанию их продолжительностей и убыванию их вероятностей.

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

1. Построить таблицу типа 1;

2. По значениям ,  установить ранги преимущества решений в отдельности по времени RT_i и по вероятности RP_i;

3. По минимальному значению суммы  RT_i+RP_i установить «оптимальное    решение».

Заключение.

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

Список литературы:

1. Керимов В.А. О возможности исследования планируемого эксперимента с использованием графовой модели типа «И/ ИЛИ» Доклады АНА, вып. LXII, № 3-4, Баку, 2006.
2. Керимов В.А. Метод сортировки исходов по уменьшению вероятности их наступления на стохастической сети. Доклады АНА, том LXIV, №1, Баку, 2008.
3. Нильсон Нильс Дж. Искусственный интеллект. Методы поиска решений.-М.: «Мир», 1973.-270 с.
4. Nilsson, Nils J. (1998). Artificial Intelligence: A New Synthesis. Morgan Kaufmann. ISBN 978-1-55860-467-4. Retrieved 28 February 2013.
5. Russell, S. and Norvig, P., 2021. Artificial Intelligence: a modern approach, 4th US ed. University of California, Berkeley, p. 141.