Граф процесса поиска допустимого решения.
Иными словами, задача оптимизации является задачей нахождения удовлетворительных решений для того случая, когда функция толерантности имеет вид
(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. Рассмотрим основные понятия этих теорий и оценим эффективность их применения для принятия оперативных и проектных решений.
