Градиентные методы решения задач нелинейного программирования

Градиентные методы решения задач нелинейного программирования

Градиентные методы решения задач

МЕТОДЫ РЕШЕНИЯ ЗАДАЧ

НЕЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

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

Общая задача нелинейного программирования (ЗНП) оп­ределяется как за­дача нахождения максимума (или минимума) целевой функции f(x1, х2 . хп) на множестве D, определяемом системой ограничений равенств и неравенств:

gi(x1, х2 . хп ) f(x), то х* называют оптимальным планом. В этом случае х* является точкой глобаль­ного максимума.

С точки зрения экономической интерпретации f(x) может рассмат­риваться как доход, который получает фирма (предпри­ятие) при плане выпуска х, a gi(x) =0; -g(x) =0 ó < g(x) – y 2 = 0 >.

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

Градиентные методы решения задач

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

Ведущее место среди прямых методов ре­шения экстремальных задач занимает градиентный метод (точнее, семейство градиентных методов) поиска стационар­ных точек дифференцируемой функции. Напомним, что стаци­онарной называется точка, в которой Ñf(x) = 0 и которая в со­ответствии с необходимым условием оптимальности является «подозрительной» на наличие локального экстремума. Таким образом, применяя градиентный метод, находят множество точек локальных максимумов (или минимумов), среди которых определяется максимум (или минимум) глобальный.

Пусть f(x)=f(x1 , x2 . xn ) — дифференцируемая функ­ция, заданная на R n , а х ( q ) =(х1 ( q ) , х2 ( q ) . хn ( q ) ) – неко­торая текущая точка. Идея данного метода основана на том, что градиент функции указывает направление ее наиболее быстрого воз­рас­та­ния в окрестности той точки, в которой он вычислен. Поэтому, если из некоторой текущей точки х (1) переме­щаться в направлении вектора Ñf(x (1) ), то функция f будет возрастать, по крайней мере, в некоторой окрестности х (1) . Следовательно, для точки

лежащей в такой окрестности, справедливо неравенство f(х (1) ) (2) ). Про­должая этот про­цесс, мы постепенно будем приближаться к точке некоторого локального максимума (см. рис. 2.1).

Однако как только определяется направление движения, сразу же встает вопрос о том, как далеко следует двигаться в этом направлении или, другими словами, возникает проблема выбора шага l в рекуррентной формуле

x ( q ) = x ( q ) +f(x ( q ) ),

задающей последовательность точек, стремящихся к точке мак­симума. Как уже говори­лось выше, если x ( q ) — нестационарная точка (т. е. |Ñf(x ( q ) ) |>0 ), то при движении в направлении Ñf(x ( q ) ) функция f(x) на некотором промежутке обязательно будет возрастать. Отсюда возникает естественная идея такого выбора шага, чтобы движение в указанном направлении продол­жалось до тех пор, пока возрастание не прекратится .

Оговоримся, что каких-либо общих рекомендаций, каса­ющихся выбора исходной точки (или, как еще говорят, началь­ного приближения) x ( 0) , не существует, однако по возможно­сти она должна находиться близко от искомого оптимального плана х*.

В зависимости от способа выбора шага l различают различные вари­анты гради­ентного метода.

Процедура «Поиск решения» в MS Excel содержит две разновидности гради­ентного метода – Метод Ньютона и метод спряженных гради­ентов.

Методы решения задач нелинейного программирования

Задачи программирования становятся нелинейными, когда в них появляются произведения, обратные величины или высшие порядки нескольких или всех переменных.

Задачи нелинейного программирования имеют более важное значение, чем линейные за­дачи, потому что они чаще встречаются на практике. Иногда можно упростить нелинейную задачу, делая ряд прибли­женных допущении, так, чтобы она формулировалась в линейной по­становке. Так, например, симплекс-метод и метод наискорейшего спуска, рассмотренные выше, не могут быть применимы в случае нелинейных ограничений и нелинейной целевой функции. В этом случае, используя итерационные процессы, задача сначала линеаризуется для небольшого интервала, так что новое решение получается из результатов предыдущего.

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

Нелинейные задачи оптимального проектирования строительных конструкций разделяются на две основные группы:

1) задачи безусловной оптимизации, в которых на управляемые переменные (х1, х2, . хn), которым соответствует минимальное значение целевой функции F (х1, х2, . хn), не накладывается никаких ограничений;

