Общая математическая модель формирования оптимальных решений

КОНТРОЛЬНЫЕ ВОПРОСЫ 1

КЛАССИФИКАЦИЯ РЕШЕНИЙ

Решение – один из необходимых моментов волевого действия и способов его выполнения. В практике ПР можно выделить 2 типа решений: допустимые и оптимальные. Допустимым решением называют решение, которое удовлетворяет ЛПР по техническим, организационным, экономическим, моральным, духовным и др. условиям их организации.

Оптимальное решение – наилучшее решение, которое соответствует наиболее эффективному способу достижения поставленной цели.

Эти виды решений связаны следующим образом.

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

Кроме того, существуют следующие виды решений (рис. 2.2.):

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

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

· Оперативное решение (как действовать?). С помощью этих решений осуществляется распределение ресурсов и средств, выбор способов действий и т.д.

Рис. 2.2

В настоящее время сложилось три подхода к принятию решений (рис. 2.3).

Рис. 2.3

Рассмотрим краткую характеристику каждого подхода.

1) Эмпирический подход (ЭП).

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

Основной недостаток данного подхода состоит в том, что в неизвестной проблемной среде и при отсутствии опыта у ЛПР этот подход дает не эффективное решение.

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

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

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

3) С 80-х годов 20-го века начал формироваться человеко-машинный (интерактивный) подход. Данный подход подразумевает, что ЛПР должно выступать в качестве активного звена в алгоритме решения соответствующих задач.

Задачей ЛПР в рамках соответствующей диалоговой программы должно являться:

1) Оперативная корректировка исходных и промежуточных данных.

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

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

1. Какие действия закладываются в основу процесса принятия решения?

2. Что использует прикладная ТПР?

3. Что формирует прикладная ТПР?

4. Что является основной задачей ТПР?

5. Что содержит простейшая схема принятия решений?

6. Приведите 3 основных вопроса, составляющих предмет ТПР.

7. Кто участвует в формировании, выборе и реализации решений в сложных системах?

8. Охарактеризуйте функции ЛГР, ЛРР, ЛПР.

9. Какие 2 типа решений можно выделить в практике ПР?

10. Что такое допустимые решения?

11. Что такое оптимальное решение?

12. Что такое аналитическое решение?

13. Что такое организационное решение?

14. Что такое оперативное решение?

15. Назовите 3 подхода к принятию решения.

16. Охарактеризуйте эмпирический подход.

17. Охарактеризуйте формальный подход.

18. Охарактеризуйте интерактивный подход.

Лекция 2

В основу формального подхода ПР полагается применение ММ, методов и соответствующих алгоритмов.

Рассмотрим общие понятия ММ процесса или явления и классификацию ММ.

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

Примеры:

Модель движения твердого тела массой под действием силы (2-й закон Ньютона); .

Модель измерения электрических параметров в проводнике (Закон Ома); .

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

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

Практика применения ММ в различных областях науки и техники сформировала следующие основные требования:

1) Простота и наглядность модели.

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

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

2) Достаточная сложность модели. Это требование необходимо для того, чтобы при использовании ММ получались не тривиальные результаты.

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

Рассмотрим общую ММ задач ПР. В качестве решения будем рассматривать
-мерный вектор , определяющий количественные характеристики формируемого решения. Обозначим через a, b и c вектора соответствующих размерностей, которые описывают количественные характеристики неуправляемых факторов, то есть таких факторов, на которые в процессе принятия решения ЛПР не может повлиять.

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

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

где – вектор-функция своих аргументов.

Будем использовать стандартную форму записи ММ формирования оптимального решения:

; (3.1)

; (3.2)

. (3.3)

Построение ММ (3.1) - (3.3) состоит в выборе или формировании функций , а также в указании знаков отношений между левой и правой частью уравнения (3.2).

В практике построения таких ММ используют два подхода:

1) Функции , конкретизируются на основе результатов фундаментальных и прикладных наук.

2) Зависимости и строятся путем непосредственного вывода.

Таким образом, постановка задачи формирования оптимального решения конкретизируется следующим образом: Найти значения элементов вектора , доставляющие максимум критерию оптимальности (3.1) и удовлетворяющие условиям (3.2) и (3.3).

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

Итак, ранее мы определили общую ММ ЗПР вид (3.1) - (3.3). В зависимости от природы и характера векторов a, b и c, входящих в эти выражения выделяют следующую классификацию ММ:

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

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

По назначению ММ в науке и технике подразделяются на:

Расчетные модели и оптимизационные модели.

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

В качестве нового знания, которое получается в результате использования ММ и методов ТПР выступают оптимальные решения.

Детерминированные модели. В таких моделях числовые значения параметров a, b и c точно известны исследователю (ЛПР).

Стохастические. В этих моделях значения параметров a, b и c являются случайными векторами, заданными с помощью их функций распределения или числовых характеристик (математического ожидания, дисперсии). Задача оптимизации данного класса носит название задачи стохастического программирования.

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

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

Математическая модель (3.1) - (3.3) называется однокритериальной моделью. Пусть ЛПР, должно учитывать целей, в этом случае используется целевых функций:

, (3.4)

Здесь – соответствующие вектора неконтролируемых факторов. Математическая модель ЗПР (3.4), (3.2), (3.3) называется многокритериальной моделью.

В зависимости от вида функций и , входящих в соответствующую ММ, выделяют линейные и нелинейные модели. В общем случае линейная однокритериальная модель ЗПР записывается в следующем виде:

(3.5)

Если модель не соответствует виду (3.5) по какой-то из компонент, то она относится к классу нелинейных моделей.

Если в модели учитывается ограничение (3.3) и вектора могут принимать только дискретный ряд значений, то это требование формально записывается так:

. (3.6)

Тогда модель (3.1), (3.2), (3.6) называется однокритериальной дискретной моделью. А модель (3.4), (3.2), (3.6) – многокритериальной дискретной моделью. Модель называется смешанной (дискретно-непрерывной), если на одну часть компонент вектора наложены условия не отрицательности вида (3.3), а на другую – вида (3.6).

Таким образом, можно предложить следующую классификацию (рис. 3.1).

Рис. 3.1

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

3.2. Краткая характеристика математических методов
формирования оптимальных решений

Рассмотрим этапы формирования оптимальных решений:

1) Построение ММ задачи является первым и основным этапом ее решения
(50-60% трудоемкости).

2) Выбор или разработка метода (алгоритма) получения оптимальных решений.

3) Разработка ПО, реализующего данный метод, алгоритм.

Все используемые на практике методы можно представить в виде следующей классификации (рис. 3.2).

Рис. 3.2

Аналитические методы – методы, позволяющие получить оптимальное решение в аналитической форме, то есть в виде конечной формулы.

, (3.7)

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

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

Аналитическое решение ЗПР в настоящее время возможно, если соответствующая ММ включает только ограничения типа равенств и не имеет ограничений на значения вектора , то есть модель имеет вид:

Такие задачи обычно решаются классическим методом Лагранжа путем построения функции Лагранжа.

Рассмотрим недостатки аналитического метода Лагранжа.

1) Не учитываются условия неотрицательности и целочисленности компонент вектора .

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

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

1) Формальные методы, в основу которых полагается некоторая формальная схема поиска оптимального решения. Например, метод градиентного спуска.

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

С точки зрения трудоемкости реализации этих методов выделяют:

а) Конечные методы – методы, позволяющие получить искомое решение за конечное число шагов с точностью проводимых вычислений. Например, нахождение максимального числа в массиве из чисел и симплекс-метод решения задач линейного программирования (ЗЛП).