Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Вопрос 30. Нелинейное программирование
Математическая модель задачи нелинейного программирования в общем виде формулируется следующим образом: найти вектор x=(x1,x2,…,xn), удовлетворяющий системе ограничений и доставляющий экстремум (наибольшее или наименьшее значение) целевой функции L=f(x1,x2,….,xn), где xj- переменные, j=1,…., n, L, f, gi – заданные функции от n переменных, bi – фиксированные значения. Рассматриваются, в основном, задачи, минимизирующие целевую функцию. Нелинейное программирование применяется при прогнозировании промышленного производства, управлении товарными ресурсами, планировании обслуживания и ремонта оборудования и т. п. Для задачи нелинейного программирования и отличие от линейных задач нет единого метода решения. В зависимости от вида целевой функции и системы ограничений разработаны специальные методы решения, к которым относятся методы множителей Лагранжа, квадратичное и выпуклое программирование, градиентный метод, приближенные методы решения, графический метод. Пример. Найти точки максимума и минимума функции z=x2+2y2 при условии 3х+2у=11. Решение. Выразим из уравнения 3х+2у=11 переменную у через переменную х и подставим полученное выражение в данную функцию z. Эта функция будет иметь единственный минимум (найдем производную, получим уравнение, приравняем его к нулю) при х0=3, при этом у0=1. Точка (3,1) – точка условного экстремума (минимума), так как вторая производная положительная. В рассмотренном примере уравнение связи оказалось линейным, поэтому его легко удалось разрешить относительно одной из переменных. Однако в более сложных случая это сделать сложно. Для отыскания условного экстремума в общем случае и используется метод множителей Лагранжа.
Метод множителей Лагранжа основан на построении так называемой функции Лагранжа. Рассмотрим функцию трех переменных . Эта функция называется функцией Лагранжа, а λ- множителем Лагранжа. Пусть решается задача определения условного экстремума функции нескольких переменных z = f(X) при ограничениях. Составим функцию L(X)=f(X)+Sliji(X), i=1,2,…,m, которая называется функцией Лагранжа. li— постоянные множители (множители Лагранжа). Определение стационарных точек этой функции приводит к решению системы уравнений Задача нахождения условного экстремума функции z = f(X) сводится к нахождению локального экстремума функции L (X). Если стационарная точка найдена, то вопрос о существовании экстремума в простейших случаях решается на основании достаточных условий экстремума — исследования знака второго дифференциала d2L(X) в стационарной точке при условии, что переменные приращения Dxi связаны соотношениями , полученными путем дифференцирования уравнений связи.
Проще говоря, для нахождения условного экстремума функции двух переменных z=f(x,y) при условии g(x,y)=C требуется найти решение системы Представленная система основана на теореме. Теорема. Если точка (х0,у0) является точкой условного экстремума функции z=f(x,y) при условии g(x,y)=C, то существует значение х0 такое, что точка (х0,у0, λ0) является точкой экстремума функции Решим теперь рассмотренный выше пример методом Лагранжа. Составляем функцию Лагранжа Приравнивая к нулю ее частные производные, получаем систему уравнений Ее единственное решение х=3, у=1, λ=-2, таким образом, точкой условного экстремума может быть только эта точка. Найдя вторые производные, можно убедиться, что в этой точке заданная функция z имеет условный минимум. Наиболее простым методом решения задач НЛП является графический метод. Если число переменных п = 2, нелинейные задачи можно решать графически. Ограничения должны быть записаны в виде неравенств Как и в случае геометрического решения задач линейного программирования, сначала необходимо построить область допустимых решений (ОДР) — множество точек плоскости, удовлетворяющих неравенствам. Но, в отличие от задач линейного программирования, здесь ОДР не обязательно будет выпуклой и может быть даже разрывной. Экстремум функции может достигаться и внутри области, и на границе. После построения ОДР следует записать уравнения линий уровня целевой функции — множество точек плоскости, в которых целевая функция постоянна, и определить направление возрастания (убывания) целевой функции, построив, например, линии уровня для разных значений С. Затем, перемещая линию уровня в нужном направлении в ОДР, найти точки области, в которых целевая функция принимает оптимальное значение.
Из нелинейного программирования наиболее разработаны задачи, в которых система ограничений линейная, а целевая функция нелинейная. Однако даже для таких задач оптимальное решение может быть найдено для определенного класса целевых функций. При этом следует отметить, что в отличие от задач линейного программирования, где точками экстремума являются вершины многогранника решений, в задачах с нелинейной целевой функцией точки могут находиться внутри многогранника, на его ребре или вершине. При решении задач нелинейного программирования для целевой функции необходимо различать понятия глобальный максимум или глобальный минимум. Глобальный максимум (минимум) функции – это ее наибольшее (наименьшее) значение из локальных максимумов (минимумов). Наличие локальных экстремумов затрудняет решение задач, так как большинство существующих методов нелинейного программирования не позволяет установить, является найденный экстремум локальным или глобальным. Поэтому имеется возможность в качестве оптимального решения принять локальный экстремум, который может существенно отличаться от глобального. Вторая часть. Информатика.
|
||||||
Последнее изменение этой страницы: 2017-01-19; просмотров: 338; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 3.129.211.87 (0.005 с.) |