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

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ

РОССИЙСКОЙ ФЕДЕРАЦИИ

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

Методы оптимизации в примерах и задачах

Учебно-методическое пособие

Рекомендовано методической комиссией факультета вычислительной

математики и кибернетики для студентов ННГУ, обучающихся

по направлениям подготовки 010400 «Информационные технологии», 010500 «Прикладная математика и информатика» и по специальности 010501 «Прикладная математика и информатика»

Нижний Новгород 2010 УДК 531.38;531.39 ББК 32.81 М-54

М-54 МЕТОДЫ ОПТИМИЗАЦИИ В ПРИМЕРАХ И ЗАДАЧАХ

/ Авторы: Бирюков Р.С., Городецкий С.Ю., Григорьева С.А., Павлючонок З.Г., Савельев В.П. Учебно-методическое пособие. – Нижний Новгород: Нижегородский госуниверситет, 2010. – 101 с.

Рецензент: кандидат физ.-мат. наук, доцент А.В. Баркалов В издание включены теоретический материал и наборы задач по шести основным разделам курса "Методы оптимизации": динамическому программированию, элементам выпуклого анализа, теории условий оптимальности, численным методам математического программирования, вариационному исчислению и оптимальному управлению.

В начале каждого раздела приведены необходимые теоретические сведения и разобраны типовые примеры.

Ответственный за выпуск: председатель методической комиссии факультета ВМК ННГУ, д.ф.-м.н., проф. Л.П. Жильцова УДК 531.38;531. ББК 32. © Нижегородский государственный университет им. Н.И. Лобачевского, Оглавление 1. Динамическое программирование и метод рекуррентных уравнений Беллмана……………………………………………………………………………... 1.1. Детерминированные управляемые процессы, теория и примеры……………….. 1.2. Управляемые марковские процессы с доходами, теория и примеры…………... 1.3. Контрольные задания…………………………………………………………….... 2. Элементы выпуклого анализа………………………………………………….. 2.1. Базовые понятия и факты…………………………………………………………. 2.2. Контрольные задания…………………………………………………………….... 3. Условия оптимальности в задачах математического программирования…... 3.1. Теория и примеры…………………………………………………………………. 3.2. Контрольные задания……………………………………………………………… 4. Вычислительные методы математического программирования…………….. 4.1. Основные понятия…………………………………………………………………. 4.2. Поиск минимума унимодальной функции на отрезке…………………………... 4.3. Поиск минимума выпуклой дифференцируемой функции……………………... 4.4. Поиск локального минимума в задачах без ограничений………………………. 4.5. Вычислительные методы решения задач с ограничениями…………………….. 4.6. Методы липшицевой многоэкстремальной оптимизации………………………. 4.7. Контрольные задания……………………………………………………………… 5. Вариационное исчисление……………………………………………………… 5.1. Основные понятия…………………………………………………………………. 5.2. Простейшая задача с фиксированными концами и ее обобщения……………... 5.3. Задачи со скользящими концами…………………………………………………. 5.4. Вариационные задачи на условный экстремум………………………………….. 5.5. Контрольные задания……………………………………………………………… 6. Оптимальное управление……………………………………………………….. 6.1. Теория и примеры………………………………………………………………….. 6.2. Контрольные задания……………………………………………………………… Литература………………………………………………………………………… 1. Динамическое программирование и метод рекуррентных уравнений Беллмана теория и примеры При постановке задач динамического программирования используются понятия, характерные для теории динамических систем: «управляемая динамическая система» и «состояние» [1]. Напомним эти понятия.

Пусть имеется изменяющийся во времени объект, на который осуществляется внешнее воздействие u (t ), трактуемое как управление, а x(t ) – некоторое описание этого объекта в момент времени t. Если при известном управлении u ( ), ( [t, t ] ), зная описание x(t ) в момент времени t, можно однозначно определить его значение x (t ) для любого t > t, то такое описание называют полным. Полное описание называют состоянием, множество возможных состояний – пространством состояний. Сам объект, допускающий возможность полного описания, называют динамической системой.

Любая динамическая система предполагает наличие однозначного оператора F, позволяющего по x (t ) определить x (t ) для любого допустимого момента времени t > t. Поскольку для управляемой системы оператор F зависит от управления, должны быть заданы множества U их возможных значений, зависящие от текущего момента времени и текущего состояния.

Таким образом, динамическая система определяется следующим набором:

< X, T, F, U >, где X – пространство состояний, T – множество допустимых моментов времени.

Рассмотрим управляемую динамическую систему с дискретным временем, состояние которой в момент времени k описывается вектором xk R n, а закон изменения ее состояния определяется соотношением, задающим оператор динамической системы: xk +1 = f k +1 ( xk, u k +1 ). Управления u k +1 выбираются из множеств управлений, допустимых в текущий момент времени k для состояния xk, т.е. u k +1 U k +1 ( xk ) R m, где множества U k +1 ( xk ) заданы.

Будем рассматривать только такие задачи, в которых дискретное время k изменяется в заранее известных пределах: k = 0, 1,..., N 1, где N задано.

Известно, что x0 принадлежит заданному множеству начальных состояний X 0. Требуется также, чтобы конечное состояние x N принадлежало заданному множеству X N допустимых финальных состояний.

Каждому переходу из состояния xk в следующее состояние поставим в соответствие функцию затрат (или доходов) на текущем шаге d k +1 ( x k, u k +1 ), зависящую, кроме xk, также от момента времени и применяемого управления.

Требуется найти такое начальное состояние x0 X 0 и такой допустимый набор управлений u1,..., u *, переводящий систему в одно из состояний x* X N, чтобы общие затраты, являющиеся аддитивной функцией затрат на отдельных шагах, были минимальны.

Заметим, что исходные формулировки прикладных задач оптимизации часто не соответствуют приведенной выше стандартной постановке, хотя после соответствующего преобразования могут быть к ней приведены [2, 3]. Для их успешного решения методами динамического программирования часто необходимо искусственно переформулировать задачу так, чтобы она оказалась записанной через некоторый управляемый динамический процесс. В этом случае наиболее важно правильно ввести понятие состояния. Критерием правильности выбора является соблюдение нескольких требований: новое состояние, а также функция затрат могут зависеть только от предыдущего состояния, текущего управления и момента времени; ограничения на текущее управление могут зависеть только от предыдущего состояния и момента времени. Нарушение хотя бы одного из правил говорит о неправильном выборе состояния или управления.

Для решения задач динамического программирования используется подход, разработанный в лаборатории Р. Беллмана в 50 -х годах XX века [2, 4].

Согласно этому подходу, вместо исходной N -шаговой задачи нужно рассмотреть набор вспомогательных задач, подобных исходной, но включающих различное количество шагов (от 1 до N ). В этих задачах требуется определить оптимальные затраты: на одном последнем шаге, двух последних шагах, трех, и т.д. при условии, что считается известным состояние, в котором оказался управляемый динамический процесс перед выполнением этих завершающих шагов. Подход Р. Беллмана основан на том, что можно установить рекуррентную связь между функциями оптимальных затрат в задачах с количеством шагов ( k + 1) и k.

Пусть Yk – множество состояний, из которых (при использовании допустимых управлений) можно ровно за k шагов попасть в одно из состояний финального множества X N. При этом можно считать, что Y0 = X N. Возьмем описывающую зависимость оптимальных затрат от состояния x N k за k последних шагов, переводящих систему из x N k в X N. Такие функции называют функциями Беллмана.

Поскольку для состояний x N 1 из множества Y1 переход в X N происходит за один шаг, то функция оптимальных затрат S1 ( x N 1 ) может быть записана следующим образом:

Заметим, что второе ограничение необходимо для того, чтобы гарантировать достижение заданного финального множества X N.

Значение u N, при котором достигается минимум в этом соотношении, обозначим через u * ( x N 1 ).

Можно доказать, что функция оптимальных затрат S k +1 ( x N k 1 ) каждой следующей задачи рекуррентно выражается через предыдущую где в ограничениях последнее условие обеспечивает попадание точки x N k в область определения функции S k.

Пусть u * k ( x N k 1 ) – значение управления, при котором достигается минимум затрат в (1.2). Выражения u k ( xk 1 ) определяют для каждого момента времени оптимальные правила управления в виде функций от текущего состояния динамического процесса, т.е. задают закон оптимального управления в форме оптимального регулятора по состоянию.

Оптимальное начальное состояние x0 можно получить из решения следующей задачи:

Систему (1.1)-(1.3) называют рекуррентными уравнениями Беллмана.

Значения оптимального управления в явном виде можно последовательно определить следующим образом: u1 = u1 ( x0 ), x1 = f1 ( x0, u1 ), … Заметим, что уравнения (1.1), (1.2) определяют следующее правило построения управления: вне зависимости от того, каким образом управляемый процесс на шаге k попал в состояние xk, далее надо применять управление, оптимальное для этого состояния в завершающем ( N k ) -шаговом процессе с учетом оптимального продолжения, и в состоянии xk нужно применять правило u k +1 ( xk ), определяющее первый «такт» такого управления Это одна из возможных формулировок принципа Беллмана в форме достаточного условия. Такой выбор управления для текущего шага учитывает его влияние на будущее, а также то, что последствия неправильного выбора, совершенного в данный момент, в будущем исправить нельзя.

Уравнения (1.1)-(1.3) записаны в форме, определяющей решение от конца процесса. Возможна запись аналогичных уравнений относительно начала процесса. При этом функции Беллмана (обозначим их для новой формы записи через Z k ( xk ) ) должны определять оптимальные затраты при переходе из состояний начального множества X 0 в состояние xk за k шагов.

Выше уже было отмечено, что при использовании метода Беллмана первым важным этапом решения является такая постановка исходной задачи, при которой она будет укладываться в схему динамического программирования. Часто это можно сделать несколькими разными способами. Важным является также то, что на основе рекуррентных соотношений Беллмана можно решать задачи, несколько отличающиеся от приведенной стандартной постановки. Например, функция общих затрат может не являться аддитивной, а иметь вид произведения затрат d k ( xk 1, u k ) по шагам (при положительности этих затрат) или максимума из этих затрат. Естественно, это приведет к соответствующим изменениям в записи (1.2) уравнений Беллмана.

Ниже применение метода динамического программирования продемонстрировано на примере трех задач. Первые две – стандартные, третья – нет.

Первая задача решается таблично, вторая – аналитически.

Пример 1. Задача об оптимальном графике закупок Предприятие планирует на период продолжительностью N дней выпуск фруктовых консервов. Стоимость закупаемой партии фруктов есть P(x) (табл.

1.1) условных единиц и зависит от ее размера x, который всегда есть число, кратное. Сырье в виде фруктов может поставляться на предприятие раз в день в течение всего периода работы. Если фрукты не используются в тот же день, когда они доставлены, их следуют хранить в холодильнике, емкость которого ограничена величиной E. Арендная плата за хранение зависит от количества хранимых фруктов x и составляет Q (x ) условных единиц в сутки.

Требуется определить количество фруктов, которое следует закупать в каждый из дней, чтобы минимизировать суммарные затраты на покупку и хранение при условии, что суточная потребность составляет условных единиц. Решить задачу, приняв, что N = 3, = 100, E = 600 и = 300. При решении считать, что запасы фруктов в начале и в конце рабочего периода отсутствуют.

