Ф.П. Васильев - Методы оптимизации (2002), страница 2

В. Арутюнову. В главе 3 дано простое обоснование антициклина ($3), теория двоиственности в линейном программировании изложена, опираясь лишь на симплекс- метод ($5). Приведено элементарное доказательство принципа максимума ПРЕДИСЛОВИЕ Понтрягина для весьма общей задачи оптимального управления, включая задачи с фазовыми ограничениями ($9 3, 4 главы 6). Часть текста, которая содержит материал, дополняющий и расширяющии основное содержание книги, напечатана петитом и при первом чтении может быть опущена.

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

Нумерация формул, теорем, лемм, определений, упражнений в каждом параграфе самостоятельнаяссылки на материалы, расположенные в пределах данного параграфа, нумеруются одним числом, вне данного параграфа,' но в пределах данной главы — двумя числами, вне данной главы' — тремя числами. Так, например, теорема 3 из 9 2 главы 4 в пределах этого параграфа именуется просто теоремой 3, в других параграфах 4-й главы— теоремой 2.3, в других главах — теоремой 4.2.3. Аналогично параграфы при ссылках на них в пределах данной главы, нумеруются одним числом, а вне этой главы — двумя числами; первое число означает номер главы',, второе— номер параграфа. Работа по подготовке.

настоящей книги к изданию не могла бы быть выполнена без помощи многих моих, коллег и читателей. Автор глубоко признателен А. С. Антипину, А. В. Арутюнов, Е. Г. Бедо сову, Н. А. Бобылеву, Н. Л. Григоренко, М. И. Зеликину, Л. Ф. Зеликнной, А. Ф. Измаилову, А, С. Ильинскому, Х. Д, Икрамову, А,. 3. Ишмухаметову, М. Йовановичу, А. С. Леонову, А. Недич, М. С. Никольскому, О.' Обрадовичу 'Н, М: Попову, М. М.

Потапову, А. В. Разгулнну,'В, А. Срочко, А. А. Станевичюсу, М.Ф. Сухинину, А. В. Тимохову,'В, В.Федорову,' А; А. Шананину, В. Янковичу, В. Ячимовичу, М, Ячимовнчу, которые своими советами, предложениями, замечаниями способствовали улучшенйю содержания'книги. Особенно благодарен А. В. Арутюнову, без помощи которого' автор не смог бы написать Я 2.4, 6,16, 6.4 в их настоящем виде, А, 3; Ишмухаметову за помощь при написании $10.7. В столь бурно развивающейся области, как теория и методы решения, экстремальных задач, очень трудно создать учебное пособие, которое' обладало бы определенной завершенностью и было бы свободным от недостатков, и поэтому автор будет признателен читателям за критические замечания по содержанию книги. Ф.,П.

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

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

Работы, посвященные но. вым метадам минимизации функций одной переменной, продолжают появляться на страницах математических книг и журналов. Мы здесь остановимся на некоторых наиболее известных методах, достаточно хорошо проявивших себя на практике. Другие методы минимизации функций одной переменной читатель найдет, например, в 176; 148; 193; 214; 257; 590; 662; 671; 681; 684; 709; 738; 7551.

