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

На правах рукописи

ЧЕРМЕНЕВ Дмитрии Александрович

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

Специальность: 05.13.18 - Математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

13 ФЕВ 2014

Воронеж — 2014

005545046

Работа выполнена в ФГБОУ ВПО «Воронежский государственный технический университет»

Научный руководитель Леденева Татьяна Михайловна,

доктор технических наук, профессор, ФГБОУ ВПО «Воронежский

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

Официальные оппоненты: Баркалов Сергей Алексеевич,

доктор технических наук, профессор, ФГБОУ ВПО «Воронежский

государственный архитектурно-строительный университет», заведующий кафедрой управления строительством, декан факультета экономики, менеджмента и информационных технологий;

Никитин Борис Егорович,

кандидат физико-математических наук, доцент, ФГБОУ ВПО «Воронежский государственный университет инженерных технологий», доцент кафедры

информационных технологий моделирования и управления

Ведущая организация ФГБОУ ВПО «Липецкий государственный

технический университет»

Защита состоится «3» марта 2014 г. в 1300 на заседании диссертационного совета Д.212.037.01 ФГБОУ ВПО «Воронежский государственный технический университет» по адресу: 394026, г. Воронеж, Московский просп., 14

С диссертацией можно ознакомиться в научно-технической библиотеке < ФГБОУ ВПО «Воронежский государственный технический университет».

Автореферат разослан «27» декабря 2013 г.

Ученый секретарь диссертационного совета

Барабанов Владимир Федорович

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Важная особенность процессов принятия решений при реализации крупных проектов заключается в необходимости учета факторов неопределенности, порождаемых как влиянием внешней среды, так и использованием приближенной информации, в частности, полученной от экспертов. Продолжительное время классическим способом учета неопределенности являлась теория вероятностей. Отличительной особенностью планирования проектов и процессов с вероятностным временем выполнения операций является статистический подход к определению временных параметров модели. Основное предположение заключается в том, что время выполнения операции является случайной величиной, имеющей ß -распределение, что позволяет вычислить вероятность выполнения проекта в заданный срок. Существенным недостатком данного подхода является невозможность получения аналитических выражений для характеристик проекта и невозможность приспособить известные алгоритмы поиска критического пути к вероятностным исходным данным. Другой наиболее известный способ учета неопределенности - применение аппарата нечетких множеств - также нашел свое применение в моделях сетевого планирования (Czamecki М.Т., Dinsmore P.C., Fleming Q.W., Pennypacker J.S., Lientz B.P., Kerzner H., Новиков Д.А., Бурков B.H., Баркалов C.A., Рыбальский В.И., Позняков В.В., Голуб Л.Г. и др.). Основное преимущество данного подхода заключается в возможности построения аналитических выражений для временных характеристик проекта, при этом продолжительность операций задается в виде нечеткого числа, параметры которого оцениваются экспертом или определяются экспериментально. Проблема данного подхода заключается в выборе формы представления нечеткого числа, за счет чего может быть повышена степень адекватности и гибкость моделей, что важно для принятия управленческих решений.

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

Работа выполнена в рамках одного из основных научных направлений ФГБОУ ВПО «Воронежский государственный технический университет» «Вычислительные комплексы и проблемно-ориентированные системы управления».

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

Для достижения этой цели решались следующие задачи.

1. Анализ существующих подходов к расчетам сетевых моделей в условиях неопределенности.

2. Обоснование выбора обобщенных гауссовых чисел, определение для них арифметических операций и операции сравнения.

\

\ \

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

4. Разработка программного комплекса для моделирования сетевых графиков и проведение вычислительного эксперимента.

Методы исследования. При выполнении работы использовались основные положения и методы теории нечетких множеств, теории графов, численных методов, интервального анализа, объектно-ориентированного программирования.

Тематика работы. Содержание диссертации соответствует п. 3 «Разработка, обоснование и тестирование эффективных вычислительных методов с применением современных компьютерных технологий», п. 4 «Реализация эффективных численных методов и алгоритмов в виде комплексов проблемно-ориентированных программ для проведения вычислительного эксперимента», п. 8 «Разработка систем компьютерного и имитационного моделирования» Паспорта специальности 05.13.18 - «Математическое моделирование, численные методы и комплексы программ».

Научная новизна. В диссертации получены следующие результаты, характеризующиеся научной новизной:

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

2) алгоритмы расчета критического и подкритического путей сетевой модели с временами выполнения операций в виде обобщенного гауссова числа, позволяющие выявить такие операции проекта, которые должны быть в полной мере обеспечены ресурсами, и отличающиеся использованием операций интервальной арифметики на каждом а -срезе нечеткого числа;

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

