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

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

Министерство образования и науки РФ

Федеральное государственное автономное образовательное учреждение высшего образования

«Нижегородский государственный университет им. Н. И. Лобачевского»

Дзержинский филиал

Направление подготовки «Государственное и муниципальное управление»

Курсовая работа

по дисциплине «Основы математического регулирования»

на тему: «Задачи и методы нелинейного программирования»

Выполнил: студент 2 курса заочной формы обучения (гр. 3-Б22 ГМУ/20)

Рябов Игорь Олегович

Проверил: проф. Павленков М.Н

г. Дзержинск

2014

Содержание

Введение

Глава 1. Нелинейное программирование

1.1 Задачи нелинейного программирования

1.2 Общая формулировка нелинейных задач

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

Глава 2. Решение задач

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

2.2 Критерии оптимальности в задачах с ограничениями

2.3 Решение задачи

Заключение

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

Введение

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

Глава 1. Нелинейное программирование

1.1 Задачи нелинейного программирования

программирование оптимальность неравенство нелинейный

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

В самом общем виде классификация представлена в таблице.

Общих способов решения, аналогичных симплекс-методу линейного программирования, для нелинейного программирования не существует.

В каждом конкретном случае способ выбирается в зависимости от вида функции F(x).

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

1.2 Общая формулировка нелинейных задач

Найти переменныех1, х2, …, хn, удовлетворяющие системе уравнений

Ш ( х1, х2, …, хn) = bi, i = 1, 2, …, m

и обращающие в максимум ( минимум ) целевую функцию

Z = f ( х1, х2, …, хn)

Примером типичной и простой нелинейной задачи является следующая:

Данное предприятие для производства какого-то продукта расходует два средства в количествех1их2соответственно. Это факторы производства, например, машины и труд, два различных сырья и т.п., а величиных1их2- затраты факторов производства. Факторы производства впредь будем считать взаимозаменяемыми. Если это «труд» и «машины», то можно применять такие методы производства, при которых величина затрат машин в сопоставлении с величиной затрат труда оказывается больше или меньше (производство более или менее трудоемкое). Объем производства (выраженный в натуральных или стоимостных единицах) является функцией затрат производства Z = f ( х1, х2). Эта зависимость называется производственной функцией. Издержки зависят от расхода обоих факторов (х1их2) и от цен этих факторов (c1иc2). Совокупные издержки выражаются формулой b = c1х1+ c2х2. Требуется при данных совокупных издержках определить такое количество факторов производства, которое максимизирует объем продукции Z.

Математическая модель этой задачи имеет вид: определить такие переменныех1их2, удовлетворяющие условиям

c1х1+ c2х2= b

х1? 0, х2? 0,

при которых функция

Z = f (х1, х2)

достигает максимума. Как правило, функция может иметь произвольный нелинейный вид. Использую классические методы оптимизации, следует четко представлять себе различие между локальным экстремумом функции, глобальным экстремумом и условным экстремумом. Понятие условного экстремума вводится для случая, когда число переменных n не меньше2 (n ? 2). Будем полагать, что функция Z = f ( х1, х2, …, хn) = f (X)дважды дифференцируема в точке Х* = (х1*, х2*, …, хn* ),(Х* € D(f))и в некоторой ее окрестности.

Если для всех точек Х этой окрестности f (X*) ? f (X) или f (X*) ? f (X), то говорят, что функция f (X)имеет экстремум в X*(соответственно максимум или минимум). Точка X*, в которой все частные производные функции Z = f (Х)равны 0, называется стационарной точкой. Необходимое условие экстремума.

Если в точке X* функция Z = f (Х)имеет экстремум, то частные производные функции в этой точке равны 0:

f 'x1(X*) = 0, i = 1, 2, ..., n.

Следовательно, точки экстремума функции Z = f (Х)удовлетворяют системе уравнений:

Для получения достаточных условий следует определить в стационарной точке знак дифференциала второго порядка. Дифференциала второго порядка обозначаетсяd2f (х1, х2, …, хn) f 'x1(X)найти частную производную по переменной хj, то получим частную производную второго порядка по переменным хi, хj, которая обозначается f ''xi, xj(X). В этом случае

Достаточные условия экстремума.

Двух переменных:

если Д > 0иа11< 0 (а22< 0), то в точкеХ0функция имеет максимум:

