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

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

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

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

Различают два вида задач математического программирования:

1. Задачи линейного программирования.

2. Задачи нелинейного программирования.

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

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

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

Постановка задачи: Дан один критерий . Объект (процесс) описан уравнением (уравнениями), включающими один искомый параметр . Имеется система ограничений:

и т.д.

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

Задача решается в два этапа:

1. Построение области допустимых решений (ОДР).

2. Нахождение в пределах ОДР оптимального решения.

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

Рис.1. Графическая иллюстрация решения однопараметрической однокритериальной задачи оптимизации

Когда однопараметрическая однокритериальная задача оптимизации решается с применением графоаналитического метода вручную, то на втором этапе применяют метод перебора. Суть его заключается в следующем. В пределах ОДР через определенный интервал h выбирается ряд значений параметра . В рассматриваемом нами случае ОДР разбита на четыре отрезка, и выбрано пять значений параметра . Для этих значений параметра рассчитываются соответствующие значения целевой функции. Среди них находят минимальное (максимальное) значение. Значение параметра , обращающее целевую функцию в минимум (максимум), является оптимальным. Если в рассматриваемом нами случае стремится к минимуму, то , если к максимуму, то .

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

Рассмотрим, например, следующий частный случай, когда целевая функция линейная (рис.2.).

Рис.2. Графическая иллюстрация решения однопараметрической однокритериальной задачи оптимизации для случая линейной целевой функции

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

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

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

В случае противоречивых критериев имеются следующие подходы к отысканию подходящего решения.

1) Замена некоторых критериев ограничениями вида ≤ или ≥. Например, минимизация стоимости f (x) → min, может быть заменена ограничением вида f (x) ≤ A, где A некоторая верхняя оценка стоимости, т.е. максимально допустимая стоимость.

2) Свертка критериев. Создается один глобальный скалярный критерий, целевая функция которого является некоторой функцией от исходных целевых функций. Наиболее употребимыми являются линейные свертки вида α f (x) + β g (x) (в случае двух критериев). Нетривиальной является задача отыскания адекватных значений коэффициентов α и β, отражающих относительную важность целевых функций f (x) и g (x).

3) Ранжирование критериев. Критерии ранжируются по степени важности.

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

Подходы 1) и 2) приводят к однокритериальной задаче.

Подход 3) приводит к задаче с упорядоченными критериями.

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

Рис 3. Множество решений.

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

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

Множество недоминируемых решений также называется множеством Парето.