4) алгоритм расчета СЕЯТ-сетевой модели, позволяющий учитывать различные типы входов и выходов для каждого разрешающего узла, отличительной особенностью которого является задание времени выполнения операций в виде обобщенных гауссовых чисел;

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

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

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

Реализация и внедрение результатов работы. Разработанный программный комплекс «Fuzzy Networks Graph» использовался в практической деятельности ОАО «Воронежпроект», а также в организации работы IT-подразделений ООО «Рексофт» (ГК «Техносерв»), Результаты диссертации в форме моделей и алгоритмов используются в учебном процессе ФГБОУ ВПО «Воронежский государственный технический университет» при чтении спецкурсов и выполнении выпускных квалификационных работ.

Апробация работы. Основные положения и результаты диссертации докладывались на следующих научных конференциях и семинарах: Современные проблемы прикладной математики и информатики (Воронеж, 2009), Конференции молодых ученых УМНИК (Воронеж, 2012), XXIV Международной научно-практической конференции «Инновации в науке» (Новосибирск, 2013), XIX Международной научной конференции «Research Journal of International Studies» (Екатеринбург, 2013), Всероссийской конференции «Новые технологии в научных исследованиях, проектировании, управлении, производстве» (Воронеж, 2013).

Публикации. По результатам исследования опубликовано 7 научных работы, в том числе 3 — в изданиях, рекомендованных ВАК РФ. В работах, опубликованных в соавторстве, лично соискателю принадлежат: [1,5] - метод дефаззификации нечеткого числа, [2] - алгоритм нечеткой классификации; [4] -разработка программного комплекса.

Структура и объём работы. Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы из 125 наименований. Основная часть изложена на 120 страницах, содержит 33 рисунка, 21 таблицу.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

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

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

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

¿(А,) = ехр

Я(х) = ехр

л ^

*-я

/

14 2/»'

, х<а,

(1)

, х>а,

где а - модальное значение, - параметры формы для функций Ь[х)

и К(х) соответственно, а',а' - параметры «ширины» нечеткого числа

соответственно слева и справа от модального значения.

Примеры обобщенных гауссовых чисел с различными параметрами формы представлены на рис . 1.

"О 0.5 1 1.5 2

Рис. 1. Семейство обобщенных гауссовых чисел

В отличие от обычного гауссова числа функция принадлежности (1) содержит дополнительный параметр /?, который позволяет регулировать направление и степень выпуклости нечеткого числа. Его можно интерпретировать как степень уверенности в данной оценке, а при больших значениях р значение а целесообразно рассматривать в виде интервала.

а -срез (слабый) обобщенного гауссова числа представляет собой отрезок вида [л^ (а),ха (а)], границы которого имеют следующий вид:

х^(а) = хА(а)-А,(а), х,(а) = х,(а) + АА(а), (2)

где

хМ-аЛо-уЯ-а1 /Л, =

