Широкое распространение получили модели математического, дискретного программирования в силу комбинаторного характера задач.

Рассмотрим типовую постановку задачи синтеза структуры системы управления сложным объектом.

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

§19 Классические задачи принятия решений

Под задачей принятия решения будем понимать процесс, который включает в себя:

генерирование альтернативных вариантов решения;

их оценку по заданному критерию эффективности;

выбор из них наилучшего.

Столь общее определение требует введения математического формализма, поэтому будем использовать аппарат общей теории систем. Дадим определение системы.

Под системой «вход-выход» в самом общем случае (абстрактная система) будем понимать отношение

(1.1)

где Y - множество параметров, называемых входными,

X - множество параметров, называемых выходными,

- знак декартова произведения.

Если отношение (1.1) является функцией, то следует пользоваться отображением:

(1.2)

Теперь сформулируем задачу принятия решения.

Пусть Y - множество исходных данных.

Конкретизация элемента y0Y приводит в дальнейшем к получению решения с конкретными числовыми параметрами, зависящими от y0.

Множество неопределённостей обозначим H, в нём элемент hH характеризует свойство действующих случайных возмущений или степень незнания параметров задачи.

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

Собственно решение задачи обозначим x, а всё множество возможных решений - X.

Построим на перечисленных множествах выходную функцию:

(1.3)

определяющую структуру и содержание задачи принятия решений.

Зададим оценочную функцию

(1.4)

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

Введём функцию допустимости (толерантности)

(1.5)

определяющую предельные значения качества решения (1.4).

Сформулируем задачу отыскания удовлетворительных (допустимых или толерантных) решений в следующем виде.

Заданы элемент y0Y и множество UfU.

Требуется определить такой элемент u0Uf и соответствующий ему элемент x0X, при которых для всех hH будет выполняться неравенство

(1.6)

Таким образом, шестёрка

(1.7)



Рис. 30 Граф поиска дополнительного решения

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

Задачу принятия оптимальных решений сформулируем следующим образом. Даны элемент y0Y и подмножество Uf. Требуется определить такой элемент u*Uf и соответствующий ему элемент x*X, при которых для всех hH и для всех uUf (u u*) будет выполняться неравенство

(1.8)

Граф процесса поиска допустимого решения.

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

(1.9)

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

Рис. 31 Граф поиска оптимального решения

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

(1.10)

Для поиска оптимального решения требуется при заданных y0Y и множестве UfU найти такой элемент u*Uf и соответствующий ему x*X, при которых для всех uUf (u u*) будет справедливо неравенство

(1.11)

Качественная постановка задачи принятия оперативных решений и обоснование необходимости формализации понятия «сложности».

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

,

- время решения задачи,

- допустимое время.

Такие задачи будем называть задачами принятия оперативных решений.

Задачи принятия оперативных решений свойственны 4-му, 3-му и в ряде случаев 2-му уровням (иерархическая схема типа).

Каким же образом можно формализовать задачи принятия оперативных решений? Казалось бы, достаточно к ограничению (1.6) ввести ограничение , однако математически это не корректно, т.к. связи между временем счёта и остальными параметрами классической задачи принятия решений не формализованы (нет зависимости между управлениями uUf и и т.д.). Следовательно, нужен иной формализм для зачачи принятия оперативных решений, более мощный.

Обратимся к практике построения СУ, в которых реализованы алгоритмы принятия оперативных решений. В них: проанализированы все возможные состояния системы и получено предельное (наименьшее) значение допустимого времени . Затем выбран такой алгоритм, который позволяет получить некоторое законченное решение за предельное время. Естественно, что вопрос о близости полученных решений к оптимальным не ставится, и эффективность СУ с алгоритмами такого типа крайне низка.

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

Недостатки систем такого типа:

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

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

Следовательно, разумно иметь набор алгоритмов, а ещё лучше - «гибкий» алгоритм, позволяющий за отведённое время получать решение задачи, максимально близкое (в заданном смысле) к оптимальному.

Однако для этого нужен соответствующий математический формализм.

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

При расчёте и проектировании САУ и АСУ к математической модели выдвигается ряд новых требований учёта технических, эксплуатационных и экономических показателей. Эти требования могут быть удовлетворены при использовании принципа сложности.

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

