Статическая условная оптимизация. Классификация задач и методов нелинейного программирования. Методы последовательной безусловной минимизации. Алгоритм метода условного градиента

Страницы работы

Фрагмент текста работы

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

В ряде задач ЛП и НП процессы зависят от времени - от нескольких периодов (этапов). При решении таких многоэтапных задач необходимо учитывать развитие экономического процесса (например, распределение ресурсов между предприятиями по годам планируемого периода). Такие задачи относятся к задачам динамического программирования.

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

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

Класс ЗНП шире класса ЗЛП. Например, производственные затраты в большинстве случаев не пропорциональны объему выпуска, а зависят от него нелинейно, доход от реализации продуктов производства оказывается нелинейной функцией цен и т.д.

Критериями в задачах оптимального планирования часто служат:

·  максимум прибыли,

·  минимум себестоимости,

·  минимум капитальных затрат;

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

1.2.1.  Классификация задач и методов нелинейного программирования

Если все эти функции f, gi, hj дифференцируемы в Rn , то (4.1) называется гладкой задачейнелинейного программирования.

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

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

Наиболее изучены задачи выпуклого программирования (ЗВП) - задачи нахождения минимума выпуклой (или максимума вогнутой) функции, заданной на выпуклом замкнутом множестве.

Сформулируем общую постановку ЗВП.

Минимизировать f(X) при ограничениях gi(X) ≤ 0, i = 1.. и hi(X) = 0, i = k + 1..m., где f(X)- выпуклая функция и каждая функция, задающая ограничение в виде неравенства,- выпуклая функция (ограничения образуют выпуклое множество), а ограничения в виде равенств - линейны.

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

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

Общая классификация методов решения задач НП приведена на рисунке

Похожие материалы

Информация о работе