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

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

Воронцов Ярослав Александрович

МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ ЗАДАЧ ВЫБОРА С РАСПЛЫВЧАТОЙ НЕОПРЕДЕЛЕННОСТЬЮ НА ОСНОВЕ МЕТОДОВ ПРЕДСТАВЛЕНИЯ И АЛГЕБРЫ НЕЧЕТКИХ ПАРАМЕТРОВ

05.13.18 — математическое моделирование, численные методы и комплексы программ

Автореферат диссертации на соискание учёной степени кандидата физико-математических наук

Воронеж — 2015

1 АПР 2015

005566739

Работа выполнена в Федеральном государственном бюджетном образовательном учреждении высшего профессионального образования «Воронежский государственный университет»

Научный руководитель:

доктор технических наук, профессор Матвеев Михаил Григорьевич

Официальные оппоненты:

Блюмин Семён Львович,

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

Аиисимов Дмитрий Николаевич,

кандидат технических наук, доцент, Московский энергетический институт, кафедра управления и информатики, доцент

Ведущая организация:

Тверской государственный технический университет

Защита состоится «20» мая 2015 г. в 15 часов 10 минут на заседании диссертационного совета Д 212.038.020 при Федеральном государственном бюджетном образовательном учреждении высшего профессионального образования «Воронежский государственный университет» по адресу: 394006, г. Воронеж, Университетская пл., д. 1, ауд. 333.

С диссертацией можно ознакомиться в научной библиотеке Воронежского государственного университета и на сайте http://www.science.vsu.ru/disser.

Автореферат разослан марта 2015 года.

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

математических наук, ... _ _ „ ,

Шабров Сергеи Александрович

доцент

Общая характеристика работы

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

Фаззификация известных ранее классических задач и создание новых нечётких моделей привела к необходимости разработки новых методов решения, позволяющих применять экспертные оценки на различных этапах моделирования. В работах известных зарубежных (D. Dubois, R. Fuller, A. Prade, R. Yager, L. Zadeh, H. Zimmermann и др.) и отечественных (В. Г. Балашов, А. Н. Борисов, В. В. Борисов, В. В. Крутлов, С. Л. Блюмин, А. А. Усков и др.) учёных и исследователей рассмотрено и проанализировано множество применений результов теории нечётких множеств и мягких вычислений к решению задач выбора, управления и принятия решений. Обратной стороной использования моделей с нечёткостью стало возникновение противоречий между решениями, полученными с применением новых методов, и результатами классических теорий, потеря устойчивости решений, нарушение естественных отношений в моделях, в которых нечёткими являются только параметры, неоправданное расширение степени нечёткости результата, повышение вычислительной сложности задач.

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

Диссертационная работа выполнена в рамках одного из основных научных направлений Воронежского государственного университета «Разработка моделей, методов и алгоритмов обработки информации для создания информационных технологий и систем нового поколения» (№ гос. регистрации 01201263910).

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

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

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

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

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

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

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

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

1. Предложена и исследована модель представления расплывчатых числовых оценок в классе треугольных 1Л-чисел, отличающаяся модификацией нечёткого 1И-числа, основанной на применении предложенного Ь-преобразования 1Л-чисел в соответствующие ЬЬ/Ш1-числа.

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

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

Достоверность научных результатов. Научные положения, теоретические выводы и практические рекомендации обоснованы корректным использованием вы-

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

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

Реализация и внедрение результатов работы. Разработанный программный комплекс «CSBusinessGraph» используется в практической деятельности по первоначальной оценке проектов ООО «Философт» (DataArt). Результаты диссертации в форме моделей, алгоритмов и программ используются в производственном процессе ООО «Философт», что подтверждается актом о внедрении. Признана целесообразность использования предложенной в диссертации методики для оптимизации процедур первоначальной оценки проектов по разработке программного обеспечения.

Апробация работы. Основные результаты работы докладывались на ежегодных научных сессиях Воронежского государственного университа и следующих конференциях различного уровня: международная конференция «Современные проблемы прикладной математики, теории управления и математического моделирования» (Воронеж, 2012 г.); международная конференция «Информатика: проблемы, методология, технологии» (Воронеж, 2013-2014 гг.); международный научно-технический семинар «Современные технологии в задачах управления, автоматики и обработки информации» (Алушта, 2013-2014 гг.); научно-техническая конференция студентов и аспирантов «Радиоэлектроника, электротехника и энергетика» (Москва, 2014).