если Д > 0иа11> 0 (а22> 0),то в точкеХ0- минимум (в этих случаяхХ0= Х*);

если Д < 0, то экстремума нет;

если Д = 0, то вопрос об экстремуме остается открытым.

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

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

Ниже рассматривается вопрос анализа «в динамике» для функций нескольких переменных, т. е. исследуются методы и алгоритмы, позволяющие на итерационной основе получать оценки х*-- вектора управляемых переменных, которому соответствует минимальное значение функции f(x). Указанные методы применимы также к задачам максимизации, в которых целевую функцию следует заменить на -f(х). Методы, ориентированные на решение задач безусловной оптимизации, можно разделить на три широких класса в соответствии с типом используемой при реализации того или иного метода информации.

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

2. Градиентные методы, в которых используются точные значения первых производных f(x).

3. Методы второго порядка, в которых наряду с первыми производными используются также вторые производные функции f(x).

Метод поиска по симплексу(S2-метод)

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

Метод поиска Хука-Дживса

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

Исследующий поиск.

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

Поиск по образцу.

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

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

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

Глава 2. Решение задач

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

Решить задачу нелинейного программирования- это значит найти такие значения управляющих переменных xj, j=1, n, которые удовлетворяют системе ограничений и доставляют максимум или минимум функции f.

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

hi(x)? 0, i=1,2,…,m (1)

а переменные x(j), т.е. компоненты вектора х, неотрицательны:

x(j)? 0 (2)

Иногда в формулировке задачи ограничения (1) имеют противоположные знаки неравенств. Учитывая, однако, что если hi(x)? 0 , то -hi(x)? 0 , всегда можно свести задачу к неравенствам одного знака. Если некоторые ограничения входят в задачу со знаком равенства, например ц(x) = 0, то их можно представить в виде пары неравенств ц(x)? 0, -ц(x)? 0, сохранив тем самым типовую формулировку задачи.

2.2 Критерии оптимальности в задачах с ограничениями

Ряд инженерных задач связан с оптимизацией при наличии некоторого количества ограничений на управляемые переменные. Такие ограничения существенно уменьшают размеры области, в которой проводится поиск оптимума. На первый взгляд может показаться, что уменьшение размеров допустимой области должно упростить процедуру поиска оптимума. Между тем, напротив, процесс оптимизации становится более сложным, поскольку установленные выше критерии оптимальности нельзя использовать при наличии ограничений. При этом может нарушаться даже основное условие, в соответствии с которым оптимум должен достигаться в стационарной точке, характеризующейся нулевым градиентом. Например, безусловный минимум функции имеет место в стационарной точке х=2. Но если задача минимизации решается с учетом ограничения, то будет найден условный минимум, которому соответствует точка x=4. Эта точка не является стационарной точкой функции f, так как(4)=4. Далее исследуются необходимые и достаточные условия оптимальности решений задач с ограничениями. Изложение начинается с рассмотрения задач оптимизации, которые содержат только ограничения в виде равенств.

2.3 Решение задачи

На предприятии имеется два вида ресурсов. Определите оптимальное распределение величин затрачиваемых ресурсов на производство некоторого продукта, если цена ресурса первого вида 3 единицы, второго - 4 единицы, а всего на производство выделено 24 единицы. Известно, что из количества х первого ресурса и у второго ресурса можно получить х у 2 2 + единиц продукта.

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

Множество допустимых решений заштриховано на рис. 1. Если целевой функции придавать фиксированные значения 1, 2, 3,..., то будем получать окружности с центром в начале координат и радиусом 1, 2, 3, … Начертим ряд окружностей (линии уровня целевой функции). Из рисунка видно, что функция z = х у 2 2 + достигает наибольшего значения, равного 8, в точке А (8;0), т.е. zmax=z (8;0)=8. Значит, количество первого ресурса должно равняться 8, а использование второго ресурса нерационально.

Заключение

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

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

Список литературы

1. Высшая Математика, ТВ и МС, Мат. Методы «Математические методы Попова Н.В».

2. «Нелинейное программирование в современных задачах оптимизации». Министерство образования и науки Российской федерации Национальный исследовательский ядерный университет «МИФИ». Москва 2011 г.

3. Методы условной оптимизации: Рек.к выполнению лаб. и практ. раб. Шипилов С.А: 2-еКемГУ.-2-е изд. перераб.- Новокузнецк.2002 г.

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