Пусть конечное или бесконечное множество

(1.12)

есть множество вариантов решения (траектории движений, алгоритмов, конструкций систем и т.д.) , причём запись xi X означает, что i-й вариант решения удовлетворяет всем ограничениям, определяемым природой рассматриваемой задачи.

Пусть также заданы критерий E(xi), отражающий степень достижения цели принимаемого решения, и показатель Z(xi), отражающий сложность (трудоёмкость, стоимость и т.д.) i-го варианта решения, т.е. являющийся «внутренним» показателем по отношению к решаемой задаче. Если задать допустимую область значений критерия E(xi), т.е. , и поставить задачу поиска решения наименьшей сложности

(1.13)

то можно дать простейшую формулировку принципа минимальной сложности.

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

(1.14)

можно получить формулировку принципа ограниченной сложности.

Выбор критерия E(xi) и показателя Z(xi) во многом определяет характер решаемой задачи.

Теперь обратимся к анализу математической теории сложности. Их к настоящему времени известно 5. Рассмотрим основные понятия этих теорий и оценим эффективность их применения для принятия оперативных и проектных решений.

§20 Алгоритмическая теория сложности

Пусть s S некоторая индивидуальная задача принятия решения из класса S и пусть x X - её решения на множестве X. Для решения любой задачи из класса S имеется алгоритм A, позволяющий с помощью программы P получить на универсальной машине (машина Тьюринга и машина Поста) со структурой (P,S) решение х задачи s.

Структура (P,S) - это частично рекурсивная функция, такая что (P,S)=х.

Обозначим через l() длину программы P, где - число знаковых символов её записи.

Чаще всего =2, т.к. для записи программы используется двоичный код.

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

(15)

Если (P,S)х , т.е. решение задачи s с помощью программы P не возможно, то .

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

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

§21 Теория информационной сложности

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

В информационной теории сложности используют предложенное Н.С.Бахваловым формальное понятие «метод решения».

Это понятие применяют к некоторому семейству задач математического программирования F, которое определяется тройкой , где E(X) - критерий оптимизации, зависящий от вектора переменных X размерности n;

G(X) - система ограничений вида

- линейные или нелинейные функции n переменных х_i;

Х - область определения х, причём обычно X=R.

Дополнительно введём понятие оракула О, который определяется:

множеством допустимых вопросов, на которые О может «ответить», характеризуя параметры оптимизационного процесса, в том числе текущее состояние вектора X.

Множеством возможных ответов;

Функцией наблюдения , приводящей в соответствие каждому конкретному вопросу для любой индивидуальной задачи из семейства F конкретный ответ yY.

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

Метод решения В - набор инструкций для формирования на каждой итерации вопросов «оракулу» и набор правил, определяющий момент останова процесса вычислений и момент формирования решения. По отношению к методу В «оракул О» можно трактовать как описание индивидуальной задачи из семейства F.

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

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

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

§22 Теория вычислительной сложности

В теории вычислительной сложности формируется пара , составленная из алгоритма А, предназначенного для решения системы задач S и , в частности, конкретной (индивидуальной) задачи s из семейства S.

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

Наибольшее распространение получила сигнализирующая времени T_A(S) , определяющая число шагов, которые необходимо проделать алгоритму А для решения индивидуальной задачи sS.

Для оценки эффективности алгоритма А на семействе задач S в теории вычислительной сложности используется верхняя оценка сигнализирующей времени

(17)

а для выбора алгоритма из заданного набора {A}, наиболее эффективного для решения задач S, минимальная оценка

(18)

Помимо сигнализирующей времени формируют следующие функции сложности:

сигнализирующая ёмкости - число ячеек оперативной памяти, необходимых для решения задачи sS алгоритмом А;

сигнализирующая колебаний (поворотов) - количество циклов в программе для реальной ЭВМ, которые изменяют типовую последовательность вычислений;

сигнализирующая режима - число обращений к долговременным запоминающим устройствам.

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

Различают задачи полиномиальной и экспоненциальной сложности:

O(n²), O(n³)

O(aⁿ), O(bn^logn) и т.п.