Публикации. По теме диссертационного исследования опубликовано 11 научных работ [1]- [11], в том числе 4 [5,6,10,11] — в изданиях, рекомендованных ВАК РФ. В работах, выполненных в соавторстве: в [5] предложено преобразование L и алгебра модифицированных нечётких чисел; в [6] выполнен анализ существующих методов сравнения нечётких чисел и предложен метод сравнения для модифицированных LL/RR-чисел; а в [10] — предложено определение устойчивости задачи нечёткого линейного программирования и разработан алгоритм решения задачи календарно-сетевош планирования и управления с нечёткими параметрами, позволяющий получать устойчивое решение.

Объем и структура работы. Диссертация состоит из введения, четырех птав, заключения и списка литературы. Полный объем диссертации 158 страниц текста с 16 рисунками и 3 таблицами. Список литературы содержит 131 наименование, включая работы автора.

Содержание работы

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

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

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

Вторая глава диссертации посвящена разработке и исследованию методов моделирования и обработки нечетких числовых величин, которые удовлетворяли бы выдвинутым к ним в главе 1 требованиям. Ввиду широкого распространения линейных моделей, исследование проводится для нечётких треугольных чисел. В качестве основной формы представления треугольных чисел в работе выбрана форма (1) в виде границ чётких а-интервалов Ха, а € [0;1], позволяющая быстро переходить к интервальной неопределённости.

хь(а)=т—а+аа

хн(а)=т+Ь—Ъа

дальнейшем при описании исследования.

Рис. 1. Предлагаемая классификация нечётких моделей

Проводится краткий анализ существующих алгебраических методов обработки нечётких чисел, выделяются их достоинства и недостатки с точки зрения применимости в нечётких моделях второго типа. Для преодоления выделенных в главе 1 недостатков существующих методов нечётких вычислений предлагается следующий подход. Исходная задача выбора значения X, удовлетворяющего некоторой функции У = / с нечёткими числовыми параметрами, рассматривается как совокуп-

ность задач с интервальной неопределенностью

1

У = /(х,А)^1}уа = /{Ха,Аа) (2)

а—О

с последующим переходом к детерминированной задаче на каждом а-уровне, для чего внутри интервала Ха выбирается точка ж (а). В диссертации предлагается выбирать значение х(а) с помощью линейного параметрического преобразования Ь х(а) = ЦХа) = А хь{а) + (1 - Х)хя(а). (3)

Для треугольных чисел а; (а) является линейной функцией ввиду линейности х1 (а) и Xя{а). После решения чётких а-уровневых задач полученные результаты у(а) аппроксимируются нечётким числом У* = {у(а)\цу(у) = а }> которое называется модифицированным решением задачи (2).

Предлагаемый подход в своей основе имеет декомпозицию нечётких чисел по а-уровням — происходит переход от использования «полноценных» треугольных чисел к алгебрам для треугольных чисел ЬЬ/Ш1-типа (т.е. таких, у которых один из коэффициентов нечёткости нулевой), и функция принадлежности чисел такого типа является обратной к линейной функции (3), которая определяет точки х(а):

/X-А.(х) = (х{а))"1 (4)

В диссертации вводится ключевое понятие модифицированного нечёткого числа. Модифицированным нечётким числам называется число А*, получаемое из А с помощью преобразования (3) и (4). В работе показано, что модифицированное нечёткое число является числом ЬЬ/ЯЯ-типа, и в дальнейшем для таких чисел используется обозначение х(а), указывающее на механизм их построения с помощью (4).

Исходя из (3) и (4) очевидно, что преобразование Ь сокращает информативность исходной нечёткой величины. Для определения степени потери нечёткой информации исследуются свойства преобразования Ь. Чтобы производить анализ и вычисления в форме, инвариантной к расположению числа на числовой оси, в диссертации предложено представление треугольного числа в виде совокупности следующих параметров:

• длина носителя е^;

• мода гпд;

• степень асимметрии АБд.

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

В работе показано, что запись треугольного нечёткого числа в виде тройки (гПд,с1д,АЗд) эквивалентна введённым ранее способам записи через коэффициенты нечёткости (т;о;6) и точки пересечения с осью Ох (хь',т',хю). При известных степени асимметрии АБд и длине носителя йд, коэффициенты нечёткости определяются по формуле