2) задачи условной оптимизации, в которых на управляемые переменные (х1, х2, . хn), которым соответствует минимальное значение целевой функции F (х1, х2, . хn), накладываются ограничения, задаваемые в виде равенств и неравенств.

Считается, что большинство задач проектирования безусловной оптимизации проще, чем задачи условной оптимизации. Поэтому, одним из способов решения задачи условной оптимизации является ее преобразование к задаче безусловной оптимизации.

Методы решения задач безусловной оптимизации можно разделить на две группы:

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

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

Рассмотрим несколько методов решения задач нелинейного программирования.

Метод прямого поиска

Суть метода прямого поиска состоит в следующем. Принимается какое-либо начальное значение целевой функции. Затем все переменные фиксируются, кроме одной, например, х1. Значение х1 изменяется до тех пор, пока функция убывает. Как только функция перестает убывать значение х1 фиксируют и запоминают последнее значение целевой функции. Далее цикл повторяется, но уже изменяется следующая переменная, например, х2. Другие переменные сохраняют постоянное значение. Цикл повторяется с каждым переменным до тех пор, пока не будет достигнут оптимум целевой функции. Об этом будет свидетельствовать то, что всякое изменение любого аргумента в сторону увеличения приведет к возрастанию целевой функции.

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

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

Градиентные методы

Ряд инженерных задач связан с оптимизацией при наличии некоторого количества ограничений на управляемые переменные. Такие ограничения существенно уменьшают размеры области, в которой проводится поиск оптимума. Может показаться, что уменьшение размеров допустимой области должно упростить поиск. На самом деле, процесс оптимизации становится более сложным, поскольку установленные критерии оптимальности нельзя использовать при наличии ограничений.

Читать еще:  Герои 6 ошибка при запуске 0xc0000906

Градиентные методы минимизации целевой функции заключается в движении от точки хk к точке хk+1 в направлении антиградиента. Градиент функции определяется как вектор – столбец из частных производных

∂F(xk)

∂ x1

Основные методы нелинейного программирования

3.1. Градиентные методы

Градиентные методы, в основе которых лежит свойство градиента функции в точке (вектора частных производных, вычисленного в точке) как указателя направления наибольшего роста функции в окрестности точки.

Так при отсутствии ограничений одна из простейших разновидностей градиентных методов — метод наискорейшего спуска предлагает выбрать некоторую точку (план) Xk и начальный шаг Hk, вычислить градиент функции в выбранной точке grad F(Xk) и осуществить переход по градиенту (при максимизации) с выбранным шагом. Если значение функции в новой точке больше предыдущего, новая точка принимается за исходную и повторяется такая же процедура. При попадании в точку с меньшим значением уменьшается шаг (например, вдвое) и переход повторяется от исходной точки. Переходы продолжаются до достаточно малого шага .

Например, если нужно решить систему уравнений

то можно заменить эту задачу задачей минимизации функции F(X,Y)=[(X 2 +1)(Y-2)-3]2+[Y-ln(X+1)] 2 (если система имеет решение, то искомый минимум равен нулю).

Градиент этой функции определяется вектором

Выбираем начальную точку M(2,1) и шаг h=1.Здесь значение функции F(M)=64, градиент в этой точке grad F(M) =[ 64.066, -80.197], нормированный градиент (вектор единичной длины, составленный из компонент, деленных на корень из суммы их квадратов) gradн F(M) = [0.62, -0.78]. Смещаемся в направлении, обратном градиенту (ищем минимум), с выбранным шагом в точку М1-h gradн F(M)=(2-1 0.62, 1+1 0.78)=(1.38, 1.78) и обнаруживаем, что F(M1)=14

Аналогичный переход с учетом gradн F(M1) = [0.19, -0.98] приводит в точку М2(1.19, 2.76), где F(M2) 5.26, gradн F(M2) = [-0.96, -0.27]. Переход в очередную точку М3(2.15, 3.03) дает F(M3) 11.33 > F(M2).Соответственно уменьшаем шаг вдвое (h=0.5) и получаем точку М4(2.15, 3.03), где F(M4)=3.78, gradн F(M2) = [0.12, 0.99].

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

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

Градиентные методы для задач с ограничениями, где при смещениях по градиенту приходится сталкиваться с опасностью «выскочить» за пределы допустимого множества решений, существенно усложняются.

Существует обширная литература по численному анализу, где значительное внимание уделяется градиентным и другим итерационным методам, но тем не менее решение нелинейных задач оптимизации при наличии ограничений иногда весьма затруднительно.

3.2 Методы Монте-Карло