Для (1) относятся задачи а) перемножения двух матриц порядка n; б) о кратяайшем маршруте на графе с n вершинами.

Для (2) - экстремальные задачи комбинаторного типа и задачи теории графов.

Задачи, для решения которых разработаны алгоритмы полиномиальной сложности, относятся к классу P-сложных задач.

Задачи, для решения которых разработаны алгоритмы экспоненциальной сложности, относятся к классу NP-полных задач.

Класс задач P-сложности является подклассом NP-сложных задач.

В книге Гэри М., Джонсон Д. «Вычислительные машины и труднорешаемые задачи», Мир, 1982

предложена классификация задач принятия решений.

Приведён список 300 NP-сложных задач. Этот подкласс характерен тем, что, если хотя бы для одной из них будет разработан алгоритм решения полиномиальной сложности, то аналогичные алгоритмы можно получить для всех NP-полных задач.

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

§23 Теория -сложности.

В 1980 г. (США) появилась первая монография о результатах работы по теории сложности, проводимой в … университете.

Первоначально теорию называли: теория аналитической сложности, затем -сложности, наконец, теорией информационной сложности. Далее будем использовать термин «-сложность», чтобы существовало отличие от теории информационной сложности.

Отличие от вычислительной сложности(оперируют с точной, полной и бесплатной информацией) в следующем:

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

Применяя теорию -сложности, можно ответить на следующие вопросы:

можно ли решить данную задачу с точностью ;

сколько это будет стоить или какова сложность задачи;

Рассмотрим основные понятия этой теории.

Пусть имеются два множества F={f} и G={g}, в которых f - элемент задачи, g - элемент решения.

Класс всех подмножеств множества G обозначим 2^G и введём оператор решения S

Оператор решения S должен обладать следующими свойствами:

а) для всех fF

б) при h₁ h₂ (19)

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

, где H - образ множества F, N(f) - располагаемая информация об элементе f.

Информационный оператор N называют полным, если он содержит всю информацию об f , и неполным в противном случае.

Рассмотрим множество

где V(N,f) - множество всех элементов f, неотличимых с помощью информации N(f) от некоторых фиксированных .

Т.к. множество А должно удовлетворять условию типа (19), то существует оценка

, которую называют локальным радиусом информации.

Глобальный радиус информации в теории -сложности

Очевидно, что если заданная допустимая погрешность , то получить решение с заданной точностью невозможно.

Для введения понятия «сложность» необходимо задать множество P простейших операций: арифметические операции, операции сравнения, операции определения максимума из n чисел и т.п. Пусть N₀ - приближённый информационный оператор. Его называют допустимым, если для всех fF существует программа вычисления N₀(f) , состоящая из конечного числа простейших операций. Если такими операциями являются p₁, p₂, …, p_l, то сложностью оператора N₀(f) называют сумму

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

Пусть R(N₀) - класс реализуемых алгоритмов, для которых радиус информации r(R(N₀),N₀) не превосходит заданную погрешность.

Сложность алгоритма

а -сложность

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

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

Число практических приложений -сложности невелико.

Глава 9 Задачи принятия решений на расширенных множествах по скалярному критерию

§24 Постановка задач

В (1.7) предполагалось, что все элементы P, G, D, y⁰ и множества U^f, H определены, при которых задача сводится к перебору всех управлений uU^f для выбора оптимального решения или к перебору до первого выполнения условий толерантности при поиске допустимого решения.

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

Такие задачи возникают практически всегда в начальный период проектирования СУ.

Определение 1. Пусть A_i - любой из элементов (множеств) шестёрки

(2.1)

Назовём расширенным множеством задачи принятия решений:

если любой элемент (множество) удовлетворяет всем свойствам соответствующего элемента (множества) шестёрки (2.1)

если для любых двух элементов (множеств) Ai и Aj имеет место условие:

или (для множеств) при , то найдутся такие элементы и , что , т.е. элементы A_i и A_j в задаче принятия решений не тождественны.

Введём для задач принятия решений следующие обозначения расширенных множеств:

P - всех используемых выходных функций P;

G - всех используемых оценочных функций G;

D - всех используемых функций допустимости