• й-А-2АБ-А а~ 2

Н-.4-

Ь=

',¿+2 А£>д

2

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

Утверждение 1. Преобразование Ь сохраняет моду нечёткого числа. Другими словами, \/Аб[0;1]: тд=т-А..

Утвериздение 2. При некоторых значениях параметра А преобразование Ь сохраняет

1. знак степени асимметрии, т.е. ЭАе[0;1]: згдп(АЗд) = згдп(АЗд.);

2. значение степени асимметрии, т.е. ЗА 6 [0;1]: /15^ = Л5'д,.

Утвервдение 3. Модифицированное число всегда содержится внутри исходного числа. Другими словами, \/А € [0; 1] : Л* С Аа; <1д > йд„ т.е. преобразование Ь уменьшает длину носителя нечёткого числа и оставляет а-интервалы модифицированного числа в рамках а-интервалов исходного числа.

На основании следствий из свойств преобразования Ь, в диссертации даются рекомендации по выбору параметра А и применимости предлагаемой методики:

• при А =-- = — сохраняется значение степени асимметрии. Применение преоб-

а+Ь а-А

разования Ь с этим значением А к нечётким ЬЬ/НП-числам не изменяет их;

• при А =-= — преобразование Ь уничтожает нечёткую информацию, зало-

а+о йд

женную экспертом в число, и сводит операции над числами к операциям над их модами;

• применимость преобразования Ь при использовании симметричных нечётких чис-

а Ъ 1

лах ограничена, поскольку А = —— = —— = -, и все вычисления в этом случае сводятся к операциям над модами чисел.

Для доказательства применимости предложенного подхода в нечётких моделях второго типа, создаётся алгебраическая система для множества всех нечётких модифицированных чисел К = {х(а)}; а£ [0; 1]. Строится чёткая алгебра Р= (К\ +,*); для её построения используется более удобная форма записи модифицированного числа

х(а)=с+ка, (5)

ще

~с=т+Ь—\(а+Ь)

_к = Х(а+Ь) — Ь (6)

Л€[0;1]; с,кеЖ

На множестве К вводится операция сложения (7), а также нейтральный (8) и противоположный по сложению (9) элементы. Доказываются свойства ассоциатив-

ности и коммутативности операции (7).

х\(рс)+х2{а) = г\{а) = С1+С2+(к1+к2)а, Г1(а)еК; (7)

б=0+0аеЛ":У5(а)б^: 5(а)+0=с+£;а!+0+0а=ж(а); (8)

-х(а) = -с-каеК: х(а) + (-х(а)) = 0. (9)

Также на множестве К вводится операция умножения. Её можно было бы определить с помощью (10) как сумму произведений компонент модифицированных нечётких чисел

Х1(а)-Х2(а)=г2(а) = (с1+к1а)(с2+к2а) = С1С2+С1к2а+С2к1а+к1к2а2, (10) однако такое определение приводит к искажению треугольного вида результата нечётких операций, т.е. г2 (а) £ К. Для того, чтобы множество К было замкнутым относительно операции умножения, используется линейная интерполяция — зависимость г2 (а) восстанавливается в виде линейной функции по значениям выражения (10) при а = 0 и а = 1. Это приводит к следующему определению операции умножения:

Г2(а) = С1С2+{с\к2+С2к\+кхк2)а-, г2(а)еК. (11)

Для операции умножения (11) вводятся нейтральный (12) и обратный по умножению (13) элементы. Доказываются свойства ассоциативности и коммутативности, а также свойство дистрибутивности умножения (11) относительно сложения (7). Показано, что для существования обратного элемента число х(а) должно иметь ненулевую моду, поскольку, согласно (6), с+к=тп^0.

1 = 1+0а€К:Ща)еК х{а)Л=х(а); (12)

¿г_1(а) = -—¡Дтга, ст^О; х~\а)еК: 2(а)г_1(а) = 1. (13)

С С\С~т~гС)

В диссертации для модифицированных нечётких чисел показывается эквивалентность записи в виде (5) и в виде

5д(а)=5А(0)+а(5А(1)-2д(0)) = агд(1) + (1-а)5д(0). (14)

На основании (14) предложен способ нечётких вычислений, называемый двухточечными вычислениями, позволяющий решать нечёткую задачу как две чёткие при а=0иа=1. Если обозначить за * произвольную арифметическую операцию, то для чисел в форме (14) её результат будет выглядеть следующим образом:

