Контрольная работа - Методы разработки нелинейных моделей - файл n1.docx

Контрольная работа - Методы разработки нелинейных моделей
скачать (130.6 kb.)
Доступные файлы (1):
n1.docx131kb.09.09.2012 02:27скачать

n1.docx



МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РК

ИНСТИТУТ УПРАВЛЕНИЯ

Кафедра «ЭКОНМИКИ»


КОНТРОЛЬНАЯ РАБОТА
По дисциплине: «ЭММ»


На тему: МЕТОДЫ РАЗРАБОТКИ НЕЛИНЕЙНЫХ МОДЕЛЕЙ






Выполнила: студентка группы УиА -3-1с/о




Шрейдер Ю.А.










Проверил (а): проф. Кусаинов Т. А.


Астана, 2009
Содержание


Введение

3

1.

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

4

2.

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

7

3.

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

9

4.

Элементы выпуклого программирования

10

Заключение

13

Список использованной литературы

14

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

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

Сама математическая модель может быть достаточно сложной, нелинейной. Это зачастую делает невозможным ее качественное исследование традиционными методами прикладной математики. Именно поэтому в громадном большинстве случаев проводиться качественное исследование на более простых, но обязательно содержательных, по отношению к исходной математической модели задачах. В этом случае мы должны говорить о модельных (упрощенных) задачах для основной математической модели (моделей для модели).
1. Методы моделирования нелинейного программирования
Многие сложные оптимизационные задачи отличаются тем, что функция цели и/или ограничения представляют собой нелинейные функции переменных величин. Такого рода задачи принято называть нелинейными. Существуют некоторые методы алгебраического представления нелинейных задач оптимизации сочетания отраслей на предприятии, выбора портфеля инвестиций, а также моделирования этих задач с использованием средств Excel. Такого рода задачи возникают в ситуациях, когда имеет место риск значительных убытков и ставится цель снизить величину риска.

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

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

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

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

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

Когда мы решаем линейные задачи, Solver гарантирует нахождение оптимального решения (если оно вообще существует). Это объясняется следующими свойствами таких задач:

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

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

При поиске оптимального решения нелинейных задач вполне
возможно, что найденное решение окажется не самым лучшим. Причина лежит в особенностях математических моделей нелинейных задач. Нелинейное программирование охватывает широкий класс настолько сложных задач, что до сих пор невозможно разработать общие методы, подобные методам в линейном программировании, которые позволяли бы решать любые задачи нелинейного программирования. Трудность решения нелинейных задач состоит прежде всего в том, что область допустимых решений здесь в отличие от задач линейного программирования может оказаться невыпуклой или иметь бесконечное число крайних точек, а возможно и то и другое одновременно. При нелинейности целевой функции возникают другие затруднения: экстремум может достигаться не только на границе, но и внутри допустимой области. Более того, целевая функция может иметь в допустимой области несколько локальных экстремумов. Для тех, кто дружит с математикой, напомним, что функция f(x) достигает в точке х*Х локального максимума (минимума), если f(x*)f(x) (f(x*)f(x) для всех х(х*) Х, где (х*)-некоторая окрестность х*. Если же f(x*)f(x) (f(x*)f(x)) для всех хХ, то в точке х* функция f(x) достигает глобального максимума (минимума). Локальный максимум (минимум) может быть существенно меньше (больше) глобального; с другой стороны, глобальный максимум (минимум) является, конечно же, и локальным.

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

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

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

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

Solver гарантирует нахождение оптимального решения задач квадратического программирования. Это объясняется свойствами задач данного класса. Во-первых, все ограничения в таких задачах линейны. Следовательно, допустимое множество решений выпукло. Во-вторых, целевая функция выпукла (вогнута). Следовательно, она имеет лишь один локальный экстремум, который одновременно является глобальным. Другими словами, функция цели достигает своего экстремума лишь в одной точке множества решений Многие практические задачи, в том числе те, в которых принимается в расчет фактор экономического риска, можно сформулировать в виде задач квадратического программирования.

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

В задачи нелинейного программирования могут входить зависимости любого вида. Поэтому в общем виде задача нелинейного программирования (НП) состоит в определении максимального (минимального) значения функции:

Z = f (xl, х2, .., хn)

при условии, что ее переменные удовлетворяют соотношениям
gi (xl, х2, .., хn) = bi, i = 1,k, (1.1)
gi (x1 x2, .. , xn) bi, i = k + l,m. (1.2)
При этом предполагается, что известны функции n переменных f и g1, а bi - заданные числа. Обычно на некоторые переменные х1, х2, . , хn накладывается условие неотрицательности. Кроме того, ограничением может служить условие целочисленности решения для ряда переменных.

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

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

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

На рис. 1.1 показана выпуклая область (круг, шар, куб) для нее отрезок AB D, а точка Р является точкой абсолютного минимума. Для невыпуклой области отрезок ABD целиком. Точки М и N являются точками минимума, но для области D точка N точкой абсолютного минимума не является. Поэтому будем говорить, что в точке М достигается глобальный минимум, а в точке N достигается локальный минимум.



Рис. 1.1. Выпуклые множества Рис. 1.2. Невыпуклые множества

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

Процесс нахождения решения ЗНП (1.1) и (1.2) с использованием ее геометрической интерпретации включает следующие этапы:

  1. находят область допустимых решений задачи, определяемую соотношениями (1.2) (если она пуста, то задача не имеет решения);

  2. строят гиперповерхность f (х1, х2, ...,xn) = h (гиперповерхность - обобщение понятия поверхности n-го порядка, так гиперповерхность 2-го порядка - гиперплоскость);

  3. определяют гиперповерхность наивысшего (наинизшего) уровня или устанавливают неразрешимость задачи из-за неограниченности функции (1.1) сверху (снизу) на множестве допустимых решений;

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

Пример 1. Найти минимальное и максимальное значения функции


При ограничениях










Находим область допустимых решений - многоугольник ОАВС (рис. 1.3).
Cтроим линию уровня






Рис. 1.3

где h - некоторая постоянная и исследуем ее поведение при различных значениях n. Преобразуем линию уровня .

При каждом значении h получаем параболу, которая тем выше отдалена от оси ОХ, чем больше значение h > 0.

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



Решая эту систему, найдем, что x1 = 3, х2 = 0, т.е Zmin = 9 в точке Е (3;0).

Максимальное значение в точке D:

.
Отсюда х1 = 3, х2 = 4, и Zmax = 13 в точке Д(3; 4).

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


3. Метод множителей Лагранжа
Пусть задана задача математического программирования: максимизировать (минимизировать) функцию

Z = f (x1, x2, ..., хn)

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

gi (x1, x2, ..., хп) = b1, i = 1,m. (1.4)

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


Вводим набор переменных ?1, ?2, ..., ?т, называемых множителями Лагранжа и составляем функцию Лагранжа:

(1.5)


Определяем частные производные ,(j = 1,п), (i =1) и рассматриваем систему (n + m) уравнений
(1.6)

c(n+m) неизвестными x1, x2, ..., xn, ?1, ?2, ..., ?т1

Всякое решение системы (1.6) определяет точку х =( в которой может иметь место экстремум функции f (x1, x2, ..., хn). Следовательно, решив систему (1.6), получают все точки, в которых функция (1.3) может иметь экстремальные значения. При этом неизвестен способ определения точек глобального минимума или максимума. Дальнейшее исследование найденных точек проводят так же, как и в случае безусловного экстремума, т.е. если для функции (1.3) существуют вторые частные производные и они непрерывны, то можно вывести достаточное условие существования локального экстремума функции в точке, являющейся решением системы (1.6). Однако практическое значение этого условия невелико.

Метод множителей Лагранжа имеет ограниченное применение, так как система (1.6), как правило, имеет несколько решений.

4. Элементы выпуклого программирования
Выпуклое программирование рассматривает задачи минимизации нелинейной, но гладкой выпуклой функции (первые производные функции непрерывны) при ограничениях, заданных нелинейными неравенствами, определяющими выпуклое множество пространства переменных.

Нужно отыскать вектор

x = (x1, x2, ..., хn), (2.1)
который удовлетворяет условиям
?i(x1, x2, ..., хn)0,(i=1,n) (2.2)

и для которого функция

Z = f(x1, x2, ..., хn) (2.3)

принимает экстремальное значение.

Векторы, удовлетворяющие условию (2.2), называются допустимыми, а искомые векторы - оптимальными.

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

Задача в форме (2.1) - (2.3) называется канонической формой общей задачи выпуклого программирования.

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



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




Строим область допустимых решений данной задачи:

a) x1 0, х2 0 - первая четверть;

б) - окружность с центром в начале координат и радиусом равным четырем. Область решений неравенства состоит из точек, лежащих внутри этой окружности и на ней самой,