Для решения данной задачи представим ее в форме задачи динамического программирования. Обозначим через uk количество фруктового сырья, закупаемое предприятием в k -ый день. За состояние xk разумно выбрать количество фруктов, оставшееся в k -ый день невостребованным. Тогда закон изменения состояния системы имеет вид: xk +1 = xk + u k +1, где k = 0,K, N 1, а, поскольку по условию задачи начальные и конечные запасы сырья отсутствуют, то x0 = x N = 0. При этом функция, описывающая затраты в k -ый день, может быть записана как d k +1 ( xk, u k +1 ) = P (u k +1 ) + Q( xk ).

Стоимость закупаемых фруктов P(x), арендная плата Q(x) последний третий день, тогда система находится в состоянии x2 и минимальные затраты за последний день зависят от u3 и составляют Областью определения функции S1 ( x2 ) является отрезок 0 x2 300.

Поскольку x2, в силу кратности, принимает лишь конечное число значений, удобно представить функцию S1 ( x2 ) в табличной форме (см. табл. 1.2).

Теперь предположим, что предприятию осталось отработать два дня.

Минимальные затраты в оставшемся двухшаговом процессе определяются значением функции S 2 ( x1 ), выражаемой через значения функции S1 :

где множество U 2 ( x1 ) = { u 2 : max{300 x1 ; 0} u 2 600 x1}. Его вид получается следующим образом: т. к. область определения функции S1 ( x2 ) есть 0 x2 300 и x2 = x1 + u 2 300, то объединяя соотношения, получаем верхнюю границу множества изменений u2. Нижняя граница получается аналогично, для этого достаточно принять во внимание, что количество «лишних» фруктов не может быть меньше нуля. Результаты вычисления функции S 2 ( x1 ) представлены правой части табл. 1.2.

Приведем пример вычисления значения S 2 (100) :

где минимум достигается при u 2 = 200 и при u 2 = 500.

На последнем шаге вычислений, т.е. когда предприятию осталось отработать три дня, функция Беллмана имеет вид При этом, поскольку x0 = 0, то достаточно вычислить эту функцию лишь в этой точке, поэтому и указанное значение достигается как при u1 = 300, так и при u1 = 600, являющихся возможными значениями оптимального управления u1 ( x0 = 0).

Чтобы по вычисленным функциям S1 ( x2 ), S 2 ( x1 ) и S 3 ( x0 ) построить оптимальный план закупки фруктового сырья, нужно взять одно из найденных на последнем шаге значений u1 = u1 (x0 ), например, u1 = 300 и найти оптимальное x1 = x0 + u1 300= 0 + 300 300= 0. Далее, в таблице для функции S 2 ( x1 ), найти величину u 2 ( x1 ), соответствующую x1 = x1 = 0 и затем вычислить x2 = x1 + u2 300 = 0 + 600 300 = 300. Наконец, по последней аналогичные вычисления для u1 = 600, находим, что в задаче имеется два оптимальных плана закупок фруктов по дням: (300, 600, 0) и (600, 0, 300).

Пример 2. Задача об оптимальном графике лечения Пусть на интервале времени (0, T ) больному должны сделать N инъекций лекарства. Стоимость одной инъекции равна a > 0. Примем, что в начальный момент t = 0 инъекция уже сделана, и в момент t = T обязательно производится завершающая. В качестве свободных переменных выберем длины интервалов между N инъекциями: u1, u 2,..., u N, тогда интервал перед завершающей будет равен T (u1 +... + u N ). Пусть издержки больного из-за наличия промежутка u k составляют (u k ) в условном стоимостном выражении. Функция (u ) будет считаться достаточно гладкой и строго выпуклой ( (u ) > 0). Требуется за счет выбора длин интервалов u k (k = 1,.., N ) добиться минимума общих издержек в виде суммы:

Эта задача в исходной постановке отличается по форме записи от задач динамического программирования. В частности, она не включает понятия состояния, и, кроме того, последний элемент в функции затрат зависит от совокупности значений u1, u 2,..., u N.

Чтобы представить задачу в форме задачи динамического программирования, будем рассматривать промежутки между инъекциями u1, u 2, …, u N как управления, а в качестве дополнительного описания (обозначим его xk ) примем время, оставшееся до завершающей инъекции после проведения k -ой.

Убедимся, что такое описание будет являться состоянием. Действиительно, начальное значение x0 = T, а каждое очередное значение xk выразится через его текущее значение и очередное управление: xk = xk 1 u k, где ограничения на выбор этого управления будут зависеть только от xk 1, а именно:

u k U k ( xk 1 ) = (0, xk 1 ). Очевидно, что функция затрат на k -ом шаге имеет зависимости от параметров функции затрат на шаге также соблюдена.

Следовательно, выбранное описание xk можно принять в качестве состояния.

Составим уравнения Беллмана. Пусть все инъекции, кроме N -й, проведены и управляемый процесс находится в состоянии x N 1, тогда минимальные (за счет выбора u N ) затраты в оставшемся одношаговом процессе составят:

Значение u N, определяющее минимум на открытом промежутке, ищем из условия обращения в ноль первой производной: (uN ) ( xN 1 uN ) = 0, поскольку вторая производная выходит за пределы допустимых значений u N.

теперь проведены все инъекции, кроме двух последних: ( N 1) -й и N -й (не считая завершающей в момент времени T ), а длина оставшегося промежутка времени составляет x N 2. Тогда Легко заметить имеющуюся закономерность. Для ее обоснования применим метод математической индукции. Предположим, что Из условия равенства нулю первой производной находим, что S k +1 ( x N k 1 ) = (k + 2)(a + ( x N k 1 (k + 2) ) ). Следовательно, доказано, что эти соотношения верны для всех k.

Поскольку начальное состояние применяя полученные оптимальные правила u k ( xk 1 ) выбора промежутков между инъекциями, получим последовательность оптимальных значений для управлений и состояний:

Окончательно имеем: оптимальные затраты равны и достигаются при проведении инъекций через равные промежутки времени Пример 3. Оптимальное соединение точек На числовой оси y имеется набор из ( N + 1) точек, размещенных в порядке возрастания координат y1 < y 2 <... < y N +1. Длины отрезков [ y1 y2 ],..., [ y N y N +1 ] заданы и выражаются положительными числами p1, p2,..., p N.

Пометим часть отрезков [ y k, y k +1 ] так, чтобы каждая точка y1, y 2,..., y N + принадлежала хотя бы одному из помеченных отрезков. Обозначим пометки через u1, u 2,..., u N, считая, что при u k = 1 отрезок [ y k, y k +1 ] помечен, а при u k = 0 – нет. Требуется расставить пометки так, чтобы сумма длин помеченных отрезков, равная вытекают следующие ограничения на u k : соседние значения uk, uk +1 не могут одновременно обращаться в ноль; кроме того, первый и последний отрезки помечаются обязательно.

Перейдем к построению решения, используя метод Р. Беллмана.

Поскольку порядок нумерации отрезков (прямой или обратный) в данной задаче значения не имеет, запишем уравнения Беллмана не от конца, а от начала процесса. Вместо одной задачи из N отрезков рассмотрим задачи из одного, двух, трех и т.д. первых отрезков. Пусть Z1, Z 2,... – наименьшие возможные суммы длин помеченных отрезков в таких задачах, а u k 1 ( k ) – оптимальная пометка ( k 1)-го отрезка в задаче, включающей k первых отрезков.

В отличие от общего случая, в этой задаче функции Беллмана не имеют аргумента, поскольку их значения зависят только от индекса, показывающего число отрезков (число шагов) в задаче. Само же количество пройденных отрезков может быть принято в этой задаче за состояние, и, таким образом, состояние совпадает с номером шага, дублируя его. Очевидно, что Z 3 = min{ p3 + Z1, p3 + Z 2 }, u2 (3) = 0, если минимум достигается на первом элементе, и u 2 (3) = 1, если на втором, т.е. первый и последний должны быть помечены.

Аналогично, для значений 2 < k + 1 N Всегда u k +1 ( k + 1) = 1, т.к. последний отрезок всегда должен быть помечен.

Покажем, как можно получить окончательное решение при конкретных данных. Пусть N = 6 и p1 = 1, p2 = 2, p3 = 1, p4 = 1, p5 = 2, p6 = 2 (рис. 1.1).

Рис. 1.1. Пример размещения точек и их оптимальное соединение Применяя приведенные расчетные формулы, получим следующий результат.

Последние найденные значения u5,6 (6) показывают, что в задаче с N = 6 отрезками отрезок p6 помечается, т.е. u 6 = 1, а p5 нет, т.е. u5 = 0. В силу того, что p5 не помечен, необходимо рассмотреть укороченную задачу для оставшихся 4-х отрезков ( p1,..., p4 ). Из полученных условных решений видно, что в возникшей четырехшаговой задаче u 4 = u 4 ( 4) = 1 и u3 = u3 (4) = 1.

Поскольку p3 оказался помеченным, то далее следует рассмотреть трехинтервальную задачу p1, p2, p3. Видим, что u 2 = u 2 (3) = 0. Но тогда остается одноинтервальная задача, и в ней u1 = 1. Следовательно, минимальная сумма длин помеченных интервалов равна Z 6 = 5, а пометки следует поставить так: u1 = 1, u 2 = 0, u 3 = 1, u 4 = 1, u 5 = 0, u 6 = 1. На рисунке эти интервалы помечены жирными линиями.

Дополнительные примеры с решениями можно найти в указанной литературе [2-5].

1.2. Управляемые марковские процессы с доходами, теория и примеры Метод динамического программирования может быть применен и для выбора оптимальной стратегии при управлении вероятностными марковскими процессами [6]. Будем рассматривать случай, когда значения, принимаемые марковским процессом, могут быть пронумерованы. Такой процесс будем называть дискретным. Вместо значений, которые принимает процесс, в дальнейшем будем использовать их номера.

Случайный процесс с дискретными значениями xn называют марковским, если он обладает свойством: для любого n 1 ( n = 1, 2, K) и любых возможных значений i0, i1, i2, K, in 1 должно выполняться следующее требование для условных вероятностей:

Значения ik, которые принимает марковский процесс, можно назвать его внутренними состояниями. Они ни в коем случае не являются его «состояниями» в терминологии динамических систем. Однако далее для краткости изложения вместо термина «внутреннее состояние» в некоторых случаях будем говорить просто о состоянии, опуская слово «внутреннее»

Если вероятность p( xn = in / xn 1 = in 1 ) перехода из состояния in 1 в состояние in не зависит от момента времени n, марковский процесс называется стационарным. В последнем случае случайный процесс перехода из одного состояния в другое на каждом шаге описывается одной и той же стохастической матрицей P = pij, элементы которой pij являются условными вероятностями того, что следующим состоянием будет состояние j, если текущим состоянием является состояние i. Эти вероятности удовлетворяют равно m ). Марковский процесс с конечным числом внутренних состояний называют конечной марковской цепью.

Рассмотрим марковскую цепь с m внутренними состояниями, вероятности нахождения в которых в момент времени n заданы вектором-строкой p(n) = ( p1 (n),..., pm (n)). Вектор p(n) описывает текущее вероятностное распределение марковской цепи по ее внутренним состояниям. В силу однозначности определения p ( n + 1) по p (n) вектор вероятностного распределения будет являться состоянием марковской цепи как динамической системы [1]. Оператор изменения этих вероятностей задается стохастической матрицей P : p ( n + 1) = p ( n) P.