хд(а)*15(а)=а(гд(1)*гв(1)) + (1-а)(гд(0)*2в(0)). (15)

В диссертации показано, что двухточечные вычисления, описываемые алгеброй <5=(М,П2) с сигнатурой Пг, 1Де М — множество пар действительных значений (х(0),ж(1)), изоморфны введённой ранее алгебре модифицированных нечётких чисел Р= (К£1\) с сигнатурой Г^. Действительно, существует отображение Г: К—^М и

2д(1 ) = с+к; (16)

обратное ему Г 1: М —>• К, описываемые формулами "с=хл(0);

и удовлетворяющее условиям (17>—(18) для бинарных операций ^ е Пь Щ € ГЬ и элементов к\,к2 € К, т^тг £ М:

Г(<рг(к1,к2)) = ф1(Г(к1,к2)); (17)

^(Г-^тьтг)) =Г-1(^(ш1,т2))= (18)

Ввиду (16), множества М и К суть одно и то же, поэтому равенства (17) и (18) после исключения Г и Г-1 доказываются простой подстановкой в общем виде. Переход к двухточечным вычислениям избавляет от необходимости вводить отношение линейного порядка на множестве К и позволяет использовать стандартные программные продукты для решения нечетких задач, т. к. нечеткая задача решается как две чётких.

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

Г /(х) = Сх —> гшп;

\Ах=В,

ще А = — матрица, аВ=|Д|, С=|с,,-| — векторы нечётких парамет-

ров. Применение к каждому из элементов матрицы и векторов преобразования Ь приводит к модифицированной задаче

К ' ' (19)

|чА*х=В*,

в которой А* = |^.(а)|, В* = {хвДа)С* = {%.(<*)}•

При изменении значений а при фиксированных коэффициентах А^ преобразования Ь, происходит возмущение задачи (19). Ввиду свойства сохранения моды, в работе предлагается зафиксировать в качестве «эталонного» решение (19) при а = 1 и использовать определение устойчивости по решению, поскольку оно включает в себя более узкое определение общей устойчивости, т.е. принципиальное существование решения возмущённой задачи. Предполагается, что нечёткая задача будет считаться устойчивой по решению, если при переходе с одного а-уровня на другой не происходит значительного изменения решения в смысле евклидовой метрики, т. е.

