Нелинейное программирование

из "Математическое оптимальное программирование в экономике "

Экстремальные задачи, в которых либо ограничения, либо целевая функция (случай, который мы рассматриваем ), л иба и то и другое нелинейны, называются задачами нелинейного программирования. К сожалению, пока не имеется общих методов, подобных методу последовательного улучшения плана или симплекс-методу в линейном программировании, которые позволяли бы решать любые задачи нелинейного программирования. Поэтому мы сможем указать на возможность решения лишь для некоторых, впрочем, весьма важных частных случаев. [c.72]
Из рис. 11 видно, что эта область невыпуклая, так как отрезок, соединяющий любые две точки на гиперболе, не принадлежит области. Кроме того, все точки, лежащие на ограничивающей область дуге окружности, являются крайними, т. е. имеется бесчисленное множество крайних точек. [c.72]
И еще одно осложнение, отличающее нелинейные задачи от линейных. Целевая функция в допустимой области может иметь несколько локальных экстремумов. (Говорят, что функция имеет в точке А локальный экстремум, если значения функции в точке А не больше (или не меньше), чем значения функции во всех достаточно близких к А точках.) Геометрическая иллюстрация этого случая приведена на рис. 13. [c.73]
Перечислив те особенности, которыми обладают нелинейные задачи по сравнению с линейными, укажем теперь некоторые возможные пути их решения. Начнем с рассмотрения нелинейных задач специального вида. Такой характер имеет в ряде случаев и упоминавшаяся выше задача размещения. [c.73]
График такой функции изображен на рис. 14. [c.74]
Возможно и применение различных итеративных методов, основанных на очень простой идее — пошаговом приближении к точке минимума. Если известно заранее, что целевая функция имеет единственный минимум, то поиск точки, в которой он достигается, может быть организован так. Возьмем в качестве начальной произвольную точку допустимой области и определим для этой точки то направление, в котором функция быстрее всего убывает. Перейдем к новой точке, сделав небольшой шаг в направлении скорейшего убывания функции. Потом снова отыскивается подходящее направление для перехода к очередной точке и т. д. Разумеется, это только грубое, схематическое описание общей идеи одного из итерационных процессов. Мы совершенно не касаемся таких вопросов, как выбор величины шага, количество необходимых шагов, продолжение поиска экстремальной точки при выходе на границу допустимой области и т. д. [c.75]
Если целевая функция имеет несколько локальных минимумов или просто заранее о ней ничего не известно, то поиск экстремальной точки еще более осложняется. Это объясняется тем, что описанный процесс улучшения плана может в этом случае привести к локальному минимуму, очень далекому от глобального. Чтобы избежать этого, приходится, завершая один поиск, начинать его снова, но уже с другой начальной точки. Проделав такую процедуру с различными (желательно многими) точками, можно выбрать в качестве приближенного решения задачи наименьший из локальных минимумов (см. (рис. 13). Чем большее число точек допустимой области просмотрено, тем больше шансов, что найденный результат представляет действительное решение задачи. [c.75]
Несмотря на большие трудности, связанные с решением задач нелинейного программирования, о которых мы постарались дать представление читателю, в настоящее время ведется большая работа по разработке новых и совершенствованию-уже известных методов их решения. В первую очередь это вызвано большой практической важностью задач такого типа, их актуальностью. Кроме упоминавшейся уже задачи размещения и выбора производственных мощностей, отметим еще одну характерную экономическую задачу, приводящуюся к задаче нелинейного программирования. [c.75]
При изучении вопросов составления планов с учетом потребления бывает необходимо использовать функцию, выражающую объем потребления некоторого продукта в зависимости от его цены. Сразу же понятно, что функция эта зачастую нелинейная. (Например, если менять цену продукта, то при большом уменьшении цены объем потребления перестает заметно расти.) Если требуется отыскать производственный план и связанные с ним цены, определить объем потребления так, чтобы он был согласован с этими ценами, и при этом максимизировать эффект от производства и потребления этого продукта, то придем к типичной задаче нелинейного программирования. Дальнейшие примеры могут быть указаны самим читателем. [c.76]
В нелинейном программировании также могут быть построены связанные с оптимальным планом оценки, однако их экономическое значение описывается более сложно, что вносит известные трудности в их применение. [c.76]

Вернуться к основной статье