Размещено на http://www.allbest.ru/

Содержание

Введение

1. Экономико-математический аппарат и его роль в обосновании управленческих решений

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

1.1.1 Специфика методов нелинейного программирования

2. История разработки основных методов нелинейного программирования

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

3.1 Градиентные методы. Метод наискорейшего спуска

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

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

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

3.4 Дробно-линейное программирование

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

3.6 Метод половинного деления

3.7 Метод «золотого сечения»

3.8 Метод Фибоначчи

3.9 Метод Гаусса-Зайделя

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

нелинейный программирование выпуклый математический



Введение

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

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

Объект исследования: организация.

Предмет исследования: процесс принятия решений в организации.

Цель работы: изучение методов принятия решений.

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

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



1. Экономико-математический аппарат и его роль в обосновании управленческих решений

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

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

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

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

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

· градиентные методы,

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

· графический метод.

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

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

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

Глобальный максимум (минимум) функции -- это ее наибольшее (наименьшее) значение из локальных максимумов (минимумов).

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

1.1.1 Специфика нелинейных программ и методы их решения

Многообразие методов решения линейных программ имеет в своей основе идею упорядоченного перебора опорных планов (вершин) исходной или сопряженной задачи.

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

1. Множество планов может оказаться невыпуклым или иметь бесконечное количество "вершин".

2. Искомые экстремумы могут достигаться как на границе множества планов, так и внутри его.

3. В нелинейных программах возникает проблема поиска глобального экстремума среди множества локальных.

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

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



2. История разработки основных методов нелинейного программирования

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

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

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

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

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

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

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

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

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

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

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

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

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

Таблица 1

Классы задач и методы их решения

Классы задач	Методы решения
Поисковые	Нелинейное программирование
Распределенные	Линейное программирования
Управление запасами	Теория управления запасами
Массовое обслуживание	Теория массового обслуживания
Календарное планирование	Теория расписания
Состязательные задачи	Теория игр



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

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

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

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

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

(X²+1)(Y-1)=3,Y=ln(X+1),

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

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

Grad F(X,Y) = {2[(X²+1)(Y-2)-3] 2X (Y-2) - 2[Y-ln(X+1)]/(X+1), 2 [(X²+1)(Y-2)-3](X²+1) - 2[Y-ln(X+1)]}.

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

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

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

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

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

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



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

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

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

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

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

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

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

F(X₁, X₂,..,X_n) = f₁(X₁) + f₂(X₂) +... + f_n(X_n).

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

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

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

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

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

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

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

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

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

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

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

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

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

1) ;

2);

3) , .

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

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

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

,

.

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

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

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

1)

2) .

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

2а) ; 2б) ;

3) ;

4) ,

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

4а) ; 4б) .

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

Таблица 2

Результаты системы, через теорему Куна-Таккера

Р	х	у			f
Р1	0		0	0	-
Р2	0	1	-1	0	0
Р3	0	0	0	-1	0
Р4	1	0	-1	-2	1
Р5	-1	0	-1	-2	1

Предварительно убеждаемся, что все точки принадлежат допустимому множеству. Подставляя их координаты в ограничения-неравенства и видя, что они остаются истинными, рассчитываем значение целевой функции в каждой из них. Кроме того, убеждаемся, что третье условие теоремы Куна-Таккера также выполнено во всех точках. Сравнивая значение целевой функции в каждой из найденных точек, видим, что наибольшее значение функции 1 достигается в точках (1;0) и (-1;0), наименьшее - в точке (0; ).

3.4 Дробно-линейное программирование

Математическая модель задачи

Дробно-линейное программирование относится к нелинейному программированию, так как имеет целевую функцию, заданную в нелинейном виде.

Задача дробно-линейного программирования в общем виде записывается следующим образом:

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

где cj, dj, bi, aij -- постоянные коэффициенты и djxj ? 0.

Рассмотрим задачу дробно-линейного программирования в виде

(3.4.1)

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

(3.4.2)

Будем считать, что d1x1 + d2x2 ? 0.

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

Из выражения (3.4.1) найдем х2:

Прямая x2 = kx1 проходит через начало координат. При некотором фиксированном значении L угловой коэффициент k прямой тоже фиксирован и прямая займет определенное положение. При изменении значений L прямая х2 = kx1 будет поворачиваться вокруг начала координат (рисунок 1).

Рисунок 1

Установим, как будет вести себя угловой коэффициент k при монотонном возрастании L. Найдем производную от k по L:

Знаменатель производной всегда положителен, а числитель от L не зависит. Следовательно, производная имеет постоянный знак и при увеличении L угловой коэффициент будет только возрастать или только убывать, а прямая будет поворачиваться в одну сторону. Если угловой коэффициент прямой имеет положительное значение, то прямая вращается против часовой стрелки, при отрицательном значении k -- по часовой стрелке. Установив направление вращения, находим вершину или вершины многогранника, в которых функция принимает max(min) значение, либо устанавливаем неограниченность задачи.



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

Задача заключается в локализации экстремума функции одной переменной, заданной на интервале [a, b] с точностью до Д. При решении этой задачи весь интервал разбивается на участки величиной Д. В узлах разбиения вычисляются значения функции Q и из них выбирается экстремальное. Этот метод требует больших затрат времени (зависящего от значения Д), но главное его преимущество - это определение глобального экстремума.

Рисунок 2 Локализация экстремума методом сканирования: геометрическая интерпретация



3.6 Метод половинного деления

Естественным и наиболее распространенным на практике методом поиска экстремума функции одной переменной является метод последовательного деления отрезка пополам. Этот метод был известен еще в древней Греции как метод дихотомии.

Пусть требуется определить экстремум унимодальной функции Q (u) на отрезке [a, b] с точностью Д. Отрезок [a, b] делится пополам и вычисляются значения функции Q (x1) = F1 и Q (x2) = F2 в точках .

На основе анализа значений F1 и F2 вдвое уменьшается интервал неопределенности и процесс повторяется пока b - a > Д.

Рисунок 3 Метод половинного деления: геометрическая интерпретация



3.7 Метод «золотого сечения»

Гораздо эффективнее, с точки зрения уменьшения затрат на вычисления, метод "золотого сечения": интервал неопределенности делится не пополам, как в методе дихотомии, а в определенном иррациональном соотношении:

Метод заключается в том, что по заданным a и b как можно точнее определяется значение внутренней точки x1 (см. рис. 2.3, б) по формуле

Точка x2 определяется как точка, симметричная точке x1 на отрезке (a - b). На основе анализа значений F1 = Q (x1) и F2 = Q (x2) интервал неопределенности сокращается путем отбрасывания из рассмотрения отрезка в котором экстремум исключен, исходя из условий унимодальности Q (u).

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

Рисунок 4 Метод «золотого сечения»: а - золотое сечение; б - геометрическое представление

3.8 Метод Фебоначчи

Метод, использующий числа Фибоначчи, позволяет наиболее эффективно достичь заданной точности в поиске экстремума функции Q (u). Числа Фибоначчи определяются соотношением:

F₀ = F₁ = 1; F_k = F_k-₁ + F_k-_2; k = 2, 3, …

При большом "k" отношение соседних чисел Фибоначчи близко к отношению "золотого сечения". Этот метод делит интервал неопределенности не в постоянном соотношении, а в переменном и предполагает некоторое, вполне определенное, зависящее от Д, число вычислений значений функции Q (u).

По заданному Д определяется количество вычислений n и соответствующее ему число Фибоначчи F_n, исходя из соотношения:



3.9 Метод Гаусса-Зейделя

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

Проиллюстрируем сначала этот метод па примере решения системы

(3.9.1)

Предположим, что диагональные элементы а11, а22, а33отличны от нуля (в противном случае можно переставить уравнения). Выразим неизвестные х1, х2и х3 соответственно из первого, второго и третьего уравнений системы (3.9.1):

(3.9.2)

(3.9.3)

(3.9.4)

Зададим некоторые начальные (нулевые) приближения значений неизвестных: Подставляя эти значения в правую часть выражения (3.9.2), получаем новое (первое) приближение для х1:

Используя это значение для x1 и приближение для х3, находим из (3.9.3) первое приближение для х2:

И наконец, используя вычисленные значения находим с помощью выражения (3.9.4) первое приближение для х3:

На этом заканчивается первая итерация решения системы (3.9.2) - (3.9.4). Теперь с помощью значений х1(1), х2(1)их3(1)можно таким же способом провести вторую итерацию, в результате которой будут найдены вторые приближения к решению: х1 = х1 (2), х2 = х2(2)и х3 = х3(2)и т.д.

Приближение с номером kможно вычислить, зная приближение с номером k- 1, как

Итерационный процесс продолжается до тех пор, пока значения х1(k), х2(k)и х3(k)не станут близкими с заданной погрешностью к значениям х1(k-1), х2(k-1)и х3(k-1).



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

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

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

Метод "затраты - эффективность" также укладывается в схему нелинейного программирования.

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

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

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

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

Размещено на Allbest.ru