Сделаем теперь цепь управляемой за счет того, что матрица вероятностей переходов P будет зависеть от некоторой стратегии-управления k ( P (k ) ).

Предположим, что при каждом внутреннем состоянии цепи мы имеем возможность выбирать одну из K стратегий, задаваемых стохастическими матрицами P (k ), k = 1, K, K. Каждой матрице P (k ) сопоставим матрицу доходов D (k ) так, что при выборе стратегии k математическое ожидание дохода qi, связанного с попаданием во внутреннее состояние i за один шаг, будет равно Обозначим через Vn (i ) максимально возможное математическое ожидание дохода за n шагов, если начальное внутреннее состояние системы было i. Тогда в соответствии с принципом оптимальности мы получим рекуррентное соотношение [7], являющееся аналогом уравнения Р.Беллмана Функция Vn (i ) играет роль функции Беллмана.

Пример 4. Задача об игрушечных дел мастере [7] Игрушечных дел мастер в течение недели изготавливает игрушки, а в воскресенье выходит на рынок, чтобы их продать. Вероятности успешной или неуспешной продажи, а также величины доходов в зависимости от результата предыдущего раунда заданы матрицами Первая стратегия соответствует отсутствию рекламы, вторая стратегия соответствует рекламе по радио, третья стратегия соответствует рекламе по телевидению. Требуется определить оптимальную стратегию в смысле максимума математического ожидания дохода на несколько шагов вперед.

Пусть V0 (1) = V0 (1) = 0. Тогда рекуррентное соотношение (1.4) позволяет нам найти оптимальную стратегию поведения (k1 (1), k 2 (1) ) в расчете на один шаг:

Итак, оптимальная стратегия поведения ( k1 (1), k 2 (1)) = (1;1) в расчете на один шаг, при этом V1 (1) = 6, V1 ( 2) = 3. Теперь подсчитаем оптимальную стратегию поведения ( k1 ( 2), k 2 ( 2)) в расчете на два шага:

Итак, в расчете на два шага оптимальная стратегия поведения (k1 (2), k 2 (2)) = (2; 3), при этом V2 (1) = 8, V2 (2) = 1.6. Теперь подсчитаем оптимальную стратегию поведения ( k1 (3), k 2 (3)) в расчете на три шага:

Итак, в расчете на три шага оптимальная стратегия поведения (k1 (3), k 2 (3)) = (2; 3), при этом V3 (1) = 9.76, V3 (2) = 0.16. Можно сделать предположение, что стратегия ( 2; 3) останется оптимальной и на большее число шагов. Рассмотрим марковский процесс, соответствующий этой стратегии:

Известно, что если все элементы матрицы вероятностей переходов строго положительны, то вне зависимости от начального распределения p (0) существует эргодической [1, 6] Переходя к пределу в записанном соотношении, получим систему двух зависимых уравнений относительно вектора p*. Дополняя ее условием нормировки p1 + p2 = 1, находим соответствующий нашей задаче вектор предельных вероятностей p* = (0.6; 0.4). Таким образом, предполагая процесс достаточно длительным, мы можем подсчитать средний доход M за один шаг при соблюдении стратегии ( 2; 3) :

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

1.3. Контрольные задания 1. Задача о путешественнике На местности имеется сеть дорог, связывающих несколько населенных пунктов. Путешественник находится в пункте a0, из которого, двигаясь по одной из трех дорог, можно попасть в пункты a1, a 2, a3. Из каждого пункта опять выходят ровно три дороги, ведущие в a 4, a5, a6. Из них – в a7, a8, a9 и так далее, вплоть до конечных пунктов b1 = a3 N 2, b2 = a3 N 1, b3 = a3 N.

Длины всех дорог заданы. Найти наиболее короткий путь из a0 в один из конечных пунктов. Решить задачу при N = 5. Оцените количество операций сложения и сравнения при ее решении по методу Беллмана, а также при полном переборе всех путей.

2. Задача о распределении инвестиций Нужно распределить между N предприятиями сумму a, выделенную для их инвестирования. Известно, что вложение средств в размере y в k -ое предприятие обеспечивает прибыль в размере d k ( y ). Целью распределения является получение максимального суммарного дохода. Решить задачу при N = 4, a = 300 при условии, что суммы инвестиций всегда кратны 50, а функции d k ( y ) для y = 50 j ( j = 0, 1,..., 6) принимают значения, заданные в табл. 1.3.

3. Задача о распределении механизмов Имеется m видов земляных работ и N > m однотипных механизмов, способных выполнять эти работы. Если назначить на i -й вид работы k механизмов, то их суммарная производительность определяется значением Gik. Считая, что матрица G, составленная из таких значений, известна, найти оптимальное по суммарной производительности размещение механизмов по всем видам работ. Решить задачу, приняв N = 4, m = 3, 4. Задача о распределении ресурса Пусть требуется распределить ограниченный ресурс a на доли x1,..., x N ( x1 0,..., x N 0, x1 +... + x N a) между N предприятиями, каждое из которых приносит доход f i ( xi ) = ci xi2 (ci > 0). Найти оптимальное распределение ресурсов.

5. Решить предыдущую задачу при f i ( xi ) = ci xi.

6. Задача о загрузке судна Судно, имеющее грузоподъемность a, загружается предметами N типов.

Один предмет i -го типа имеет стоимость yi и вес zi. Требуется найти вариант загрузки судна, при котором стоимость взятых на борт предметов максимальна.

Решить задачу для N = 3, a = 200, y1 = 25, y 2 = 40, y3 = 80, z1 = 40, z 2 = 50, z3 = 70.

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

8. Задача о налоге В Н-ской области решили ввести дополнительный налог на рост доходов частных фирм. Если за N месяцев доходы фирмы образуют возрастающий ряд 0 < p1 p2... p N +1 то, согласно установленным правилам, фирма должна уплатить дополнительный налог в размере r > 0. При заданном значении начальных и конечных доходов где p1 = a < b = p N +1 фирма должна спланировать график возрастания своих доходов так, чтобы дополнительный налог был минимален. Получить решение задачи аналитически.

9. Задача о надежности Технологическая цепочка изготовления изделия включает N операций, выполняемых на автоматизированных участках конвейерной обработки.

Устройство, выполняющее операции на i -ом участке, имеет вероятность работы без отказа pi и стоимость ci. Для повышения надежности на участке можно установить mi дублеров, повысив надежность участка до значения Pi (mi ) = 1 (1 pi )1+ mi. Средства, выделенные на установку устройствдублеров, ограничены значением C. Решить задачу о выборе оптимального количества дублеров, приводящем к максимизации надежности всей технологической цепочки.

c2 = 4, c3 = 4. Для упрощения расчетов принять приближенные значения функций Pi (m) из табл. 1.4.

10. Задача о замене оборудования Частное предприятие планирует в течение N лет заниматься выпуском изделий, используя некоторое оборудование. В начале можно либо купить новое оборудование возраста x0 = 0 лет и стоимостью p, либо подержанное оборудование возраста x0 > 0 лет по его ликвидной стоимости ( x0 ).

Показатели эксплуатации оборудования включают: f (t ) – стоимость произведенных за год изделий на оборудовании возраста t лет; r (t ) – затраты на эксплуатацию в течение года оборудования возраста t лет.

В процессе эксплуатации оборудование можно менять, продавая старое по ликвидной стоимости (t ) и покупая новое стоимостью p. В конце N -го года оборудование продается по ликвидной стоимости. Определить оптимальный возраст оборудования x0 при начальной покупке и оптимальный 11. Предприятие, выпускает товары, изготавливая их отдельными партиями. Чем больше размер этих партий, тем относительно дешевле обходится выпуск. Поэтому в отдельные месяцы выгодно выпускать больше изделий, чем это нужно для удовлетворения спроса, а излишки хранить на складе для их реализации в последующие месяцы. За хранение в течение месяца каждой тысячи штук изделий нужно платить = 1 усл.ед. Емкость склада ограничена величиной C = 4000 штук.

Составить оптимальный план производства на N = 4 месяцев, при котором общая сумма затрат на производство и хранение была минимальной, а спрос на изделия – всегда удовлетворен. Объемы спроса по месяцам составляют mi (i = 1,.., N ) изделий (при решении принять: 2000, 3000, 3000 и 2000). Начальные запасы готовых изделий составляют C0 = 2000. Размер производимых партий не может превышать p = 4000 изделий. Затраты, связанные с выпуском парий изделий объемом vi (i = 1,.., N ) штук (принять:

1000, 2000, 3000 и 4000), определяются величинами (соответственно 13, 15, 17 и 19 есл.ед.).

12. Товар в количестве C = 100 ед. может реализовываться на трех рынках по ценам p1, p 2 и p3 за единицу продукции. Определить оптимальное распределение товара между рынками при следующих зависимостях цены от объема предлагаемой продукции xi на данном рынке:

13. Используя уравнения Беллмана, составить расчетную схему решения задачи максимизации суммарной прибыли от работы k цехов, выпускающих изделия разных видов. Прибыль от выпуска x изделий j -го вида (он производятся j -м цехом) определяется значением Pj (x) (табл. 1.5). Изготовление одного изделия j -го вида требует определенного количества сырья m типов, а именно C j 1, K, C j m. Запасы этого сырья, общие для всех цехов, составляют z1, K, z m. Решить задачу при следующих данных: K = 3, m = 2, расходы сырья для изделия первого типа: C11 = 2, C12 = 4 ; второго: C21 = 4, C22 = 2 ; третьего: C31 = 1, C32 = 3 ; а запасы составляют z1 = 10, z 2 = 12.

14. Задача о ритмичности производства Пусть имеется некоторое производство, которое ежедневно обеспечивается поставками сырья в количествах p1, p 2,..., p N. Излишки сырья хранятся на складе емкостью E. Начальное количество сырья на складе задано и составляет E0. Обозначим x1, x2,..., x N — объемы сырья, ежедневно забираемые на производство. Общее количество перерабатываемого за N дней сырья известно и равно A. По известному графику поставок сырья p1, p2,..., p N составить график его потребления x1, x2,..., x N, минимизирующий неритмичность производства, понимаемую как iN 1 ( xi A N ). Сырье следует считать штучным. Решить задачу при N = 5, 15. Задача о фермере Для фермера, разводящего крупный рогатый скот, определить оптимальный график продаж при следующих условиях. Каждый год некоторое количество голов скота yi отправляется на продажу. Стоимость проданного скота определяется функцией ( yi ) = k yi ( k > 0). Оставшаяся часть стада увеличивается за год в раз ( > 1). Начальное поголовье равно A. Решить задачу определения оптимального графика продаж при N = 4. Затраты на приобретение начального стада и его содержание не учитывать.

16. Задача о фермере 2.

Решить задачу 12 с учетом следующих факторов. Изменение поголовья стада за год происходит за счет приплода с коэффициентом > 1 и падежа с коэффициентом 0 < < 1. Стоимость содержания единицы скота в год составляет C. Выяснить зависимость оптимальной стратегии продаж от соотношения коэффициентов,, C. Принять, что падеж происходит только в «старой» части, а приплод наблюдается только в оставшейся. Можно считать, что затраты на содержание приплода составляют половину общей годовой стоимости содержания.