Y - всех используемых множеств входных условий Y;

U - всех используемых допустимых областей управления

H - всех используемых областей неопределённости.

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

В то же время введение расширенных множеств позволяет сформулировать и формализовать новые задачи.

Рассмотрим ряд задач, полагая, что в (2.1) присутствует лишь одно расширенное множество и что достаточно ограничиться поиском допустимого решения.

24.1 Задача. Идентификация типов внешних воздействий

Пусть имеется шестёрка

<P(Y), G(Y), D(Y), Y, U^f(Y), H(Y)> , в которой расширенным множеством является множество всех возможных множеств входных условий Y . Поскольку выбор конкретного YY может привести к изменению P, G и других компонентов шестёрки, введём запись P(Y), G(Y) и т.д., которую далее целесообразно заменить более простой, выделяя в шестёрке лишь рассматриваемые элементы:

<P, G, D, Y, U^f, H>

Для данной шестёрки имеет смысл следующая задача принятия решений: Найти такое подмножество Y'Y , любой элемент которого y'Y'позволяет определить элемент u⁰U^f и соответствующий ему элемент x⁰X так, что для любого hH будет выполнено неравенство (1.6).

и условие (2.2)

где - некоторый априори заданный показатель эффективности выбора Y' из Y.

Далее сформулируем постановку задачи более кратко: Для шестёрки <P, G, D, Y, U^f, H> найти такое подмножество Y'Y , любой элемент y' которого удовлетворяет условиям <y', u⁰, x⁰>S и (2.2).

Отношение порядка: количественное превосходство, предшествование, подчинённость, включение, предпочтение.

Запись вида (2.2) означает, что Y' предпочтительнее, чем Y, где Y - любое из подмножеств в Y и Y'Y.

Рис. 32 Выбор типа внешних воздействий

Орграф на рисунке 2.1 - процедура выбора типа внешних воздействий. Этот орграф в сравнении с классической задачей (рисунок 1.2) имеет более развитую структуру.

24.2 Задача. Идентификация неопределённостей

Задана шестёрка <P, G, D, Y⁰, U^f, H> (2.3)

Сформулируем задачу:

Найти такое подмножество H'H , для любого элемента h' которого выполняется условие <y⁰, u⁰, x⁰>S и кроме того

(2.4)

Здесь - показатель эффективности выбора H' и H ,

- заданное отношение оценок Z на H.

Для данной задачи требуются дополнительные пояснения.

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

Неопределённость можно характеризовать:

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

интервальными значениями параметров типа

В задаче 2.2 рассматривается случай, когда способ задания H не приводит к изменению самой процедуры принятия решения. Но в большинстве случаев способ задания H влияет на процедуру принятия решения. Тогда в (2.1) надо сделать расширенными множества H и P.

24.3 Задача. Выбор критериев

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

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

(2.5)

Теперь для <P, G, , y⁰, U^f, H> можно поставить следующую задачу принятия решения на расширенных множествах:

Найти такой элемент G'G , что выполняется <y⁰, u⁰, x⁰>S, т.е. удовлетворяются требования к первичным показателям качества (2.5) и, кроме того, выполняется условие

(2.6)

Здесь - показатель эффективности выбора G' из множества альтернатив G , отражающий сложность процедуры принятия решений с критерием G'.

24.4 Задача. Выработка технического задания

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

Рассмотрим шестёрку <P, G, D, y⁰, U^f, H> , в которой расширенное множество D - множество всех функций допустимости.

Задачу принятия решений сформулируем следующим образом:

Найти такое множество D'D , для которого <y⁰, u⁰, x⁰>S, т.е. выполняется ограничение (2.5.) на первичные показатели качества и, кроме того, условие

(2.7)

где - показатель эффективности выбора D', D - произвольное подмножество множества D, D'D.

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

24.5 Задача. Выработка технического задания совместно с критерием его оценки

Задачи формирования критерия и функции допустимости объединяются в одну задачу. При этом для расширенных множеств G и D , т.е. для <P, G, D, y⁰, U^f, H> может быть поставлена следующая задача принятия решений:

Найти такие множества G'G и D'D, для которых <y⁰, u⁰, x⁰>S, т.е. решение удовлетворяет первичным показателям качества и, кроме того, выполняется условие

