Оптимизационная задача управления построением имитационной модели в корпоративной информационной системе

УДК 5l9.876.5:658.5 DOI: 10.12737/20291

А.И. Якимов, Е.А. Якимов, В.И. Аверченков, H.H. Ивкина

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

СИСТЕМЕ

Рассмотрена задача многокритериального управления технологическим процессом (ТП) построения имитационной модели с использованием принципа оптимальности Беллмана. Обоснованность оптимального решения показана для одно- и двухмерных характеристик потока на дугах ориентированного ациклического графа ТП. Представлен

пример решения оптимизационной задачи с использованием ресурсов и р-типа в корпоративной информационной системе.

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

A.I. Yakimov, E.A. Yakimov, V.I. Averchenkov, N.N. Ivkina

OPTIMIZATION PROBLEM OF CONTROL BY SIMULATION MODEL FORMATION IN CORPORATE INFORMATION SYSTEM

The use of the wide spectrum of information technologies in corporate information systems allows offering the iteration method for a distributed formation of simulation models. In accordance with this method at each stage of designing the commercial software tools with certain functionality are used.

The considered technological process (TP) of simulation model formation (software toll creation) is a controlled system being at one of the states variable at each stage of a technological process as a result of a control action (control). At the same time the efficiency of a control process is characterized by a multidimensional purposeful function (PF) subject to a system state and control used.

In the investigation presented the problem of multicriterion control of a technological process of

simulation model formation in accordance with Bellman's principle of optimality. The justification of an optimum solution is shown for the unidimensional or two-dimensional characteristics of a flow on arches of an oriented acyclic graph of a technological process. The presented example of the solution of the optimization problem with the use of resources of f- and p-type in a corporate information system shows the necessity of priority criterion definition for the final choice of a route on a graph with technological modes, that is, an optimum variant of resource distribution.

Key words: simulation model, multicriterion control, Bellman's principle of optimality, technological process, corporate information system.

Введение

Использование широкого спектра информационных технологий в корпоративных информационных системах позволяет предложить итерационный метод распределенного построения имитационных моделей [1]. В соответствии с этим методом на каждом этапе проектирования применяют коммерческие программные средства с определенной функциональностью. Например, для этапа статистического анализа данных могут быть использованы следующие коммерческие программные продукты: MS Excel с макросом-дополнением XLSTAT-Pro

