1612726855-66ce2678ed92310585f0bb1a36623206 (Алексеева, Кутненко - Учебное пособие)

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИНОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТЕ. В. Алексеева, О. А. Кутненко, А. В. ПлясуновЧИСЛЕННЫЕ МЕТОДЫ ОПТИМИЗАЦИИУчебное пособиеНовосибирск, 2008УДК 519.6ББК В.173.1/2Алексеева Е. В., Кутненко О. А., Плясунов А. В. Численные методыоптимизации: Учеб. пособие / Новосиб. ун-т. Новосибирск, 2008. 128 с.Учебное пособие написано на основе лекций, которые читались на факультете информационных технологий и механико-математическом факультете Новосибирского государственного университета. В нем подробнорассмотрены классические методы решения задач математического программирования.Пособие предназначено для студентов механико-математического факультета, факультета информационных технологий, а также для всех, ктожелает освоить рассматриваемые методы самостоятельно.Пособие разработано в рамках национального проекта «Образование» вНГУ.Рецензентыдоктор физико-математических наук, профессор Э.

Х. Гимадидоктор физико-математических наук, профессор А. А. Колоколов© Новосибирский государственный университет, 2008ВВЕДЕНИЕУчебное пособие написано на основе лекций по курсу «Методыоптимизации», читаемых на факультете информационных технологийНовосибирского государственного университета. Основной акцент сделан наизложении методов решения задач математического программирования, атакже обосновании их сходимости или конечности в зависимости отрассматриваемого класса задач. Такой подход может оказаться полезным присамостоятельномизучениичисленныхметодовоптимизации.Предполагается, что читатели знакомы с курсами математического анализа илинейной алгебры.Данное издание является продолжением и дополнением ранееопубликованных пособий [1], [2]. В нем представлены задачи классическоговариационного исчисления и оптимального управления. Эти темы изложены втом варианте, в котором они читаются в течение ряда лет на механикоматематическом факультете и факультете информационных технологийуниверситета.

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

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

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

Ссылки в пределах главы обозначаются одним числом, авне главы – двумя числами. Например, теорема 5 из первой главы будет вдругих главах именоваться как теорема 1.5.4ГЛАВА 1ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ И ОБОЗНАЧЕНИЯ§ 1. Экстремальные задачи. ОпределенияЗадачи отыскания наибольших или наименьших величин часто возникаютв науке, технике и экономике. Чтобы применять математические методы дляих решения и анализа, необходимо уметь переходить от содержательной кматематической постановке задачи. Для этого нужно определить целевуюфункцию f , множество допустимых решений Q для функции f и критерийоптимизации extr Î{min, max} . Таким образом, тройка вида ( f , Q, extr ) задает экстремальную или оптимизационную задачу.Формально математическая постановка выглядит следующим образом:f ( x) ® extr .xÎQУчитывая равенство min f ( x ) = - max(- f ( x)) , в дальнейшем ограничимсяxÎQxÎQрассмотрением только задач минимизации.Будем говорить, что задача минимизации решена, если1. либо найдено ее оптимальное решение, то есть точка x * Î Q такая, чтоf ( x * ) £ f ( x ) для всех x Î Q .

Символически это записывается в виде равен-ства f ( x * ) = min f ( x ) ;xÎQ2. либо найден конечный инфинум f * = min f ( x ) целевой функции наxÎQмножестве Q в случае, когда оптимального решения не существует;3. либо доказано, что целевая функция неограниченна снизу на множестведопустимых решений;4. либо установлено, что множество допустимых решений пусто.Далее будем рассматривать экстремальные задачи, в которых допустимоемножество задается в следующем виде: Q = {x Î S | ji ( x ) £ 0, i = 1,K, m} , гдеS является либо подмножеством пространства R n , либо подмножеством Z n ,либо – B n . Функции ji (x) , i = 1, K , m , – скалярные функции со значениями вR . Выражения x Î S , ji ( x ) £ 0 , i = 1, K , m , называются ограничениями оптимизационной задачи. Ограничения вида ji ( x ) £ 0 , i = 1, K , m , называютсяфункциональными, а ограничение x Î S называется ограничением типавключения.

Различие между функциональными и нефункциональными ограничениями условно, так как каждое включение можно записать как функциональное ограничение и, наоборот, любое функциональное ограничение легкопревратить во включение. Одновременное использование этих ограничений5делает постановку задачи более структурированной и, следовательно, болеенаглядной. Формально экстремальная задача в этом случае записывается вследующем виде:(1)f ( x) ® minxÎSji ( x ) £ 0, i = 1,K, m .(2)В зависимости от природы множества S экстремальные задачи классифицируются как [2, 4, 6, 9]:· дискретные или комбинаторные, если множество S конечно илисчетно;·целочисленные, если S Í Z n ;·булевы, если S Í B n ;··вещественные, если S Í R n ;бесконечномерные, если S – подмножество гильбертова пространства.Если S = R n , или S = Z n , или S = B n и отсутствуют ограниченияji ( x ) £ 0, i = 1,K, m , то есть m = 0 , тогда экстремальная задача называетсязадачей безусловной оптимизации.

В противном случае говорят о задаче условной оптимизации.Если принять во внимание свойства целевой функции f и ограниченийji ( x ) £ 0, i = 1,K, m , то возникает более тонкое деление конечномерных экстремальных задач на классы:·непрерывное (математическое) программирование ( f , ji (x) ,i= 1, K , m , – непрерывные, произвольные, нелинейные функции, S –·связное, компактное подмножество R n );дискретное (математическое) программирование ( f , ji (x) ,=i 1, K , m , – нелинейные функции, S – дискретное множество);нелинейное целочисленное программирование ( f , ji (x) , i = 1, K , m ,·– нелинейные функции, S Í Z n );непрерывная нелинейная оптимизация без ограничений ( f – непре-·рывная, произвольная, нелинейная функция, m = 0 , S = R n );целочисленная нелинейная оптимизация без ограничений ( f – про-··извольная, нелинейная функция, m = 0 , S = Z n );выпуклое программирование ( f , ji (x) , i = 1, K , m , – произвольные,выпуклые функции, S – выпуклое подмножество R n );6··линейное программирование ( f , ji (x) , i = 1, K , m , – произвольные,линейные функции, S = R n );целочисленное линейное программирование ( f , ji (x) , i = 1, K , m , –произвольные, линейные функции, S Í Z n ).При решении каждой оптимизационной задачи возникает три проблемы[4].

Первая из них связана с существованием оптимальных решений задачи.При анализе этой проблемы в ряде случаев может оказаться полезной следующая теорема, с помощью которой можно иногда определить, достигает лифункция своего глобального минимума и максимума.Теорема 1 (Вейерштрасса). Если функция f (x ) определена и непрерывнана замкнутом ограниченном множестве X , то она достигает на этом множестве своих точных верхней и нижней границ.Условие компактности множества X , использованное в теореме, являетсядовольно жестким. И неприменимо для таких часто встречающихся множеств, как S = R n или S = R³n . Однако, ослабляя ограничения на множествоX и накладывая дополнительные требования на функцию f , из теоремыВейерштрасса можно получить следующие два следствия.Следствие 1.