Методы Монте-Карло. Здесь отыскивается n — мерный параллелепипед, включающий в себя множество планов, и затем моделируются N случайных точек с равномерным законом распределения в параллелепипеде (практически во всех программных средах предусмотрено наличие соответствующих датчиков псевдослучайных чисел).

В точках, попавших во множество планов, вычисляются значения функции и запоминается точка текущего экстремума. После этого берется параллелепипед меньших размеров с центром в найденной точке, и в нем вновь моделируются N случайных точек. Процесс такого стохастического моделирования заканчивается при малых размерах параллелепипеда. Методы Монте-Карло имеют преимущество над моделированием на детерминированной сетке, так как их точность имеет порядок
1/ и не зависит от размерности задачи. Естественно, этими методами никто не пользуется при ручном счете; они просты для программной реализации и обычно используются при поиске начального приближения для градиентных методов.

3.3 Методы выпуклого программирования. Метод множителей Лагранжа

Методы выпуклого программирования, реализующие поиск минимума выпуклой функции или максимума вогнутой на выпуклом множестве планов.

Если множество планов — выпуклый многогранник, то эти методы допускают использование симплексного метода.

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

При решении многих задач нелинейного программирования определенный эффект дает метод множителей Лагранжа.

Пусть требуется найти экстремумы функции F(X) при условиях fi(X)=0 (i = 1 .. m).

Функция называется функцией Лагранжа и коэффициенты iмножителями Лагранжа.

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

Например, при поиске максимума F(X1, X2) = X1+X2 при единственном условии X1 2 +X2 2 =1 строится функция Лагранжа

Строим систему уравнений

решение которой дает и экстремальные значения целевой функции

Для определения типа найденного экстремума можно построить матрицу вторых производных F(X), вычисленных в экстремальной точке, и определить знаки главных ее миноров. Если все они положительны, то найден минимум; если они чередуются, начиная с минуса, то найден максимум (правило Сильвестра).

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

3.3.1 . Теорема Куна-Таккера

Пусть задача нелинейного программирования имеет вид

Для решения поставленной задачи используется центральная теорема математического программирования – теорема Куна-Таккера, выдвигающая необходимые условия существования решения задачи нелинейного программирования. Достаточные условия существования решения формулируются в теоремах Куна-Таккера второго, третьего и т.д. порядках и в данном курсе не рассматриваются.

Теорема (Куна-Таккера) Точка может являться решением задачи нелинейного программирования только в том случае, если в ней выполнены следующие условия:

1) ;

2) ;

3) , .

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

Решение. Запишем ограничения в стандартном виде

Первое условие теоремы Куна-Таккера позволяет записать два уравнения:

,

.

Второе условие теоремы позволяет записать еще два уравнения: , .

Подставляя в них функции и вычислив производные, получаем систему из 4 уравнений с 4 неизвестными:

Рассмотрим несколько ветвей решения системы уравнений:

1)

2) .

Вторая система распадается на два случая:

2а) ; 2б) ;

3) ;

4) ,

Эта система распадается на две

4а) ; 4б) .

После того как система решена результаты собираются в таблицу:

Общий вид задач нелинейного программирования

Математическая модель задачи нелинейного программиро­вания в общем виде формулируется следующим образом: найти вектор = 1, x2, …, xn), удовлетворяющий системе ограни­чений и доставляющий экстремум (наибольшее или наименьшее зна­чение) целевой функции: L=f(x1,x2,x3,…xn), где xj переменные, j = ; L, f, gi заданные функции от n переменных, bi — фиксированные значения.

Читать еще:  Код ошибки 60 сбербанк зарплатный проект

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

Нелинейное программирование применяется при прогнози­ровании промышленного производства, управлении товарными ресурсами, планировании обслуживания и ремонта оборудова­ния и т.д.

Для задачи нелинейного программирования нет единого метода решения.

В зависимости от вида целевой функции и системы ограничений разработаны специальные методы решения, например, такие как:

методы множителей Лагранжа,

квадратичное и выпуклое программи­рование,

приближенные методы реше­ния,

Из нелинейного программирования наиболее разработаны задачи, в которых система ограничений линейная, а целевая функция нелинейная.

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

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

Глобальный максимум функции — наибольшее значение из ло­кальных максимумов.

Глобальный минимум функции — наименьшее значение из ло­кальных минимумов.

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

2. Графический метод решения задач нелинейного программирования.