(http://www.xlstat.com/); STADIA с необхо-

димыми статистическими функциями (http://www.protein.bio.msu.su/ ~akula/index.htm); SPSS (Statistical Package for Social Science) - профессиональный статистический программный пакет (http://www.spss.com/); STATA -(http://www.stata.com/); STATISTICA - пакет программ фирмы StatSoft Inc. (http://www.statsoft.com/); JMR для анализа данных (http://www.jmp.com/); SYSTAT -статистическая система для персональных компьютеров (http://systat.com/); NCSS -программа, рассчитанная на непрофессионалов в области статистической обработки (http://www.ncss.com/); MINITAB 14 - про-

граммный пакет с возможностью визуализации результатов работы (http://www.minitab.com/); STATGRAPHICS PLUS - статистическая программа, содержащая более 250 статистических функций (http://www.statgraphics.com/); PRISM с основными применяемыми статистическими функциями (http://www.graphpad.com/) [2]. Необходимая программа выбирается в со-

ответствии с реализуемым оператором ¥г на г-м этапе.

В последовательности операторов ¥г будем рассматривать два типа ресурсов -человеческий (ресурс /-типа) и программный (ресурс р-типа), используемый на этапах построения имитационной модели (создания программного средства). В связи с неоднозначностью выбора таких ресурсов ставится оптимизационная задача [3].

Постановка задачи

Пусть технологический процесс (ТП) проектирования, разработки и

эксплуатации имитационной модели (программного средства) ТехРг состоит из п фиксированных этапов:

def

TexPr = {St1\i = 1,

Этапы Stit последовательно.

i=1, ...,n,

n}. (1) выполняются

Пусть каждый из этапов Sti предполагает выбор одного из допустимых технологических режимов (ТР) ¥Рщ,ц, определяемых использованием

человеческого ресурса (ресурса /-типа) и одного из видов допустимого программного обеспечения (ресурса р-типа) на г-м этапе (рис. 1):

def

St, ° {FPr(, k)| к = 1,..

def

R (i, к )°(/,f.

Здесь R(i,k) - вектор-идентификатор номера технологического режима, включающий порядковый номер этапа St, i, i е {1,...,n}; код используемого ресурса f-типа fk, fk е {1,...,f}; порядковый номер используемого ресурса p-типа pik, pik е {1,...,\p\}; порядковый номер ТР в пределах нумерации режимов этапа Sti k , k е {1,...,\Vi\}, где \Vi\ - мощность множества номеров технологических режимов на i-м этапе ТП.

Себестоимости отдельных ТР складываются из стоимостей

def

Res ° {Res J r = 1,

def

Cost ° {Cost r \ Cost r e R,

Технологический процесс (1) может быть представлен в виде нагруженного ориентированного ациклического графа [4], вершинами которого являются ТР (2). Для интерпретации в виде графа ТП (1) разделяется на n этапов. Исток графа представляет собой нулевой этап ТП (1). Нумерация вершин выполняется последовательно от истока (0 этап) к стоку

| V | }, i = 1, ..., n ,

Р&> к)

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

программных средств (ресурса р-типа) [2].

Пусть Res, Cost - множества ресурсов f-, р-типа и стоимостей соответствующих ресурсов:

r = 1, ..., \Res \} .

(n+1 этап). Вершины соединяются дугами в соответствии с последовательностью этапов (рис. 1).

Обозначим через Tuv нагрузку на дугу графа (рис. 2), исходящую из вершины с номером u е Vi-1 и входящую в вершину с номером v е Vi, где Vi - множество номеров вершин для i-го этапа ТП (1):

& ^о IV, 1 +1,1 ^ IV, | + 2, X ,=0 \Vj\l /

1п .

^

^

-

ГРЯ{2,\У2\)

РРВ

ГРК

-1

РРКп,\Уп\)

-О

0 этап

1 этап

2 этап

п этап

п+1 этап

Рис. 1. Последовательность технологических этапов проектирования, разработки и эксплуатации имитационной модели

2 этап п этап

Рис. 2. Нагрузки на дуги ориентированного графа

Пусть нагрузки тш интерпретируются как временные затраты и/или стоимости затрат ресурсов на обработку информации

при решении одной имитационной задачи в соответствии с ТР (2) и ТП (1).

Решение задачи многокритериального управления построением имитационной модели

В общем случае одним из возможных методов решения задачи определения оптимальных ТР (2) для ТП (1) является метод динамического программирования -метод нахождения последовательных оптимальных решений в задачах с многошаговой (многоэтапной) структурой [5-8].

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

эффективность процесса управления характеризуется многомерной целевой функцией (ЦФ), зависящей от состояния системы и применяемого управления.

Пусть в начальный момент времени (0 этап ТП (1)) система находится в

I ... К-Я ..

I I I

0 этап 1 этап 2 эг

исходном состоянии т0 (рис. 3). На следующем шаге в результате управления у1 система из состояния т0 переходит в состояние т1=g1(т0^ у1) (переход с 0 этапа ТП (1) на 1 этап). При этом достигается эффект Н1 (т0, у1).

^п ~ ёп

П

Рис. 3. Последовательность состояний и управлений

Далее управление у2 переводит систему из состояния т1 в состояние т2=g2(тl9 У2) и достигается эффект ^ (т1, У2).

Принцип оптимальности Беллмана утверждает, что на последовательности

Ji (Т_1, уг, уг+1,..., Уп ) = ^ _1, У1) + ^+1 (т, уг+1) + ...

+ К (тп_l, Уп ), г = 1,..., п.

Введем следующее обозначение:

ёеГ

Рх(Т_1) ° тах(тхп) (14 (т _1, , +1,..., уп^ х = 1,..., п.

Ух> Ух+1— Уп

оптимальных управлений у1 , у2 уг , г=1,...,п, должна достигать тах(тт) каждая из функций

Тогда из (4) и (5) могут быть получены уравнения, называемые

функциональными уравнениями Беллмана

[7]:

Рх (Т_1) = тах(тт)(^х+1 ^(тх_1,Ух))+Ьх (тх_1,Ух)), х =1..., п.

Решение уравнений Беллмана позволяет найти последовательность оптимальных управлений и оптимальных значений ЦФ.

С учетом обозначений нагрузок на дуги графа тш функциональное уравнение (6) принимает вид

Т = тхп

где и е ¥г-1 - номера вершин, из которых исходят дуги графа (г - 1)-го этапа ТП; V е V - номера вершин, в которые входят дуги

Соотношение 1. Пусть тш е Я. Тогда для ТП (1) верны равенства вида [5]

графа г -го этапа ТП; V - множество номеров вершин вида (3) для г-го этапа ТП.

Нагруженные дуги, исходящие из одних и тех же вершин, эквивалентны ввиду интерпретации их характеристик -временных и/или стоимостных затрат для одного и того же ТП (1) построения имитационной модели (создания программного средства), поэтому справедливы следующие соотношения:

У

и

"и е _i"viv2е [TUVi = Tuv2 ], i = 1,...,

n .

Соотношение 2. Пусть tu

(t\7, t

uv > uv

)е Л2, tuv = (t(1),t(2)), t

/ ' uv1 v u^ ' uv1 u

= (t(1) V uv„

t

Тогда для ТП (1) верны равенства вида

Vu е Vt viv2е Vt[(t(1) = t(1)) л (tKZ) =t(Z)) о

i _1 12 i LV uv, u^^ v uv uv О '

-(2) _ (2) -

о (т = т )], г = 1,..., п .

4 ЫУ1 ЫУ 2 ' '

Утверждение 1. Пусть для тЫУ е К справедливы соотношения вида (8). Тогда для рассматриваемой задачи

функциональное уравнение Беллмана (7) принимает вид

ТУ = = -1 + т1П (тах ){ТЫУ } ,

-1

где - оптимальное состояние на г-м

этапе, L, е Л, L0= i = 1, ..., n .

то=0,

i _1

v е Vt,

Доказательство проводится методом математической индукции.

Утверждение 2. Пусть для = (т™ , т™) е я 2 справедливы

соотношения вида (9). Тогда для рассматриваемой задачи из уравнения Беллмана (7) следует [5]

2

u

L, =

L(t _1) 1 + Fmf}

Т + Fm )т

L(i _1) 2 + 2 V u,v | u,v

L,. л, + Fm, <t

(i _1) 1 1 u,v | u,v

= Fm1

uе V,_1

Fm2

pOpt = 1, 2;

L

(i_1) 2

+ Fm 7{t(2)}

2 ^ uv

где Li=(Ln La)T, Lo=(0 0)T, u £ V-i, v £ V , t=1,...,n; pOpt - параметр наивысшего приоритета критериев оптимизации ТП (1) по 1-му (времени) либо 2-му (стоимости ресурсов) измерениям векторов Tuv е Л ; Fm 1, Fm2 е {min, max} - лексикографически упорядоченные параметром pOpt критерии оптимизации ТП по 1-му и 2-му измерениям векторов состояний на этапах ТП соответственно.

Замечание. Доказательство

утверждения 2 проводится с

использованием метода математической индукции с учетом значений измерений векторов Tuv(pOpt) е Л. При этом оптимизация ТП (1) методом динамического программирования (в указанной многокритериальной задаче

def г

Fl ° f

pOpt = 2,1,

выбора предпочтительных ТР

рассматриваемого ТП) в первую очередь проводится по наиболее важному критерию (измерению pOpt векторов е К). В случае совпадения оптимальных по наиболее важному критерию значений для нескольких ТР рассматриваемого оптимизируемого этапа ТП проводится оптимизация по другому, менее значимому из измерений векторов тЫУ(р°Р) е К, по которому и выбираются предпочтительные ТР (2) ТП (1).

Выбор последовательности

оптимальных управлений (оптимальных ТР для ТП либо оптимального маршрута по графу) определяется

последовательностью предикатов вида

\flij е {True , False }, i = 1, ..., n, j = 1,..., | Vt |}.

