Semenalidery.com

IT Новости из мира ПК
0 просмотров
Рейтинг статьи
1 звезда2 звезды3 звезды4 звезды5 звезд
Загрузка...

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

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

Большинство существующих методов в нелинейном программировании можно разделить на два больших класса:

  1. Прямые методы — методы непосредственного решения исходной задачи. Прямые методы порождают последовательность точек – решений, удовлетворяющих ограничениям, обеспечивающим монотонное убывание целевой функции.
    Недостаток: трудно получить свойство глобальной сходимости.
    Задачи с ограничениями в виде равенств.
    Метод замены переменных (МЗП)
  2. Двойственные методы — методы, использующие понятие двойственности. В этом случае легко получить глобальную сходимость.
    Недостаток: не дают решения исходной задачи в ходе решения – оно реализуемо лишь в конце итерационного процесса.
    • Метод множителей Лагранжа (ММЛ)
    • Методы штрафов
    • Метод множителей
    • Методы линеаризации для задач условной оптимизации
      Алгоритм Франка–Вульфа
      Метод допустимых направлений Зойтендейка
    • Метод условного градиента
    • Метод проекции градиента
    • Сепарабельное программирование.
    • Квадратичное программирование

Методы поиска нулей функции

  1. Метод Ньютона (Метод касательных)
  2. Метод хорд
  3. Комбинированный метод
  4. Метод итераций
  5. Метод секущих

Методы минимизации функций

Функция одной переменной

Функция двух переменных

  1. Матрица Гессе. . Позволяет ответить на вопрос является ли функция выпуклой или вогнутой, а также определить тип экстремума (минимум или максимум).
  2. Производные второго порядка
  3. Экстремум функции двух переменных.

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

  1. Метод Хука–Дживса
  2. Метод сопряженных направлений (метод Пауэлла). Найти минимум целевой функции методом сопряженных направлений: f(x)=3x1 – x1 3 + 3x2 2 + 4x2. x 0 =(0.78;1)

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

  1. Метод наискорейшего спуска (метод Коши).
  2. Метод Ньютона
  3. Метод Марквардта. Найти минимум функции: y=x1 2 +4x2 2 +x1x2+1-5x2 методом Марквардта с начальной точкой (10;10) и εxy= ε|f(x)|=0.5. Предельное число итераций равно M=5.
  4. Метод сопряженных градиентов (метод Флетчера-Ривса).
  5. Метод Бройдена–Флетчера–Гольдфарба–Шанно (квазиньютоновские методы).

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

Прямые методы

  1. Метод множителей Лагранжа. В задачах 301-320 используя метод множителей Лагранжа найти точки экстремума функции z=f(x,y) при заданном условии: z=xy+7x , 2x+y=1
  2. Условия Куна-Таккера.

Метод проекции градиента.
Метод условного градиента.

Методы линеаризации для задач условной оптимизации

Методы перебора применимы для отыскания экстремумов унимодальных целевых функций. Действие любого из методов поиска заключается в сужении области поиска экстремума (длины l 0):
а) до области заданной длины (e> 0), проводя минимальное число измерений значений функции (методы дихотомии, золотого сечения);
б) до наименьших возможных размеров ln при заданном числе измерений n (метод Фибоначчи).
Первая формулировка целесообразна в том случае, если с каждым измерением связаны значительные затраты средств или времени, однако на поиск отпускаются неограниченные средства, которые мы все же стремимся минимизировать; вторая – когда исследователь располагает ограниченными средствами и, зная расходы, связанные с каждым измерением, стремится получить наилучший результат.

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

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

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

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

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

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

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

Размещено на 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 Цели, задачи и актуальность методов нелинейного программирования

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

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

Читать еще:  Язык программирования matlab

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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].

Читать еще:  Ноутбук dexp безопасный режим

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

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

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

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

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

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

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

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

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

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

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

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

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

Читать еще:  Линейное программирование геометрическим методом

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

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

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

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

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

∂F(xk)

∂ x1

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ссылка на основную публикацию
Adblock
detector