17. Задача о распределении с неизвестным начальным состоянием Предприятие работает в течение N лет. Затраты по начальной закупке сырья равны y0, где y0 — количество покупаемого сырья. В начале i -го года часть xi имеющегося сырья пускается в производство. Это приносит доход f i ( xi ). Определить оптимальное начальное количество и использование сырья по годам, максимизирующее суммарный доход с учетом затрат на покупку сырья. Принять N = 2, = 1, f1 ( x1 ) = x1, f 2 ( x2 ) = 0.5 x2.

18. Задача о динамическом выделении с возвратами Предприятие функционирует N лет. Начальный капитал равен a.

Каждый год некоторая часть ui имеющейся суммы пускается в оборот с условием возврата в кассу в конце года суммы в размере дохода выплачивается сумма f i (ui ) в качестве вознаграждения работникам.

Найти оптимальные значения u1, u 2,..., u N, максимизирующие сумму выплаченных вознаграждений. Выполнить расчет при N = 3, f1 (u ) = 0.1 u 2, 19. Задача о динамическом распределении с возвратами Составить оптимальный план ежегодного распределения средств между двумя предприятиями в течение N лет, если начальная сумма средств равна A, доходы от вложения средств x1 и x2 в предприятия составляют f1 ( x1 ) и Вложенные средства возвращаются в общую кассу для перераспределения в размере 60% от x1 для первого и 20% от x2 для второго предприятия. Каждый год все имеющиеся в общей кассе средства полностью перераспределяются с точностью до остатка, меньшего ; x1 и x2 выбираются кратными. Решить задачу при N = 3, A = 400, = 50 и значениях функций f1 ( x1 ) и f 2 ( x2 ) из табл. 1.6.

20. Задача о многоступенчатой ракете Ракета-носитель с N ступенями имеет общую массу M, включающую массу m выводимого на орбиту космического аппарата и топливо. Вес оболочек ступеней считается равным нулю. Обозначим вес топлива в ступенях ракеты через u1, u 2,..., u N. Будем считать, что прирост скорости ракеты при сгорании k -ой ступени пропорционален отношению u k ( m + u N +... + u k ).

Требуется определить оптимальное распределение топлива по ступеням ракеты. Выполнить расчеты при N = 3, M = 64, m = 1.

21. Задача о ракете с импульсным управлением Ракета с массой m движется по прямой вне поля силы тяжести.

Реактивный двигатель работает в импульсном режиме. Сообщаемая величина импульса u [ V,V ], а затраты топлива пренебрежимо малы по сравнению с массой корабля. Считать, что порция топлива сгорает мгновенно. Найти значения u1, u 2, K, u N, при которых ракета из состояния покоя перейдет в другое состояние покоя, максимально удаленное от начального. Принять, что приращение скорости, полученное в k -й момент времени, начинает оказывать влияние на приращение координаты только в следующий ( k + 1) -й момент времени. Решить задачу при N = 3 и N = 5 ; m = 1, V = 10. Интервал между импульсами принять равным единице.

Указание: сообщение системе импульса u изменяет ее количество движения (произведение массы на скорость) на величину u.

22. Задача оптимального управления с дискретным временем Методами динамического программирования решить следующую задачу.

23. Задача с неаддитивным критерием Представить задачу математического программирования max i =1 xi iN 1 ai xi c, x1,..., xN 0, динамического программирования. Записать уравнения Беллмана. Найти оптимальное решение при N = 3, a1 = 1, a 2 = 2, a3 = 3 и c = 10.

24. Задача с разностным уравнение второго порядка Используя динамическое программирование, записать расчетную схему решения задачи для произвольного N : min i =1 ( xi2 + ui2 ), если x0 = a, x1 = 2a ;

xi+2 + xi +1 + xi = ui +1 и x N +1 = 0. Найти оптимальное решение для N = 3; 4.

25. Задача о производстве Господин M, желая построить коттедж, одолжил у своего друга на N недель мини-установку по производству дешевого кирпича с функцией производительности f (x) штук в неделю, где x - количество использованного сырья. Следует считать, что производная функции f (x ) положительна и убывает при увеличении x.

Перед началом производства имелась сумма денег A. Стоимость единицы сырья в ценах стартовой недели равна C. Коэффициент инфляции за неделю равен > 1. Сырье покупается еженедельно в количествах x1, x2,..., x N. По окончании N -й недели на оставшиеся неистраченные деньги покупается готовый более дорогой кирпич по цене B за штуку (в ценах стартовой недели). Необходимо составить рекуррентные уравнения Беллмана для определения оптимальных размеров закупки сырья, приводящих к максимизации общего количества полученного кирпича.

26. Задача о накоплении Составить рекуррентные уравнения Беллмана для предыдущей задачи при следующем изменении ее условий. Вначале в фонд развития вносится сумма денег A. Средства на покупку сырья берутся из фонда развития. Кирпич производится не для личного использования, а для продажи по цене B за штуку ( в ценах стартовой недели). При этом 50% получаемой от продажи суммы добавляется к оставшимся в фонде средствам, а остальные 50% используются на оплату рабочим, налоги и потребление. Необходимо составить рекуррентные уравнения Беллмана, позволяющие решить задачу об оптимальном выделении средств на закупку сырья для максимизации суммы денег в фонде развития к концу N -й недели.

27. Задача о графике эксплуатации Электростанция имеет L агрегатов. Предположим, что производительность одного агрегата за неделю равна C, а единица произведенной электроэнергии продается по цене b. График оплачиваемого производства электроэнергии по неделям задан: p1, p2,..., p N, и нарушаться не должен.

Избыточно произведенная электроэнергия не оплачивается. Затраты на поддержание в рабочем состоянии l агрегатов в течение недели равны r (l), затраты на консервацию l агрегатов составляют ( l). Затраты на пуск равны P ( l). Составить рекуррентные уравнения Беллмана для определения оптимального графика эксплуатации агрегатов.

28. Задача о дискотеке Cтудент пришел на дискотеку, там ему понравились две девушки: Алиса и Бэтти, с которыми он и решил танцевать.

Однако характер у девушек оказался разным. Алиса предпочитает танцевать со знакомыми мальчиками (с вероятностью 0.7 принимает приглашение к танцу) и не любит танцевать с незнакомыми мальчиками (с вероятностью 0.4 принимает приглашение к танцу). Бэтти, наоборот, предпочитает танцевать с незнакомыми мальчиками (с вероятностью 0.8 принимает приглашение к танцу) и не любит танцевать со знакомыми мальчиками (с вероятностью 0.3 принимает приглашение к танцу). Общей чертой у Алисы и Бэтти является их короткая память: если студент не станцевал с ней хотя бы один раз, то она его уже не помнит, то есть он для нее незнакомец. Определить оптимальную стратегию поведения студента в расчете на несколько танцев вперед, если на каждый очередной танец он успевает сделать приглашение к танцу только одной из девушек.

29. Задача об экзаменационной сессии Студент уже сдал один экзамен на 4, но ему предстоит сдать еще три экзамена. При подготовке к экзаменам он из-за недостатка времени может выбрать одну из следующих двух стратегий: либо выучить часть материала довольно хорошо, либо пройтись быстро по всему материалу. Определить оптимальную в смысле набранных баллов стратегию поведения студента на оставшиеся три экзамена, если матрицы вероятностей получения оценок 5, 4, 3, 2 в зависимости от предыдущей оценки для двух стратегий имеют вид:

30. Задача о погоне Догоняющий находится в i -той клетке из 5 клеток, образующих круг. За один такт он с вероятностью p = 1 / 2 перемещается по часовой стрелке в соседнюю клетку, с вероятностью q = 1 / 3 перемещается против часовой стрелки в соседнюю клетку, с вероятностью r = 1 / 6 остается на месте.

Убегающий находится в j -той клетке и на каждом такте может выбрать одну из трех стратегий поведения: (a) переместиться по часовой стрелке в соседнюю клетку; (b) остаться на месте; (c) переместиться против часовой стрелки в соседнюю клетку. Расстояние между догоняющим и убегающим определяется по формуле d = i j. Определить стратегию убегающего на три такта вперед, максимизирующую сумму расстояний между догоняющим и убегающим.

31. Стохастическая задача о фермере Состояние продуктивности земли, используемой фермером, может быть (a) хорошим, (b) удовлетворительным, (c) плохим. Вероятности перехода продуктивности земли из одного состояния в другое без проведения агротехнических мероприятий за один сезон заданы матрицей P (1). Однако фермер может провести комплекс агротехнических мероприятий, и тогда вероятности перехода продуктивности земли из одного состояния в другое за один сезон будут заданы матрицей P ( 2). Матрицы доходов для двух стратегий поведения: D (1), D ( 2). Найти оптимальную стратегию фермера на 4 сезона.

P(1) = 0.0 0.5 0.5, P(2) = 0.2 0.6 0.2, D (1) = 0 5 1, D(2) = 5 4 1.

2. Элементы выпуклого анализа 2.1. Базовые понятия и факты Выпуклый анализ в настоящее время является обширным разделом математики, начало которому было положено в работах немецкого математика и физика Германа Минковского (1864-1909). Ниже приведены отдельные понятия и факты из выпуклого анализа, используемые в следующих разделах данного пособия. Дополнительный материал можно найти, например в [8-10].

Далее всюду будем предполагать, что рассматриваются элементы и множества из пространства R n конечной размерности. Пусть x и y - два элемента из R n, тогда множество называется отрезком [ x, y ] в R n. Элемент отрезка может быть записан в иной Непустое множество D R n называется выпуклым множеством, если для любых элементов x и y из D соединяющий их отрезок [ x, y ] D, т.е.

считается выпуклым по определению.

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

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

Множество называется конусом (с вершиной в точке 0), если > =. Конус не обязательно является выпуклым множеством.

Множество внутренних точек из D будем обозначать int D, а замыкание - D. Эти операции не нарушают выпуклости, причем для выпуклого множества D int D = D и int D = int D.

Если x1, x 2, K, x k – элементы из R n, то их выпуклой линейной комбинацией называют множество Выпуклая линейная комбинация совпадает с выпуклой линейной оболочкой элементов x1, x 2, K, x k, под которой понимается наименьшее выпуклое множество, содержащее все эти точки.

Пусть на множестве D R n задана функция Q. Множество epiQ( D) R n +1 называют ее надграфиком (эпиграфом), если Функцию Q, определенную на выпуклом множестве D, называют выпуклой на D, если epiQ (D) - выпуклое множество. Выпуклость функции можно определить иначе (эти определения эквивалентны).

Функция Q, определенная на выпуклом множестве D R n, называется выпуклой (выпуклой вниз) на D, если x, y D, [0, 1] Если при тех же условиях вместо неравенства вида « » выполняется неравенство вида « », то функция называется вогнутой (выпуклой вверх). Если функция называется строго выпуклой (строго вогнутой).

Согласно последних определений выпуклость функции Q на D геометрически означает, что для всякого отрезка [ x, y ], включенного в D, график этого отрезка ( 0 1) проходит нестрого ниже соответствующей хорды, опирающейся на значения Q (x ) и Q ( y ) (рис. 2.1).