(2.8)

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

24.6 Задача. Выбор области управления

Пусть в (2.1) вместо U^f содержится совокупность этих множеств U. Тогда:

Найти такое множество U^fU , любой элемент которого u'U^f таков, что <y⁰, u', x'>S и, кроме того, выполняется условие

(2.9)

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

24.7 Задача. Выбор модели объекта.

Запишем вместо единственной функции P множество функций P.

Предположим возможность различного математического описания одного и того же объекта.

Сформулируем задачу: Найти элемент P'P, для которого при любом заданном y⁰Y найдётся элемент u'U^f такой, что <y⁰, u', x'>S, т.е. выполняется условие толерантности (1.6)

кроме того, условие

(2.10)

где - показатель эффективности выбора выходной функции P', P - произвольный элемент из P.

Частный случай этой задачи: в качестве альтернативных форм выходной функции используют различные области допустимых решений X^f . Именно такая постановка задачи принятия решений имеет место в теории решения задач, при доказательстве теорем и т.п., когда y⁰ - «условие задачи», а x^f - «то, что требуется доказать» или «искомое решение».

Таким образом, частные варианты задачи 2.7 можно отнести к области теории решения задач или к области искусственного интеллекта без условия (2.10).

Введение оценок и (2.10) позволяет характеризовать «внутренние свойства» процесса принятия решений, поскольку «внешние свойства», определяющие цель решения, уже полностью отражены условиями толерантности типа (1.6) или «первичными показателями качества» (2.5).

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

Общие процедуры принятия решений на расширенных множествах и графы структур решений.

Необходимо определить процедуры принятия решений на расширенных множествах.

Стратегия 1

Формирование расширенного множества.

Проверка существования допустимых решений для каждого из подмножеств, принадлежащих расширенному множеству.

Оценка решений для всех допустимых подмножеств по критерию предпочтения (сложности).

Выбор наиболее предпочтительного (наименее сложного).

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

Где? - в экстремальных задачах комбинаторного типа; в задачах, решаемых итерационными методами.

Стратегия 2. Если оценки предпочтения сформированы или получить их просто.

Формирование расширенного множества.

Оценка предпочтения выбора подмножеств.

Исключение бесперспективных подмножеств (путём формирования и проверки условия , где - допустимая оценка).

Проверка существования допустимых решений для всех Y, удовлетворяющих условию п.3.

Выбор наиболее предпочтительных вариантов решения.

Стратегия 3. Один из вариантов общей стратегии поиска элемента минимальной сложности.

Формирование подмножества в расширенном множестве.

Оценка предпочтения подмножеств.

Упорядочивание подмножеств по предпочтению Y'>Y'', Y''>Y''' и т.д.