Рассмотрим примеры решения задач нелинейного програм­мирования с двумя переменными, причем их целевые функции и системы ограничений могут быть заданы в линейном и не­линейном виде. Так же как и в задачах линейного программи­рования, они могут быть решены графически.

2.1. Задача с линейной целевой функцией и нелинейной системой ограничений

Пример 1. Найти глобальные экстремумы..

Целевая функция . Ограничения:

Решение. Область допустимых решений — часть окруж­ности с радиусом 4, которая расположена в первой четверти.

Линиями уровня целевой функции являются параллельные прямые с угловым коэффициентом, равным -2.

Глобальный минимум достигается в точке O (0, 0), глобальный максимум — в точке А касания линии уровня и окружности. Проведем че­рез точку А прямую, перпендикулярную линии уровня.

Прямая проходит через начало координат, имеет угловой коэффициент 1/2 и уравнение x2 = 1/2х1.

Решение системы, очевидно:

х1 = 8 /5, x2 = 4 /5, при этом L = 16 /5 + 4 /5 = 4 .

Ответ. Глобальный минимум, равный нулю, достигается в точке O (0, 0), глобальный максимум, равный 4 , — в точке А(8 /5, 4 /5).

2.2. Задача с нелинейной целевой функцией и линейной системой ограничений

Пример 2. Найти глобальные экстремумы.

Целевая функция Ограничения:

Решение. Область допустимых решений – фигура OABD .

Линиями уровня будут окружности с центром в точке O1. Максимальное значение целевая функция имеет в точке D(9, 0), минимальное — в точке O1 (2, 3). Поэтому

Ответ. Глобальный максимум, равный 58, достигается в точке D (9, 0), глобальный минимум, равный нулю, — в точке O1 (2, 3).

3. Метод множителей Лагранжа

Дана задача нелинейного программирования

при ограничениях:

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

Для решения задачи составляется функция Лагранжа

где λi множители Лагранжа.

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

Затем определяются частные производные:

Приравняв к нулю частные производные, получим систему

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

Пример 8. Найти точку условного экстремума функции

Решение. Составим функцию Лагранжа:

Пояснения. Для составления функции Лагранжа запишем ограничения в виде: q1=x1-x2-2 и q2=x2+2x3-4. Функция Лагранжа есть сумма целевой функции и ограничений, умноженных на множитель, который будет получен при решении системы составленной из частных производных функции Лагранжа.

Найдем частные производные функции Лагранжа по пере­менным x1, x2, x3, λ1, λ2. Приравняв к нулю полученные вы­ражения, решим систему

Определим характер экстремума, изменяя полученные зна­чения переменных.

Измененные значения должны удовлетво­рять заданной системе ограничений.

Возьмем х1 f2(2), т.е. в данный момент оборудование необходимо заменить, так как величина прибыли, получаемая в результате замены оборудования, больше, чем в случае ис­пользования старого. Результаты расчетов помещаем в табли­цу, момент замены отмечаем звездочкой, после чего дальней­шие вычисления по строчке прекращаем (табл. 29.2).

Можно не решать каждый раз уравнение, а вычис­ления проводить в таблице. Например, вычислим f4(t):

Дальнейшие расчеты для f4(t) прекращаем, так как f4(4) = 23

Методы решения задач нелинейного программирования

Автор: Пользователь скрыл имя, 14 Марта 2012 в 14:53, курсовая работа

Описание работы

Цель данной курсовой работы – отразить использование различных методов в решении задач нелинейного программирования.
Для достижения цели курсовой работы необходимо выполнить следующие задачи:
Рассмотреть общую постановку задачи нелинейного программирования;
Описать графический метод решения задач нелинейного программирования;
Описать метод множителей Лагранжа для решения задач нелинейного программирования;
Описать градиентный метод решения задач нелинейного программирования;
Рассмотреть на примерах вышеперечисленные методы решения задач нелинейного программирования.

Содержание

ВВЕДЕНИЕ………………………………………………………………………. 3
1. ОБЩАЯ ПОСТАНОВКА ЗАДАЧИ НЕЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ…………………………………………………5
2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ НЕЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ С ДВУМЯ ПЕРЕМЕННЫМИ………………6
3. МЕТОД МНОЖИТЕЛЕЙ ЛАГРАНЖА ……………………………….. 8
4. ПРИМЕР РЕШЕНИЯ ЗАДАЧИ НЕЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ МЕТОДОМ МНОЖИТЕЛЕЙ
ЛАГРАНЖА ……………………………………………………..………. 9
5. ГРАДИЕНТНЫЙ МЕТОД……………………………………………. …11
6. ПРИМЕР РЕШЕНИЯ ЗАДАЧИ НЕЛИНЕЙНОГО
ПРОГРАММИРОВАНИЯ ГРАДИЕНТНЫМ МЕТОДОМ……………..…12
ЗАКЛЮЧЕНИЕ………………………………………………………………. 17
СПИСОК ИСПОЛЬЗУЕМЫХ ИСТОЧНИКОВ…………………………. ….19