Рис. 2.1. Поведение сечения выпуклой функции, где Q = Q ( x ) + (1 ) Q ( y ) Если функция Q является аффинной, т.е. Q ( x ) = a x + b, то она одновременно и выпукла и вогнута.

Можно доказать, что функция Q, выпуклая на выпуклом D, непрерывна в любой точке x int D (на границе D функция может быть разрывной), более того x int D и любого направления v ( || v ||= 1) существует производная по направлению Q ( x) v (дифференцируемости в точке x при этом может не быть).

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

Заметим, что применив данный критерий, можно отсечь часть множества D, не содержащую точки x* глобального минимума Q на D, используя результат измерения Q ( y ) : x* D I {x : (Q( y ), x y ) 0}.

В случае, когда выпуклая функция Q недифференцируема в точке y, вместо вектора градиента можно использовать вектор субградиента v( y ), определяемый следующим условием: x D Q ( x) Q ( y ) + (v( y ), x y ).

Вектор субградиента также можно использовать для отсечения подобласти в D, не содержащей глобального минимума. Множество всех субградиентов, построенных для выпуклой функции Q в точке Q называется субдифференциалом Q ( y ) = {v : x D Q ( x) Q ( y ) + (v, x y )}.

Критерий выпуклости для дважды непрерывно дифференцируемой функции. Пусть Q определена на открытом выпуклом множестве D. Q выпукла на D тогда и только тогда, когда матрица Гессе (обозначим ее 2Q( x) ) неотрицательно определена на D, т.е. x D и произвольного d d T 2Q( x)d 0. Заметим, что в силу непрерывности вторых частных производных матрица Гессе будет симметрической.

Если гессиан функции Q всюду в D положительно определен, функция будет строго выпукла на D, но обратное неверно. Например, x 4 строго выпукла в R1, а ее вторая производная в нуле равна нулю.

Напомним, что характер знакоопределенности симметрической матрицы A = AT определяется по знаку квадратичной формы d T Ad для d 0. Если знак может быть различен для разных d, то матрицу A называют знаконеопределенной.

Известно, что собственные числа 1, 2, K n симметрической матрицы всегда действительны, а представление соответствующей ей квадратичной образом, знаки набора собственных чисел характер знакоопределенности матрицы, например при i 0 ( i = 1, K, n ) матрица A будет неотрицательно определена.

Критерий Сильвестра позволяет взаимнооднозначно связать положительную определенность матрицы A с положительностью ее главных миноров 1 0,, n 0, а отрицательную определенность – с чередованием их знаков, начиная с отрицательного: 1 0, 2 0, 3 0, … Если значения некоторых из миноров обратились в ноль, критерий неприменим. Например, из того, что 1 0, 2 0, …, n 0 не следует неотрицательная неопределенность матрицы. Это наглядно иллюстрирует следующий контрпример. Пусть задана симметрическая матрица А.

Отметим дополнительные свойства выпуклых функций. Если f выпукла в R n, C – некоторая константа, то множество точек выпукло, если f аффинна, то x R n : f ( x) C выпукло.

Путь Q – выпуклая функция на выпуклом множестве D. Тогда задача min Q( x) : x D называется задачей выпуклого математического программирования. Она замечательна тем, что любой ее локальный минимум является глобальным, а множество глобальных минимумов является выпуклым.

Если же Q строго выпукла на D, ее глобальный минимум будет единственным, кроме того, он будет являться строгим минимумом.

Пример 1. Исследование области выпуклости и вогнутости функции Составим матрицу Гессе и вычислим главные миноры Функция f выпукла в любой выпуклой области, где матрица Гессе неотрицательно определена. Область положительной определенности определяется условиями 1 x 1 0, 2 ( y 2)( x 1) 1 0, обеспечивающими строгую выпуклость. Выпуклость будет на замыкании этого множества.

Функция f вогнута в любой выпуклой области, где матрица Гессе неположительно определена. Область ее отрицательной определенности определяется строгую вогнутость. Вогнутость будет на замыкании этого множества.

Таким образом, функция выпукла на любом выпуклом подмножестве множества ( x; y ) : y 1 1 x 1, x 1 и вогнута на любом выпуклом подмножестве множества ( x; y ) : y 1 1 x 1, x 1 (рис. 2.2).

2.2. Контрольные задания 1. Влияют ли линейные члены квадратичной функции на ее выпуклость?

2. Пусть Gi - выпуклые множества, i = 1, K, s. Доказать выпуклость множеств: (a) пересечения 0 и < 0 ; (d) разности G1 G2 ; (e) выпуклой линейной оболочки для 3. Доказать, что при выпуклости множества G будут выпуклы: (a) его замыкание G ; (b) множество его внутренних точке int G.

4. Показать, что множество D выпукло в том и только в том случае, когда при любых 1 0, 2 0 1D + 2 D = (1 + 2 ) D [12].

выпуклые множества. Показать, что A( X ) и A1 (Y ), т.е. образ X и прообраз 6. Доказать выпуклость множества {x R n : f ( x) C } для выпуклой в R n функции f.

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

8. Построить вид областей выпуклости и вогнутости функций:

9. Построить вид областей выпуклости и вогнутости функций в зависимости от параметра p :

(a) Q( x, y) = px2 + xy + py2 ; (b) Q( x, y) = px2 + 4 xy + y 2 ; (c) Q( x, y) = x3 + py3.

10. Пусть Q - выпуклая функция на выпуклом множестве D. Показать, что при x, y D, [0,1], для которых x + (1 ) y D, выполняется следующие утверждения: (a) функция Q( x) = e ( x ) выпукла на D ;

(b) функция Q ( x) = 1 / ( x) вогнута на D0 = {x D : ( x) < 0};

(c) если ( x) > 0, то 2 ( x) выпукла на D.

12. Доказать, что Q ( x ) = ( x + h) ( x ) — неубывающая функция при h > 0, если (x) — выпуклая функция.

13. Доказать с помощью критерия выпуклости для непрерывно дифференцируемых функций справедливость неравенств:

14. Доказать, что при выпуклости функций f1, K, f m на выпуклом D их сумма с неотрицательными коэффициентами также выпукла на D.

( ) = (Q( x + v) Q( x)). Показать, что в области > 0 функция ( ) монотонно невозрастает при убывании.

16. Доказать, что при существовании глобального минимума выпуклой функции Q на выпуклом множестве D любой ее локальный минимум будет глобальным, а их множество – выпуклым.

17. Доказать, что строго выпуклая функция на выпуклом D не может иметь более одного глобального минимума.

18. Выпуклая функция Q определена на D = [0,10]2 R 2. Известны значения ее градиента в трех точках:

x 2 = (2; 2), Q( x 2 ) = (5; 5) ; x 2 = (2; 5), Q( x 3 ) = (5;10). Построить оценку положения глобального минимума.

19. Определить субдифференциал Q ( x, y ) выпуклой функции:

3. Условия оптимальности в задачах математического программирования 3.1. Теория и примеры Рассмотрим задачу о нахождении допустимых значений x, при которых функция Q (x) достигает минимума в области Запишем эту задачу в виде предполагая, что минимум существует.

Будем рассматривать решения x* двух типов: глобально-оптимальные, когда x D : Q ( x* ) Q ( x ), и локально-оптимальные, когда существует такая окрестность U ( x* ) точки x*, для которой x D I U ( x* ) значение Всюду ниже функции Q, g = ( g1,..., g N ), h = ( h1,..., hM ) будем считать достаточно гладкими.

Для задач, не обладающих выпуклостью, необходимые условия наличия в x* локального минимума дает следующая теорема Каруша-Куна-Таккера.

Для того, чтобы точка x* была локальным минимумом рассматриваемой задачи, необходимо выполнение группы условий:

(а) x* D – допустимость;

(b) (*, 1,..., *, 1,..., M ) 0 – нетривиальность;

(c) * 0, * 0, (i = 1,..., N ) – неотрицательность;

разложимость;

(e) *i g i ( x * ) = 0, (i = 1,..., N ) – условие дополняющей нежесткости.

Ограничения-неравенства, обращающиеся в ноль в точке x*, называют активными в этой точке. Для множества номеров активных в точке x* неравенств удобно ввести специальное обозначение – I ( x* ).

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

Из (е) следует, что для неактивных в точке x* неравенств *i = 0.

Следовательно, неактивные ограничения не входят в условие разложимости (d) и не влияют на выполнение условий оптимальности. Фактически, в (d) суммирование выполняется только по номерам i I ( x* ).

Заметим, что для задач без ограничений-равенств аналогичную теорему обычно называют теоремой Куна-Таккера (при этом все, что связано с равенствами, из условий теоремы следует исключить), а для задач без ограничений-неравенств – теоремой Лагранжа. В последнем случае первая из сумм в правой части условия разложимости отсутствует, а условия (c) и (d) – неотрицательности и дополняющей нежесткости – вообще не нужны, а требование нетривиальности запишется в виде: (*, 1,..., M ) 0.

Если ввести функцию Лагранжа, записав ее с использованием векторных обозначений:

то условие разложимости (d) можно представить как условие стационарности функции Лагранжа: L( x*, *, *, * ) = 0.

Если функции g1,..., g N выпуклы (вниз), ограничения – равенства либо отсутствуют, либо аффинны, функция Q (x ) выпукла (вниз), то такая задача называется выпуклой. В выпуклой задаче математического программирования все локальные минимумы являются глобальными.

Если задача математического программирования выпукла и при этом допустимая область D регулярна в точке x* (регулярность области в точке – это свойство, гарантирующее, что условия оптимальности всегда выполняются в этой точке при 0 0 ), то условия теоремы Каруша-Куна-Таккера (а)-(e) будут не только необходимыми, но и достаточными условиями, определяющими точку глобального минимума x*.

Можно указать простые достаточные условия регулярности для двух классов задач.

Условие регулярности Слейтера. Оно применимо только при следующих условиях: g1 ( x),..., g N ( x) выпуклы (вниз), h1 ( x),..., hM ( x) либо отсутствуют, либо аффинны. Если при этих условиях в множестве D из (3.2) существует допустимая точка x, все неравенства в которой выполняются строго, т.е.

g i ( x ) < 0 (i = 1,..., N ), то область D регулярна во всех своих точках.

Из условия Слейтера можно получить следующее удобное следствие.

Если область D задана аффинными ограничениями и D, то D регулярна во всех своих точках.

Для невыпуклого гладкого случая можно использовать достаточное условие регулярности в форме независимости градиентов: если в точке x* активны (т.е. обращаются в равенства) ограничения g i1 ( x* ) = 0,..., gir ( x* ) = 0 и система векторов g i1 ( x* ),..., g ir ( x* ), h1 ( x* ),..., hM ( x* ) линейно независима, то область D регулярна в точке x*.

принять * = 1 (за счет замен множителей Лагранжа), а также не рассматривать альтернативный вариант записи основного градиентного соотношения (d) при * = 0. Для невыпуклых задач даже при регулярности допустимого множества в точке x* условия (а)-(е) остаются лишь необходимыми условиями локального минимума, тогда как для выпуклых задач при наличии регулярности условия (а)-(е) становятся критерием глобального минимума.