У£>0ЭЯ>0Уа1,а2е[0;1] |а!-а2| <<5=> ||х(а1)-х(а2)|| <е. (20) Согласно методике двухточечных вычислений, задачу (19) достаточно решить на двух а-уровнях. Получаемая пара векторов х(а = 1) и х(а = 0) позволяет восстановить модифицированные решения в соответствие с (14). Однако при а = 0 все значения А5, ще 5 — один из индексов Ац, В{, С, — принимают граничные значения (0 или 1). Для решения данной проблемы вводятся дополнительные ограничения для параметров Ад:

(А£-А5)2->1шп (21)

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

ав

устойчивостью решения. Ввиду противоречивости критериев (21) и целевой функции задачи (19), возникает задача векторной оптимизации, для решения которой используется аддитивная свёртка критериев:

Г(х, А) = С*х+7^(АЬА5)2-яшп (22)

я

Семантика целевой функции (22) такова: ищется решение х и вектор параметров А £ преобразования Ь, которые позволяют удовлетворить исходный критерий оптимизации и при этом максимально сохранить нечёткую информацию, заложенную экспертами в параметры задачи. Безразмерный коэффициент 7 позволяет привести значение свёртки к одному порядку со значением исходной целевой функции.

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

В качестве модели проекта в сетевом планировании рассматривается направленный ациклический граф (3 = {У,Е), V =п, \Е\=т, в котором работам проекта IVдлительностью т) каждая, сопоставлены дуги графа е= 1 ,т, а событиям проекта гг с временами наступления £г- сопоставления вершины графа Уг, г = 1,7г. Событие 2х — начало работ по проекту, событие гп — окончание проекта. Граф (? обладает следующими свойствами:

• существует ровно одна вершина ь>1 <Е V, называемая истоком, из которой рёбра только исходят, т.е. \/г=2,п ^(«,',«1);

• существует ровно одна вершина уп £ V, называемая стоком, в которую рёбра графа только входят, т.е. Уг = 1,гг—1 ^(г>п,г>г);

• для любой вершины графа Уг € V, г = 1 ,п существует путь ...уп, проходящий через неё;

• для любого ребра е^ 3 = 1,т существует путь И1...уп, содержащий это ребро.

Задача сетевого планирования сводится к поиску общего времени выполнения проекта Т, которое равно длине максимального пути в графе, называемого также критическим. Соответственно, операции, которые принадлежат пути максимальной длины, также называются критическими. В диссертации указано, что алгоритмический метод решения задачи сетевого планирования (модифицированные алгоритмы Дейкстрьг и Форда-Мура-Беллмана) не позволяет проводить её анализ на устойчивость, т.е. на изменение критического пути. В качестве основного способа решения выбрано решение задачи линейного программирования (23) с нечёткими временными оценками

Т=^-(1-Яшп (23)

при ограничениях на времена наступления событий

в = 1,т, (24)

ще и — времена наступления событий начала и окончания работы ги8 соответственно. В результате решения данной задачи получается общее время выполнения проекта Г и совокупность критических операций Эх.

Для решения задачи (23)-{24), в работе применяется преобразование Ь и методика двухточечных вычислений. Формулируется задача для произвольного а-уровня

\Т(а)

Результатом решения задачи (25) является вектор времён t (а) = {¿о(а),...А(а)}; который является календарным планом а-уровня, а также множество критических операций 51 (а). Нечеткость оценок т, обуславливает проблему устойчивости решений задачи (25) в смысле (20). Очевидно, что если на всех а-уровнях критический путь не изменяется и проходит по одним и тем же дугам, то решение устойчиво. В связи с этим в работе в качестве метрики сходства решений выбрана мощность симметрической разности двух множеств критических операций: Уаьа2е[0;1]; о^оа 51(а1)Д52(а2) = 0, (26)

Полученное при а = 1 решение задачи (25) даёт активные ограничения на критические операции. Для управления устойчивостью решения параметры Л необходимо включить в целевую функцию, подобно (22). В итоге при а = 0 решается видоизменённая задача

5=1 (27)

(л,-и. > т3{а,Х3), Уй 51 (1),в = 1,77г.

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

1. Решается невозмущённая задача (25) при а= 1. Ввиду свойства 1 преобразования Ь, это решение соответствует модифицированному решению (Т(1),£(1),51(1)). Фиксируется множество операций 51(1), образующих критический путь.

2. Фиксируется критический путь при всех а^ 1. Для этого в задаче (25) нестрогие неравенства меняются на равенства \/в1 € 51 (1), т. е. выбранные операции всегда будут критическими. Данный шаг позволяет выполнить условие устойчивости задачи по решению (26).

3. Решается возмущённая задача (27) с изменённой целевой функцией. Результатом решения задачи является кортеж (Т(0),£(0),А), где А — вектор параметров преобразования Ь.

4. Решение исходной задачи представляет из себя тройку (т,5\,Х^. Функция принадлежности общего времени выполнения проекта Т восстанавливается по значениям Т(0) и Т(1), либо число Т оставляется в виде (5).

Предложенный алгоритм иллюстрируется на примере проекта, заданного таблицей 1.

Таблица 1. Оценки длительностей операций проекта и их взаимосвязи

Операция Предш. операции а m b Преобразование L А*

А - 1 2 3 тлН = Ал(1+а)+(1-Ал)(5-За) 1/4

В - 2 4 1 тв(а) = Ав(2+2а) + (1-Ав)(5-а) 2/3

С А 4 7 2 тс(а) = Ас(3+4а)+(1-Ас)(9-2а) 2/3

D В 2 6 3 ?о(а) = Ая(4+2о:) + (1-Ав)(9-За) 2/5

Е В 1 10 2 тЕ(а) = АЕ(9+а)+(1-АЕ)(12-2а) 1/3

F С 1 5 1 fF(a) = AF(4+a)+(l-AE)(6-a) 1/2

G D,E 4 5 1 fG(a) = AG(l+4a)+(l-AG)(6-a) 4/5

Н F,G 2 4 3 ?я(а) = Ая(2+2а)+(1-Ая)(7-За) 2/5

Для решения задачи использовалась надстройка «Поиск решения» в Microsoft Excel (рис. 2). При а = 1 решение задачи (25) привело к результату Т(1) = 23, í(l) = {0;7;4;14;14;14;19;23}, Sx{ 1) = {B,E,G,H}. При а = 0 решалась задача (27), которая при а = 0 приняла вид

я

nO)=í8-í1+7^(A:-As)2->min (28)

s=A

í3-íi = 5-3AB Í6-Í2^9-6Ac Í4-Í3^9-5Ad - Í5-Í3 = 12-3A£; (29)

t7-t6^6-2XF Í7-Í5 = 6-5Ag ts-t7 = 7-5XH

Значение 7 выбирается порядка 10, чтобы соответствовать максимальному значению ттал:. В результате решения задачи (28) при ограничениях (29) получается, что Т* (0) = 20,83, t (0) = {0; 4,23; 2,96; 13,92; 13,92; 9,97; 15,79; 20,67}, Si(0) = {B,E,G,H}, А = {0,25; 0,68; 0,67; 0,4; 0,35; 0,5; 0,83; 0;43}.

На основании решений при а = 1 и а = 0 формируется окончательный результат: критический путь Si = {B,E,G.H}, нечёткое время выполнения Т(а) = 20,67+2,33а.

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

1 2 а 8 с d E F g H I i k m....... .........n........!

Операция XL m Параметры XR А В Лямбда идеал Тау(Альфа) ^ Лям6дапоиск Tay( Альфа) Гамма 0 100 Лямбда diff

3 А 1 2 5 1 3 0,2500 2 LA 0.2500 3,99999708 LA 0,0000

4 8 2 4 5 2 1 0,6667 4 LB 0,6817 2,9550035 LB 8 0,0002

5 С 3 7 9 4 2 0,6667 7 LC 0.6667 4,99999766 LC С 0,0000

6 0 4 6 9 2 3 0,4000 6 LD 0,4000 7,00000351 LD D 0,0000

7 Е 9 10 12 1 2 0,3333 10 LE 0,3483 10,9S50016 LE 0,0002

8 F 4 5 6 1 1 0,5000 5 LF 0,5000 5,00000421 LF Q,00q0

9 10 6 1 2 5 6 4 7 4 1 2 3 0,8000 0,4000 5 LG 4 LH 0,8250 0,4250 1,87500284 4,8750047 LG G H 0,0006 0,0006 0.0000

11 Ф1 0 0 0 0 0 0,0000 0 LOI 0,0000 0: LOl'-LOl

12

13 События Время Резерзы Оптимум События Время Условия Резервы Оптимум

14 0 2-tl>tauA 7 5 23 0,0090 t2-tl>tauA 4,2195 0,2195 20,83001

15 7.t3-tl>tauB 4 0 4,2285 t3-tl=tau8 2.95S0 0,0000

16 4 6-t2>tauC 7 0 2,9640 t6-t2>tauC 5,7413 0,7413

17 14t4-t3>tauD 10 4 13,9190 t4-t3>tauD 10,9550 3,9550

18 14 tS t3>tauE 10 0 13,9190 t5-t3«tauE 10,9550 0,0000

19 14 t7-t6>tauF 0 9.9698 t7-t6>tauF 5,8242 0,8242

20 19 t7-t5>tau6 ...........5 .............. О.......................... 15,7940t7 t5=tau6 1,8750 0,0000

21 23 l8-t7>tauH 4 0 8 20,6690 t8-t7=tauH 4,8750 0,0000

22 t5-t4>tau<5 0 0 t5-t4>tau®l 0,0000 0,0000

Рис. 2. Решение задачи сетевого планирования в Microsoft Excel

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

В качестве средства разработки применяется интегрированная среда Microsoft Visual Studio 2010. Особенностью разработанного программного продукта «CSBusinessGraph» является то, что он не использует никаких специализированных средств и третьесторонних библиотек для представления нечётких чисели выполняет все вычисления только с использованием действительных переменных.

К основным функциональным возможностям программного продукта относятся: создание модели проекта в виде вершинного графа в ручном режиме или импорт существующей модели из XML-файла; поддержка модели проекта в согласованном состоянии — проверка отсутствия циклов в графе и наличие только одной компоненты связности; формирование временных оценок выполнения операций, выраженных в виде треугольных чисел; автоматическое преобразование вершинного графа в стрелочный; реализация механизма расчёта критического пути на основе а-уровневых и двухточечных вычислений с применением выбранного пользователем вида значений параметров А преобразования L; экспорт отчёта о решении задачи в формат Microsoft Excel с формированием графиков для модифицированных нечётких оценок, общего времени выполнения проекта и построением стрелочного графа с выделением критических операций.

На рис. 3 изображено главное окно приложения с открытым в нём проектом.

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

Основные результаты работы

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

Рис. 3. Главное окно приложения

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

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

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

Основные публикации по теме диссертации

1. Воронцов Я. А., Матвеев М. Г. Информационные технологии управления проектами в условиях расплывчатой неопределённости // Современные проблемы прикладной математики, теории управления и

математического моделирования: материалы V международной конференции. Воронеж, 11-16 сентября 2012 г. Дополнительный выпуск, — Воронеж : Издагельско-полиграфический центр Воронежского государственного университета, 2012, — С. 8-10,

2. Воронцов Я. А., Матвеев М, Г. Разработка информационных технологий и средства управления проектами в условиях расплывчатой неопределённости // Сборник студенческих научных работ факультета компьютерных наук ВГУ / Под ред. к.ф.-м.н. Е. А. Сирота. — Воронеж : Издательско-полшрафический центр ВГУ,

2012.-С. 30-35.

3. Воронцов Я. А., Матвеев М. Г. Влияние преобразования Ь на результаты арифметических операций с нечёткими ЬЯ-числами // Сборник трудов XXII международного научно-технического семинара «Современные технологии в задачах управления, автоматики и обработки информации», Алушта, 18-24 сентября 2013 г. — М.: Изд-во МГУПИ, 2013. — С. 14-15.

4. Воронцов Я. А., Матвеев М. Г. Исследование свойств линейного отображения в задачах с нечёткими параметрами // Информатика: проблемы, методология, технологии: материалы XIII научно-методической конференции. 7-8 февраля 2013 г.: в 4 т.— Т. I,— Воронеж : Издательсюэ-полиграфический центр ВГУ,

2013,-С. 298-304.

5. Воронцов Я. А., Матвеев М. Г. Алгебраические операции с нечеткими 1Л-числами с использованием преобразования Ь // Программная инженерия. — 2014. — № 8. — С. 23-29.

6. Воронцов Я. А., Матвеев М, Г. Методы параметризованного сравнения нечётких треугольных и трапециевидных чисел II Вестник ВГУ, серия «Системный анализ и информационные технологии». — 2014. — № 2. - С. 90-97.

7. Воронцов Я. А., Матвеев М. Г. Постановка задачи об устойчивости альфа-уровневого метода поиска нечёткого критического пути // Информатика: проблемы, методология, технологии: материалы XIV Международной научно-методической конференции, Воронеж, 6-8 февраля 2014 г.: в 4 т- Т. 2,-Воронеж : Издательский дом ВГУ, 2014. — С. 360-363.

8. Воронцов Я. А., Матвеев М. Г. Способ решения нечёткой задачи КСПУ с использованием преобразования Ь // Радиоэлектроника, электротехника и энергетика: двадцатая международная научно-техническая конференция студентов и аспирантов: тезисы докладов. Москва, 27-28 февраля 2014 г.: в 4 т. — Т. 2. — М.: Издательский дом МЭИ, 2014, — С. 58.

9. Воронцов Я. А., Матвеев М. Г. Устойчивость критического пути в задаче сетевого планирования с нечёткими параметрами // Сборник трудов XXIII международного научно-технического семинара «Современные технологии в задачах управления, автоматики и обработки информацию», Алушта, 14-20 сентября 2014 г. — М. : ИКД «Зерцало-М», 2014,- С. 73-74.

10. Воронцов Я. А., Матвеев М. Г. Устойчивость решения в задаче о критическом пути с нечёткими параметрами // Вестник ВГТУ.- 2014,- Т. 10, № 6.- С. 40-43.

11. Воронцов Я, А., Матвеев М. Г., Каншцева О. И. Арифметические операции над двухкомпонентными нечёткими числами // Вестник ВГУ, серия «Системный анализ и информационные технологии». — 2014. — № 2. - С. 75-82.

Работы [5,6,10,11] опубликованы в изданиях, рекомендованных ВАК РФ.

Подписано в печать 11.03.15. Формат 60*84 */1б. Усл. печ. л. 0,93. Тираж 100 экз. Заказ 140.

Отпечатано с готового оригинал-макета в типографии Издательского дома ВГУ. 394000, Воронеж, ул. Пушкинская, 3