Решение задач условной оптимизации методом Лагранжа. Градиентные методы решения задач безусловной оптимизации. Метод дробления шага. Оптимизационные задачи для выпуклых функций. Решение задачи нелинейного программирования методом допустимых направлений.
Аннотация к работе
Например, иногда затраты (3) в производстве растут не пропорционально количеству (N) произведенной продукции (3 = Зед х N), а нелинейно. Зная нелинейный закон (квадратичный или какой-либо другой) и условия, ограничивающие объем выпуска различной продукции, можно попытаться найти оптимальный план объема выпуска для будущего производства. • Возможности производства (мощности, количество единиц оборудования, энергообеспечение и т.д.) не всегда соответствуют поставленным задачам; поэтому часто приходится "на ходу", параллельно с выпуском ограниченного количества продукции перестраивать производство под большие объемы; затраты при этом растут непропорционально количеству выпускаемого товара. • Некоторые технологические процессы изготовления продукции требуют непрерывного потока материальных ресурсов (сырья, материалов, энергоресурсов, химических веществ и т.д.), причем эти потоки со временем могут увеличиваться непропорционально количеству выпускаемой продукции, а следовательно, нелинейно увеличиваются и затраты. • В некоторых случаях износ оборудования в производстве требует затрат, которые растут непропорционально количеству производимой на этом оборудовании продукции.Как уже упоминалось во введении, предположение о возможности описать зависимости между управляемыми переменными с помощью линейных функций далеко не всегда адекватно природе моделируемого объекта. Например, в экономических моделях цена товара считается независимой от количества произведенного продукта, однако в повседневной жизни мы постоянно сталкиваемся с тем, что она может зависеть от объема партии товара. Аналогичные замечания могут быть сделаны и по поводу технологических ограничений: расход определенных видов сырья и ресурсов происходит не линейно, а скачкообразно (в зависимости от объема производства). Общая задача нелинейного программирования (ОЗНП) определяется как задача нахождения максимума (или минимума) целевой функции f(x{, х2,..., хп) на множестве D, определяемом системой ограничений Задача (2) является весьма общей, т. к. допускает запись логических условий, например: или запись условий дискретности множеств: Набор ограничений, определяющих множество D, при необходимости всегда можно свести либо к системе, состоящей из одних неравенств: либо, добавив фиктивные переменные у, к системе уравнений: Перечислим свойства ЗИП, которые существенно усложняют процесс их решения по сравнению с задачами линейного программирования: 1.Одним из наиболее общих подходов к решению задачи поиска экстремума (локального максимума или минимума) функции при наличии связующих ограничений на ее переменные (или, как еще говорят, задачи условной оптимизации) является метод Лагранжа. В случае дифференцируемое™ функций f и gi справедлива теорема, определяющая необходимое условие существования точки условного экстремума в задаче (3)-(4). Идея данного метода основана на том, что градиент функции указывает направление ее наиболее быстрого возрастания в окрестности той точки, в которой он вычислен. Условие (13) означает равенство нулю скалярного произведения градиентов функции f точках х(q 1) и х(q) Геометрически оно может быть интерпретировано как перпендикулярность векторов градиентов функции f в указанных точках, что и показано на рис. Продолжая геометрическую интерпретацию метода наискорейшего спуска, отметим, что в точке х(q 1) вектор , будучи градиентом, перпендикулярен линии уровня, проходящей через данную точку.В качестве начального приближения возьмем точку х(1) = (0,0). Система неравенств типа (18), из решения которых определяется интервал допустимых значений для , для данной задачи примет вид: Тогда достигается при . Путем подстановки координат точки х(2) в (27) определим множество активных ограничений в точке . Соответственно, задача (24) - (25), которую требуется решить для определения допустимого прогрессивного направления s(2) с учетом того, что и , примет вид: В данном случае оптимальный план ЗЛП находится довольно просто и равен . Отбросив дополнительную переменную s, получаем вектор s(2) = (1,0), т. е. очередная точка будет определяться как Действуя по аналогии с предыдущей итерацией, для определения промежутка допустимых значений шагового множителя составляем систему неравенств (18): Окончательно имеем .Делая вывод по работе, можно сказать, что задачи нелинейного программирования можно классифицировать в соответствии с видом функции F(x), функциями ограничений и размерностью вектора х (вектора решений). Общих способов решения, аналогичных симплекс-методу линейного программирования, для нелинейного программирования не существует. Задачи нелинейного программирования на практике возникают довольно часто, когда, например, затраты растут не пропорционально количеству закупленных или произведенных товаров. Многие задачи нелинейного программирования могут быть приближены к задачам линейного программирования, и найдено близкое к оптимальному решению.
План
Содержание
Введение
Глава I. Постановка задачи нелинейного программирования
Глава II. Методы решения задач нелинейного программирования
Глава III. Пример решения задачи нелинейного программирования методом допустимых направлений