Рассмотрим геометрический смысл этих условий при числе переменных n = 2 в случае отсутствия ограничений-равенств ( M = 0 ).

Предположим, что в точке x* активны только два ограничения с номерами 1 и 2 (рис. 3.1 а). Вектора градиентов g1 ( x* ), g 2 ( x* ) для этих ограничений являются внешними нормалями к соответствующим фрагментам границы допустимого множества. В общем случае, если фрагменты границ пересекаются без касания, система этих векторов линейно независима, следовательно, допустимое множество будет регулярно в точке x* и в системе условий Куна-Таккера можно принять * = 1. Из (с)-(е) следует, что если x* – локальный минимум, то при 1 0, * 0. Геометрически это означает, что вектор антиградиента целевой функции в точке x* содержится в замкнутом конусе A( x* ), натянутом на внешние нормали к границам активных неравенств (рис. 3.1 (а)):

В случае дифференцируемости функции Q ( x * ) v = (Q ( x * ), v ).

Поэтому направления ее строгого локального убывания образуют открытый конус B( x* ), показанный на рис. 3.1 (b) где Для локальной оптимальности x* требуется локальная (в окрестности точки x* ) непересекаемость допустимого множества D с конусом B( x* ) направлений строгого локального убывания (после перемещения его вершины в точку x* ). Чтобы это требование было выполнено, необходимо и достаточно, чтобы внутренняя нормаль к границе конуса B( x* ) (такой нормалью является вектор антиградиента функции) не покидала конуса A( x* ), а это означает возможность разложения (3.4) с неотрицательными коэффициентами.

На рис. 3.2 показан пример ситуации, когда в окрестности точки x* возникло пересечение D с B( x* ). При этом в разложении (3.4) окажется 1 > 0, * < 0. Появление отрицательного значения у множителя Лагранжа свидетельствует о возможности строгого уменьшения значения Q( x* ) за счет ухода с фрагмента границы g 2 ( x) = 0 множества D (при этом точка, естественно, не должна покидать допустимое множество).

Рис. 3.1. Показано: (a) – конус при неотрицательных значениях множителей Лагранжа; (b) – конус B( x * ) направлений Рис. 3.2. Порождение допустимого направления v со строгим убыванием функции при нарушении неотрицательности множителя Лагранжа ( 2 < 0 ) При аналитическом поиске решений системы условий Каруша-КунаТаккера (а)-(е) нелинейность уравнений дополняющей нежесткости является фактором, усложняющим решение. Эти уравнения можно исключить, если проводить суммирование по i в (d) только по номерам активных в точке x* неравенств, т.е. по i I ( x* ). Однако множество номеров I ( x * ) активных в точке x* ограничений-неравенств нам неизвестно, поэтому понадобятся гипотезы о его составе: I ( x* ) = J, где J – предполагаемое множество номеров активных неравенств. Система условий (а)-(d) с суммированием в (d) только по i J будет включать замкнутую систему уравнений относительно x*, * и Коррекция предполагаемого набора J должна выполняться с учетом результатов решения системы условий Куна-Таккера, составленной при предыдущей гипотезе относительно I ( x* ). Возможно три основных случая при нарушении условий. В первом случае система может оказаться несовместной, тогда нужно изменить множество J. Во втором случае полученное значение x* может нарушить некоторые из ограничений, которые считались неактивными в точке решения: g i ( x* ) > 0. В этом случае нарушенные ограничения или часть из них следует ввести в число предполагаемых активных, т.е. в множество J. Для этого полагаем J := J I { i}. В третьем случае некоторые из множители случае, показанном на рис. 3.2. При смещении с границ таких ограничений в множество D функция Q (x) будет строго локально убывать (см. рис. 3.2) (для выполнения этого свойства в рассматриваемой точке должно соблюдаться достаточное условие регулярности в форме линейной независимости градиентов), следовательно, при поиске решения задачи неравенства с *i < следует вывести из числа предполагаемых активных, т.е. исключить их из J.

Для этого полагаем J := J \ { j}.

Если же все условия-неравенства * 0, g ( x* ) 0 окажутся выполненными, то в выпуклой регулярной задаче найденная точка x* будет ее глобальным минимумом.

Пример 1. Выпуклая задача Разберем задачу с двумя переменными, в которой нужно найти min( x1 + 19 x2 x1 + 100 x2 ) при следующих ограничениях: x1 1, x2 1, Приведем задачу к стандартному виду, выбрав и проанализируем ее свойства.

Все функции ограничений-неравенств g i 0 ( i = 1, K, 4 ) аффинны, а, значит, выпуклы, поэтому допустимая область D в задаче выпукла. Более того, если взять, например, точку ( x1, x2 ) = ( 2,+2), то эта точка будет допустимой и все неравенства в ней будут выполняться строго. Используя достаточное условие регулярности Слейтера, можно утверждать, что область D будет регулярна во всех своих точках, следовательно, в условиях Куна-Таккера * 0 и его можно принять равным единице.

Для проверки выпуклости функции Q запишем для нее матрицу вторых производных:

Ее главные миноры 1 = 2 > 0, 2 = 400 19 2 > 0.

По критерию Сильвестра матрица положительна определена. Поскольку для выпуклости дважды непрерывно дифференцируемых функций Q (x) необходимо и достаточно неотрицательной определенности этой матрицы, то Q(x) выпукла в R 2. Таким образом, условия Куна-Таккера будут необходимыми и достаточными условиями, определяющими решение задачи.

Выпишем градиенты функций задачи.

Для того, чтобы воспользоваться условиями Куна-Таккера, необходимо принять гипотезу о наборе активных в точке решения ограничений-неравенств.

Предположим вначале, что I ( x* ) = J =, т.е. в точке решения нет активных неравенств. Условия экстремума примут вид Q ( x1, x2 ) = 0, что даст точку (0;0), которая является безусловным минимумом функции Q(x). В ней нарушаются ограничения с номерами 1 и 2, поэтому данная точка не будет являться решением в задаче с ограничениями.

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

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

Включим нарушенные ограничения 1 и 2 в число предполагаемых активных, приняв гипотезу I ( x * ) = J = {1, 2}. Система условий Куна-Таккера будет иметь вид:

На рис. 3.3 приведено взаимное расположение Q, g1 и g 2 в найденной точке (обозначим ее как точку A). Штриховкой и дугой отмечено открытое полупространство направлений строгого локального убывания функции Q в точке (1; 1). Очевидно, что можно, не покидая ограничения g 2 ( x) = 0, уйти с границы g1 ( x) = 0 (соответствующей 1 < 0 ), уменьшив значение Q(x). Поэтому исключим 1-е ограничение из числа активных, т.е.

выполним коррекцию J := J \ { 1}. Это приведет к J = { 2}.

Рис. 3.3. Иллюстрация к решению выпуклой задачи из примера Примем гипотезу I ( x * ) = J = {2}. Получим новую систему условий Куна-Таккера Решая, находим x1 = 19 2 ; x2 = 1; 2 = 19 2 2 + 200 > 0. На рис. 3.3 эта точка обозначена как B.

Эта точка допустимой не является, т.к. в ней нарушаются ограничения с номерами 3 и 4, а именно, g 3 ( x ) = 13 2 и g 4 ( x ) = 7. Одновременно оба включить в число предполагаемых активных нельзя, поскольку система из трех равенств окажется несовместной.

В рассматриваемом простом примере можно достаточно точно построить линии равного уровня функции Q ( x) = C. Они, очевидно, будут эллипсами с центрами в точке безусловного минимума (0; 0) и повернутыми по отношению к координатным направлениям x1, x2 осями. Такое построение позволило бы точно предсказать, какое из нарушенных неравенств действительно активно в точке решения. Однако мы не будем прибегать к подобному анализу. Более того, при дальнейших вычислениях не будем использовать также информацию о взаимном расположении границ 3-го и 4-го ограничений, вытекающую из рис. 3.3.

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

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

Применим указанный подход к нашей задаче. Вычислим расстояния от точки B до границ нарушенных ограничений. Разделим значения функций 3-го и 4-го ограничений в этой точке на нормы их градиентов, т.е. на 2 и 5, соответственно. Поскольку при x = B значения соотносятся так:

g 3 ( x ) / 2 = 13 8 > g 4 ( x ) / 5 = 7 5, то предполагаемым активным будем считать 3-е ограничение.

Примем гипотезу I ( x * ) = J = {2,3}. Система условий примет вид:

В результате получаем x1 = 5, x2 = 1, 2 = 96 > 0, 3 = 9 > 0. Остальные ограничения в найденной точке выполняются, следовательно, x * = ( 5; 1) является глобальным минимумом задачи; Q ( 5; 1) = 600.

Рассмотрим еще один пример, в котором минимизируемая функция не является выпуклой.

Пример 2. Невыпуклая задача Пусть требуется найти глобальный минимум в задаче:

Допустимая область D задана линейными ограничениями (равенствами и неравенствами) и является выпуклой. Более того, нетрудно подобрать такую допустимую точку, например, x1 = 1, x2 = 1, x3 = 1, что неравенства выполняются строго, следовательно, для области D выполнено достаточное условие регулярности Слейтера. Поскольку все ограничения в задаче аффинны, можно было для выяснения вопроса о регулярности воспользоваться не самим условием Слейтера, а следствием из него для областей такого вида. Тогда было бы достаточно установить только непустоту множества D. Это значит, что в условиях Каруша-Куна-Таккера всегда можно считать 0 = 1.

Матрица Гессе имеет вид:

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

Запишем ее характеристический полином относительно переменной p :

p 3 p. Подсчитав собственные числа, видим, что p1 = 0, p2,3 = ±1.

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

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

В рассматриваемой задаче для упрощения решения можно, используя связь x 2 + x3 = 2, исключить x2 из ограничений. Тогда задача примет вид:

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

Проведем исследование. Область D2 неограниченна. Изучим поведение функции вдоль прямых области. Введем вектор = (1; 1), направленный вдоль этих прямых. Функция Q(x) имеет по направлению положительную вторую производную, поскольку Отсюда и из квадратичного вида функции Q (x ) следует существование конечного минимума в задаче, поскольку на бесконечности функция будет возрастать равномерно по параметру c.

Исследуем границу x3 x1 = 1. Система условий Куна-Таккера примет вид:

1 – множитель Лагранжа. Они выполняются при x1 = 0.5, x3 = 0.5, где 1 = 0.5. Значение функции равно 0.25 (точка A на рис. 3.4).

Исследуем границу x1 x3 = 2. Для нее имеем следующую систему необходимых условий локального минимума:

Они выполняются при x1 = +1, x3 = 1, 1 = 1 (точка B на рис. 3.4).

Значение функции равно 1, т.е. меньше, чем в первой найденной точке.

Следовательно, глобальный минимум вспомогательной задачи достигается в точке x1 = 1, x3 = 1, а для исходной задачи — в точке x1 = 1, x2 = 3, x3 = 1.

Рис. 3.4. Структура задачи на линейном многообразии, порожденном ограничениемравенством (стрелками показаны направления возрастания функции) Дополнительный материал и задачи по данному разделу можно найти в литературе [5, 8-16].