Работа содержит 1 файл

курсовая .doc

Величины себестоимости изделий (т.е. затраты на их выпуск) зависят от объема их производства и приближенно описываются следующими формулами:

• себестоимость одного изделия A: 7+0,2X1, где X1 — объем производства изделий A;

• себестоимость одного изделия B: 8+0,2X2, где X2 — объем производства изделий B.

Требуется составить план производства, обеспечивающий предприятию максимальную прибыль.

Предварительно найдем градиент целевой функции:

grad E = =(5-0,4X1, 2-0,4X2).

Найдем также начальное допустимое решение. В качестве такого решения можно использовать любой набор значений X1 и X2, удовлетворяющий системе ограничений. Начальное допустимое решение можно найти, например, следующим образом: исключить из целевой функции все нелинейные элементы и решить симплекс-методом полученную задачу линейного программирования. Для рассматриваемого примера такая задача будет следующей:

E = 5X1 + 2X2 → max.

Решив эту задачу, получим начальное допустимое решение: X1(0) =6,923, X2(0)=0. Найдем значение целевой функции для этого решения: E(0) = 5·6,923 —0,2·6,9232 + 2·0 — 0,2·02 = 25,03.

Необходимо также задать требуемую точность решения задачи (ε). Зададим ее равной 500 ден.ед., т.е. будем считать, что решение найдено, если переход к новому решению приводит к увеличению целевой функции не более чем на 500 ден.ед. В данной задаче целевая функция выражается в тысячах ден.ед., поэтому ε=0,5.

Читать еще:  Код ошибки 0x1000007e

Решим задачу, используя итерационный алгоритм на основе метода

1. Определяется градиент целевой функции в точке ОДР, соответствую-

щей текущему решению:

grad E (X(0))= (5-0,4·6,923; 2-0,4·0) = (2,2; 2).

2. Определяется угловая точка ОДР, соответствующая предельно допустимому (без нарушения ограничений) перемещению от текущего решения в направлении градиента. Для этого решается задача линейного программирования с исходной системой ограничений и целевой функцией, коэффициентами которой являются координаты градиента:

f = 2,2X1 + 2X2 → max.

Решение этой задачи следующее: X*1 =4,863, X*2 = 4,463. Это означает, что поиск нового решения будет выполняться в направлении от точки X(0)= =(6,923; 0) к точке X*= (4,863; 4,463).

3. Составляются уравнения для перехода к новому решению:

X1(1) =X1(0)+ λ (X1*- X1(0));

где λ – коэффициент, задающий величину перемещения от текущего решения к новому решению в направлении точки X*. Этот коэффициент определяется на следующем шаге.

Для рассматриваемого примера эти уравнения имеют следующий вид:

X1(1) = 6,923 + λ(4,863-6,923) = 6,923 – 2,06λ;

X2(1) = 0 + λ(4,463-0) = 4,463λ.

4. Определяется коэффициент λ. Этот коэффициент находится таким образом, чтобы переход к новому решению обеспечивал максимальное значение целевой функции. С этой целью уравнения для перехода к новому решению, построенные на шаге 3, подставляются в целевую функцию E. В результате целевая функция представляется как функция от коэффициента λ:

E = 5(6,923 – 2,06λ) — 0,2(6,923 – 2,06λ)2 + 2·4,463λ — 0,2(4,463λ)2 =

Значение λ находится из условия экстремума целевой функции, т.е. из условия dE/dλ=0:

1. Если значение λ, найденное из уравнения dE/dλ=0, оказывается больше единицы, то принимается λ=1. Это означает, что экстремум целевой функции в направлении, задаваемом градиентом, находится за пределами ОДР. В этом случае новое решение должно находиться на границе ОДР (т.е. в точке X*), но не выходить за нее.

2. Если уравнение dE/dλ=0 не имеет решений (например, не зависит от λ), то также принимается λ=1.

5. Из уравнений, составленных на шаге 3, определяется новое решение:

X1(1) = 6,923 – 2,06·0,448 = 6;

X2(1) = 4,463·0,448 = 2.