_1

_1

_1

Пример оптимизационной задачи управления построением имитационной модели

Рассматривается выбранный для управления [6] производственно-исследования ТП построения экономической деятельностью

имитационной модели для системы промышленного предприятия (рис. 4).

0 этап 1 этап 2 этап 3 этап 4 этап 5 этап 6 этап 7 этап 8 этап

Рис. 4. Ориентированный граф с технологическими режимами

Пусть процесс TexPr (1) построения имитационной модели (изготовления программного средства) состоит из n=8

технологических этапов Sti, i=1,___,8: St1 -

вербальное моделирование; St2 -концептуальное моделирование; St3 -разработка формальной модели; St4 -программирование; St5 - верификация; St6 - проведение имитационных

экспериментов; St7 - обработка статистики имитации; St8 - выбор решения.

При этом на каждом из этапов допускается выбор одного из следующего количества допустимых технологических режимов: 1 этап - \V1\=3; 2 этап -\V2\ = 1; 3 этап - \Уз\=3; 4 этап - \V4\ = 1; 5 этап -\Vj\=2; 6 этап - \V6\=3; 7 этап - \Vz\=1; 8 этап - |V8| = 1. Технологические режимы на каждом этапе определены человеческим ресурсом, т.е. используемыми

специалистами, и выбранным

