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

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

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

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

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

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

Рис. 3.2

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

, (3.7)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1. Дайте определение математической модели.

2. В каких случаях применяют ММ?

3. Перечислите требования, предъявляемые к ММ.

4. Сформулируйте задачу формирования оптимального решения.

5. Перечислите виды ММ.

6. Охарактеризуйте каждый из видов ММ.

7. Перечислите этапы формирования оптимальных решений.

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

9. Охарактеризуйте каждый из методов формирования оптимальных решений.

10. В каком случае можно использовать аналитический метод Лагранжа?

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

4. Линейные модели задач принятия решений

Данные модели занимают основное место в ТПР. Это объясняется тем, что линейные модели являются простыми и наглядными, линейные задачи решаются с помощью конечных численных методов. Отметим, что линейные модели вообще являются первым этапом решения практических задач за счёт их простоты. В этом случае при определённых предположениях нелинейные зависимости заменяются их линейными аппроксимациями. На рис. 4.1 функция f(x) – исходная нелинейная зависимость, а – ее линейная аппроксимация. Такая замена правомерна только при выполнении условия .

Рис. 4.1

Линейные модели в ТПР в основном строятся двумя путями:

• непосредственного вывода зависимости f^*(x);

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

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

П ример:

Оптимального решения этой задачи (рис. 4.2) не существует, так как переменная принадлежит полуинтервалу [0,1), где не входит в множество допустимых решений данной задачи. Если ограничение заменить на , то множество допустимых значений х будет принадлежать интервалу и тогда , а .