Проверка существования допустимых решений для наиболее предпочтительного подмножества Y' и (если в Y' Допустимых решений не существует) в подмножествах Y'', Y''' и т.д.

Этими стратегиями не покрываются все варианты организации процедур решения задач на расширенных множествах альтернатив. Для формирования таких стратегий удобно использовать специальную конструкцию - граф структур решения (ГСР). Он является ориентированным мультиграфом, как правило, …-параллельной формы, в котором каждая вершина отражает факт решения какой-либо подзадачи (или выполнение определённой операции).

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

Любой маршрут начинается в вершине О и заканчивается в вершине N, и соответствует одному конкретному варианту решения задачи.

Для задачи, представленной на рисунке 2.1 , ГСР - простая цепь из вершины О в вершину N, в которой каждый уровень (подзадача) изображён одной дугой.

ГСР представляет три стратегии.

Стратегия 1: маршрут О, 2, 3, N

Стратегия 2: O, 1, 4, 5, 3, N

Стратегия 3: O, 1, 4, 6, N

Рис. 33 Граф структур решения

С помощью ГСР можно наглядно и компактно отобразить содержание и количественные характеристики задачи принятия решений на расширенных множествах альтернатив.

§25 Математическая постановка задачи принятия оперативных решений

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

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

Рассмотрим задачи на расширенных множествах.

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

(1)

для данного случая конкретизируют так

(2)

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

(3)

25.1 Задача 2.9. Выбор алгоритма принятия оперативных решений

Задача характеризуется пятёркой

<P, G, Y, U, H> (4)

в которой фиксированы множество Y, определяющее возможный набор исходных данных, элемент y*Y, который характеризует некоторый «типовой» элемент исходных данных, и оценочная функция G.

Множества P, U, H - расширенные.

Необходимо определить такие элементы P*P, подмножества U^f*U, H*H, в которых существует элемент u*U^f* и преобразование

, такое что для всех hH* выполняется условие

(5)

и обращается в минимум критерий (3).

Концепция доминантных условий в проблеме принятия решений.

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

Каковы же средства её преодоления?

Аристотелю принадлежит утверждение: «Ум, направленный на существо предмета, как суть его бытия, истинен всегда; ум же, касающийся чего-то другого - не всегда».

Каким же образом в процессах принятия решений определять «существо предмета» и как строить процесс решения? Советский психолог Я.А.Пономарёв исследовал процессы творчества и установил 5 уровней в развитии и существовании мышления.

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

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

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

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

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

По словам Аристотеля, именно выявление этого основного принципа и есть проявление ума, направленного на существо предмета.

Целенаправленную детерминированную составляющую творческих поисков человека А.А.Ухтомский назвал доминантой, понимая под ней длительную установку научного поиска, т.е. основной принцип, которому необходимо следовать в процессе научного познания.

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

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

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

Классифицируем доминантные условия по 4-м типам в порядке, пропорциональном эффективности их применения и обратно пропорциональном сложности их получения.

Доминантные условия 1-го типа:

Их определяют в форме функциональных соотношений, между параметрами задачи. С позиций задач принятия решения на расширенных множествах это означает, что используется шестёрка <P, G, D, y⁰, U^f, H> , в которой среди множества выходных функций P должна существовать такая P^d, которая: приводит к минимальной оценке сложности, но эта оценка существенно ниже оценок для всех остальных выходных функций.

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

Доминантные условия 2-го типа:

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

Пример: замена нелинейных уравнений линеаризованным. С точки зрения формализма задач принятия решений на расширенных множествах применение этих условий означает: если исходная задача характеризуется <P, G, D, y⁰, U^f, H> , то решаемая вместо неё задача определяется <P', G', D', y⁰, U^f', H'>, для которой выполняется хотя бы одно из соотношений P'P, G'G, D'D, U^f' U^f, H'H. При этом должно выполняться условие

Z(P', G', D', y⁰, U^f', H')RZ(P, G, D, y⁰, U^f, H).

Доминантные условия 3-го типа:

Применяют для разделения исходной общей задачи на локальные подзадачи.

Могут быть варианты: 1) последовательная декомпозиция и преобразование исходной задачи в цепочку подзадач; 2) параллельная декомпозиция.

В 1-м случае выходная функция исходной задачи разделяется по крайней мере на две функции

При этом может быть достигнуто и разделение допустимых областей управления на U^f₁ и U^f₂.

Во 2-м случае: разделение общей задачи на L независимых, как правило, однотипных задач, что требует в общем случае:

- разделения исходных данных y⁰ на y⁰₁, …, y⁰_i, …, y⁰_L.

разделения области (ресурсов) управления на U^f₁, …, U^f_i, …, U^f_L.

И формирования выходных функций вида . Решение исходной задачи формируется как объединение .

Доминантные условия 4-го типа:

С их помощью ограничивают множество допустимых управлений U^f более узкой областью U^f' U^f.

Трудности получения допустимых условий 4-го типа и эффективность их использования минимальны.

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

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

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

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

Глава 10. Методы и алгоритмы решения задачи выбора (назначения) в классической постановке на расширенных множествах альтернатив

§26 Постановка задач

Широкое применение во многих сферах управления техническими и экономическими объектами имеет следующая детерминированная задача принятия решения.

Имеется два равноценных множества элементов Q_i и Q_j , элементы которых нумеруются числами натурального ряда от 1 до n.

Множество управляющих воздействий характеризует наличие связи между элементами и , если , и отсутствие связи, если .

Каждой паре поставлено в соответствие неотрицательное число , характеризующее стоимость установления связи между и , т.е. y⁰Y определяется n числами .

Требуется для каждого найти единственный, связанный только с , элемент такой, при котором достигается минимум общей стоимости всех n связей, т.е. оценочная функция G имеет вид:

Множество допустимых управлений U^f ограничено условиями неповторяемости элементов и во всех связях:

Данную задачу называют задачей выбора или назначения.

Эту задачу можно трактовать как частный случай известных нелинейных распределений у задач.

Пусть имеется n складов, в каждом из которых хранится 1 единица ресурса, и n пунктов потребления, запрашивающих одну единицу ресурса, а также известны неотрицательные числа , определяющие стоимость доставки единицы ресурса из склада i в пункт потребления j.

Требуется распределить ресурсы между складами так, чтобы

(3.1)

и выполнялись ограничения

(3.2)

(3.3)

принимает значения только 1 или 0.

В первом случае ресурс со склада i поступит в пункт j , во втором случае этого не происходит.

(3.2) введены для того, чтобы каждый пункт потребления мог получить только одну единицу ресурса.

(3.3) показывают, что на каждом складе хранится всего одна единица ресурса.

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

Задача (3.1)…(3.3) - классическая задача выбора.

Задача, где (3.2), (3.3) имеют другой вид или отсутствуют - неклассическая.

 Точные методы решения классической задачи выбора.

Точные методы - позволяют получать оптимальное решение задачи.

26.1 Методы линейного программирования

Задачу выбора можно решать методами линейного программирования после преобразования задачи (3.1)…(3.3) к стандартной форме задачи линейного программирования. Такое преобразование можно осуществить по следующей схеме.

Матрицу исходных данных задачи выбора А порядка n транспонировать в матрицу С размера [1n²]

(3.4)

где A_i - i-я строка матрицы А.

Аналогично переменные сгруппировать в матрицу-строку

,

где - матрица-строка, составленная из следующих компонентов:

Ограничения (3.2), (3.3) преобразовываются к виду

, (3.5)

где

;

Матрица E_i содержит во всех строках, кроме i-й нулевые элементы, а в строке i - все элементы равны единице.

I - единичная матрица порядка n.

Матрица В имеет размер [n²1].

Получив (3.4) и (3.5), можно сформулировать задачу выбора как стандартную задачу линейного программирования.

(3.6)

26.2 Метод динамического программирования

Для реализации метода динамического программирования введём функцию Беллмана в следующем виде: - оптимальное значение критерия (3.1) при распределении k типов ресурсов с номерами между первыми k пунктами потребления. На первом шаге необходимо вычислить n значений , , , …, .

На втором шаге последовательно определить значения

Число таких - число сочетаний из n элементов по 2.

На третьем шаге следует использовать соотношения

,

которые соответствуют вариантам решения на третьем шаге.

Для произвольного k-го шага (i < k n) можно записать функциональные уравнения динамического программирования

(3.7)

Число вариантов решения на k-м шаге будет равно . Оно увеличивается с ростом k (при k=1 равно n), достигает максимума при k=n/2 или k=(n+1)/2 и k=(n-1)/2 (для нечётных n) и снова снижается до n на последнем n-м шаге.

Общее число вариантов решения, которое необходимо проанализировать за все n шагов динамического программирования, определим по формуле:

(3.8)

Метод не является самым эффективным среди методов решения задачи выбора.

26.3 Методы кратчайшего увеличивающего пути

В последние годы благодаря работам японских учёных (К.Томизава), получили распространение методы кратчайшего увеличивающего пути (КУП).

Пусть в матрице исходных данных выбора порядка n (обозначим её A_(n)) выделена квадратная подматрица порядка (n-1), т.е. A_(n-1), и пусть для этой подматрицы каким-либо образом найдено оптимальное решение. Для простоты предположим, что это оптимальное решение сформировано из элементов главной диагонали A_(n-1). Как же найти оптимальное решение для полной задачи?

Поскольку для A_(n-1) известно оптимальное решение, то возможны две альтернативы:

добавить к известному решению «свободный» элемент ;

заменить в оптимальном для матрицы A_(n-1) решении элемент парой элементов и .

Сформируем n разностей . Последняя из них для i=n есть ноль. Все остальные могут быть как положительными, так и отрицательными. Выберем из этих n разностей наименьшую. Если она будет равна нулю, то к решению для A_(n-1) необходимо добавить элемент , если это отрицательное число, то из A_(n-1) нужно исключить соответствующий минимальной разности элемент и ввести в решение элементы и . Очевидно, что для A_(n) при этом будет получено оптимальное решение.

В методах кратчайшего увеличивающего пути для получения A_(n-1) используют матрицу A_(n-2), для получения A_(n-2) - A_(n-3) и т.д.

Первоначальную матрицу определяют в результате проведения подготовительного этапа.

Оценки сложности для точных методов КУП

- среднее время счёта задачи выбора;

- коэффициент пропорциональности, зависящий от квалификации программиста, типа ЭВМ и т.д.

§27 Приближённые методы решения классической задачи выбора

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

27.1 Методы локальных вариаций «текущей величины» и их вариации

В основе метода для задачи назначения лежит общая идея метода локальных вариаций Ф.Л.Черноусько. Предположим, что для задачи (3.1)…(3.3) известно опорное решение, элементы которого удобно расположить на главной диагонали матрицы А.

Метод локальных вариаций состоит в последовательном сравнении каждой пары элементов, принадлежащих опорному решению , с парой элементов для всех i от 1 до n-1.

Если для некоторого i получено < , то строки i и i+1 меняют местами, значение i увеличивают на 1 и процесс сравнения продолжают до i=n-1.

Данное решение - первое приближение - подвергают той же процедуре проверки и так до тех пор, пока для некоторого приближения в течение всего цикла вариаций от i=1 до i=n-1 лучших решений не обнаружится.

Метод локальных вариаций чувствителен к локальным экстремумам и не гарантирует достижения абсолютного минимума.

Для увеличения точности используют метод «бегущей волны», который отличается следующим:

сравниваются локальные стратегии, составленные не из 2, а из n'<n элементов;

при сравнении стратегий (особенно если n' велико) используется не прямой перебор, а один из точных методов решения задачи выбора с матрицей размером n'n'.

Точность с увеличением n' возрастает, но увеличиваются и вычислительные трудности.

Оценка числа вычислительных операций:

- коэффициент пропорциональности, зависящий от ЭВМ и языка программирования;

- среднее число вычислительных операций, необходимое для сравнения двух локальных решений, перестановки строк матрицы А и перехода к следующему сравнению;

k - число итераций.

Для метода «бегущей волны»:

(n')³ - свидетельствует о том, что был использован метод Куна или метод Мака (венгерский метод).

27.2 Методы, основанные на доминантных условиях первого типа

Использование доминантных условий значительно снижает вычислительные трудности решения комбинаторных задач. Рассмотрим 3 приближённых метода решения задачи выбора, сформированные на некоторых эвристических предположениях о характере искомого решения, которые относятся к методам, основанным на доминантных условиях 1-го типа.

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

Сформулируем некоторые условия, которым должны удовлетворять выбираемые элементы.

Наиболее естественным кажется предположение о том, что оптимальное решение , должно содержать минимальный элемент, принадлежащий А.

Поэтому доминантное условие сформулируем в виде

(3.9)

где - первый из включаемых в решение элементов А.

Если элемент выбран, то из матрицы А можно исключить ту строку и тот столбец, на пересечении которых находится . К полученной матрице порядка (n-1) также можно применить условие выбора вида (3.9) и т.д.

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

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

Рассмотрим, например, задачу с матрицей особого вида:

(3.10)

Используя доминантные условия в форме (3.9), получим , затем , затем , после чего в решение включим единственный из оставшихся элементов . Легко установить, что найденное решение не минимизирует, а максимизирует заданный критерий.

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

(3.11)

В этом случае матрицу А преобразуем в матрицу D по следующим формулам:

Приведённые преобразования в D являются эквивалентными в том смысле, что оптимальные стратегии для D и A совпадают.

Для задачи выбора с матрицей (3.10), используя данный метод, можно получить оптимальное решение. Отличительная особенность метода - увеличение объёма вычислений.

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