Определяется значение целевой функции для полученного решения:

E(1) = 5·6 — 0,2·62 + 2·2 — 0,2·22 = 26.

6. Проверяется условие окончания поиска решения. Для этого определяется разность значений целевой функции для нового и предыдущего решения: ΔE = |E(1) –E(0)| = |26-25,03| = 0,97. Эта величина сравнивается с заданной точностью ε. Если ΔE ≤ ε, то текущее решение принимается в качестве оптимального. В данном случае ΔE = 0,97, ε = 0,5. Таким образом, условие окончания поиска решения не выполняется. Требуется следующая итерация.

1. Определяется градиент целевой функции в точке ОДР, соответствующей текущему решению:

grad E (X(1))= (5-0,4·6; 2-0,4·2) = (2,6; 1,2).

2. Определяется угловая точка ОДР, соответствующая предельно допустимому перемещению от текущего решения в направлении градиента. Для этого решается следующая задача линейного программирования:

f = 2,6X1 + 1,2X2 → max.

Решение этой задачи следующее: X1*=4,863, X2* = 4,463.

3. Составляются уравнения для перехода к новому решению:

X1(2) = 6 + λ(4,863-6) = 6 – 1,137λ;

X2(2) = 2 + λ(4,463-2) = 2 + 2,463λ.

4. Определяется коэффициент λ из условия экстремума целевой функции:

E = 5(6 – 1,137λ) — 0,2(6 – 1,137λ)2 + 2(2 + 2,463λ) — 0,2(2 + 2,463λ)2 =

5. Из уравнений, составленных на шаге 3, определяется новое решение:

X1(2) = 6 – 1,137·0 = 6;

X2(2) = 2 + 2,463·0 = 2.

Определяется значение целевой функции для полученного решения:

E(2) = 5·6 — 0,2·62 + 2·2 — 0,2·22 = 26.

6. Проверяется условие окончания поиска решения. Определяется разность значений целевой функции для нового и предыдущего решения:

Δ E = |E (2)-E (1)| = 0. Так как ΔE ≤ ε, оптимальное решение найдено: X1=6, X2=2. Оптимальное значение целевой функции E=26.

Таким образом, предприятию следует выпустить 6 изделий типа A и 2 изделия типа B. Такой план производства обеспечит предприятию максимальную прибыль в размере 26 тыс ден.ед.

1. В данном случае решение оказалось целочисленным, как и требуется по смыслу задачи. Если бы оно оказалось дробным, то для поиска оптимального целочисленного решения потребовалось бы применять специальные методы нелинейного целочисленного программирования.

2. В рассмотренном примере решалась задача с целевой функцией, подлежащей максимизации. Если требуется минимизация целевой функции, то задача решается точно так же. Единственное отличие состоит в том, что целевая функция W в задаче, решаемой на шаге 2,также подлежит минимизации

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

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

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

Применение экономико-математических методов и моделей позволяет существенно улучшить качество планирования и получить дополнительный эффект без вовлечения в производство дополнительных ресурсов.

Данная курсовая работа направлена на изучение методов решения задач нелинейного программирования. В ходе выполнения работы были выполнены такие задачи, как:

 Рассмотрение общей постановки задачи нелинейного программирования;

 Описание графического метода решения задач нелинейного программирования;

 Описание метода множителей Лагранжа для решения задач нелинейного программирования;

 Описание градиентного метода решения задач нелинейного программирования;

 Рассмотрение на примерах методов решения задач нелинейного программирования.

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

СпиСОК ИСПОЛЬЗуемых ИСТОЧНИКОВ

1. Бодров В.И Математические методы принятия решений / В.И. Бодров, Т.Я. Лазарева, Ю.Ф. Мартемьянов. – Тамбов: Издательство ТГТУ, 2004. – 83 с.

2. Самаров К. Л. Функции нескольких переменных. Нелинейное программирование / К. Л. Самаров. – М. : ООО «Резольвента», 2009. – 26 с.

3. Исследование операций в экономике / под. ред. Н.Ш. Кремера . – М. : Юнити, 2000. – 408 с.

4. Ковалев В.В. Финансовый анализ: методы и процедуры / В.В. Ковалев. – М.: Финансы и статистика, 2002. – 560 с.

5. Смородинский С.С. Оптимизация решений на основе методов и моделей математического программирования / С.С. Смородинский, Н.В. Батин. – Минск: БГУИР, 2003. – 136 с.

IT Новости из мира ПК
Добавить комментарий