Формирование состава методов, минимизирующих суммарные затраты на решение задач управления

Тип работы:
Реферат
Предмет:
Кибернетика


Узнать стоимость

Детальная информация о работе

Выдержка из работы

УДК [303. 732. 4:519. 816]: 687. 513. 6/.8 ББК 22. 183. 1:32. 965. 9
Г. А. Попов, Е. А. Попова
ФОРМИРОВАНИЕ СОСТАВА МЕТОДОВ, МИНИМИЗИРУЮЩИХ СУММАРНЫЕ ЗАТРАТЫ НА РЕШЕНИЕ ЗАДАЧ УПРАВЛЕНИЯ
G. A. Popov, E. A. Popova
FORMATION OF THE STRUCTURE OF THE METHODS MINIMIZING TOTAL COSTS OF THE SOLUTION OF MANAGEMENT PROBLEMS
Исследуется проблема выбора оптимального состава методов для решения заданной совокупности задач. Критерием оптимальности является целевая функция, учитывающая прибыль от решения задач заданными методами и издержки, связанные с реализацией методов. Приведены формализованные постановки указанной задачи, описаны процедуры формирования исходных данных. Отмечено, что полученные задачи могут быть решены стандартными методами целочисленного программирования.
Ключевые слова: задача метаоптимизации, методы решения задач, эффективность результата решения, издержки метода, формализованная постановка.
The problem of the choice of the most optimum structure of methods for the solution of the specified set of tasks is studied. The criterion of the optimality is a target function considering profit on the solution of tasks by the specified methods and expenses, connected with realization of the methods.
The formalized statements of the specified task are given- the procedures of formation of basic data are described. It is noted that the received tasks can be solved by the standard methods of integer programming.
Key words: problem of metaoptimization, methods of the task solution, efficiency of the decision result, the method expenses, the formalized statement.
Введение
Одной из серьезных проблем, возникающих при формировании множества задач управления путем построения дерева целей на основе методов системного анализа, является большое число задач, получаемых в результате реализации методики в полном объеме. Так, например, при формировании дерева целей для типового вуза на основе метода Сагатовского в [1] была проведена оценка общего количества задач, которое получится на седьмом уровне после полной реализации методики: оказалось, что общее число задач превосходит 50 000, что практически невозможно реализовать на практике. Возможным выходом из подобной ситуации является прекращение детализации полученных задач на определенном уровне так, чтобы количество задач, полученное в результате подобного прекращения процесса их формирования, не превосходило заданной приемлемой величины. Однако при этом может оказаться, что в действительности прерванная задача реально представляет собой целую совокупность близких задач. Возникает проблема: как подбирать методы, пригодные для решения целой совокупности задач, наиболее рациональным образом. Именно этой проблематике и посвящена предлагаемая работа. Исследования по данной тематике ранее проводились в [2, 3].
Формализованная постановка задачи
Итак, на основе системного анализа целей и задач и существующих методов их решения можно разработать процедуру выбора методов в зависимости от характера подлежащих решению задач. Одним и тем же методом в общем случае можно решать различные задачи и одну и ту же задачу можно решать различными методами. В то же время, очевидно, существует один или несколько наиболее эффективных методов решения для каждой задачи. Тогда, если в системе управления необходимо регулярно решать некоторый набор задач, можно выбрать и реа-
лизовать в системе такую совокупность методов, чтобы общая эффективность решения задач была наибольшей. Возникает проблема, как осуществить выбор искомой совокупности методов. Указанная проблема может быть сформулирована в виде следующей задачи оптимального выбора методов решения — задачи метаоптимизации [2]. Приведем одну из возможных постановок общей задачи метаоптимизации.
Пусть с некоторой известной периодичностью должны решаться задачи из множества 2 = {2!, 22,…, 2П}, причем под 2 у может пониматься как вполне конкретная одна задача, так
и группа или класс однотипных задач. Пусть, далее, имеется множество методов М = {МХ, М2, …, Мк}, которые могут быть использованы в системе для решения этих задач, причем каждая задача может быть решена хотя бы одним методом. Далее, пусть
и Qvm (п = 1, п- т = 1, к) есть соответственно эффективность результата от решения п-й задачи
ц-м методом и связанные с этим издержки. Тогда в наиболее общей постановке задача метаоптимизации может быть сформулирована следующим образом: выбрать такую совокупность А
П К
методов из множества М, чтобы величина ^ ^ - QVm) была максимальной и при этом вы-
п=1 т=1
полнялись заданные ограничения на время решения, объем используемой памяти и затраченные на решение ресурсы. Отметим, что время решения и объем используемой памяти могут быть заключены в оптимизационный функционал.
Приведем формализованную модель этой задачи, ее возможные варианты, а также возможные методы решения получающихся вариантов задачи метаоптимизации.
Анализ параметров, требуемых для решения задачи метаоптимизации
Введем обозначения: п — число задач, которые требуется решать в системе- К — число имеющихся методов решения- 17 — частота решения 7-й задачи за данный фиксированный период времени- сК)(К = 1,3) — удельные затраты: на реализацию алгоритма (К = 2), теоретический анализ и подготовку исходных данных (К = 1) применительно ку-му методу- Pj — эксплуатационные затраты, связанные с у-м методом, в течение рассматриваемого интервала времени- и у — средние (потенциальные) потери при однократной реализации у-го метода- V — максимальный экономический эффект от решения 7-й задачи- е37К) (К = 1,3) — среднее время подготовки исходных данных для реализующего алгоритма (К = 1), работы алгоритма (К = 2) и теоретический анализ модели для приведения ее к виду, удобному для алгоритмической реализации (К = 3) при решении 7-й задачи у-м методом- М — максимальный объем памяти, доступной для использования- 7 — максимально допустимое время решения 7-й задачи- еКу) [1] -значение К-го (К = 1,7) универсального показателя эффективности применения у-го метода к решению 7-й задаче, где ?1 — показатель адекватности модели, построенной на основе данного метода, решаемому классу однородных задач- е2 — показатель универсальности модели, характеризующей пределы ее адекватного применения при варьировании характеристик исходной задачи- ?3 — показатель средней трудоемкости решения задач данного класса рассматриваемым методом- ?4 — показатель средней погрешности решения задач данного типа рассматриваемым методом- ?5 — показатель среднего объема памяти, требуемой для решения задач данного класса рассматриваемым методом- ?6 — показатель устойчивости метода при решении задач данного класса, характеризующей чувствительность метода к варьированию характеристик исходной задачи- ?7 — показатель толерантности решения задач данного класса рассматриваемым методом, характеризующий удобство получения результата для восприятия и использования.
Предположим, что доход У7у за рассматриваемый период от решения 7-й задачи у-м
методом выражается зависимостью
(,) с (у& quot-) с (гЛ с ('-) с'-
4
6
е^),
где /() — коэффициент уменьшения максимального эффекта при решении 7-й задачиу-м методом, вызванного несовершенством метода или степенью его несоответствия модели поиска. Возможный вид функции обсуждается ниже. Тогда доход за рассматриваемый период от решения 7-й задачи у-м методом Я7]- равен: Я7]- = 17У7]-. Далее, величина финансовых затрат за рассматриваемый период от решения 7-й задачи у-м методом равна:
о, = X, (& lt-с<- '-¦ е& lt-у+с, ¦ + 4 '-& gt-. е& lt-5)).
На основе приведенных соотношений заключаем, что прибыль, равная разности между доходом и финансовыми затратами, за рассматриваемый период времени от решения і-й задачи ,-м методом равна:
О =Х, у. /(е, е2У), е (і), е"'-), е,-е6)и] - X4'-)е35
(1)
т=1
Введем следующую переменную: Ху = 1, если у-й метод включен в формируемый пакет методов решения, и Ху = 0 в противном случае. Тогда суммарная прибыль за рассматриваемый период равна:
Л* п К К
І = '- -XР,
,=1 і=і і=і
, х, •
(2)
При этом методы, входящие в пакет методов решения, должны удовлетворять определенным ограничениям на требуемый объем памяти и суммарное время решения разных задач, а именно:
е ('-) & lt- М,
е (Ю
= X
е (іі)
¦'-Зт
(3)
(4)
т=1
Таким образом, одна из общих формализованных постановок задачи метаоптимизации может быть записана в виде: выбрать величины Х К 1 так, чтобы выполнялись ограничения (3), (4) и величина I достигала максимального значения, т. е. (ввиду (1) и (2)):
К
Ґ
Xх, XX, У ¦ /К'-е& gt-, е'- е"'-1. е"& gt-)-е?%(- Xс
І=1 і=1 [ т=1
3 ___ ____
е (г,) & lt-М, X еЗт & lt- Т (і = 1, п), X, = 0 V1, = 1, К)•
Л
(і)е ('-) I- р
к Ч к г г'-
(r) тах, {х,}
(()
т =1
3
Анализ возможного вида функции затрат
В оптимизируемый функционал задачи (5) входит неизвестная функция затрат/(). Исследуем ее возможный вид. Как следует из определения функции /(), она характеризуется двумя группами факторов: степенью «несовершенства» модели задачи по отношению к рассматриваемому методу решения, что характеризуется показателями е (7/), е27/), и возможностями
самого метода, что характеризуется показателями е4у),. Поэтому представляются ес-
тественными предположения, что функция /() разбивается в произведение двух функций, т. е. представлена в виде
1(8
/ (?j, e2, ?4, e6, e7) = /jCej, e2) /2(64, e6, e7),
где функции /1() и f2()изменяются в пределах от 0 до 1. /1() и /2()есть коэффициенты, отражающие степень приемлемости рассматриваемого метода задаче и эффективность самой процедуры поиска на основе этого метода для решения задачи соответственно.
Исследуем вначале возможный вид функции /1(). Ниже будем предполагать, что оценки ?1 и ?2 представлены в виде числовых величин. Для этого, если ?1 и ?2 имеют форму лингвистических оценок, их надо предварительно перевести в числовую форму, пользуясь одной из возможных шкал преобразования (например, шкалой Харрингтона).
Рассмотрим маргинальные свойства функции /1(). Если ?1 = 0, т. е. рассматриваемый метод совершенно неприемлем для решения рассматриваемой задачи, необходимо /(?1, ?2) = 0 для любого ?2. Если ?1 = 1, т. е. метод полностью приемлем по своей структуре для решения рассматриваемой задачи, необходимо /(?1, ?2) = 1. Далее, если ?2 = 0, т. е. метод совершенно не универсален и способен решать только те задачи, которые заложены в его модели, необходимо / (?1, ?2) =?1. Если же ?2 = 1, т. е. метод способен решать существенно больший круг задач, получающихся на основе обобщения исходной задачи, будем считать, что в этом случае величина /1() увеличивается (по сравнению со случаем ?2 = 0) на величину, пропорциональную самой оценке (т. е. ?1) и ее дефекту (т. е. 1 — ?1) — получаем соотношение:
/1(?1,1) = ?1 + K?1(1 — ?1)(K & gt- 0) для любых ?1 е [0,1]. Нетрудно убедиться, что условие
max /1(?1,1) & lt- 1 включает условие K & lt- 1.
0& lt-?1 & lt-1
Таким образом, получаем следующее соотношение:
Г/1(0, ?2) = 0, /1(1, ?2) = 0, /1(?1,0) = ?1,
1/1(?1,1) = ?1 + K ?1(1 — ?1).
Представим /1() в виде /1(?1, ?2) = ?1 • ?1(?1, ?2). Тогда из (6) следует, что q1(?1, ?2) конечно для всех ?1, ?2 е [0,1] и справедливы соотношения:
^(1,?2) = 0, q1 (?1,0) = ?1, ^(?1,1) = ?1 + K (1 — ?1).
Далее, аналогично продолжается цепочка преобразований и обозначений:
^(?1, ?2) = 1 + (1 — ?1)& lt-?2(?1, ?2), ^(?1,0) = 0,2 (?1, 1) = 1 K-
q2 (?^ ?2) = ?2 • q3 (?1, ?2), q3 (?1,1) = K-
& lt-?э (?1, ?2) = K + (1 — ?2)& lt-?4(?1, ?2), причем все функции qm (?1, ?2)(m = 2,4) конечны для всех ?1, ?2 е [0,1]. Отсюда выводим:
/1(?1, ?2) = ?1 {1 + (1 — ?1)?2 (K + (1 — ?1)q4(?1, ?2))}.
В последнем выражении K и функции q4(?1, ?2) могут быть произвольными. Полагая (для простоты и определенности) K = ½ и q4(?1, ?2) = 1, окончательно получаем
/1 (?1, ?2) = ?1{1 + (1 — ?1)?2(½ + (1 — ?1)}.
Рассмотрим теперь функцию /2 (•). Заметим, что если все рассматриваемые методы являются конечными и итерационными, то в качестве /2 (•) можно взять введенный в [4] пронормированный показатель приемлемости конкретного метода для решения конкретной задачи. В противном случае оценку конкретных значений /2 (•) можно получить на основе экспертных процедур.
Таким образом, процедуры нахождения значений f1() и У20 описаны, что позволяет решить задачу метаоптимизации (5) на основе любого метода целочисленного программирования.
Постановка задачи метаоптимизации для систем реального времени
В задаче метаоптимизации суммарное время решения задач за рассматриваемый период может быть введено в критерий оптимизации, что часто важно для задач, решаемых в режиме
n к
реального времени, для задач оперативного управления. Положим J = XXX, e3J) Xi. Тогда
i=1 i=1
соответствующая задача метаоптимизации может быть записана в виде следующей многокритериальной задачи:
Г/ ® max, J ® min,
[е (/) & lt-M, x = 0 v 1 (i = 1П- J = 1K).
Заключение
Приведенные постановки задач метаоптимизации в системах принятия решений используются в направлениях и сферах, относящихся к искусственному интеллекту (в частности, в робототехнике), где возникает необходимость обеспечить решение большого числа близких задач на основе заданного набора методов. В этом случае, при возникновении относительно новой (незнакомой) задачи, начальный выбор метода может быть осуществлен на основе решения соответствующей задачи метаоптимизации. В дальнейшем, при дополнении описанной методологии решения задач соответствующими процедурами самообучения [5], может быть найден более приемлемый метод решения указанной задачи, а соответствующие коэффициенты, описывающие степень приемлемости выбранного метода для решения рассматриваемой задачи, будут уточнены. Указанную процедуру предполагается рассмотреть в последующих работах.
СПИСОК ЛИТЕРАТУРЫ
1. Попов Г. А., Попова Е. А. Классификация функций и задач вуза на основе метода Сагатовского // Вестн. Астрахан. гос. техн. ун-та. Сер.: Управление, вычислительная техника и информатика. — 2009. -№ 1. — С. 7−17.
2. Герасименко В. А., Попов Г. А., Таирян В. И. Основы оптимизации в системах управления. — Деп. в ВИНИТИ, № 213-В89, 1989. — 497 с.
3. Попов Г. А., Попова Е. А. Процедура оценки эффективности методов оптимизации: тез. докл. Междунар. конф. «Математические методы в технике и технологиях — ММТТ-23». — Саратов, 2010. -Т. 7. — С. 72−75.
4. Попов Г. А. Модель оценки уровня развития самообучающейся системы // Вестн. Астрахан. гос. техн. ун-та. — 2008. — № 2 (43). — С. 251−257.
5. Шлезингер М. П., Главач В. Десять лекций по статистическому и структурному распознаванию. -Киев: Наук. думка, 2004. — 548 с.
Статья поступила в редакцию 27. 06. 2012 ИНФОРМАЦИЯ ОБ АВТОРАХ
Попов Георгий Александрович — Астраханский государственный технический университет-
д-р техн. наук, профессор- зав. кафедрой «Информационная безопасность», popov@astu. org.
Popov Georgiy Aleksandrovich — Astrakhan State Technical university, Doctor of Technical Sciences,
Professor- Head the Department & quot-Information Security& quot-- popov@astu. org.
Попова Екатерина Александровна — Астраханский государственный технический университет-
старший преподаватель кафедры «Информационная безопасность" — popova@astu. org.
Popova Ekaterina Aleksandrovna — Astrakhan Technical State university, Senior Lecturer
of the Department & quot-Information Security& quot-- popova@astu. org.

ПоказатьСвернуть
Заполнить форму текущей работой