Модели нелинейного программирования в управленческих решениях.

Курсовая работа. Модели нелинейного программирования в управленческих решениях. ...

Введение 2
1. Экономико-математический аппарат и его роль в обосновании управленческих решений 5
1.1 Цели, задачи и актуальность методов нелинейного программирования 5
1.1.1 Специфика нелинейных программ и методы их решения 6
2. История разработки основных методов нелинейного программирования 7
3. Основные методы нелинейного программирования 10
3.1 Градиентные методы 10
3.2 Методы Монте-Карло 11
3.3 Методы выпуклого программирования. Метод множителей Лагранжа. 12
3.3.1 Теорема Куна-Таккера. 13
3.4 Дробно-линейное программирование. 15
3.5 Метод прямого сканирования. 16
3.6 Метод половинного деления. 16
3.7 Метод «золотого сечения». 17
3.8 Метод Фебоначчи. 17
4. Области применения методов нелинейного программирования 19
Заключение. 21
Список литературы: 22

Цели. Субъект управления (будь то индивид или группа) принимает решение исходя не из своих собственных потребностей, а в целях решения проблем конкретной организации.
• Последствия. Частный выбор индивида сказывается на его собственной жизни и может повлиять на немногих близких ему людей. Менеджер, особенно высокого ранга , выбирает направление действий не только для себя , но и для организации в целом и её работников, и его решения могут существенно повлиять на жизнь многих людей. Если организация велика и влиятельна, решения её руководителей могут серьёзно отразиться на социально – экономической ситуации целых регионов. Например, решение закрыть нерентабельное предприятие компании может существенно повысить уровень безработицы.

