Содержание к диссертации
Введение
Глава 1. Анализ проблематики моделирования развивающихся сложноструктурированных технических систем 12
1.1 Принципы построения и тенденции развития сложноструктурированных технических систем 12
1.1.1 Технология асинхронного режима передачи 13
1.1.2 Технология MPLS 15
1.1.3 Классы решений в области OSS/BSS-систем 17
1.2 Модели анализа распределенных сложноструктурированных технических систем 23
1.2.1 Модели на основе аппарата теории массового обслуживания 23
1.2.2 Модели на основе социальных систем 28
1.3 Оптимизационные модели решения задач развития
сложноструктурированных технических систем 32
1.3.1 Анализ процесса развития сложноструктурированных технических систем 32
1.3.2 Модели задачи о размещении 36
1.3.3 Модели оптимизации состава комплекса технических средств 40
1.4 Цель работы и задачи исследования 43
Глава 2. Оптимизационная модель задачи о размещении и алгоритм ее численной реализации в условиях развивающихся сложноструктурированных технических систем 45
2.1 Модифицированная оптимизационная модель задачи о размещении 45
2.2 Анализ применимости модели задачи о размещении в условиях развивающихся сложноструктурированных технических систем 48
2.3 Сравнительный анализ вариантов численной реализации задачи о размещении 57
2.3.1 Генетический алгоритм 57
2.3.2 Алгоритм вероятностного поиска с запретами 60
2.3.3 Обобщенный алгоритм метода ветвей и границ 62
2.4 Модифицированный алгоритм метода ветвей и границ с применением метода Гомори 67
Выводы 79
Глава 3. Алгоритмизация решения динамической задачи о ранце на основе модификации метода Беллмана в условиях оптимизации состава комплекса технических средств 80
3.1 Обобщенная постановка динамической задачи о ранце и средства численной реализации на примере оптимального формирования состава потребительской корзины 80
3.2 Анализ процесса развития структуры комплекса технических средств 90
3.3 Оптимизационная модель выбора состава комплекса технических средств узлов обслуживания сложноструктурированных технических систем 94
3.4 Численная реализация модели оптимизации состава комплекса технических средств развивающихся сложноструктурированных технических систем 98
Выводы 110
Глава 4. Программная реализация моделей оптимального развития сложноструктурированных технических систем 111
4.1 Программный комплекс моделирования и анализа развивающихся сложноструктурированных технических систем 111
4.2 Пользовательский интерфейс 116
4.3 Практическая реализации программного комплекса в условиях мультисервисной сети ПАО «Ростелеком» 123
Заключение 130
Библиографический список
- Технология асинхронного режима передачи
- Анализ применимости модели задачи о размещении в условиях развивающихся сложноструктурированных технических систем
- Оптимизационная модель выбора состава комплекса технических средств узлов обслуживания сложноструктурированных технических систем
- Пользовательский интерфейс
Введение к работе
Актуальность темы. Развитие технологий передачи
информации привело к формированию класса
сложноструктурированных технических систем, основы научного
подхода к моделированию и синтезу которых были заложены в
середине XX-го века в работах Л. Клейнрока, Н. Джейсоула, Дж.
Ньюэла, Г. П. Башарина. К сложноструктурированным техническим
системам первого поколения относятся простые телефонные службы
(Plain Old Telephone Service – POST), использующие аналоговые
системы передачи данных, координатные и квазиэлектронные узлы
коммутации. В настоящее время множество
сложноструктурированных технических систем составляют
телефонные, телевизионные, компьютерные, радиосистемы, а также мультисервисные сети (IP/MPLS), обеспечивающие взаимную интеграцию и передачу по единым каналам передачи данных информации разных типов.
Разработанные к настоящему времени методы моделирования и анализа сложноструктурированных технических систем в основном используют аппарат теории массового обслуживания, социальных систем и математического программирования. В контексте решения задач развития сложноструктурированных технических систем данные методы могут быть применены для построения статических моделей с ориентацией на формирование априори прогнозируемого резерва требуемых ресурсов, что ограничивает возможность принятия решений на долгосрочный период. Все это обусловливает целесообразность разработки новых методов моделирования и анализа развивающихся сложноструктурированных технических систем с использованием аппарата динамического и дискретного программирования.
Учитывая вышеизложенное, актуальность темы
диссертационной работы продиктована необходимостью разработки
математических моделей анализа сложноструктурированных
технических объектов в условиях их развития на основе
модификации методов динамического и дискретного
программирования.
Тематика диссертационной работы соответствует одному из
научных направлений ФГБОУ ВО «Воронежский государственный
технический университет» «Вычислительные комплексы и
проблемно-ориентированные системы управления».
Цель работы и задачи исследования. Целью диссертационной работы является разработка математических моделей оптимизации процессов развития сложноструктурированных технических систем на основе модификации методов дискретного и динамического программирования, а также алгоритмов численной реализации и комплекса средств программной реализации.
Для достижения поставленной цели в работе определены следующие задачи исследования:
- системный анализ проблематики моделирования и анализа
развивающихся сложноструктурированных технических систем и
определение основных параметров, влияющих на эффективность их
функционирования;
- разработка модифицированной оптимизационной модели
задачи о размещении, обеспечивающей ускоренную сходимость при
решении задач развития структуры;
- разработка эффективного алгоритма численной реализации
модели задачи о размещении;
- разработка модифицированной оптимизационной модели
задачи о ранце в условиях динамической постановки, применительно
к задаче оптимизации состава комплекса технических средств
развивающихся сложноструктурированных технических систем;
- разработка эффективного алгоритма численной реализации
модели динамической задачи о ранце на основе модификации метода
Беллмана;
разработка программного комплекса моделирования и анализа развивающихся сложноструктурированных технических систем;
практическая апробация разработанных моделей и алгоритмов численной реализации применительно к задаче планирования развития структуры и комплекса технических средств на примере мультисервисной сети в реальных условиях.
Методы исследования. В основу диссертационного
исследования положены методы теории математического
моделирования, дискретной математики, динамического
программирования, теории графов, методы объектно-
ориентированного программирования.
Тематика работы соответствует следующим пунктам паспорта специальности 05.13.18: п.1 – «Разработка новых математических методов моделирования объектов и явлений»; п.3 – «Разработка, обоснование и тестирование эффективных вычислительных методов с применением современных компьютерных технологий»; п. 4 -
«Реализация эффективных численных методов и алгоритмов в виде комплексов проблемно-ориентированных программ для проведения вычислительного эксперимента».
Научная новизна. В работе получены следующие результаты, отличающиеся научной новизной:
- модифицированная оптимизационная модель задачи о
размещении, отличающаяся включением в систему ограничений
территориальных показателей ценности размещения, что
обеспечивает ускоренную сходимость при решении задач развития
структуры;
- алгоритм численной реализации оптимизационной модели
задачи о размещении, отличающийся модификацией метода ветвей и
границ, с использованием процедуры, базирующейся на методе
Гомори, для формирования графа решений и таблицы рекордов, и
механизма альфа-бета отсечения для предотвращения повторных
вычислений;
- модифицированная оптимизационная модель задачи о ранце,
отличающаяся предложенной динамической постановкой в условиях
взаимосвязанных временных интервалов применительно к задаче
оптимизации состава комплекса технических средств развивающихся
сложноструктурированных технических систем;
- алгоритм численной реализации оптимизационной модели
динамической задачи о ранце, отличающийся модификацией метода
динамического программирования Беллмана, реализующего
процедуру выбора оптимального варианта решения из нескольких
альтернативных в соответствии с установленными ограничениями;
- структура проблемно-ориентированного программного
комплекса моделирования и анализа развивающихся
сложноструктурированных технических систем, отличающаяся
взаимной интеграцией систем моделирования, планирования и
оптимизации, обеспечивающая совместную работу в рамках единых
доменных моделей.
Практическая значимость. Предложенные в работе модели и алгоритмы их численной реализации ориентированы на практическое использование разработчиками программного обеспечения в составе систем поддержки принятия решений, связанных с оптимизацией процессов развития сложноструктурированных технических систем. Разработанный программный комплекс является универсальным и многоцелевым, и может быть реализован в условиях развивающихся объектов и систем из других предметных областей, в том числе
производственных систем. Функциональные модули программного комплекса могут быть использованы автономно. Например, модуль, решающий динамическую задачу о ранце, целесообразно применять в условиях формирования состава потребительской корзины.
Компоненты программного комплекса прошли
государственную регистрацию в ФГБУ «Федеральный институт промышленной собственности» (РОСПАТЕНТ).
Реализация и внедрение результатов работы. Теоретические
результаты работы, а также разработанный программный комплекс
получили практическое внедрение в условиях мультисервисной сети
Воронежского филиала ПАО «Ростелеком». Ожидаемый
экономический эффект от внедрения достигнут за счет повышения качества и оперативности принятия управленческих решений по развитию информационной сферы предприятия.
Результаты исследования внедрены в учебный процесс кафедры
электропривода, автоматики и управления в технических системах
ФГБОУ ВО «Воронежский государственный технический
университет» в рамках дисциплин «Системный анализ» и «Исследование операций».
Апробация результатов работы. Основные положения
диссертационной работы докладывались и обсуждались на
Международной научной конференции «Современные методы
прикладной математики, теории управления и компьютерных
технологий» (Воронеж, 2014, 2015), Международной научно-
технической и научно-методической конференции «Современные
технологии в науке и образовании» (Рязань, 2016), Всероссийских
конференциях «Новые технологии в научных исследованиях,
проектировании, управлении, производстве» (Воронеж, 2013),
«Перспективные исследования и разработки в области
информационных технологий и связи» (Воронеж, 2014), «Прикладная
математика, механика и процессы управления» (Пермь 2013),
Международной научно-практической конференции
«Антропоцентрические науки: инновационный взгляд на образование и развитие личности» (Воронеж, 2014), а также на научных семинарах кафедры электропривода, автоматизации и управления в технических системах ВГТУ (2013-2015.)
Публикации. По теме исследования опубликовано работ, отражающих основные положения исследования, в т.ч. 6 статей в журналах, рекомендованных ВАК РФ. В работах, опубликованных в соавторстве и приведенных в конце автореферата, лично соискателю
принадлежат: в [1,2,8] – разработка модифицированной
оптимизационной модели задачи о размещении, обеспечивающей ускорение сходимости при решении задач оптимизации структуры за счет учета территориальных показателей; [3,5,9] – разработка оптимизационной модели задачи о ранце в динамической постановке, и ее применение для решения задачи оптимизации состава комплекса технических средств сложноструктурированных технических систем; [6,10] – разработка модифицированного алгоритма метода ветвей и границ с применением процедур, базирующихся на методе Гомори, и механизма альфа-бета отсечения в качестве численной реализации разработанной модели задачи о размещении; [4,10] – разработка алгоритма численной реализации модели динамической задачи о ранце на основе модифицированного метода Беллмана и его практическое применение в рамках задачи оптимизации комплекса технических средств мультисервисной сети, [5,7,11] – разработка структуры программного комплекса моделирования и анализа развивающихся сложноструктурированных технических систем.
Структура и объем работы. Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы из 142 наименований и приложений. Основная часть работы изложена на 144 страницах, содержит 28 рисунков, 7 таблиц.
Технология асинхронного режима передачи
Рассмотрим первую группу моделей анализа распределенных ССТС. Так как они сходны по своему включают в себя распределенные системы обработки информации (РСОИ), анализ характеристик которых связан с обработкой потоков случайных транзакций и вычислением вероятностей состояния системы, то для анализа таких систем возможно применение теории массового обслуживания. Средствами обработки и передачи информации обеспечивается транспорт транзакций при прохождении их через систему. Важными параметрами таких транзакций являются скорость и длина пакетов, которые для основного чиста систем подвержены случайным статическим изменениям. В связи с этим для анализа их влияния на систему необходимо применение вероятностных методов, которые выбираются в соответствии с теорией массового обслуживания.
Теоретические основы данного направления были заложены в работах Л. Клейнрока, Н. Джейсоула, Г. П. Башарина. В работах [5,59,60,25] было показано, что сетей массового обслуживания(СМО) являются адекватными моделями функционирования СТСС.
Предложенные в данных работах модели не учитывают существенную характеристику распределенной обработки информации, связанную с оценкой вероятности состояния системы, которая существенно влияет на оперативную маршрутизацию информационных потоков [50]. Обработка информации в распределенных ССТС моделируется потоками транзакций разного типа, которые проходят сквозь систему в соответствии со своим маршрутом. Функции распределения, характеризующие поведение системы, экспоненциального или эрлангового вида, то систему можно описать с помощью однородных непрерывных марковских процессов, часто даже с помощью однородных процессов рождения и гибели. Тогда аналитическое определение величин становится относительно легким. Для анализа таких систем наиболее подходят методы t и метод фаз Эрланга. Для подкласса СМО и надежности с экспоненциальным распределением всех встречающихся величин существуют и упрощенные, чисто алгебраические методы получения стационарных вероятностей состояний (метод уравнений состояний Z) [47].
В процессе анализа и моделирования распределенных ССТС основными параметрами являются качество их функционирования и параметры систем, включенных в состав. Можно выделить следующие параметры функционирования: время обработки транзакции, интенсивность и характер обслуживания в узле обработке транзакций (УОТ), загрузка УОТ, определение УОТ с максимальной загрузкой («узкого места»), средняя длина очереди на обслуживание в УОТ, вероятности нахождения распределенной ССТС в каком-либо состоянии.
Состояние замкнутой СМО в стационарном режиме характеризуется количеством циркулирующих в ней транзакций N. В случае, если для УОТ интенсивность обслуживания не зависит от текущей загрузки и все УОТ обрабатывают транзакции по принципу FCFS (первый пришел, первый обслужен), то Ti(N) - средняя величина времени ожидания транзакции для i-го УОТ может быть вычислена по формуле (1.1). А длины очереди - Li(N) - в свою очередь вычисляются по формуле (1.2). Tt (N) = Tt (N -1) (1 + Lt (N -1)) (1.1) N)=„ N (1.2) i=1 Pt(и,N) = Tt(N -1) Pt(n-1,N-1),n 1,Pt(0,0) = 0 (1.4) Исходя из начальных условий L,- = 0(/ = 1,...,М), средние характеристики СМО можно рассчитать рекуррентно по N [16]. Для случаев рассмотрения замкнутых СМО, которые обрабатывают несколько классов транзакций одновременно и интенсивность обслуживания для УОТ зависят от нагрузки, вводится следующее допущение. Пусть множество существующих классов транзакций можно разбить на укрупненные классы, такие, что если класс г принадлежит укрупненному классу , то транзакция этого класса может за конечное число шагов перейти в любой другой класс s, который также принадлежит укрупненному классу [57,9] Данное разбиение гарантирует, что для замкнутой СМО количество транзакций укрупненного класса будет постоянным. В случае использования подобных допущениях, формулы, аналогичные (1.1) - (1.4) можно применить для расчета характеристик СМО.
Введем следующие обозначения: Nr(N1N2,...Nr) - вектор, характеризующий количество транзакций классов от 1 до г в СМО; пг = (п1 п2,..., п2) - вектор, характеризующий состояние УОТ (количество в УОТ транзакций классов с 1 по г-й без учета этапа обслуживания транзакции); 1Г - вектор, г - координата которого равна 1, а все остальные 0. Тогда, используя введенные обозначения, вероятность того, что в состоянии системы Nr, i-e состояние УОТ будет равно пг, можно вычислить по формуле: I n=1 Pt (nR,NR )=Y ir (NR ) PJ (nR-lR,NR-lR )/fiir (щ) (1.5) Среднее время ожидания транзакции класса r в i-м УОТ, зависящем от нагрузки, равно: Tir № J=21 pi (nR-bNR-lR Ж M (1.6) n= R Для расчета СМО по этому алгоритму требуется выполнить г=1 количество шагов, причем каждый шаг требует 2RM-R операций сложения-вычитания и 2RM+R операций умножения-деления. Вычислительная сложность алгоритма значительно возрастает с увеличением обобщенных классов, хотя при рассмотрении систем распределенной обработки информации количество обобщенных классов не будет превышать одного десятка, т. к. каждому обобщенному классу будет соответствовать одно приложение в РСОИ [4]. Из формул (1.1)-(1.3) видно, что вычисление всех основных параметров СМО можно свести к вычислению нормализующих констант для различных состояний СМО. Для замкнутых СМО нормализующая константа представляет собой сумму произведений. Количество слагаемых в этой сумме соответствует мощности пространства состояний систем и даже для однородных СМО Вследствие комбинаторного возрастания пространства (N + M-1) составляет М-1 ) состояний сети при увеличении количества центров и классов транзакций мощность состояний сети резко возрастает, так что прямой расчет нормализующей константы становится практически невозможным даже для сетей небольшой размерности
Анализ применимости модели задачи о размещении в условиях развивающихся сложноструктурированных технических систем
Одной из главных проблем спирального цикла является определение момента перехода на следующий этап. Для ее решения вводятся временные рамки для каждого из этапов, и переход осуществляется в соответствии с заранее заданным планом, который формируется на основе анализа статистических данных, полученных в предыдущих проектах, и личного опыта разработчиков.
Моделирование системы позволяет решить основные проблемы, возникающие при разработке и анализе результатов проектирования развивающейся информационной системы.
Для проверки применимости разработанной модифицированной модели задачи о размещении в условиях развивающихся ССТС, рассмотрим как ведет себя исследуемая система в условиях развития.
Обычно схема размещения узлов обслуживания системы является следствием ее истории развития, так, например, мультисервисные сети и сети интернет являются результатом развития городских телефонных сетей (ГТС) больших городов и мегаполисов. ГТС в г. Москва сначала состояли из одной телефонной станции [45]. Таким образом при выборе мест размещения коммутационного оборудования очевидно не было возможности предвидеть структуру будущих ГТС, количество коммутационных станций в которых может оцениваться десятками и сотнями.
В настоящее время задачи, которые связаны с созданием новой структуры системы возникают достаточно редко, в следствие чего задачи развития структуры непосредственным образом связаны с задачами интеграции полученной в ходе оптимизации структуры с уже реализованным вариантом решения. Заметим, что в рамках рассмотрения задачи изначального размещения узлов обслуживания ССТС, существующие варианты реализации зачастую могут являться неоптимальными и даже избыточными. Однако, изменение существующей структуры в плане перемещения или ликвидации работающих улов обслуживания может повлечь за собой неоправданные издержки на перемещение оборудования и переподключение пользователей, что в свою очередь не может не сказаться на стабильности работы системы в целом. В следствие этого, при рассмотрении каждого из таких вариантов необходимо оценить соответствующие риски. Зачастую в таких ситуациях целесообразнее модернизировать состав комплекса технических средств узла обслуживания, что позволит минимизировать издержки на поддержку работы системы.
Развитие ССТС, и, в частности, сетей связи, может быть обусловлено двумя основными причинами: ростом численности населения и появлением новых технологий. Данные причины приводят к изменению потребности пользователей в услугах системы. В этом контексте можно выделить следующие факторы, влияющие на развитие структуры ССТС: изменению уровня потребности пользователей в услугах на территории, обслуживаемой системой и появление потребности в услугах на территории не обслуживаемой ранее [45]. Появлением новых технологий в контексте рассмотрения задачи оптимального развития ССТС можно пренебречь, так как данный фактор является слабо предсказуемым, что ликвидирует возможность его учета.
В первом случае стоит рассматривать два варианта. При повышении уровня потребности может возникнуть ситуация, когда для удовлетворения всех потенциальных пользователей в состав ССТС необходимо ввести дополнительный узел обслуживания для разгрузки уже существующих узлов, поскольку возможности магистральных линий по одновременному обслуживанию большого количества пользователей ограничены. Однако в большинстве случаев, данная проблема может быть решена установкой дополнительного оборудования в конкретные узлы.
При понижении уровня потребности в услугах может возникнуть ситуация, когда один или несколько существующих узлов обслуживания целесообразнее исключить из состава системы. В этой связи стоит учесть возможные затраты по переводу пользователей на обслуживание другими узлами и соответствующие риски. Однако практика показывает, что исключение узла обслуживания из состава системы – это крайняя мера и она может быть применена, когда все другие действия не могут принести существенной выгоды. В большинстве случаев такие проблемы могут быть решены исключением оборудования из состава узла обслуживания и, возможно, установкой его в состав других узлов.
Во втором случае, когда потребность в услугах ССТС появляется на территории ранее не обслуживаемой, единственным вариантом решения задачи удовлетворения сложившейся пользовательской потребности может быть размещение нового узла обслуживаниям на данной территории. При этом определенно стоит учитывать затраты на установку узлов и прибыль, которую можно получить в следствие удовлетворения пользовательской потребности.
Рассмотрим схему принятия решений представленную на рис. 1.1 в контексте принятия решений о развитии структуры узлов ССТС в отрыве от задачи оптимизации комплекса технических средств узлов обслуживания. Для этого исключим такие составляющие принятия решений как множество оборудования возможного к установке в узлах обслуживания и множество установленного оборудования. В рамках рассмотрения задачи о размещении данные параметры являются избыточными. Важными параметрами для решения задачи размещения являются территориальные уровни потребностей пользователей в услугах системы, на основании которых и принимается решение о развитии структуры узлов обслуживания в каждом конкретном случае.
Такие факторы, как увеличение и снижения уровня потребности пользователей на территории обслуживаемой системой можно свести к одному фактору изменения уровня потребности. Тогда схема принятия решений в условиях решения задачи развития структуры узлов обслуживания ССТС может быть представлена на рис. 2.2.
Оптимизационная модель выбора состава комплекса технических средств узлов обслуживания сложноструктурированных технических систем
Для рассмотрения задачи выбора оптимального состава комплекса технических средств в динамической постановке необходимо для начала рассмотреть динамическую задачу о ранце. Подробно задача о ранце в статической постановке изложена в работах [135,129,114].
В динамической постановке задачу о ранце можно представить в виде задачи его наполнения для каждого из последовательных подынтервалов в рамках общего времени решения задачи таким образом, чтобы затраты на добавление новых объектов в ранец были минимальны, при его наполнении объектами с некоторой общей суммарной ценностью.
Для формальной постановки динамической задачи о ранце введем следующие обозначения: [0;Т] - временной интервал решения задачи о ранце; є [0; Т] - временные подынтервалы решения задачи о ранце, в рамках которых осуществляется выбор оптимального состава ранца, к = 1, К; К - общее количество временных подынтервалов; В = {b1,b2,...,bI} - конечное множество объектов, из которых осуществляется выбор на каждом подынтервале; / - общее количество возможных к включению в состав ранца объектов; с1к - стоимость включения в состав ранца объекта bj на подынтервале времени , i = 1J, k = 1,K; Vjfc - ценность включения объекта bj на подынтервале времени t , i = 1,J, может отражать как количественные показатели объема объекта, в этом случае данный параметр не будет зависеть от времени, так и некоторую абстрактную ценность объекта, которая может изменяться во времени; Vmin - минимальная суммарная ценность объектов, включенных в состав ранца, для подынтервала времени
Используя введенные обозначения динамическую задачу о ранце на можно сформулировать как задачу выбора такого объектов из конечного множества В = {Ь1,Ь2,..., bj} для каждого из подынтервалов времени є [0; J7] , k = 1,К, чтобы суммарная стоимость их приобретения оказалось минимальной. При этом так же необходимо, чтобы суммарная ценность объектов, включенных в состав ранца превышала минимальны установленный порог ценности Vmin для каждого из подынтервалов k, к = 1, К . Для формального рассмотрения задачи о ранце будем считать, что решение о включении объекта в состав ранца на подынтервале для каждого из объектов bj, i = 1,J принимается в отдельный интервал времени tki [31,121,135,105,139,106]. Тогда рассматриваемую задачу можно записать в виде задачи линейного целочисленного программирования (3.1) при ограничениях (3.2) и (3.3): к і (3.1) 1jt(ffc fo-- min, k=1i= Г1, объект Ъ: входит в состав ранца на подынтервале t,; (3.2) x(tM) = \ i1 x(tkt)vkt vmin , k=1,K. (3.3) г= 10, в противном случае. Практическое применение описанной модели может быть связано с ее реализацией как в рамках рассмотренных задачах наполнения потребительских корзин, так и в рамках других развивающихся объектов в области IT (мультисервисные сети), экологических, энергетических систем и т.д.
Формально рассмотренную задачу можно считать модифицированной версией задачи о ранце, представленной в динамической постановке [4]. Таким образом для ее решения можно воспользоваться методом динамического программирования. В его основе лежит представление исходной задачи в виде семейства подзадач более мелкого масштаба. Тогда решение задачи свозится к многошаговому процессу принятия решений, каждое из которых направлено на достижение единой цели. Подробно техника решения задач динамического программирования рассмотрена в работах [11, 51, 103, 83,84, 12].
Основываясь на данных работах, решение задачи о ранце можно свести к последовательному вычислению значений рекуррентной функции для каждого из этапов принятия решений. Как было сказано выше, для формирования такой функции будем считать, что решение о включении товара или услуги bj, i=1,I для каждого подынтервала времени , к = 1,К принимается в отдельный интервал времени tfc. Таким образом, временной интервал [0;Г] решения задачи развивается на множество меньших подынтервалов принятия решений Введем следующие обозначения: S - оптимальное значение целевой функции (3.1), описываемой уравнениями (3.4), (3.5); х ={x (t11),x (t12),...,x (tKI)} - вектор оптимального решения рассматриваемой задачи, т.е. S = f] i1 (e)% ; k=1i= к I - оптимальное значение ценности для подынтервала k =li=l решения Тогда рекуррентные соотношения для ее решения задачи (3.1) можно сформулировать следующим образом: О, Г=0, (3.4) S(tu,V ) = \cb 0 F vb, + 00, Г УХ; [S{th-\yy\ x(th) = 0; (3.5) к і (3.6) o r Y.Hvik k=\i=\ где V - итерационная переменная ценности, которая может изменяться в пределах границ (3.6). Тогда для каждой итерации ограничение (3.3) можно переформулировать следующим образом:
Рассмотрим реализацию процедуры решения динамической задачи о ранце на примере задачи о формировании оптимального состава потребительской корзины. В первую группу потребительской корзины должны быть включены продукты питания. В реалиях России их общая стоимость составляет около половины общей стоимости корзины, в странах Западной Европы эта цифра не превышает 20% [79]. Таким образом продукты питания являются неотъемлемой частью общей потребительской корзины и затраты на их приобретение необходимо учитывать постоянно.
Во вторую группу включены непродовольственные товары - одежда, обувь, головные уборы, белье, лекарства. Данные товары так же являются неотъемлемой частью прожиточного минимума человека, однако потребность в их приобретении может варьироваться в зависимости от сезона и наличия или отсутствия у человека аналогичных предметов в собственности [89, 69, 128].
Третья группа потребительской корзины состоит из необходимого минимума услуг: коммунальные услуги, расходы на транспорт, культурные мероприятия и т.д. Некоторые из этого набора услуг являются необходимыми для человека вне зависимости от сезона, такие как коммунальные услуги, однако их стоимость может варьироваться. Так затраты на отопление в зимний период будут выше, а затраты на водоснабжения в летний период могут увеличиться для жителей частного сектора, использующих систему центрального водоснабжения для полива собственного огорода [69, 40].
Таким образом можно выделить два неотъемлемых параметра для каждой из рассмотренных групп: ценность товара или услуги для человека и стоимость его/ее потребления. В случае первой из рассмотренных групп ценность может рассматриваться как энергетическая ценность продукта питания. В случае второй и третьей групп ценность товара или услуги является абстрактной величиной, отражающей необходимость конкретного товара или услуги для человека [31].
Таким образом можно сделать вывод о том, что модель (3.1), при ограничениях (3.2) и (3.3), может быть применена для решения задачи оптимального формирования потребительской корзины и, соответственно, ее решение лежит в области применения аппарата динамического программирования.
Примером применения оптимизационной модели (3.1), может быть не только рассмотренная задача, но и задача наполнения ежедневной продуктовой корзины с учетом энергетической ценности продуктов питания. Решение такой задачи может найти примирение как в областях медицины и диетологи, так и в бытовых областях ежедневного потребления [40].
Возможны так же реализации оптимизационной модели (3.1) для решения задач наполнения складов для обеспечения работы логистических компаний, задач выбора оптимального состава оборудования для экологических, энергетических и развивающихся IT систем.
Зададим начальные условия задачи оптимального формирования потребительской корзины. Пусть временной интервал [0;Г] разбит на К = 3 подынтервалов и значения стоимости и ценности товаров и услуг В = {Ъ1,Ъ2,Ъ3,Ъ4} заданы в табл. 3.1.
Пользовательский интерфейс
Для реализации графического интерфейса пользователя выбрана технология Windows Presentation Foundation(WPF) с применением шаблона проектирования Model-View-ViewModel (MVVM). Данный шаблон проектирования обеспечивает легкость реализации графического интерфейса за счет возможностей автоматического обновления изменений, реализованных программно и избавляет разработчика от необходимости постоянного контроля за состояние и наполнение элементов интерфейса. Технология WPF поддерживает шаблон MVVM на программном уровне [73,75,115,109,138].
В качестве хранилища данных создана база данных в СУБД Microsoft SQL Server 2012. Для обеспечения взаимодействия между базой данных и программой используется технология Entity Framework 6.0, поддерживающая формат работы Code First, что позволяет сгенерировать структуру базы данных на основе программных моделей, реализованных на языке C#. Так же использование данного подхода облегчает работу с обновлениями базы данных за счет наличия реализованной возможности миграции изменений, что позволяет разработчику самому не заботится о консистентности текущей структуры базы данных [125,127,126].
В соответствии с выбранными средствами и технологиями была разработана структура решения в Visual Studio 2013, представленная на рис. 4.2 [113,110,107,133].
Модули, реализующие методы ветвей и границ, Гомори и динамического программирования соответствуют аналогичным алгоритмам о писанными в главах 2 и 3 [113,110,107,133]. Реализация данных методов в виде отдельных классов позволяет использовать библиотеку «Elizarov.Msn. DynamicOptimization.Bll» для решения задач, не связанных с оптимальными развитием СТСС [80]. Таких как задача о ранце, задача о назначениях и целого ряда задач линейной оптимизации.
По своей структуре программный комплекс моделирования и анализа развивающихся ССТС условно разделяется на четыре основные части: интерфейс пользователя, подсистему моделирования и анализа, подсистему оптимизации и модуль хранения и обработки данных.
Пользовательский интерфейс обеспечивает удобный ввод и редактирование данных модели. За счет реализации архитектуры MVVM изменения, произведенные пользователем моментально применяются ко всей модели [115,109]. Так, например, после добавление в модель нового узла обслуживания автоматически обновятся все структуры, связанные со стоимостными характеристиками задачи размещения без необходимости нажатия кнопок сохранения. За счет этого пользователь программного комплекса будет избавлен от проблем с релевантностью данных на той или иной форме. Исходя из параметров, задаваемых для оптимизационных моделей развития СТСС, интерфейс состоит из редактора модели, включающего редакторы расположения узлов обслуживания, характеристик узлов, мест размещения, оборудования, стоимостных характеристик и территориальных потребностей пользователей. За решение задачи оптимизации отвечает компонент расчета оптимального результата и форма отчета. Существует возможность сохранения данных модели в файл и чтения их из файла, при этом данные модели постоянно сохраняются в базу данных приложения. Структура интерфейса пользователя программного комплекса представлена на рис. 4.3.
Редактор карты расположения узлов обслуживания и мест их размещения служит, интерфейс которого представлен на рис. 4.4, для визуального отображения структуры в виде удобном для представления пользователю. После добавления узлов обслуживания и мест их размещения с помощью соответствующих редакторов, или путем нажатия соответствующих кнопок во вкладке редактора карты, их элементы могут быть размещены на карте, при этом это действие не является необходимым для решения задачи оптимизации комплекса технических средств, но желательным для последующего визуального представления отчета о решении задачи размещения узлов обслуживания и выбора состава комплекса технических средств.
Редактор мест размещения и их характеристик, интерфейс которого представлен на рис. 4.6, служит для добавления и удаления возможных мест размещения из соответствующей базы знаний, а также изменения их основных характеристик.
Редактор стоимостей размещения и расформирования узлов обслуживания сети, интерфейс которого представлен на рис. 4.7, служит для задания соответственных характеристик для всех возможных комбинаций узлов обслуживания и мест их размещения. Список полей в данном редакторе обновляется автоматически после добавления, удаления и изменений названий узлов обслуживания и мест их размещения в соответствующих редакторов. Таким образом после изменения списков узлов обслуживания и мест их размещения необходимо задать новые стоимостные характеристики.
Редактор уровней территориальных потребностей пользователей в услугах системы, интерфейс которого представлен на рис. 4.8, служит для задания соответственных характеристик для мест размещения узлов обслуживания на каждом из интервалов оптимизации. Так же во вкладке данного редактора осуществляется задание количества интервалов оптимизации для решения задачи выбора оптимального состава комплекса технических средств. Список полей в данном редакторе обновляется автоматически после добавления, удаления и изменений названий узлов обслуживания или изменения числа интервалов оптимизации.