3.2. Контрольные задания 1. Используя теорему Лагранжа, определить глобальный минимум в задачах: (a) min x2 x1 3 : x1 + x2 = 1 ; (b) min x1 + ( x2 1)2 + x3 : x D, Начертите на плоскости ( x1, x2 ) вид области D. В ее угловых точках постройте внешние нормали к границам, а также вектор Q (x). Используя геометрическую трактовку условий Куна-Таккера, ответьте на вопрос: может ли точка глобального минимума располагаться в одной из вершин? На основе полученных результатов сделайте выводы о возможном положении точки условного минимума. Проверьте Ваши предположения с помощью теоремы Куна-Таккера, найдите решение.

3. Используя геометрические представления, укажите точку минимума в задаче min{x2 : x1 + x2 1; x1 + x2 0; x1 + x2 0}.

Обоснуйте полученные результаты с помощью условий Куна-Таккера.

4. Проверьте выполнение условий Куна-Таккера в точках (0;2), (0;0), ( 2 ;0), (1;0), (0.05;0) для задачи: min { 10 x1 + 5 x2 x1 + 2 x2 10 : x D}, 5. Найдите расстояние от начала координат до выпуклого множества D = {x R 2 : x1 x2 4; x1 0}. Обоснуйте результат с использованием теоремы Куна-Таккера.

D = {x R 2 : x1 + x2 4; 2 x1 + x2 5}. Дайте геометрическую трактовку условиям неотрицательности множителей Лагранжа.

Указание: Решите задачу, рассмотрев четыре возможных случая относительно множества I ( y ), содержащего номера неравенств, на границе которых находится проекция точки y : I ( y ) =, { }, {2}, {, 2}.

множества:

(b) шар 8. Найдите минимум функции при ограничениях x1 - x2 - 3, - x1 + 5 x2 15, 0 x1 5.

Как изменится решение, если добавить ограничение-равенство x1 + x3 = 1? Как изменится решение, если кроме ограничения-равенства добавить еще одно дополнительное неравенство: 10 x2 x1 1 ?

9. Проверьте выпуклость и регулярность области 0 x2 x1 }. Найдите решение задачи: min{x1 + x2 + 4 x1 2 x2 : x D}.

Указание: если предположить, что активно одно ограничение x2 x1, то может возникнуть проблема с аналитическим определением значения множителя Лагранжа. Попробуйте оценить его знак без явного вычисления.

10. На классе гладких задач исследовать область D на регулярность, используя достаточные условия и определение регулярности области в точке.

Ваши выводы, если из описания области D исключить последнее неравенство 11. Найдите решения следующих задач:

12. Найдите минимум функции x1 x1 x2 + 2 x2 4 x1 5 x2 + x3 при ограничениях x1 + 2 x2 + x3 6, x1 2, x1 0, x2 0.