Поэтому возникают отделы: производственный, отдел сбыта, финансовый, отдел кадров и пр. Эти отделы имеют разные цели функционирования, во многом взаимно противоположные.Производственный отдел хочет, чтобы продукция была однообразной (мало номенклатуры), и, если даже нет сбыта, этот отдел хочет производить продукцию, его цель - как можно больше продукции узкой номенклатуры (чтобы не перенастраивать станки для удешевления продукции).Отдел сбыта требует широкой номенклатуры продукции (чтобы было легче продать), чтобы были товары, даже редко пользующиеся спросом (они могут понадобиться все равно). Поэтому этот отдел не возражает против запасов (если и производства нет).Однако, финансовый отдел выступает против запасов, так как это связанные деньги, и его задача минимизировать эти связанные деньги (т.е. деньги в товаре), а это значит минимизировать запасы. Финансовый отдел требует сохранения производства даже, если не идет продажа товара.Отдел кадров против сохранения производства, если продажа товара не идет, так как это связано с увольнением людей, что является очень неприятной процедурой.Задача отдела исследования заключается в том, чтобы найти правильное решение, которое принесет пользу (выгоду) всей системе в целом (всей фирме в целом), а не отдельным его подразделениям.Таким образом, исследование операций связано с организацией, управлением системами, т.е. с исследованием оказания влияния на системы с точки зрения повышения их эффективности.Наука, которая занимается управлением, называется кибернетикой. Теория операций - часть кибернетики. Иногда ее называют операционной кибернетикой. Теория операций имеет синонимы: теория принятия решений, анализ операций, оценка операций, исследование операций, теория системной оценки, теория системных исследований, теория организационного управления. Наиболее часто используют названия теория операций, теория оптимальных решений, теория принятия решений.Задачи этой теории можно разделить на классы: поисковые, распределенные, управления запасами, массового обслуживания, календарного планирования, состязательные задачи.Таблица 1.Классы задач и методы их решенияКлассы задачМетоды решенияПоисковыеНелинейное программированиеРаспределенныеЛинейное программированияУправление запасамиТеория управления запасамиМассовое обслуживаниеТеория массового обслуживанияКалендарное планированиеТеория расписанияСостязательные задачиТеория игр3. Основные методы нелинейного программирования3.1 Градиентные методыГрадиентные методы, в основе которых лежит свойство градиента функции в точке (вектора частных производных, вычисленного в точке) как указателя направления наибольшего роста функции в окрестности точки.Так при отсутствии ограничений одна из простейших разновидностей градиентных методов - метод наискорейшего спуска предлагает выбрать некоторую точку (план) Xk и начальный шаг Hk, вычислить градиент функции в выбранной точке grad F(Xk) и осуществить переход по градиенту (при максимизации) с выбранным шагом. Если значение функции в новой точке больше предыдущего, новая точка принимается за исходную и повторяется такая же процедура. При попадании в точку с меньшим значением уменьшается шаг (например, вдвое) и переход повторяется от исходной точки. Переходы продолжаются до достаточно малого шага.Например, если нужно решить систему уравнений(X2+1)(Y-1)=3,Y=ln(X+1),то можно заменить эту задачу задачей минимизации функции F(X,Y)=[(X2+1)(Y-2)-3]2+[Y-ln(X+1)]2 (если система имеет решение, то искомый минимум равен нулю).Градиент этой функции определяется векторомGrad F(X,Y) = {2[(X2+1)(Y-2)-3] 2X (Y-2) - 2[Y-ln(X+1)]/(X+1), 2 [(X2+1)(Y-2)-3](X2+1) - 2[Y-ln(X+1)]}.Выбираем начальную точку M0(2,1) и шаг h=1.Здесь значение функции F(M0)=64, градиент в этой точке grad F(M0) =[ 64.066, -80.197], нормированный градиент (вектор единичной длины, составленный из компонент, деленных на корень из суммы их квадратов) gradн F(M0) = [0.62, -0.78]. Смещаемся в направлении, обратном градиенту (ищем минимум), с выбранным шагом в точку М1=М0-h gradн F(M0)=(2-1 0.62, 1+1 0.78)=(1.38, 1.78) и обнаруживаем, что F(M1)=14 < F(M0).Аналогичный переход с учетом 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(X1, X2,..,Xn) = f1(X1) + f2(X2) +... + fn(Xn).При решении многих задач нелинейного программирования определенный эффект дает метод множителей Лагранжа.Пусть требуется найти экстремумы функции F(X) при условиях fi(X)=0 (i = 1.. m).Функция называется функцией Лагранжа и коэффициенты ?i - множителями Лагранжа.Можно доказать, что необходимым условием экстремума исходной задачи является обращение в нуль всех частных производных функции Лагранжа.Например, при поиске максимума F(X1, X2) = X1+X2 при единственном условии X12+X22=1 строится функция ЛагранжаСтроим систему уравнений решение которой дает и экстремальные значения целевой функции.Для определения типа найденного экстремума можно построить матрицу вторых производных F(X), вычисленных в экстремальной точке, и определить знаки главных ее миноров. Если все они положительны, то найден минимум; если они чередуются, начиная с минуса, то найден максимум (правило Сильвестра).Сам по себе метод множителей Лагранжа не дает существенного эффекта из-за необходимости решать, как правило, нелинейную систему уравнений; не гарантирует тип отыскиваемого экстремума, кроме глобальных дает и множество локальных экстремумов, но полезен при генерации идей и создании методов нелинейного программирования.3.3.1 Теорема Куна-Таккера.Пусть задача нелинейного программирования имеет вид:Для решения поставленной задачи используется центральная теорема математического программирования - теорема Куна-Таккера, выдвигающая необходимые условия существования решения задачи нелинейного программирования. Достаточные условия существования решения формулируются в теоремах Куна-Таккера второго, третьего и т.д. порядках и в данном курсе не рассматриваются.Теорема (Куна-Таккера) Точка может являться решением задачи нелинейного программирования только в том случае, если в ней выполнены следующие условия:1) ;2);3) , .Пример Найти наибольшее и наименьшее значения функции при заданных ограничениях при ограничениях и .Решение. Запишем ограничения в стандартном видеПервое условие теоремы Куна-Таккера позволяет записать два уравнения:,.Второе условие теоремы позволяет записать еще два уравнения: , .Подставляя в них функции и вычислив производные, получаем систему из 4 уравнений с 4 неизвестными:Рассмотрим несколько ветвей решения системы уравнений:1) 2) .Вторая система распадается на два случая:2а) ; 2б) ;3) ;4) , Эта система распадается на две4а) ; 4б) .После того как система решена результаты собираются в таблицу:Таблица 2Результаты системы, через теорему Куна-ТаккераРхуfР1000-Р201-100Р3000-10Р410-1-21Р5-10-1-21Предварительно убеждаемся, что все точки принадлежат допустимому множеству. Подставляя их координаты в ограничения-неравенства и видя, что они остаются истинными, рассчитываем значение целевой функции в каждой из них. Кроме того, убеждаемся, что третье условие теоремы Куна-Таккера также выполнено во всех точках. Сравнивая значение целевой функции в каждой из найденных точек, видим, что наибольшее значение функции 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).Установим, как будет вести себя угловой коэффициент k при монотонном возрастании L. Найдем производную от k по L:Знаменатель производной всегда положителен, а числитель от L не зависит. Следовательно, производная имеет постоянный знак и при увеличении L угловой коэффициент будет только возрастать или только убывать, а прямая будет поворачиваться в одну сторону. Если угловой коэффициент прямой имеет положительное значение, то прямая вращается против часовой стрелки, при отрицательном значении k -- по часовой стрелке. Установив направление вращения, находим вершину или вершины многогранника, в которых функция принимает max(min) значение, либо устанавливаем неограниченность задачи.3.5 Метод прямого сканирования.Задача заключается в локализации экстремума функции одной переменной, заданной на интервале [a, b] с точностью до Д. При решении этой задачи весь интервал разбивается на участки величиной Д.