Исследование операций. Линейное, динамическое программирование




Исследование операций - часть 66


На практике применяется ряд методов решения подобных задач; все они (при сколько-нибудь значительном числе переменных) очень сложны и трудоемки. Мы не будем пытаться излагать эти методы здесь, а отошлем интересующегося читателя к более подробным руководствам (например, [7, 8]).

В заключение скажем несколько слов о задачах нелинейного программирования.

Общая постановка задачи нелинейного программирования следующая. Найти неотрицательные значения переменных х1, х2, ..., xn, удовлетворяющие каким-то ограничениям произвольного вида. Например

             (11.3)

и обращающие в максимум произвольную нелинейную функцию этих переменных:

W = W (x1, х2, ..., хn) => mах.       (11.4)

Общих способов решения задачи нелинейного программирования не существует; в каждой конкретной задаче способ выбирается в зависимости от вида функции W и накладываемых на элементы решения ограничений.

Задачи нелинейного программирования на практике возникают довольно часто, например, когда затраты растут не пропорционально количеству закупленных или произведенных товаров (эффект «оптовости»), но многие нелинейные задачи могут быть приближенно заменены линейными (линеаризованы), по крайней мере в области, близкой к оптимальному решению. Если это и невозможно, все же обычно нелинейные задачи, возникающие на практике, приводят к сравнительно «благополучным» формам нелинейности. В частности, нередко встречаются задачи «квадратичного программирования», когда W есть полином 2-й степени относительно переменных х1, x2, ..., хn, а неравенства (11.3) линейны (см. [7, 8]). В ряде случаев при решении задач нелинейного программирования может быть с успехом применен так называемый «метод штрафных функций», сводящий задачу поиска экстремума при наличии ограничений к аналогичной задаче при отсутствии ограничений, которая обычно решается проще. Идея метода состоит в том, что вместо того, чтобы наложить на решение жесткое требование вида

(x1, х2,

..., xn)

 0, можно наложить некоторый достаточно большой «штраф» за нарушение этого условия и добавить к целевой функции W(.x1, x2, ..., xn) штраф вида a
(x1, x2, ..., xn), где а—коэффициент пропорциональности (в случае, когда целевая функция максимизируется, а отрицательно, если минимизируется — положительно).


Содержание  Назад  Вперед