в) -x1*x2 + 2 = 0 или х2 = - обратная пропорциональная зависимость. Область решений неравенства -х1*х2 + 2 0 - полуплоскость, лежащая над правой ветвью кривой и левой ветви.

Таким образом, с учетом совокупности этих условий, областью допустимых решений данной задачи является замкнутая выпуклая область ВСДА (рис. 2.1).

Соответственно функции Z = Зх1 + х2 проводим вектор n(3,1), показывающий направление скорейшего возрастания функции Z. Строим, линию уровня 3x1 + х2 = h и перемещаем ее в направлении п. В точке А() функция Z принимает минимальное значение, а в точке С( - максимальное значение.

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

Рис. 2.1

Находим минимальное значение функции Z, для чего определяем координаты точки А. С одной стороны, линия уровня и касательная к кривой из уравнения Зх1 + х2 = h имеют угловой коэффициент К =-3, с другой стороны, производная от функции х2 = равна х'2 = -, а в точке А эта
производная равна и равна значению -3. Из соотношения находим, что следовательно, и при
этом Zmin =
Существующие методы позволяют решать узкий класс задач, ограничения которых имеют вид (2.2).






Заключение

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

В данной теме рассмотрен вопрос нахождения решения задач нелинейного программирования с использованием ее геометрической интерпретации и с помощью метода множителей Лагранжа.
Список использованной литературы
1. Абуов К.К., Шлефрин И. Математическое программирование. Акмола, 1998.

2. Практический менеджмент в примерах и задачах. Т. Кусаинов./ Астана 2001.-60с.

3. Шапкин А. С., Мазаев Н. П., Математические методы и модели исследования операций: Учебник.- 4-е изд. – М.:Издательско-торговая корпорация «Дашков и Ко», 2007. - 400с.

4. Замков О.О., Толстопятенко А. В., Черемных Ю. Н. Математические методы в экономике:Уч/Под общ. Ред. д.э.н., проф. А. В. Сидоровича. 4-е изд., стереотип. – М.: Изд. «Дело и Сервис», 2004. -368с.



Учебный материал
© nashaucheba.ru
При копировании укажите ссылку.
обратиться к администрации