программным обеспечением:

FP1 =< f11, BPwin > , FP 2 =< f11 , Rational Rose > , FP 3 =< f11, Power Designer > , FP 4 =< f21 , BPwin > , FP5 =< f31, Enterprise Architect > , FP6 =< f32, Enterprise Architect > , FP7 =< f33, Enterprise Architect > , Studio > , FP9 =< f51, MS Visual Studio > ,

FP10 =< /52 , MS Visual Studio > ,

FP11 =< /61 ,MS Visual Studio > ,

FP12 =< /62, MS Visual Studio > ,

FP 13 =< /63, MS Visual Studio > ,

FP14 =< /71, Statistica > ,

FP15 =< /71, SPSS > ,

FP16 =< /81, MS Excel Solver > .

Пусть определены временные затраты для каждого из ТР ТП. Время Ti (ч), i=1,...,8, необходимое для

обработки информации при решении одной имитационной задачи на этапах ТП (1): 1 этап - T1 = 5,2; 7,8; 10,3; 2 этап - T2 = 6,0; 3 этап - T3 = 6,4; 6,4; 6,4; 4 этап - T4 = 8,7; 5 этап - T5 = 10,7; 10,1; 6 этап - T6 = 8,6; 8,6; 4,3; 7 этап - T7 = 15,0; 19,0; 8 этап

- T8 = 12,8.

Пусть определены (известны и достоверны) стоимости ресурсов S¡ (руб.),

i=1,___,8, для обработки информации при

решении одной задачи на соответствующих стадиях ТП: 1 этап - S1 = 1499,0; 1543,0; 1485,0; 2 этап - S2 = 5934,0; 3 этап - S3 = 9877,0; 9598,0; 9429,0; 4 этап

- S4 = 2431,0; 5 этап - S5 = 5577,0; 5220,0; 6 этап - S6 = 8584,0; 8544,0; 2287,0; 7 этап -S7 = 16539,0; 15475; 8 этап - S8 = 130,0.

Соответственно с учетом

Ti=(tu,...,tm), Si=(sii,...,st\vi\), i=1,_,8, нагрузки на дуги графа ц е R2 принимают значения: то¡ = то2= тоз= (0,0); тм = (t¡¡, sn),

Т24 = (tl2, S12), Т34 = (tl3,Sl3); T45 = Т46 =

Т47= (t21, S21); Т58 = (t31, S31), Т68 = (t32, S32), T78 = (t33, s33)'; т89 = T8 10 = (t4U s41); T9 11 = T9 12 = T9 13 = (t51, S51), T10 11 = T10 12 = T10 13 = (t52, S52); T11 14 = T11 15 = (t61, S61), T 12 14 = T12 15 = (t62, S62), T13 14 = (t63, S63) T14 16

