В самом общем случае задача нахождения оптимального (максимального или минимального) значения целевой функции может быть записана как:
U=f(X)→ max;X,W,
где X = (x1,x2,…,xn);
W - область допустимых значений переменных x1,x2,…,xn;
f(X) - целевая функция.
Для того чтобы решить эту оптимизационную задачу, достаточно указать X0ОW такое, что f(X0) ≥f(X) при любом XОW, f(X0) ≤f(X)при любом XОW. Методы решения оптимизационных задач зависят как от вида целевой функции f(X), так и от строения допустимого множества W. Если целевая функция в задаче является функциейn переменных, то методы решения называют методами математического программирования.
В математическом программировании принято выделять следующие основные задачи в зависимости от вида целевой функции f(X) и от области W:
· задачи линейного программирования, если f(X) и W линейны;
· задачи целочисленного программирования, если ставится условие целочисленности переменных x1,x2,…,xn;
· задачи нелинейного программирования, если f(X) или W имеют нелинейный характер.
Общая постановка задачи нелинейного программирования выглядит следующим образом. Найти неотрицательные значения элементов решения x1,x2,...,xn,удовлетворяющие ограничениям произвольного вида и обращающие в максимум произвольную нелинейную функцию этих элементов решения:
W=f(x1,x2,...,xn)→ max.
Общих способов решения таких задач нет. Иногда их сводят к задачам линейного программирования, рассматривая полученные решения как приближенные. В ряде случаев применяют так называемый "метод штрафных функций" сводящий задачу поиска экстремума при наличии ограничений к аналогичной задаче при отсутствии ограничений, которая обычно решается проще.
Идея метода штрафных функций в том, что вместо наложения системы ограничений, налагается некоторый достаточно большой "штраф" за нарушение ограничений, который добавляется к целевой функции W. Штраф имеет общий вид: a(x1,x2,...,xn), где a - коэффициент пропорциональности (если W максимизируется он отрицателен, если минимизируется - положителен). Далее можно, увеличивая абсолютное значение a, посмотреть, как изменяется при этом оптимальное решение (x1°,x2°,...,xn°)и, когда оно практически перестанет меняться, остановиться на нем.
В ряде случаев при решении задач нелинейного программирования оказывается полезным так называемый "метод случайного поиска", состоящий в том, что вместо упорядоченного перебора возможных вариантов решения применяется случайный розыгрыш.
На практике часто встречаются задачи, совпадающие по постановке с задачами линейного программирования, но отличающиеся той особенностью, что искомые элементы решения непременно должны быть целыми. Такие задачи называют задачами целочисленного (дискретного) программирования; дополнительное условие целочисленности существенно затрудняет их решение. В ряде случаев задачи целочисленного программирования сводят к задачам линейного программирования, а полученные элементы решения рассматривают как приблизительные.
В последнюю очередь упомянем о задачах стохастического программирования. Их особенность в том, что ищется оптимальное решение в условиях неполной определенности, когда ряд параметров, входящих в целевую функцию W и ограничения, накладываемые на решение, представляют собой случайные величины. Часто такие задачи сводят к детерминированным (рассматривая случайные величины как математические ожидания).
В тех случаях, когда использование точных методов затруднительно или исключено, применяют различного рода приближенные алгоритмы, полученные на основе "здравого смысла". Такой подход в специальной литературе часто называют эвристическим программированием, а решаемые задачи - задачами эвристического программирования.
Задачи целочисленного, нелинейного, стохастического и эвристического программирования решаются с привлечением достаточно сложного математического аппарата, поэтому ниже рассмотрен лишь инструментарий линейного программирования и некоторые понятия динамического программирования.