й 1. Постановка задачи Пусть К = (х: — оо < х < со) — числовая ось, Х вЂ” некоторое множество из К, /(х) — функция, определенная на множестве Х и принимающая во всех точках х е Х конечные значения: Примерами множеств из К являются: отрезок (а, Ь1= (х Е И: а < х < Ь), интервал (а, Ь) = (х Е К: а < х < Ь), полуинтервалы (а, Ь) = (х е К: а < х < Ь), (а, Ь'1 = (х 6 И: а < х < Ь), где а, Ь вЂ” заданные числа.

Будем рассматривать задачу минимизации функции /(х) на множестве Х. Начнем с того, что уточним постановку этой задачи, Для этого сначала напомним некоторые определения из классического математического анализа. О пределе ние 1. Точку х. е Х называют точкой минимума функции /(х) на множестве Х, если /(х„) < /(х) для всех х е Х; величину /(х,) называют наименьшим или минимальным значением /(х) на Х и обозначают ш1п/(х) =/(х,). Множество всех точек минимума /(х) на Х будем чах обозначать через Х,. В зависимости от свойств множества Х и функции /(х) множество Х, может содержать одну, несколько или даже бесконечно много точек, а также возможны случаи, когда Х„пусто. П р и м е р 1.

Пусть |(х) = зйп'(я/х) при х 540 н /(0) =О. На множестве Х = (х: 1 < х < 2) минимальное значение /(х) равно нулю, множество Х„ состоит из единственной точки х, = 1. Если Х = (х: 1/3 < х < Ц, то Х, содержит три точки: 1/3, 1/2, 1; если Х = (х; 0 < х < 17, то Х, = (х: х = 1/ть,п = 1, 2,...) — счетное множество. В случае Х = (х: 2 < х < оо), 10 Гк !. МЕТОДЫ МИНИМИЗАЦИИ ФУНКЦИЙ ОДНОЙ ПЕРЕМЕННОЙ $1. ПОСТАНОВКА ЗАДАЧИ функция 1'(х) не имеет наименьшего значения на Х.

В самом деле, какую бы точку хе Х ни взять, найдется точка е е Х (например, е = к при достаточно большом к) такая, что 1,(х) > !'(о). Это значит, что Х„пусто. Пример 2. Функция г(х) = !х)+ !х — 1( — 1 на Х =(х: !х) < 1) принимает свое наименьшее значение, равное нулю, но всех точках отрезка Х„= (х: 0 < х < 1). Если Х = (х: 1 < х < 2), то Х, содержит одну точку х,=1; если Х =(х: 1 <х <21, то Х,=И. Пример 3.

Пусть г"(х)=х при х~О и г"(0)=1. На множествах Х=(х: 0<х<1) или Х=(х: 0<х<1~ эта функция не имеетнаименьшего значения, т. е. Х„=И. Пример 4. Пусть г"(х) =1п х, Х =(х: О< х < Ц. Здесь Х„=о, так как во всех точках из Х функция принимает конечные значения, а для последовательности х, = 1/к (к = 1, 2...) имеем 1!ш Т(х,) = †.

ь Определение 2. Функция г(х) называется ограниченной снизу на множестве Х, если существует такое число М, что У(х) > М для всех х Е Х. Функция у(х) не ограничена снизу на Х, если существует последовательность (х,) Е Х, для которой !пп ~(х„) = -оо.

В примерах 1-3 функции ограничены снизу на рассматриваемых множествах, а в примере 4 функция не ограничена, В тех случаях, когда Х, =О, естественным обобщением понятия наименьшего значения функции является понятие нижней грани функции. Определение 3. Пусть функция Ях) ограничена снизу на множестве Х. Тогда число Т, называют нижней гранью 1(х) на Х, если: 1) ~„< Г'(х) при всех х Е Х; 2) для любого сколь угодно малого числа г > 0 найдется точка х, Е Х, для которой Г(х,) < Гч+ г.

Если функция Т(х) не ограничена снизу на Х, то в качестве ннжйей грани Г'(х) на Х принимается 1; = — со. Нижнюю грань г"(х) на Х обозначают через !п1 Г'(х) = ~„. мчх В примерах 1 — 3 ~„= О, а в примере 4 Х„= — оо. Если Х, ~!2!, то, очевидно, нижняя грань г"(х) на Х совпадает с наименьшим значением этой функции на Х, т. е. !п1 г"(х) = ппп Т(х). В этом ФчХ *чХ случае говорят, что функция !'(х) на Х достигает своей нижней грани. Подчеркнем, что !п1 г"(х) = 1'„всегда существует, а ппп Т(х), как мы видели из мчх чХ примеров 1 — 4, не всегда имеет смысл.

Введем еще два определения. О п р е д е л е н и е 4. Последовательность (Г(х.)1 е Х называется минимизируюшгй для функции Т(х) на множестве Х, если 1пп г(х„) = !п1 г(х) = Т,. Из определения и существования нижней грани следует, что минимизирующая последовательность всегда существует. О и р е д е л е н и е 5.

Скажем, что последовательность 4х 1 сходится к непустому множеству Х, если 11ш р(х„, Х) = О, где р(хю Х) = !и! !х„— ь ~ю кчХ вЂ” х~ — расстояние от точки х„до множества Х. Заметим, что если Х„ф О, то всегда существует минимизирующая последовательность, сходящаяся к Х„' например, можно взять стационарную последовательность х„= х, (к = 1, 2,...), где х, — какая-либо точка из Х,. Однако не следует думать, что при Х, ф Я любая минимизирующая последовательность будет сходиться к Х,. * х~ Пример 5, Пусть Т(х)=,, Х =К.

Очевидно, здесь А=О и ! ч хз множество Х„состоит из единственной точки х„=О. Последовательность х„= й (й = 1, 2,...) является минимизирующей, так как 1!ш У(х„) =О, но р(х„Х„) = й не стремится к нулю, Теперь перейдем к формулировке задачи минимизации функции 1(х) на множестве Х.

Здесь возможны различные подходы. Обычно принято различать задачи двух типов. К первому типу относят задачи, в которых требуется определить величину г'„= !п1 Т(х). Сразу же подчеркнем, что в задачах лчХ первого типа неважно, будет ли множество Х„точек минимума г(х) на Х непустым или оно пусто, Ко второму типу задач относят те задачи, у которых множество Х.