= (t71, S71), T15 16 = (t72, S72), T1617 = (t81, S81).

Оптимальные ТР ТП (1) определяются согласно принципу поэ т ап н ой оптимизации Беллмана с использованием построенных функций в и д а (10) . При этом строится последовательность двухмерных векторов вида

_ (_

1[1] 1[2]

L_ 2[1] L_ 2 [2]

_ (_  _ (_  I L _ 8[1]

"' L_ 8 [2]

где Ь_8[1], Ь_8[2] - итоговое оптимальное время выполнения этапов ТП и стоимость расхода ресурсов соответственно.

Оптимальный маршрут по графу представляет собой последовательность предикатов (10) следующего вида:

fl 11 fl 12

fl 13 J

(fl 21

fl 31 fl 32 fl 33 J

fl 51 fl 52 J

Г fl 61 ^

fl 62

1 f 63 J

1 f 71 1  (fl 81 )•

Jl 72 J

В результате решения

оптимизационной задачи с заданными исходными данными получены следующие оптимальные ТР выбранного ТП:

1) с минимальными временными затратами и минимальными затратами ресурсов (pOpt=1 - оптимизация в первую очередь по времени (1-я координата), во вторую - по стоимости ресурсов; Fm1, Fm2=min): Lmin* = L_8 = (68,5; 43469,0), где время составило 68,5 ч, стоимость ресурсов - 43469 руб.; маршрут по графу -< 0 - 1 - 4 - 7 - 8 - 10 - 13 - 14 - 16 - 17 >;

Заключение

В представленном исследовании решена задача многокритериального управления технологическим процессом построения имитационной модели в соответствии с принципом оптимальности Беллмана. Обоснованность оптимального решения показана для одно- и двухмерных характеристик потока на дугах ориентированного ациклического графа ТП. Представленный пример решения

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

1. Аверченков, В.И. Метод распределенного построения имитационной модели производственной деятельности промышленного предприятия / В'И. Аверченков, А.И. Якимов, О.М. Демиден-ко, H.H. Ивкина // Южно-Сибирский научный вестник. - 2015. - № 4(12). - С. 22-28.

2) с минимальной суммарной стоимостью затрат ресурсов и времени (pOpt=2 - оптимизация в первую очередь по стоимости ресурсов (2-я координата), во вторую - по времени; Fml, Fm2=min):: Ьтт* = Ь_8 = (77,6; 42391), где время составило 77,6 ч, стоимость ресурсов -42391 руб.; маршрут по графу - < 0 - 3 - 4 - 7 - 8 - 10 - 13 - 15 - 16 - 17 >.

Общий программный комплекс, обеспечивающий решение рассматриваемых задач, описан в работе [8].

оптимизационной задачи с

использованием ресурсов /- и p-типа в корпоративной информационной системе показывает необходимость определения приоритетного критерия для

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

2. Якимов, А.И. Информационная оценка программных средств для управления экономической деятельностью промышленного предприятия на основе имитационной модели / А.И. Якимов, К.В. Захарченков // Вестник Брянского

государственного технического университета. -2014. - № 1(41). - С. 94-101.

3. Шафер, Д.Ф. Управление программными проектами : достижение оптимального качества при минимуме затрат : [пер. с англ.] / Д.Ф. Шафер, Р.Т. Фатрелл, Л.И. Шафер. - М.: Вильямс, 2003.

- 1136 с.

4. Новиков, Ф.А. Дискретная математика для программистов : учебник / Ф.А. Новиков. - 2-е изд.

- СПб.: Питер, 2007. - 368 с.

5. Аверченков, В. И. Многокритериальное управление технологическим процессом с использованием принципа оптимальности Беллмана / В.И. Аверченков, А.И. Якимов, Е.М. Борчик // Известия Волгоградского государственного

1. Averchenkov, V.I. Method for simulation model distributed formation of enterprise production activity / V.I. Averchenkov, А.1. Yakimov, О.М. Demi-denko, N.N. Ivkina // South-Siberian Scientific Bulletin. - 2015. - № 4(12). - pp. 22-28.

2. Yakimov, А.1. Information estimate of software tools for enterprise economic activity control based on simulation model / АТ. Yakimov, K.V. Zakhar-chenkov // Bulletin of Bryansk State Technical University. - 2014. - № 1(41). - pp. 94-101.

3. Shafer, D.F. Program Project Management: Achievement of Optimum Quality at Minimum Costs: [transl. from Engl.] / D.F. Shafer, Я.Т. Fa-trell, L.I. Shafer. - М.: Williams, 2003. - pp. 1136.

4. Novikov, FA. Discrete Mathematics for Programmers: Textbook / FA. Novikov. - 2-d Edition. - S-Pb.: Peter, 2007. - pp. 368.

5. Averchenkov, V.I. Mulicriterion control of technological process using Bellman's Principle of opti-

технического университета. - 2014. - Т. 22. -№ 25(152). - С. 95-101.

6. Якимов, А.И. Технология имитационного моделирования систем управления промышленных предприятий: монография / А.И. Якимов. - Могилев: Белорус.-Рос. ун-т, 2010. - 304 с.

7. Беллман, Р.Э. Динамическое программирование и уравнения в частных производных / Р.Э. Беллман, Э. Энджел. - М.: Мир, 1974. - 420 с.

8. Аверченков, В.И. Концепция оценки эффективности процессов управления в корпоративных информационных системах предприятий / В.И. Аверченков, С. К. Крутолевич, А. И. Якимов, К.В. Захарченков // Вестник Брянского государственного технического университета. - 2016. -№1 (49). - С. 113-119.

mality / V.I. Averchenkov, A.I. Yakimov, Е.М. Borchik // Proceedings of Volgograd State Technical University. - 2014. - Vol. 22. - № 25(152). -pp. 95-101.

6. Yakimov, A.I. Simulation Techniques of Enterprise Control Systems: Monograph / A.I. Yakimov. -Mogilyov: Belorus.-Russian University, 2010. - pp. 304.

7. Bellman, R.E. Dynamic Programming and Partial Derivative Equations / R.E. Bellman, E. Engel. -М.: World, 1974. - pp. 420.

8. Averchenkov, V.I. Concept of control efficiency estimate in corporate information systems of enterprises / V.I. Averchenkov, S.K. Krutolevich, A.I. Yakimov, K.V. Zakharchenkov // Bulletin of Bryansk State Technical University. - 2016. - №1 (49). - pp. 113-119.

Статья поступила в редколлегию 28.04.2016.

Рецензент: д.т.н., профессор Брянского государственного технического университета

Спасенников В. В.

Сведения об авторах:

Аверченков Владимир Иванович, д.т.н., профессор Брянского государственного технического университета, е-тах1:ауег@,1и-ЬгУа^кш. Якимов Анатолий Иванович, к.т.н., доцент кафедры «Автоматизированные системы управления» Белорусско-Российского университета, тел.: +375 (222) 252447, +375 (44) 7163816, е-тах1: Укт@,М.ЬУ.

Якимов Евгений Анатольевич, к.т.н., ст. преподаватель кафедры «Автоматизированные системы управления» Белорусско-Российского университета, е-тах1: e-soft@bk.ru.

Ивкина Наталия Николаевна, аспирант Брянского государственного технического университета, е-тах1: к^@Ди-ЬгУа^к.ги.

Averchenkov Vladimir Ivanovich, D.Eng., Prof. of Bryansk State Technical University, е-mail:aver@tu-bryansk.ru.

Yakimov Anatoly Ivanovich, Can.Eng., Assistant Prof. of the Dep. "доцент кафедры «Automated Management Systems" Belarussian-Russian University, Phone: +375 (222) 252447, +375 (44) 7163816, е-mail: ykm@tut.by.

Yakimov Eugene Anatolievich, Can.Eng., Senior lecturer of the Dep."Automated Management Systems" Belorussian-Russian University, е-mail: e-soft@bk.ru.

Ivkina Nataliya Nikolayevna, Post graduate student Bryansk State Technical University, е-mail: kts@tu-bryansk.ru.