Задачи online – оптимизации: парадигма и методы
Глушкова В.В., Ершов С.В., Каспшицкая М.Ф.
Глушкова В.В., Ершов С.В., Каспшицкая М.Ф.
Задачи online– оптимизации: парадигма и методы
В 1964 г. был опубликован первый проект Единой Государственной Сети Вычислительных Центров ( ЕГСВЦ) , впоследствии доработанный и получивший название ОГАС (ОбщеГосударственная Автоматизированная Система управления экономикой ) [1] . Одной из отличительных черт этого и последующих проектов было управление экономическими и социальными процессами страны в onlineрежиме. За это отвечали Автоматизированные Системы Управления (АСУ) различного назначения.Сегодня аналогами АСУ различных уровней в экономике являются системы, осуществляющие управление бизнес-процессами, производственными процессами, управление финансовыми потокамии т.д., такие, к примеру, как - BPM (англ. BusinessProcessManagement, управление бизнес-процессами), ERP (англ.EnterpriseResourcePlanning, планирование ресурсов предприятия), MES (англ. ManufacturingExecutionSystem, система управления производственными процессами), CRM-система, (англ. CustomerRelationshipManagement, Система управления взаимоотношениями с клиентами) и др. В этих системах часто приходится решать очень сложные в вычислительном отношении задачи в реальном режиме времени. Подобные же задачи очень часто возникают при работе сегодняшних ситуационных центров, идеология которых также в свое время также была разработана и заложена в проекте ОГАС.
В даннойработе авторами рассматриваетсямодель многокритериальной, комбинаторной задачи onlineоптимизации с нечеткими даннымии предлагаются приближенные методы для ее решения, позволяющие решать задачу в onlineрежиме.
Рассматривается новый класс оптимизационных задач [2] на примере комбинаторных задач – комбинаторные online– оптимизационные задачи. Отличие этих задач от представленных в научной литературе задач оптимизации состоит в том, что ищется оптимальное решение на заданном временном отрезке при выполнении ограничительных условий, зависящих от времени и принятых предыдущих решений. Вообще говоря, при online– оптимизации осуществляется поиск оптимального значения интеграла целевой функции F(x,t) при изменении временного параметра tна фиксированном отрезке [0,T] при выполнении определенных ограничительных условий на переменные, входящие в формальную постановку задачи:
F(F(t),x(t),t)= 
F(x(t))dt, tÎ[0,T].
Естественно , что функция Fможет иметь и другой вид: суммы, меры, энтропии и др. Многие производственные задачи можно формализовать как комбинаторные задачи online– оптимизации. Например, задачи оптимизации прибыли за определенный период времени (год) при сезонном производстве с учетом ограничений на ресурсы. Также ряд оптимизационных задач планирования в производственной, финансовой, социальной сферах могут быть рассмотрены в обозначенном выше аспекте.
Итак, рассмотрим класс комбинаторных задач online– оптимизации. Пусть имеется некоторый объект, в результате функционирования которого образуется прибыль P. ТребуетсяоптимизироватьприбыльP за промежуток времени Т, например, за год. Уточним величину P.Пусть
P=P(T) = 
,
т.е. прибыль является суммой nвеличин. Каждая из величин Pi(t) зависит, кроме того, от определенной совокупности переменных, что принадлежат областям, изменяющимся во времени, т.е.
Pi(t) = pi(t, xi1, xi2, . . . ,
),
причем xij(i)ÎDij(i)(t) – числовые или комбинаторно–числовые переменные.
Задача состоит в оптимизации величины P(T) при выполнении ограничительных условий на переменные в течение временного периода [0,T]. В случае неограниченных ресурсов решение состояло бы из суммы элементарных оптимумов (дневных) на протяжении времени Т (года). Если ресурсы ограничены, то процесс решения значительно усложняется: нужно работать с «оглядкой» на предыдущие и последующие шаги оптимизации.
Отметим, что «ресурс» (допустимая область) изменяется в зависимости от времени и предыдущих решений.
Следует отметить также, что задачи рассматриваемого типа очень сложные в вычислительном отношении. Поэтому целесообразно применять для их решения приближенные методы, в частности, локально-оптимальные [3,4].
Необходимо отметить еще один момент. Рассматриваемый класс задач по своей сути является нечетким, т.е. при формализации используются как приближенные величины, так и упрощенные зависимости, т.е. здесь уместно использование теории нечетких множеств [5].
В настоящей работе рассмотрена многокритериальная комбинаторная online-оптимизационная задача для случая разнородных информационных данных, представленных для ее решения. Предлагается online-модификация нечеткого варианта метода вектора спада, описана соответствующая версия для определения приближенного множества Парето.
Постановка задачи. Пусть дано множество А(t) элементов, зависящее от параметра t, |A(t)|=n(t), и множество признаков B(t), |B(t)|=k(t).
Причем, относительно множества B(t) заметим, что оно состоит из объектов различной природы: четких чисел, нечетких чисел, булевых либо лингвистических переменных. И пусть каждому из элементов ai(t), i=1,2,…,n(t)множества A(t) поставлен в соответствие кортеж из k(i(t)) объектов, принадлежащих множеству B(t). Таким образом, множеству A(t) соответствует таблица 
, где aij(t) – признак bj(t)ÎB(t) элемента ai(t), представленный объектом одного из четырех названых выше видов.
Суть задачи состоит в том, чтобы для каждого tÎ[0,T] выбрать из множества A(t) подмножество A0(t)ÊA(t) изm(t)элементов таким образом, чтобы достичь оптимума функционалов 
, r=1, . . . ,r0при выполнении условия U(x,t)£C0(t), tÎ[0,T], C(t) – некоторая константа, зависящая от временного параметра.
Для приближенного решения этой задачи предлагается нечеткий локально-оптимальный метод, являющийся обобщением метода, изложенного в [6]. Суть этого метода состоит в построении приближенного множества Парето, соответствующего определенному tÎ[0,T].
С п и с о к л і т е р а т у р и
1. Морозов А.А., Глушкова В.В., Жабин С.А. Научные и организационные принципы информационного общества в проекте ОГАС 1980 г., Гилея № 71 (4), стр. 921-926.
2. Каспшицька М.Ф., Єршов С.В. Задачі online-оптимізації комбінаторного типу. Компьютерная математика, 2014, №2, стр.
3. Сергиенко И.В. Математические модели и методы решения задач дискретной оптимизации. –Киев: Наук. Думка, 1985. – 384с.
4. Korte B., Vygen J. Combinatorial Optimization: Theory and Algorithms, 5th Edition. –Berlin: Springer, 2012. –678p.
5. Ємець О.О., Ємець Ол.О. Розв`язування задач комбінаторної оптимізації на нечітких множинах. –Полтава: ПУЄТ, 2011. –239с.
6. Парасюк И.Н., Каспшицкая М.Ф. О развитии метода вектора спада на случай размытых окрестностей //Компьютерная математика. –2008. – №2. – С. 145–155.
Матеріали Всеукраїнської науково-практичної конференції, присвячено 50-річчю проекту ОГАС "В.М.Глушков - піонер кібернетики", НТУУ "КПІ",11 грудня 2014 р., м. Київ, стр. 44-46