Г.=(-1п «Г-

Учитывая представление (2), а -срез обозначим А° = (.*, (а). Л, (а)^.

Пусть А и В - гауссовы числа с функциями принадлежности вида (1), А" = (;с,(а),ДДа)), Ва =(хв(а),Ав(а)) - их а-срезы (аб[0,1]), с -обычное число. Обозначим

а = (хл (а) - Д, (а)),а = {хл (а)+Д, («)).

Ь = (хв (а) - Ля (а)),Ь = (хв (а) + Дв (а)).

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

/±с=(^(я)±с,Д,(а)), (3)

А'/с = (хм(а)/с, АА(а)/с), (5)

1/А°={1/а,1/а), (6) А" ±В" = (í, (а)±£д(а),Д.1(а) + Дв (а)),

А"-В" = (тт{аЬ; аЬ ;аЬ;аЬ тах\аЪ;аЪ;аЪ;аЬ , (7)

Аа/Ва=((а,а)-(1/Ь,1/Ь)У (8)

Обобщая формулу суммы для п гауссовых чисел, получим

<9>

\ I=1 1=1 I

В диссертации предложено несколько способов сравнения обобщенных гауссовых чисел на основе формализованных отношений равенства, нечеткого равенства, приближенного с заданной точностью равенства. Кроме того, для данного типа чисел адаптирован вероятностный подход, согласно которому сравнение интервалов сводится к сравнению вероятностей различных отношений (<,=,>) между ними. Поскольку а-срезы нечетких чисел представляют собой замкнутые интервалы, то в диссертации были выведены формулы для вычисления вероятностей Р(Аа >Ва),Р(Аа <Ва),Р(Аа = Ва) (табл. 1). На основе предложенного способа сравнения обобщенных гауссовых чисел были разработаны процедуры для нахождения максимального МахОаиББ и минимального МтваиБЭ обобщенных гауссовых чисел для заданной совокупности нечетких чисел.

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

Уа1(Р) = а+^-±{а2{-1па1)' ^-а, (-¡па,)""П (10)

2п „,4 '

в основу которой положен подход Ягера-Филева, учитывающий все а-срезы нечеткого числа. Это позволило уйти от интегрирования функций,

включающих функцию принадлежности (1), что предполагается во многих методах дефазификации.

Таблица 1

Вероятности отношений равенства, больше и меньше а -срезов обобщенных гауссовых чисел

Обобщенные гауссовы числа

Несимметричные Симметричные

Ситуация 1

Р(А" < В") , И - Х„ (а)) + (Д, (а) + Д„ (а))]2 1 - ^

4Д,(а)Дй(а)

Р(А" = В") -2

Р(А' > В") 0 0

Ситуация 2

Р(А• < В°) (¿„(а)-*Да)) + (Дя(а)-Л») {Ь-а) + [авуУ* V )

2Д»

Р(А" = В") д ,(«) «Ж

Р(А° > В") (А, (а)-А, («))-(*, («)-*,(«))

2Д„(а)

Ситуация 3

Р(А° < В°) *»(а) + Ма)-а 2Д„(а) Ь-а + сгну 2 <г„У^

Р(А' = В") 0 0

Р(А" > В") а-*„(а) + Д„(а) 2Д» а-Ь + ^уР"

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

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

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

Задача 1 (определение временных параметров). Будем считать, что продолжительность работы (/,_/) задана в виде обобщенного гауссова числа ttJ с функцией принадлежности вида (1). Обозначим через раннее и

позднее времена наступления j'-го события соответственно, полагая, что они также задаются в форме обобщенных гауссовых чисел с функцией принадлежности (1). Для а е (0,7] определим а-срезы перечисленных нечетких

параметров по формуле (2) в виде (^.(а),ДДа)) , (т^^.А^а)} ,

(«) А(,)(«))•

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

1. Начальному событию 1 присвоим раннее время

2. Двигаясь по сети в порядке возрастания номеров вершин-событий, определим раннее время наступления / -го события по формуле

при этом для нахождения max используется процедура MaxGauss.

3. Для конечного события сети N положим

(«) Aw («))=( tm («)-V) ("))' (12>

при этом величину критического пути для данного а -среза определим в виде интервала

К («)=[tm («) - A„w («)+V) (")] • (13)

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

(tw(«) А(о («)>(«И* Aw («)+Д* («))}. (И)

при этом для нахождения используется процедура MinGauss. Для начального события сети должно выполняться условие

(fM W А« («)> = (f»M (°0AW («)> = (0.Д. («)) • (15)

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

Зафиксируем а е (0,/] и рассмотрим /-е событие. Поскольку времена имеют интервальное представление, то для соответствующих интервалов предложены варианты определения отношения равенства.

В случае, если используется отношение четкого равенства, должно выполняться следующее условие:

откуда получим соотношения для параметров обобщенных гауссовых чисел

Т —Т = —

»(О МО 2

д„(0(а)-А,(о(а)=5

40«

I +гт1 Уь'л>) + <7р{ 'У"

(17)

(16)

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

J t(i)(n)-Tp[!)H = Ô(a),

При использовании вероятностного подхода предполагается, что вероятность равенства этих интервалов превышает 0.5.

В диссертации проанализированы условия критичности работы и события. В классическом случае работа (/,_/') является критической тогда и только тогда, когда ее полный резерв равен нулю. В нашем случае интервальное представление полного резерва для фиксированного а е {0,1\ будет иметь следующий вид:

R^u)(«)(«К(«)А(,)(«)+ДИо(Я)+А, («)>- <18>

что обусловливает для каждого а е (0,/] равенстве интервалов, т.е.

Например, для обобщенных симметричных гауссовых чисел выражение ( 19) принимает вид

Т»0ГТ-'

;(0 - 'Ли/^ Но-, ) = {0>ô°v^ ) ' (2°)

откуда получаем следующее условие критичности работы:

Ям, л,А-л,Л

(21)

Задача 2 (определение подкритических путей). Пусть задана величина 8 отклонения работы от критического пути в виде обобщенного гауссова числа. Для каждого ае[0,1] можно определить величину (¿>(а),Д(а)). Все работы,

полный резерв которых не превосходит (£(а),Д(а)), будем называть подкритическими. Они образуют подкритические пути, длина (¿(а),Д(аг)) которых удовлетворяет неравенству

(Гя,(а),Д(а)>-^И,ДИ)2(1(а),А(а))^(ги,(а),Д(а)). (22) Коэффициентом напряженности к^ работы (/.у) называют максимальное

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

(ьу,Л(а) А ("))

отношении вычисляется по формуле 4-——-г-тг. а вероятностный

{К«,Л(а), А, (а))

метод сравнения получаемых нечетких чисел позволяет для каждой работы вычислить коэффициент напряженности. Данный коэффициент характеризует напряженность по срокам выполнения работы. Чем ближе коэффициент напряженности к (1,ДДа)), тем сложнее выполнять эту работу в

установленные сроки, что позволяет оперативно принимать решения.

Задача 3 (оптимизация сетевой модели). Пусть условие Т№ < Тд выполняется, однако за счет резервов времени возможна перестройка плана, приводящая к уменьшению ТКР и сопровождающаяся соответствующими

изменениями продолжительностей работ Пусть {Ьц (а), А,, (а)} - величина

ресурса, выделяемого на выполнение работы (/,/); ,у(а)) - величина

ресурса, переносимого с работы (/.у). Очевидно, что если ресурс в объеме

^ (а),Д,у (а)) переносится с работы (/.у) на работу (И,к) и (хм (а),Ды (а)) -

величина переносимого ресурса, то величины (х,; (а),А,Да)) и {х^ (а),А;; (а))

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

В диссертации получены следующие формулы для пересчета новых продолжительностей работ (/,у) и для каждого а :

= ('„ («)А И(1 +ct (*„ (а),Д„ (а))), (23)

С = ('« (а).Д« (а)) (1-е« (*« («),Дм (а)»,

1 1

гДе c,j =7—

b,j

Задача 4 (расчет GERT-сетей). Обобщениями сетевых моделей являются GERT-сети, отличительной особенностью которых является наличие нескольких типов входов и выходов у каждой вершины, называемых в GERT-сетях узлами. В классическом случае время выполнения операции (/,/) есть случайная величина YtJ. По определению операция (i,j) может быть вьшолнена

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

что узел i выполнен. Пусть случайная величина Ytj задана плотностью fu (х),

со

tnfii{s) = M[e),J ] = J е"/г(x)dx - ее производящая функция моментов. Если

—аэ

время выполнения операции задано в виде нечеткого числа с функцией принадлежности вида (1), то производящую функцию моментов при фиксированном а определим следующим образом:

my¡ (S) = M[e{'Áa)AÁ°b = е<'«МА»> = (24)

В соответствии с правилами расчета GERT-сетей далее определяется

гir I \ ^'«("(АМ) / лД,.(от)\ ,„_.

IV,AS) = Р^V ' = \Р„е ' >P,je ' } ■ (25)

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

получается замкнутый граф. Топологическое уравнение для замкнутых графов, известное как правило Мейсона, имеет следующий вид:

я = = (26)

где — сумма эквивалентных пропускных способностей для всех

возможных контуров длины i.

На основе правила Мейсона вычисляется математическое ожидание времени выполнения GERT-сети. Проведенные вычислительные эксперименты показали приемлемость использования для задания времени выполнения работ обобщенных гауссовых чисел.

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

10

Четвертая глава посвящена особенностям программной реализации системы компьютерного моделирования «Fuzzy Networks Graph».

Программное средство разработано в среде программирования Microsoft Visual Studio 2012 с использованием языка программирования С# и платформы .NET Framework.

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

Подсистема расчета сетевой модели

Модуль определения временных параметров

Модуль определения критических и подкритическ их путей

Модуль оптимизации сетевой модели

^ Подсистема формирования и анализа информации^

Модуль редактирования сетевой модели

Модуль визуализации результатов

Подсистема расчета 1 EP i -сетей

Модуль расчета ГЕРТ-сетей

Библиотека методов для работы с обобщенными гауссовыми нечеткими числами

Редактирование нечетких чисел

Нечеткая арифметика

Интервальная арифметика

Дефаззификация нечетких чисел

Сраанение нечетких чисел

Рис. 2. Структура программного комплекса «Fuzzy Networks Graph»

На разработанный программный комплекс получено свидетельство о регистрации программ для электронных вычислительных машин, баз данных, топологии интегральных микросхем per. № 2012619154 от 10.10.2012.

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

К основным функциональным возможностям программного комплекса относятся: ввод и редактирование информации о времени выполнения операций проекта, редактирование сети, определение временных характеристик сетевой модели, поиск критических и подкритических путей, оптимизация сетевой модели, расчет по методу PERT, расчет ожидаемого времени выполнения GERT-сети.

В качестве исходной информации задается приближенное значение продолжительности работ в виде обобщенного гауссова числа. Для каждого а -среза находится критическое время и соответствующий путь. Результаты расчета для одного из примеров представлены в табл. 2. В зависимости от а получены три критических пути (на рис. 3 они изображены различными линиями). С увеличением а длина интервала, определяющего критическое время, уменьшается. Полученные результаты сравнивались с методом PERT. Результаты расчета по этому методу: сеть содержит единственный критический путь длины 73.

Таблица 2

Результаты вычислительного эксперимента

Значение а для а -среза обобщенного гауссова числа Длина критического пути Критический путь

PERT 73 1-2-3-6-9-11-12-13

а = 0,1 [59,43;92,84] 1-4-11-12-13

а = 0,2 [60,64;85,46] 1-4-П-12-13

а = 0,3 [61,50;81,66] 1-4-11-12-13

а = 0,4 [50,50;90,97] 1-2-3-6-9-11-12-13

а = 0,5 [52,45;88,50] 1-2-3-6-9-11-12-13

а = 0,6 [57,25;83,54] 1-2-3-7-9-11-12-13

а = 0,7 [58,88;82,02] 1-2-3-7-9-11-12-13

а = 0,8 [60,59;80,61] 1-2-3-7-9-11-12-13

а = 0,9 [62,70;79,13] 1-2-3-7-9-11-12-13

а = 0,99 [66,74;76,72] 1-2-3-7-9-11-12-13

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

1.0 -■

л 0.8 •-

■в-

а ад --

0.2 --

о.о —|—i—1—•—I—i—i—1—<—I—.—•—|—1—I—•—•—I—i—|—|—|—I—.—I—.—.—I—I— 40 50 60 70 80 90 100

Оценка

Рис. 3. а -срезы критического времени для примера из табл. 2

Программный комплекс «Fuzzy Networks Graph» использовался для планирования работ по реализации программного проекта (рис. 4).

■i CakulateNetwofk

| Расчитать j а-уссвень —...........-

! Индекс i i Продолжительность interval T рн T po T пн Т по Рп

1 2 5.1.2:4:0.3 [4.25:5.05! [0.0) [4.25:5.05) [-16.43.16.431 1-11.38:20.68) [-16,43:16.43)

2 1 4 23:0.5:2:2:4 [22.72:24.511 [0.01 (22.72.24.51) [-10.76:13,21] 113.75:35.931 1-10.76:13.21]

3 2 3 6:3,4:0,4.0.7 [5,82:580] [4,25:5 05] [10.07.11,85] 1-11,38:20.681 R58:26.5CJ (-16,43.16.43)

4 2 4 7:3:1.0.4:2 [6.82:7,571 [4,25.5.05] (11.07:12,521 [618:29.11] [13.75.35.931 [1.13.24.861

5 3 1 4:1:2:0.4.3 [394:5.37] [10.07:11.35] [14.01:17.22] 13.38:31.99) 113.75:35.93] [-3.4721.92]

6 3 5 18.1 1,0.3.2 [17.98:18.57] [10.07:11.85] [28.05:30.42] 15 30.30.73] |23 87:48.71] [-6.55:20.66) i

7 3 6 14:4.2:3.1 111,25:14.65) [10.07:11.85] [21.32:26.50] 1-6.79:29.09] [7.36:40,34] [-18.64:19.021

8 3 I7 5:1:1,3:2 [4.31:5,571 [10.07:11.85! [14.38:17.42] [-4,58:26.501 1(0.99:30.81) [-16,43:16.43]

9 4 11 29:1:4 2:0.4 [28.43.29.24] [22.72:24.51] (51 15,53,75] I [13.75.35 93] |42.99:64.36] 1-10.76.13.211

та 5 8 16:1.5:0,9.0.3:1.5 [15.96:16.43/ [28.05:30.42) [44,01.46,851 123.87.48,71) , [40,30.64,67) J-6.55.20.66!

11 6 9 13:4.5:3,5 [10.25:16.99] [21.32:26.50] [31.57:43.49! [7.86:40.34] [24,85.50.59! [-18,64.19,021 1

12 6 10 7:2.4:1.9,1 5.0.6 [5.87.7.291 [21.32.26.50] [27.19:33.79] [36.35.61.7Е] [43 64.57 65] [9.35:40.46]

13 7 9 22:3.8.2.5:2.1.3 8 [19.78:23.86! [14,38.17.421 134.16.41.28] [099:30,81] [24,85:50.59] [-16.43:16.431 ■

14 8 10 3.0.3:1 2:0.4:0.9 [2,98:3.34] [44.01:45.85) [46.99:50.19] [40.20:64 67] [43,64 67.65] [-6.55:20 66]

15 8 13 82.4,1 9.1:4 [7.22.9.43) [44.01,46.35) (51,23,56.28] [53.27:71.911 [62.70:79.13] [6.42:27.90] '

16 9 10 5:1,7:2,1:3.0.6 [3.83.5.32) [34.16.41.281 [37,99,46.50] [38 32.63 82] [43.64:67,65] [-2.S5.29.66i

к |1? 9 11 17:4.7:2.3.2:4 113.77:18.14] 134.16 41.28] 147,93:59,42] [24,25 50.59] [42,99 54.36) [-16 4 3.16 431

Рис. 4. Расчет параметров сетевой модели на основе программного комплекса «Fuzzy Networks Graph»

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

2. Разработаны модифицированные алгоритмы расчета критического и подкритического путей сетевой модели, в которой время выполнения операций задано в виде обобщенного нечеткого гауссова числа.

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

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

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

Основные результаты диссертации опубликованы в следующих работах:

Публикации в изданиях, рекомендованных ВАК РФ

1. Леденева, Т. М. Параметрический метод сравнения нечетких чисел [текст] / Т. М. Леденева, Д. А. Черменев, С. С. Жданова // Вестник Воронежского государственного технического университета. - 2010. - Т.6. -№6.-С. 62-66.

2. Леденева, Т. М. Влияние методов дефаззификации на нечеткую классификацию [текст] / Т. М. Леденева, Д. А. Черменев // Вестник Воронежского государственного технического университета. - 2012. - Т.8. -№8. - С. 24-27.

3. Черменев, Д. А. К определению арифметических операций и операций сравнения для обобщенных гауссовых нечетких чисел [текст] / Д. А. Черменев // Системы управления и информационные технологии. - 2013. - №4(54). - С. 74-77.

Свидетельства на программы для электронных вычислительных машин, базы данных, топологию интегральных микросхем

4. Черменев, Д. А. Классификация на основе методов сравнения нечетких чисел / Д. А. Черменев, Т. М. Леденева // ФГБОУ ВПО «ВГТУ» Per. № 2012619154 от 10.10.2012. М.: РОСПАТЕНТ, 2012.

Статьи и материалы конференций

5. Леденева, Т. М. О сравнении нечетких чисел [текст] / Т. М. Леденева, Д. А. Черменев // Актуальные проблемы прикладной математики, информатики и механики: сб. тр. Междунар. конф. - Воронеж, 2009. - С. 21-25.

6. Черменев, Д. А. Использование обобщенных гауссовых чисел при расчете ГЕРТ-сети [текст] / Д.А. Черменев // Инновации в науке: сб. тр. XXIV междунар. заочной науч.-практ. конф. - Новосибирск, 2013. - С. 75-81.

7. Черменев, Д. А. Использование обобщенных гауссовых нечетких чисел при оптимизации сетевого графика [текст] / Д.А. Черменев II Международный научно-исследовательский журнал. - 2013. № 9-1(16). - С. 125-128.

Подписано в печать 27.12.2013 Формат 60x84/16. Бумага для множительных аппаратов. Усл. печ. л. 1,0. Тираж 80 экз. Зак. №301

ФГБОУ ВПО «Воронежский государственный технический университет» 394026, Воронеж, Московский просп., 14

СЕТЕВОЕ МОДЕЛИРОВАНИЕ ПРОЕКТОВ С НЕЧЕТКИМ ВРЕМЕНЕМ ВЫПОЛНЕНИЯ НА ОСНОВЕ ОБОБЩЕННЫХ

ГАУССОВЫХ ЧИСЕЛ

Специальность 05.13.18 - Математическое моделирование, численные

методы и комплексы программ

На правах рукописи

0420*'! 456442

ЧЕРМЕНЕВ Дмитрий Александрович

Диссертация на соискание ученой степени кандидата технических наук

Научный руководитель доктор технических наук, профессор Леденева Т.М.

Воронеж-2014

ВВЕДЕНИЕ..............................................................................................................3

ГЛАВА 1. АНАЛИЗ СУЩЕСТВУЮЩИХ МЕТОДОВ СЕТЕВОГО ПЛАНИРОВАНИЯ......................................................................................................8

1.1. Характеристика проекта и модели планирования и управления................8

1.2. Временные характеристики сетевого графика и алгоритм расчета..........28

1.3. Учет неопределенности при расчете сетевых графиков............................31

1.4. Постановка задачи исследования................................................................32

ГЛАВА 2. НЕЧЕТКИЕ ЧИСЛА, ИХ СВОЙСТВА И ХАРАКТЕРИСТИКИ..34

2.1. Арифметические операции и дефаззификация обобщенных гауссовых нечетких чисел...........................................................................................................48

2.2. Сравнение нечетких обобщенных гауссовых нечетких чисел..................54

ГЛАВА 3. АЛГОРИТМЫ РАСЧЕТА И ОПТИМИЗАЦИИ СЕТЕВОГО

ГРАФИКА С ПРОДОЛЖИТЕЛЬНОСТЯМИ РАБОТ В ФОРМЕ ОБОБЩЕННЫХ ГАУССОВЫХ НЕЧЕТКИХ ЧИСЕЛ.......................................................................61

3.1. Алгоритм расчета критических путей..........................................................61

3.2. Алгоритм расчета подкритического пути....................................................66

3.3. Оптимизация сетевого графика....................................................................69

3.4. Алгоритм расчета СЕЯТ-сети.......................................................................78

ГЛАВА 4. ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ ДЛЯ РАСЧЕТА ПАРАМЕТРОВ

СЕТЕВОЙ МОДЕЛИ.................................................................................................88

4.1. Программная реализация...............................................................................88

4.2. Функциональные блоки программного комплекса.....................................89

4.3. Интерфейсная часть программного комплекса...........................................91

4.4. Результаты и анализ вычислительного эксперимента................................95

ЗАКЛЮЧЕНИЕ....................................................................................................112

СПИСОК ЛИТЕРАТУРЫ...................................................................................113

ПРИЛОЖЕНИЯ...................................................................................................124

Актуальность темы. Важная особенность процессов принятия решений при реализации крупных проектов заключается в необходимости учета факторов неопределенности, порождаемых как влиянием внешней среды, так и использованием приближенной информации, в частности, полученной от экспертов. Продолжительное время классическим способом учета неопределенности являлась теория вероятностей. Отличительной особенностью планирования проектов и процессов с вероятностным временем выполнения операций является статистический подход к определению временных параметров модели. Основное предположение заключается в том, что время выполнения операции является случайной величиной, имеющей ß -распределение, что позволяет вычислить вероятность выполнения проекта в заданный срок. Существенным недостатком данного подхода является невозможность получения аналитических выражений для характеристик проекта и невозможность приспособить известные алгоритмы поиска критического пути к вероятностным исходным данным. Другой наиболее известный способ учета неопределенности — применение аппарата нечетких множеств - также нашел свое применение в моделях сетевого планирования (Czamecki М.Т., Dinsmore P.C., Fleming Q.W., Pennypacker J.S., Lientz B.P., Kerzner H., Новиков Д.А., Бурков B.H., Баркалов C.A., Рыбальский В.И., Позняков В.В., Голуб Л.Г. и др.). Основное преимущество данного подхода заключается в возможности построения аналитических выражений для временных характеристик проекта, при этом продолжительность операций задается в виде нечеткого числа, параметры которого оцениваются экспертом или определяются экспериментально. Проблема данного подхода заключается в выборе формы представления нечеткого числа, за счет чего может быть повышена степень адекватности и гибкость моделей, что важно для принятия управленческих решений.

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

Работа выполнена в рамках одного из основных научных направлений ФГБОУ ВПО «Воронежский государственный технический университет» «Вычислительные комплексы и проблемно-ориентированные системы управления».

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

Для достижения этой цели решались следующие задачи.

1. Анализ существующих подходов к расчетам сетевых моделей в условиях неопределенности.

2. Обоснование выбора обобщенных гауссовых чисел, определение для них арифметических операций и операции сравнения.

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

4. Разработка программного комплекса для моделирования сетевых графиков и проведение вычислительного эксперимента.

Методы исследования. При выполнении работы использовались основные положения и методы теории нечетких множеств, теории графов, численных методов, интервального анализа, объектно-ориентированного программирования.

Тематика работы. Содержание диссертации соответствует п. 3 «Разработка, обоснование и тестирование эффективных вычислительных методов с применением современных компьютерных технологий», п. 4 «Реализация эффективных численных методов и алгоритмов в виде комплексов проблемно-ориентированных программ для проведения вычислительного эксперимента», п. 8 «Разработка систем компьютерного и имитационного моделирования» Паспорта

специальности 05.13.18 - «Математическое моделирование, численные методы и комплексы программ».

Научная новизна. В диссертации получены следующие результаты, характеризующиеся научной новизной:

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

2) алгоритмы расчета критического и подкритического путей сетевой модели с временами выполнения операций в виде обобщенного гауссова числа, позволяющие выявить такие операции проекта, которые должны быть в полной мере обеспечены ресурсами, и отличающиеся использованием операций интервальной арифметики на каждом а -срезе нечеткого числа;

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

4) алгоритм расчета СЕЯТ-сетевой модели, позволяющий учитывать различные типы входов и выходов для каждого разрешающего узла, отличительной особенностью которого является задание времени выполнения операций в виде обобщенных гауссовых чисел;

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

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

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

Реализация и внедрение результатов работы. Разработанный программный комплекс «Fuzzy Networks Graph» использовался в практической деятельности ОАО «Воронежпроект», а также в организации работы IT-подразделений ООО «Рексофт» (ГК «Техносерв»). Результаты диссертации в форме моделей и алгоритмов используются в учебном процессе ФГБОУ ВПО «Воронежский государственный технический университет» при чтении спецкурсов и выполнении выпускных квалификационных работ.

Апробация работы. Основные положения и результаты диссертации докладывались на следующих научных конференциях и семинарах: Современные проблемы прикладной математики и информатики (Воронеж, 2009), Конференция молодых ученых УМНИК (Воронеж, 2012), XXIV Международная научно-практическая конференция «Инновации в науке» (Новосибирск, 2013), XIX Международная научная конференция «Research Journal of International Studies» (Екатеринбург, 2013), Всероссийская конференция «Новые технологии в научных исследованиях, проектировании, управлении, производстве» (Воронеж, 2013).

Публикации. По результатам исследования опубликовано 7 научных работ, в том числе 3 - в изданиях, рекомендованных ВАК РФ. В работах, опубликованных в соавторстве лично соискателю принадлежит: [1,5] - метод дефаззификации нечеткого числа, [2] - алгоритм нечеткой классификации; [4] -разработка программного комплекса.

Структура и объём работы. Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы из 125 наименований. Основная часть изложена на 120 страницах, содержит 33 рисунка, 21 таблицу.

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

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

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

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

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

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

1.1. Характеристика проекта и модели планирования и управления

Из определения, приведенного в [38], следует, что «проект - ограниченное во времени целенаправленное изменение отдельной системы с установленными требованиями к качеству результатов, возможными рамками расхода средств и ресурсов и специфической организацией». К основным параметрам проекта относятся[90]: сроки, стоимость, качество.

По определению из [117]: Управление проектом (УП) или Project Management (РМ) - это искусство руководства и координации людских и материальных ресурсов на протяжении жизненного цикла проекта путем применения современных методов и техники управления для достижения определенных в проекте результатов по составу и объему работ, стоимости, времени, качеству и удовлетворению участников проекта.

Существует несколько различных направлений в теории управления проектами.

1) модели календарно-сетевого планирования и управления [1416,32,39,40,46,51];

2) "качественный" подход к управлению проектами [41,54,56,66,73,85,87,88,91,94-96,106-109,111-116,118,121-123], который близок своей методологией к менеджменту организаций [35,36,71,72];

3) "количественный" подход, который основывается на синтезе и анализе математических моделей и механизмов управления проектами (процедурах принятия управленческих решений) [4,7-10,17-30,33,43,44,57,63,64,67,101].

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

Модели и методы управления

л

о н о>

К

К §

Ч о

«

N Я й га о

Он К И л ч и

Методы распределения ресурса [8,19,28] Механизмы активной экспертизы [19,27,28,83] Механизмы внутренних цен [27,105] Конкурсные модели [19,27] Механизмы обмена [58]

я я

со

К

к

а

(-4

Он

о

ч о н и

Я

Я ч

(Ц

ч о

Механизмы смешанного финансирования [28,63] Противозатратные механизмы [19,27,105] Механизмы «затраты-эффект» [2,15,23,27] Модели агрегирования [7,14,58,76]

Механизмы самоокупаемости [21,23,28]

Модели выбора ассортимента [9,27] Механизмы закупок [9,10]

Оптимизационные модели обменных производственных схем[15]

Модели оптимизации производственного и коммерческого циклов [15] Модели оптимизации структуры [37,47,76,77] Механизмы назначения [28,63]

л

ч о

Й

3

к

Ч О)

ч о

к

я о

Он

я ч

я

а

о

Модели стимулирования [78,79] Методы стимулирования [55,76,78]

Механизмы «бригадной» оплаты труда [78,105] Механизмы стимулирования в матричных структурах управления [47,55,80]

ч о н о 2

я ч о ч о

«

ч

о &

я о и

Модели и методы комплексного оценивания [2,3,28,30,63] Модели и механизмы согласия [28,63] Многоканальные механизмы [19,28] Методы опережающего самоконтроля [17,28] Модели страхования [20,23,28] Компенсационные механизмы [17,28]

Планирование и управление комплексом проектных работ является достаточно сложной задачей с противоречивыми требованиями. При оценке стоимостных и временных параметров выполнения проектов используются различные методы. Среди уже существующих наибольшее значение имеют методы сетевого планирования [53,61,76,82], которые могут успешно и широко применяться при оптимизации планирования и управления сложными разветвленными комплексами работ, которые требуют участия большого количества исполнителей, а также затрат ограниченных ресурсов [5,6,46,53].

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

Введем основные понятия сетевого планирования.

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

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

СПУ основывается на разработанных одновременно и независимо методе оценки и пересмотра планов PERT [61,62,90, 101] (PERT — Program Evaluation and Review Technique) и методе критического пути МКП (СРМ - Critical Path Method) [53, 62,69, 90,101].

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

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

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

При использовании методов и моделей сетевого планирования сокращение сроков реализации новы