13. Решите задачу min{ x1 + 2x2 +6x3 2x1x2 4x2 x3 13x1 22x при ограничениях x1 + x2 + x3 2, x1 + 2 x2 + x3 3, 4 x1 + 6 x2 + x3 5, 14. Найдите минимум функции x1 + x 2 10 x1 8 x 2 в пространстве 2 x1 + x2 + x3 = 6.

15. На допустимом множестве, заданном следующими ограничениями:

определения минимума функции 24x1 + x2 + 4 x3 8x1x3 12x3 + 36x1 x2.

16. Найдите глобальный минимум в задаче ограничениях x3 0.5 x1 1, x1 + 5 x3 10, 5 x1 8, x1 + x2 = 1.

18. С использованием теоремы Куна-Таккера докажите, что из всех треугольников с общим углом при вершине и заданной суммой длин боковых сторон равнобедренный треугольник имеет наименьшее основание.

19. В углах прямоугольной заготовки с размерами A на B вырезают квадраты с размерами x на x. Из оставшейся части собирают коробку.

Определите значение x, при котором объем коробки максимален.

20. Найдите разложение положительного числа R на N вещественных сомножителей так, чтобы их сумма была минимальной.

21. Рассмотрите задачу о ритмичности производства (задачу № 11 из раздела 1), предполагая, что сырье не является штучным, т.е. значения xi не целочисленны. Решите задачу при следующих значениях параметров: N = 5, 22. Найдите глобальные минимумы в задаче:

23. Решите задачу определения глобальных минимумов функции x1 + x2 2 x1 x3 при следующих ограничениях: 1 x1 x3 2 x1, x1 = x2 x3.

24. Найдите глобальный минимум в задаче: min{x1 + 2 x2 x3 x3 : x D} D = {x R 4 : x1 + x4 = 4, x2 + x3 = 8, x1 0, x2 0, x3 0}. Обоснуйте его единственность.

25. Найдите глобальный минимум функции x1 x1 x3 x3 + x2 x3 на D :

26. Обосновать существование глобального минимума и найти его в задаче min 3x2 + 3x3 + 2x1x2 10x2 14x3 : x D, где допустимое множество 27. Найти глобальный минимум, обосновав его существование, в задаче:

4. Вычислительные методы математического программирования 4.1. Основные понятия Вычислительным методам решения задач математического программирования посвящена обширная литература [8-11, 13, 17, 18, 19].

В общем случае задача математического программирования представима в виде:

где E - множество простой геометрической структуры, например, E = R n или E = {x : ai xi bi, i = 1, K, n}. Постановка (4.1)-(4.2) зависит от набора функций, представимого вектор-функцией f = (Q, g1, K, g N, h1, K, hM ).

Вычислительный метод должен строить для задачи (4.1)-(4.2) оценку решения e k (интервальную или точечную) по координатам или по значению функции, проводя испытания функций f в точках x 0, x1, K, x k. Результат испытания J k = J ( x k, f ) включает значение функции f k = f ( x k ), а также может включать значение ее частных производных до порядка p (обычно p = 1 или p = 2 ). Значение p называют порядком испытания, например, результат испытания первого порядка имеет вид J k = ( f k, f k ), а второго – J k = ( f k, f k, 2 f k ). Результаты испытаний, проведенных за k шагов, образуют множество поисковой информации k = { ( x s, J s ) : s = 1, K, k }.

Вычислительный метод (или алгоритм) решения задачи (4.1)-(4.2) строится исходя из имеющейся априорной информации о свойствах функций f и представляет набор правил = Pk (k ), Ek (k ), M k (k ), k = 0,1, K Они определяют выбор точки следующего испытания x k +1 = Pk (k ), текущую ( k = 0 - нет останова, k = 1 - останов).

Одним из принципов построения методов оптимизации является принцип наилучшего гарантированного результата. Он может быть использован, если для класса решаемых задач = { f } и выбранного класса алгоритмов A = { } можно ввести функцию эффективности d (, f ), показывающую, насколько удачным было применение к задаче f. Например, значение d можно трактовать как меру остаточной погрешности в оценке решения задачи f с использованием метода.

Функцию d * ( ) называют гарантированной эффективностью метода соответственно, если Заметим, что оптимального метода может не существовать, но -оптимальный всегда существует.

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

Пусть метод уже выполнил k испытаний, результаты которых запомнены в виде поисковой информации k. Обозначим через k апостериорный класс функций Таким образом, в классе k содержатся те функции из исходного класса, результаты испытаний которых во всех точках x s уже проведенных испытаний совпадают с имеющимися результатами J s этих испытаний. Функции из k неразличимы по результатам испытаний в точках x s ( s = 1, K, k ).

Пусть функция d (k ) описывает эффективность проведенных испытаний. Гарантированной эффективностью очередного испытания в точке x называют Говорят, что метод последовательно оптимален на один шаг вперед (одношагово оптимален), если выбор следующего испытания подчиняется условию Если нижняя грань в определении x k +1 не достигается, используют значение x, обеспечивающее ее -приближение.

4.2. Поиск минимума унимодальной функции на Пусть u - класс функций Q, унимодальных на отрезке [a, b] R1: они должны иметь на этом отрезке единственный глобальный минимум (обозначим его x* ) и строго убывать на [a, x* ], а на [ x*, b] – строго возрастать. Унимодальные функции не обязаны быть непрерывными. Их испытания включают только измерения значений функции.

Пусть методом проведено N измерений в точках a < x1 < K < xN < b с результатами Qk = Q( x k ) и k * (Q ) = arg min{Qk : k = 1, K, N }, где под « arg min » понимается номер испытания с наименьшим значением. Тогда Заметим, что здесь под x0 и xN +1, по определению, понимаются точки a и b, в которых измерения не проводятся. Данный интервал является оценкой решения, т.е. e N = [ xk * (Q ) 1, xk * (Q ) +1 ]. Эффективность выполненных измерений можно оценить длиной этого интервала. Заметим, что в общем случае не только номер k * (Q ), но и координаты самих точек измерений xk зависят от функции Q.

N -шаговые пассивные методы N проводит ровно N измерений, то такой метод называют N -шаговым. Если для метода N правила Pk выбора точек испытаний не зависят от накопленной поисковой информации k, то метод называют пассивным. Пассивный N -шаговый метод N полностью определяется набором точек измерений a < x1 < x2 < K < x N < b, положение которых не зависит от минимизируемой функции. Для таких методов функцию эффективности можно принять в виде гарантированная эффективность на классе Q u примет вид Это позволяет построить для каждого N оптимальные или оптимальные пассивные алгоритмы, гарантированная эффективность которых (b a ) ( N 2 + 1) + для четных N. Для этих методов степень сокращения исходного интервала невысока за счет пассивного характера поиска.

Последовательные методы могут обладать лучшей эффективностью.

Метод дихотомии – неоптимальный последовательный метод Это простой последовательный метод, позволяющий сокращать интервал поиска в два раза с использованием каждых двух новых измерений. Первое измерение не приводит к сокращению интервала. Данный метод не является ни оптимальным, ни -оптимальным.

Описание алгоритма (a) Задать > 0 – точность решения.

(c) Пока b a >, выполнять пункт (d), иначе – перейти на пункт (e).

Используя измерения функции в трех точках x, c и y ( a < x < c < y < b ), в зависимости от того, какое из трех значений Qx, Qc, Qy меньше, установить новые значения: если наименьшим было Qx, то b := c, c := x, Qc := Qx ; если наименьшим было Qc, то a := x, b := y ; если наименьшим было Qy, то a := c, c := y, Qc := Qy (рис. 4.1). Вернуться на пункт (c).

(e) Полученный интервал [a, b] принять в качестве интервальной оценки решения.

Гарантированная эффективность метода дихотомии за N измерений d * ( дих ) = (b a) 2( N 1) 2 ( N всегда нечетно).

Рис. 4.1. Один из трех возможных случаев сжатия интервала поиска в методе дихотомии Метод золотого сечения и метод Фибоначчи Рассмотрим методы, которые для очередного сжатия интервала поиска используют только одно новое измерение (кроме начального этапа, требующего проведения сразу двух измерений). Исходя из симметрии задачи, первые два измерения в точках x2 и y2 целесообразно размещать симметрично относительно центра интервала, а на вновь образованных интервалах новое измерение проводить в точке, симметричной точке прежнего измерения, существующей внутри интервала (рис. 4.2).

Обозначим через k доли, составленные длинами соответствующих частей текущего интервала по отношению к его собственной длине. Из рис. 4. вытекает следующая их взаимосвязь:

Рис. 4.2. Размещение точек измерений в симметричном методе Метод золотого сечения использует постоянную пропорцию деления k = = ( 5 1) 2, полученную как стационарное решение уравнения (4.3).

Описание алгоритма (a) Задать > 0 - точность решения.

построить новую точку x = b (b a ).

(c) Пока b a >, выполнять пункт (d), иначе – перейти на пункт (e).

(d) Провести измерение в новой точке ( x или y ) и запомнить результат (в Qx или Q y ). Если Qx < Q y, то положить b := y, y := x, Q y := Qx и выбрать новую точку x = b (b a) ; иначе, при Qx > Q y, положить a := x, x := y, Qx := Q y и выбрать новую точку y = a + (b a ). Вернуться к пункту (c).

(e) полученный интервал [ a, b ] принять в качестве интервальной оценки решения.

Гарантированная эффективность метода золотого сечения за N Метод Фибоначчи построен американцем Дж. Кифером (J. Kiefer) в году и назван в честь использованной в нем последовательности чисел ным на множестве AN всех последовательных N -шаговых методов для класса унимодальных функций u.

Метод Фибоначчи обладает симметрией при размещении всех точек измерений, кроме последнего N -го. На всех итерациях используются оптимальные пропорции * в размещении точек, удовлетворяющие (4.3) и подобранные из условия наилучшего гарантированного сжатия исходного интервала за N измерений. Значения * = FN k +1 FN k + 2.

* = 1 2, что не позволяет разместить последнее измерение симметрично к имеющемуся (в силу * = 1 2 оно обязательно окажется в центре текущего интервала), поскольку это вызвало бы наложение двух точек измерений. Чтобы избежать повторного вычисления в имеющейся точке, последнее измерение смещают от него на малое > 0.

Гарантированная эффективность метода Фибоначчи d * ( N ) = Фиб = (b a) FN + < d * ( N ) при достаточно малом. Известно, что при N гарантированная эффективность метода золотого сечения достаточно близка к эффективности метода Фибоначчи, а именно FN (1 ) N 1 1.17 при N. Это соотношение выполняется уже начиная с семи измерений.

Для применения метода Фибоначчи необходимо заранее определить значение N. При решении задачи с заданной точностью > 0 величину N вычисляют, исходя из условия d * ( N ).

Описание алгоритма (a) Задать > 0 - точность решения и, 0 < Q y, положить a := x, x := y, Qx := Q y, провести новое испытание вернуться к пункту (d).

(f) Если Qx < Q y, то положить b := y, y := x, Q y := Qx и провести новое испытание в точке x = y, Qx := Q ( x ) ; иначе, при Qx > Q y, положить a := x, x := y, Q x := Q y, провести новое испытание y = x +, Q y := Q ( y ). Положить k = N, перейти на пункт (g).

(g) Если Qx < Q y, положить b := y, иначе, при Qx > Q y, положить a := x. Принять интервал [ a, b] в качестве интервальной оценки решения.

Иллюстрация размещения точек испытаний для метода Фибоначчи приведена на рис. 4.3.

Рис. 4.3. Сокращение интервала и размещение испытаний в методе Фибоначчи на первых итерациях при N = 6 для некоторого варианта значений функции (указаны доли длин 4.3. Поиск минимума выпуклой дифференцируемой Пусть в точке x s проведено испытание первого порядка функции Q с вычислением Qs и Qs. Используя критерий выпуклости дифференцируемой функции, получим оценку снизу в виде Q ( x ) Qs + ( Qs, x x s ). Если проведено k испытаний, оценка принимает вид Q ( x ) Qk ( x ), где Пусть для выпуклой дифференцируемой функции Q поставлена задача с ограниченной допустимой областью, описанной системой линейных неравенств:

Описание алгоритма (a) Задать > 0 - точность поиска по значению функции.

испытания и положить k = k0.

(c) Получить очередную точку x k +1 = arg min { Qk ( x ) : Ax b }.

(d) Проверить критерий останова: вычислить Qk = min{ Qs : s = 1,..., k } - текущую оценку глобально-оптимального значения. Если Qk Qk ( x k +1 ), остановить вычисления и перейти к пункту (f), иначе – к пункту (e).

(e) Провести испытание в точке x k +1 : Qk +1 = Q( x k +1), Qk +1 = = Q( x k +1 ). Увеличить счетчик k := k + 1 и вернуться к пункту (c).

(f) В качестве оценки решения принять точку xk { x1, K, x k }, для которой Q ( xk ) = Qk.

Замечание: выбор точки x k +1 в пункте (c) алгоритмически сводится к решению задачи линейного программирования в пространстве векторов 4.4. Поиск локального минимума в задачах без ограничений локальной оптимизации имеют вид итерационных процедур где d k - направление шага, определяемое по результатам испытаний J k в основных точках поиска x k, а t k - скалярный шаговый множитель [8-10], [13, 17, 18]. Его величина определяется с использованием дополнительных испытаний, порядок которых может быть ниже, чем у основных.

Критерии и алгоритмы выбора шагового множителя Функцию Q будем считать по крайней мере гладкой, а d k – направлением ее строгого локального убывания в точке x k.

Критерий 1 (существенности убывания функции):

Критерий 2 (близость к минимуму по направлению):

Критерии 2 и 3 используются совместно с критерием 1. Ниже приведено алгоритмическое описание трех способов выбора шагового множителя: правило Армихо, правило одномерной минимизации и правило Вулфа.

Правило Армихо (a) Задать параметры:, 0 < < 1 - параметр критерия 1; > 0 начальное значение шагового множителя;, 0 < < 1 - коэффициент сжатия.

(d) При первом выполнении условия t 1 ( ) принять t k = t.

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

Правило одномерной минимизации Согласно этому правилу, выбор t k должен удовлетворять требованию 0 < < < 1. Выбор подходящего t k происходит в два этапа. На первом этапе определяется отрезок [0, T ], содержащий точку t * первого локального минимума функции (t ) = Q ( x k + t d k ) на луче t 0. На втором этапе, в предположении унимодальности функции (t ) на [0, T ], выполняется процедура поиска ее минимума (например, методом золотого сечения) до первого обнаружения значения t, удовлетворяющего заданным условиям.

Этап 1. Сканирование луча с удвоением шага (a) Задать начальное значение шага 0 < t или (t ) > 0, если значение производной вычисляется), то положить T = t и завершить этап 1; иначе положить t := t, t := t и вернуться к пункту (b).

Этап 2. Минимизация на [0, T ] с целью определения t k (b) Выполнить одним из методов поиск минимума (t ) на отрезке [0, T ], считая ее унимодальной, до момента первого испытания в точке t 1 ( ) 2 ( ), после чего поиск остановить.

Правило одномерной минимизации требует вычисления градиента функции для каждого t, проверяемого на этапе 2. Это может приводить к гораздо большим затратам, чем при использовании правила Армихо. Однако выбор t k по правилу одномерной минимизации (по крайней мере при 1 – коэффициент «экстраполяции». Положить t = и = = 0.

(b) Если t 1 ( ) 3 ( ), перейти к пункту (e), иначе – к пункту (c).

(c) Если t 1 ( ), положить a = t и перейти к пункту (d), иначе, если t 2 ( ), положить a = t. Если при этом a 0, перейти к пункту (d), а при a = 0 выполнить «экстраполяцию», положив t := a r и вернуться к пункту (b).

(d) Выполнить «интерполяцию»: t := + (1 ) и вернуться к пункту (b).

Методы безусловной локальной оптимизации Методы градиентного поиска К этой группе относятся методы, использующие итерационное соотношение (4.4), в котором направление шага d k = Qk. Шаговый множитель может выбираться по любому из трех указанных выше правил:

Армихо, одномерной минимизации или Вулфа. Сходимость градиентного поиска к стационарной точке функции Q обеспечивается во всех случаях из любой начальной точки при весьма слабых требованиях на Q. Если используется правило одномерной минимизации в варианте «аккуратного»

одномерного поиска ( 0, что Таким образом, обеспечивается сходимость со скоростью геометрической прогрессии, при этом величины x k +1 x * и x k x * имеют одинаковый порядок малости. Такая сходимость называется линейной. В качестве критерия останова в градиентных методах обычно используют условие Qk +1.

Метод Ньютона и его модификации Метод Ньютона предполагает, что функция Q по крайней мере дважды непрерывно дифференцируема. Проводятся испытания второго порядка J k = Qk, Qk, 2Qk. Точка x k +1 размещается в стационарной точке квадратичной аппроксимации, построенной по результату k -го испытания.

Шаговый множитель выбирается равным единице, т.е. t k = 1. В методе Ньютона где d ньют определяют из решения линейной системы В явной форме Однако при вычислениях этот вид записи не применяется, за исключением одномерного случая ( n = 1 ), когда Сходимость метода Ньютона к стационарной точке обеспечивается для функций Q C 2 ( R n ) при условии det ( 2Q ( x* ) ) только лишь в некоторой окрестности x *. Сходимость является сверхлинейной, т.е. x k +1 x* = o( x k x* ), следовательно, ошибка убывает быстрее, чем любая геометрическая прогрессия. Если у функции существуют третьи производные и они ограничены в области сходимости, то сходимость по крайней мере квадратична, т.е. существует C 0 такая, что с некоторого шага Расширение области сходимости метода Ньютона может быть достигнуто за счёт введения шагового множителя t k, выбираемого по правилу Армихо, Вулфа или одномерной минимизации. В первых двух случаях следует выбирать значения параметра = 1.

Заметим, что в методе Ньютона направление d ньют будет являться направлением локального убывания только в случае выполнения очевидного условия ( ( 2Qk ) 1 ( Qk ), Qk ) < 0. Оно может нарушаться, если матрица 2Qk не будет являться положительно определённой, что говорит о нарушении выпуклости функции. Таким образом, для невыпуклых функций метод Ньютона (для возможности регулировки шагового множителя) должен быть модифицирован путем замены матрицы 2Qk на близкую к ней положительно определённую. Обычно для этого используется модифицированное преобразование Холесского [18].

В качестве основного критерия останова в методе Ньютона используется останов по малости нормы градиента: Qk.

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

Описание метода (a) Задать > 0 – параметр останова, 0 < < < 1 – параметры одномерной минимизации, x 0 - начальную точку.

(c) Если (Qk, p k ) 0 (т.е. p k – не направление строгого локального убывания), то выполнить замену p k = Qk, x 0 = x k и положить k = 0 ;

иначе не изменять p k.

(d) Принять d k = p k и определить шаговый множитель t k по алгоритму «аккуратной» одномерной минимизации, вычислить Qk +1 = Q ( x k +1 ), Qk +1 = Q ( x k +1 ), увеличить счетчик k := k + 1.

(e) Проверить критерий останова: при Qk остановить вычисления и принять за оценку решения x k. При Qk > перейти к пункту (f).

пункту (d); иначе определить где Укажем на некоторые дополнительные свойства метода в случае его применения к квадратичной функции Q (x) с положительно определенной матрицей Гессе 2Q = A. Для таких функций метод строит систему направлений p 0, p1, K, p N 1, которая будет являться A-сопряженной, т.е.

i j ( pi, A p j ) = 0 при нетривиальности самих векторов. При этом глобальный минимум квадратичной функции будет найден (если не учитывать критерий останова) не более, чем за N шагов (где N – размерность пространства переменных x ), а система градиентов Q0, Q1, K, QN окажется взаимно ортогональной.