ПРАКТИЧЕСКИЕ ЗАНЯТИЯ Гладкие конечномерные экстремальные задачи с ограничениями типа равенств

Шатина А.В.

МЕТОДЫ ОПТИМИЗАЦИИ

ПРАКТИЧЕСКИЕ ЗАНЯТИЯ

Данное учебное пособие создано на основе семестрового курса «Методы оптимизации», читаемого студентам третьего и четвертого курсов МИРЭА(ТУ), обучающимся по специальностям «Прикладная математика», «Прикладная математика и информатика», «Информационные системы и технологии».

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

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

Пособие предназначено для студентов, аспирантов и преподавателей.

 

СОДЕРЖАНИЕ

 

Занятие 1. Занятие 2. Занятие 3. Занятие 4. Занятие 5. Занятие 6. Занятие 7. Занятие 8. Занятие 9. Занятие 10. Занятие 11. Занятие 12. Занятие 13. Занятие 14.	Гладкие конечномерные задачи без ограничений ......................................................................... Гладкие конечномерные экстремальные задачи с ограничениями типа равенств .................... Гладкие конечномерные экстремальные задачи с ограничениями типа равенств и неравенств .................................................................... Элементы выпуклого анализа. Выпуклые задачи ....................................................................... Графический метод решения задач линейного программирования ............................................... Симплекс–метод решения задач линейного программирования ............................................... Транспортная задача ........................................... Простейшая задача классического вариационного исчисления ................................................... Задача Больца ....................................................... Изопериметрическая задача ............................... Задача с подвижными концами .......................... Задача Лагранжа .................................................. Задача оптимального управления ...................... Задача оптимального управления (продолжение) ........................................................................ Ответы к задачам для самостоятельного решения.................................................................. Список литературы ..............................................

 

 

Занятие 1. Гладкие конечномерные задачи без ограничений.

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

В пространстве вводятся операции сложения и умножения на число:

,

.

Расстояние между элементами в вводят следующим образом: . Это расстояние называют евклидовым. Если в ввести норму элемента по формуле , то .

Постановка задачи состоит в нахождении экстремума функции :

.

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

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

. ▲

Теорема 1. (Необходимые условия локального экстремума 1‑го порядка)

Если – точка локального экстремума функции переменных и функция дифференцируема в точке , то

. ■

Точки , в которых , называются стационарными.

Теорема 2. (Необходимые условия локального экстремума I‑II порядка)

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

Теорема 3. (Достаточные условия локального экстремума I-II порядка)

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

1) ,

2) и некотором , то . ■

Условие 2) теоремы 3 является условием положительной (отрицательной) определенности квадратичной формы с матрицей . При практическом применении теоремы 3 возникает вопрос, будет ли квадратичная форма положительно или отрицательно определенной. Критерием положительной (отрицательной) определенности квадратичной формы является критерий Сильвестра.

Критерий Сильвестра. Квадратичная форма положительно определена все главные миноры матрицы положительны:

Квадратичная форма отрицательно определена . ■

Теорема 4. (Достаточные условия локального экстремума I-II порядка для функции двух переменных)

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

а) Если , то ;

б) если , то ;

в) если , то ;

г) если , то требуется дополнительное исследование.

■

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

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

Следствие. Если функция непрерывна на и , то она достигает своего абсолютного минимума (максимума) на любом замкнутом подмножестве пространства . ■

Пример 1. .

Выпишем необходимые условия локального экстремума 1‑го порядка:

 

Решая полученную систему уравнений, находим стационарные точки:

.

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

.

Для точки :

.

Для точки :

.

Для точки :

.

Для точки :

.

Далее,

при ;

при .

Поэтому .

Ответ: ;;

. ●

Пример 2. .

Необходимые условия локального экстремума 1-го порядка имеют вид:

Решая полученную систему уравнений, найдем стационарные точки: , .

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

С помощью теоремы 4 проведем исследование полученных стационарных точек.

Для точки имеем:

.

Для точки имеем:

критерий Сильвестра не дает ответа на вопрос об экстремуме функции .

Рассмотрим окрестность точки в пространстве . При имеют место соотношения:

.

Откуда следует, что .

Для решения вопроса об абсолютном экстремуме, вычислим предел . Перейдем к полярным координатам: . Тогда

Согласно следствию теоремы Вейерштрасса , .

 

Ответ: ; . ●

 

Пример 3. .

Необходимые условия 1-го порядка имеют вид:

Решая полученную систему алгебраических уравнений, находим стационарные точки:

.

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

.

В точке :

.

В точке :

.

Для точек :

требуется дополнительное исследование.

Рассмотрим точки из окрестности токи . Здесь - вещественные числа произвольного знака, сколь угодно малые по модулю. Тогда

.

Если , то , следовательно, и .

Если , то . Так как , а может быть как отрицательным, так и положительным, то и .

Если , то , следовательно, и .

Если , то

.

Так как , а может быть как отрицательным, так и положительным, то.

Если , то , следовательно, и .

Покажем, что :

при , при .

Ответ: ;

при и ;

при ;

. ●

 

Задачи для самостоятельного решения.

1.2. . 1.3. . 1.4. .

Занятие 2. Гладкие конечномерные экстремальные задачи с ограничениями типа равенств.

Постановка задачи:

, (1)

где функции переменных определены и непрерывно дифференцируемы в некоторой области (т.е. и определены и непрерывны в ).

Определение. Точки , удовлетворяющие условиям ,называются допустимыми по ограничению в задаче (1). ▲

Определение. Говорят, что допустимая точка доставляет в задаче (1) локальный минимум (локальный максимум): (), если такое, что для любой допустимой точки , удовлетворяющей условию , выполнено неравенство . ▲

Определение. Функция , где , называется функцией Лагранжа задачи (1), а числа - множителями Лагранжа. ▲

Теорема 1. (Необходимое условие локального экстремума 1‑го порядка)

1) Пусть - точка локального экстремума в задаче (1), а функции непрерывно дифференцируемы в этой точке. Тогда существует ненулевой вектор множителей Лагранжа такой, что для функции Лагранжа задачи (1) выполняется условие стационарности по :

. (2)

2)Для того, чтобы , достаточно, чтобы векторы были линейно независимы. ■

Определение. Допустимые точки , в которых выполнены условия (2), называются стационарными. ▲

Теорема 2. (Необходимые условия локального экстремума I‑II порядка)

Пусть 1) ;

2) ;

3) система векторов линейно независима (условие регулярности).

Тогда существует вектор множителей Лагранжа такой, что для функции Лагранжа задачи выполнены условия:

а) стационарности: ;

б) неотрицательной (неположительной) определенности квадратичной формы

для всех , удовлетворяющих условию . ■

Теорема 3. (Достаточные условия локального экстремума I-II порядка)

Пусть 1) ;

2) система векторов линейно независима (условие регулярности);

3) существует вектор множителей Лагранжа такой, что для функции Лагранжа задачи выполнены условия:

а) стационарности: ;

б) положительной (отрицательной) определенности квадратичной формы

для всех и удовлетворяющих условию . Тогда

. ■

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

 

Для решения задач с ограничениями типа равенств следует:

1) Составить функцию Лагранжа .

2) Найти стационарные точки из системы уравнений

 

(3)

3) Найти решение среди стационарных точек или доказать, что решения нет.

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

Замечание 1. Для определения и из системы (3) получается уравнений с неизвестными. Множители Лагранжа определяются с точностью до пропорциональности. Следует отдельно рассмотреть случаи и . Если , то, умножив все множители Лагранжа на одно и то же число, можно добиться, например, равенства . Тогда число уравнений сравняется с числом неизвестных.

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

Пример 1. .

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

.

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

Нетрудно убедиться, что эта система уравнений решений не имеет.

Если же , то система (3) принимает вид:

Откуда получаем . ●

Пример 2. .

Решение. Составим функцию Лагранжа .

Найдем стационарные точки из системы уравнений:

1) Если , то из первых двух уравнений системы получим , что противоречит третьему уравнению связи.

2) Положим . Тогда

.

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

Ответ:

. ●

 

Пример 3. .

Решение. Составим функцию Лагранжа .

Найдем стационарные точки:

1) Если , то из первых двух уравнений системы получим , что противоречит последнему условию системы.

2) Положим . Тогда

Получена одна стационарная точка . Заметим, что . Действительно, возьмем две последовательности допустимых точек . Тогда

при ,

при .

Следовательно, найденная стационарная точка может доставлять в задаче только локальный экстремум. Проведем непосредственную проверку. Рассмотрим допустимые точки из окрестности этой точки . Из уравнения связи получим:

.

Тогда при достаточно малом по модулю

.

Откуда следует, что является точкой локального минимума в поставленной задаче.

Ответ: . ●

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

Пример 4. .

Решение. Составим функцию Лагранжа

.

Найдем стационарные точки из системы уравнений:

 

 

Если , то из третьего уравнения получаем . Тогда из первого и второго уравнения получим , что противоречит ограничениям задачи.

Положим . Тогда из первых трех уравнений системы получим: . Подставим эти значения в четвертое и пятое уравнения системы:

.

Получаем следующие стационарные точки:

при ;

при ;

при ;

при .

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

;

.

Для точки имеем:

.

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

Для точки имеем:

;

.

Следовательно, .

Для точки имеем:

;

.

Следовательно, .

Для точки имеем:

.

Следовательно, .

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

.

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

Ответ:

;

;

. ●

 

Задачи для самостоятельного решения.

2.2. . 2.3. . 2.4. .

Занятие 3. Гладкие конечномерные экстремальные задачи с ограничениями типа равенств и неравенств.

Постановка задачи:

, (1)

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

Определение. Множество

называется множеством допустимых точек задачи (1). ▲

Определение. Говорят, что допустимая точка доставляет в задаче (1) локальный минимум, и пишут , если такое, что для любой допустимой точки , удовлетворяющей условию , выполнено неравенство . ▲

В задачах, имеющих ограничение в виде неравенств, важно, является ли рассматриваемая задача задачей на минимум или задачей на максимум. Задачу на максимум можно свести к задаче на минимум:

.

Определение. Функция , где , называется функцией Лагранжа задачи (1), а числа - множителями Лагранжа. ▲

Теорема. (Необходимые условия локального минимума 1-го порядка)

Пусть - точка локального минимума в задаче (1), а функции непрерывно дифференцируемы в некоторой окрестности этой точки. Тогда существует ненулевой вектор множителей Лагранжа такой, что выполняются условия:

а) стационарности функции Лагранжа:

;

б) дополняющей нежесткости:

;

в) неотрицательности:

. ■

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

Определение. Допустимые точки , в которых выполняются условия а), б), в), называются критическими. ▲

 

Для решения задач вида (1) с ограничениями типа равенств и неравенств следует:

1) Составить функцию Лагранжа .

2) Найти критические точки из системы уравнений и неравенств:

(2)

При этом следует рассмотреть отдельно два случая: и . В случае положить равным единице или другой положительной константе.

3) Провести исследование полученных решений системы (2).

Замечание. Если требуется найти все экстремумы функции, то следует сначала решить задачу на минимум, а затем решить задачу на максимум, сведя ее к задаче на минимум.

Пример 1.

.

Решение. Составим функцию Лагранжа

Найдем критические точки из системы уравнений и неравенств:

 

 

1) Если , то из первых трех уравнений системы получим , что противоречит последнему неравенству системы.

2) Положим . Получим следующую систему для нахождения критических точек:

(3)

 

Рассмотрим два варианта выполнения условия дополняющей нежесткости (четвертого уравнения в системе (3)):

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

2.2) . Тогда получим следующую систему уравнений:

Из первых трех уравнений системы выразим через :

.

Подставив эти значения в четвертое и пятое уравнения системы, получим . Найденное значение противоречит условию .

Заметим, что множество

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

Ответ: . ●

 

Пример 2.

,

.

Решение. Составим функцию Лагранжа

.

Найдем критические точки из системы уравнений и неравенств:

(4)

1) Если , то из первых трех уравнений системы получим , , т.е. все множители Лагранжа обращаются в ноль.

2) Положим . Рассмотрим четыре варианта выполнения условий дополняющей нежесткости).

 

2.1) . Подставляя эти значения и в первые три уравнения системы (4), получим несовместную систему уравнений:

 

2.2) . Тогда

Таким образом, получена критическая точка при .

 

2.3) . Тогда второе и третье уравнения системы (4) принимают вид:

откуда следует, что система (4) решений не имеет.

 

2.4) . Тогда

 

Не выполняются условия неотрицательности для множителей Лагранжа .

Проведем исследование полученного в пункте 2.2) решения. Рассмотрим допустимую точку из окрестности точки . Из ограничений задачи получим условия на :

Оценим разность :

.

Так как разность принимает неотрицательные значения не обязательно для малых по модулю значений , то .

Ответ: . ●

 

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

 

Пример 3.Найти наибольшее и наименьшее значение функции на множестве

.

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

Найдем стационарные точки функции :

.

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

.

Исследуем функцию на границе множества .

На стороне .

На стороне .

На стороне . Найдем значение этой функции в стационарной точке и на концах отрезка . Имеем при . Далее, . Сравнивая полученные значения функции , заключаем:

.

Ответ: . ●

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

1) построение множества допустимых точек ;

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

3) исследование поведения целевой функции при движении вдоль ограничения к исследуемой точке и от нее.

Рис.3.1

Пример 4. .

Решение: Множество допустимых точек задачи ограничено эллипсом и окружностью и на рисунке 1 изображено в виде заштрихованной замкнутой области на плоскости . Линии уровня целевой функции задаются уравнением и при представляют собой множество концентрических окружностей с центром в точке и радиусом . Окружность имеет общие точки со множеством допустимых точек при выполнении условия . Поэтому минимальное значение функции достигается в точке и равно 4, а максимальное значение этой функции достигается в точке и равно 36.

Линии 1,2,3 на рисунке 1 задаются соответственно уравнениями:

.

Ответ:

●

 

Задачи для самостоятельного решения.

3.2. . 3.3. . 3.4. .

Занятие 4. Элементы выпуклого анализа. Выпуклые задачи.

Определение. Множество называется выпуклым, если и элемент . ▲

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

Пусть задана функция . Рассмотрим два множества:

- эффективное множество,

- надграфик.

Определение. Функция называется выпуклой, если - выпуклое множество. Функция называется собственной, если и . ▲

Утверждение. Собственная функция выпукла тогда и только тогда, когда выполняется неравенство Иенсена:

.

■

Утверждение. Сумма конечного числа выпуклых функций есть выпуклая функция.

Действительно, пусть , где - выпуклые функции . Тогда

. ■

Примеры выпуклых функций.

1) ,

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

1а) , 1б) ,

1в).

2) ,

где - выпуклое открытое множество пространства , функция определена и дважды непрерывно дифференцируема на множестве и

.

3) .

4) .

Действительно, и

,

т.е. для функции выполняется неравенство Иенсена.

5) .

Действительно,

.

Кроме того,

либо,

либо ,

т.е. для функции выполняется неравенство Иенсена.

6) .

Выпуклость этой функции следует из свойств нормы: , .

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

. ▲

 

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

 

Свойства субдифференциала.

1)Субдифференциал является выпуклым множеством в пространстве .

2)Если - выпуклая собственная функция и дифференцируема в точке , то .

 

Примеры субдифференциалов выпуклых функций.

1) ,

2) ,

3) ,

4) ,

Теорема Моро-Рокафеллара.

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

. ■

Выпуклые задачи без ограничений.

Теорема. (Аналог теоремы Ферма) Для того чтобы точка доставляла в выпуклой задаче без ограничений абсолютный… Доказательство:

Выпуклые задачи с ограничением (выпуклые задачи).

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

Задачи выпуклого программирования.

Постановка задачи:

, (1)

где - выпуклые функции, - выпуклое множество.

Определение. Точка называется допустимой в задаче выпуклого программирования, если и .

▲

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

Теорема Куна-Таккера.

а) принцип минимума для функции Лагранжа : ; б) условия дополняющей нежесткости:

Задачи для самостоятельного решения.

4.1.. 4.2.. 4.3..

Занятие 5. Графический метод решения задач линейного

Программирования.

(1) (2)

Задачи для самостоятельного решения.

Решить задачи линейного программирования графическим методом: 5.1. , , , , . 5.2. , , , , . …   5.7. Для изготовления сплава из меди, олова и цинка в качестве сырья используют два сплава тех же металлов,…

Программирования.

Постановка задачи линейного программирования в общей форме имеет вид: (з)

Метод искусственного базиса нахождения

Начальной крайней точки

Рассмотрим задачу линейного программирования в канонической форме: , (зк) где – неизвестная переменная, и – заданные векторы, – заданная матрица размера . Будем считать, что (если , то умножим…

Задачи для самостоятельного решения.

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

Занятие 7. Транспортная задача.

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

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

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

 

; (з)

; (1)

; (2)

.

 

Условие (1) означает, что из пункта весь груз вывезен в пункты назначения, а условие (2) означает, что количество груза, завезенного в пункт со всех пунктов отправления, соответствует требуемому. Транспортную задачу удобно записывать в виде платежной матрицы:

 

			…
			…
			…
…	…	…	…	…
			…

 

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

 

Если суммарные запасы пунктов отправления больше суммарной потребности пунктов назначения, т.е. , то равенства (1) заменяются неравенствами:

, а условия (2) остаются без изменений. В этом случае для сведения к замкнутой модели следует:

а) ввести фиктивный пункт назначения с требуемой величиной ввоза ;

б) положить ;

в) ввести дополнительные переменные .

Тогда придем к замкнутой модели транспортной задачи.

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

Если суммарные запасы отправителей меньше суммарных запросов пунктов назначения, т.е. , то равенства (2) заменяются неравенствами:

, а условия (1) остаются без изменений. В этом случае для сведения к замкнутой модели следует:

а) вести фиктивный пункт отправления с требуемой величиной вывоза ;

б) положить ;

в) ввести дополнительные переменные .

Тогда придем к замкнутой модели транспортной задачи.

Если в задаче имеется дополнительное требование полностью удовлетворить потребности пункта назначения , то следует положить , где - достаточно большое положительное число.

Пример 1. Привести транспортную задачу, заданную платежной матрицей (табл. 7.1), к замкнутой модели.

 

Таблица 7.1

 

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

 

Таблица 7.2

●

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

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

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

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

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

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

 

Первоначальный план перевозок. Таблица 7.3

Для краткости в матрице плана перевозок не пишем нулевые значения небазисных перевозок.

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

.

 

Метод «северо-западного угла» не учитывает стоимости перевозок. Поэтому начальный план может оказаться далеко не оптимальным. Следующий метод стоимости перевозок учитывает.

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

В оставшейся части платежной матрицы вновь ищется минимальный элемент, и процедура повторяется до тех пор, пока первоначальный план перевозок не… В качестве минимального элемента возьмем и назначим максимально возможную… Для найденного плана перевозок

Метод потенциалов.

2) Найти первоначальный план перевозок (начальную крайнюю точку множества допустимых элементов). 3) Провести исследование плана перевозок . Для найденного плана перевозок… 4) Провести исследование матрицы

Задачи для самостоятельного решения.

Решить транспортные задачи с заданными платежными матрицами:

 

7.1.

 

7.2.

 

7.3.

 

7.4.

 

7.5.Решить транспортную задачу, заданную платежной матрицей, при дополнительном требовании удовлетворения пункта назначения :

Занятие 8. Простейшая задача классического

Вариационного исчисления.

Рассмотрим некоторое функциональное пространство . Пусть каждому элементу поставлено в соответствие число . Тогда говорят, что на множестве задан… Линейное пространство называется нормированным, если на определен функционал ,… а) , причем ;

Пример 2.

.

Решение: Интегрант задачи равен .

Выпишем уравнение Эйлера: .

Уравнение Эйлера представляет собой линейное однородное дифференциальное уравнение второго порядка с постоянными коэффициентами. Его общее решение имеет вид:

.

Константы найдем из граничных условий:

.

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

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

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

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

Так как , а , то .

Из этого примера видно, что уравнение Эйлера - необходимое, но не достаточное условие экстремума. ●

Пример 3.

.

Решение: Заметим, что интегрант задачи не зависит явно от . Поэтому имеет место интеграл энергии:

.

Тогда

.

Так как на концах отрезка интегрирования функция принимает положительные значения, то перед квадратным корнем следует взять знак «плюс». Из краевых условий найдем константы : . Получаем единственную допустимую экстремаль . Заметим, что .

Возьмем произвольную допустимую функцию

.

Рассмотрим разность

.

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

Ответ: . ●

 

Пример 4.

.

Решение: Выпишем интегрант задачи и уравнение Эйлера:

;

. (3)

Уравнение Эйлера представляет собой линейное неоднородное дифференциальное уравнение второго порядка с постоянными коэффициентами. Его общее решение представляется в виде суммы общего решения соответствующего однородного уравнения и частного решения неоднородного уравнения: .

Корни характеристического уравнения равны , поэтому

.

Частное решение неоднородного уравнения ищем в виде:

.

Подставляя эту функцию в уравнение (3), получим . Поэтому

.

Постоянные найдем из краевых условий:

.

Получаем единственную допустимую экстремаль:

.

Проведем исследование полученного решения. Для этого возьмем произвольную допустимую функцию и рассмотрим разность

 

.

При выводе последнего неравенства было использовано неравенство Стеклова.

Неравенство Стеклова В.А.

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

Пример 5. Задача о брахистохроне.

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

Решение: Введем в плоскости систему координат , где ось горизонтальна, ось направлена вертикально вниз, а точка совпадает с началом координат (рис. 8.2). Пусть , а - функция, задающая уравнение кривой, соединяющей точки и .

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

 

.

Интегрант задачи не зависит явно от , следовательно, имеет место интеграл энергии:

.

 

Рис. 8.2

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

.

Выполним замену переменной: , тогда

и

. Интегрируя последнее равенство, получаем:

(4)

Так как кривая проходит через точку , то . Постоянна находится из условия . Уравнения (4) являются параметрическими уравнениями семейства циклоид. Следовательно, кривой наискорейшего спуска является циклоида. ●

 

Задачи для самостоятельного решения.

8.2. . 8.3. . 8.4..

Занятие 9. Задача Больца.

 

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

(з)

Здесь - функция трех переменных, называемая интегрантом, - функция двух переменных, называемая терминантом, отрезок фиксирован и конечен, . Функционал называется функционалом Больца. ▲

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

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

 

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

Тогда и выполнены условия:

а) уравнение Эйлера

;

б) условия трансверсальности

.

Здесь использованы следующие обозначения:

,

Доказательство: Возьмем произвольную, но фиксированную функцию . Рассмотрим функцию одной вещественной переменной

.

Функция является допустимой для любого . Так как , то функция имеет экстремум в точке . В силу условий гладкости функция дифференцируема в точке и по теореме Ферма .

Продифференцируем функцию :

;

(1)

.

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

.

Согласно лемме Дюбуа-Реймона (см. предыдущее занятие) и функция удовлетворяет уравнению Эйлера:

.

Осталось вывести условия трансверсальности. Проинтегрируем по частям второе слагаемое в равенстве (1):

. (2)

Подставим (2) в (1):

(3)

В силу уравнения Эйлера выражение в квадратных скобках, стоящее под знаком интеграла в равенстве (3), тождественно равно нулю. Поэтому получаем следующее равенство:

. (4)

Положим . Тогда из (4) получим: .

Положим . Тогда из (4) получим:.

Теорема полностью доказана. ■

 

Пример 1. .

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

а) уравнение Эйлера

;

б) условия трансверсальности

,

.

Проинтегрируем уравнение Эйлера:

.

Постоянные найдем из условий трансверсальности:

,

.

Откуда получаем . Единственная допустимая экстремаль задачи имеет вид: .

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

 

.

 

Учитывая уравнение Эйлера и условия трансверсальности, получим:

.

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

 

Ответ: . ●

Пример 2.

 

.

Решение: Интегрант и терминант задачи имеют вид:

.

Выпишем необходимые условия локального экстремума:

а) уравнение Эйлера

;

б) условия трансверсальности

,

.

Найдем общее решение дифференциального уравнения Эйлера:

.

Постоянные найдем из условий трансверсальности:

;

.

Получаем: .

Проведем исследование полученного решения . Для этого возьмем произвольную допустимую функцию и рассмотрим разность:

.

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

.

Для другой допустимой последовательности функций , сходящейся к по норме пространства , получим:

.

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

Покажем, что . Действительно, для последовательности функций имеем:

при .

Для последовательности функций

при .

Ответ: . ●

 

Пример 3.

.

Решение: Выпишем интегрант задачи и терминант задачи:

, .

Необходимые условия локального экстремума:

а) уравнение Эйлера

;

б) условия трансверсальности

,

.

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

Общее решение однородного уравнения имеет вид:. Частное решение неоднородного уравнения следует искать в виде: .

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

Постоянные найдем из условий трансверсальности:

,

.

Тогда .

Проведем исследование полученного решения. Для этого возьмем произвольную допустимую функцию и рассмотрим разность

.

С учетом того, что функция удовлетворяет уравнению Эйлера и условиям трансверсальности, получим:

.

Покажем, что . Для этого рассмотрим две последовательности функций, сходящихся к тождественно нулевой функции по норме пространства . Действительно, для последовательности функций получим:

.

А для последовательности функций

.

Следовательно, .

Покажем, что . Действительно, для последовательности функций имеем:

при .

Для последовательности функций

= при .

Ответ: .●

 

Пример 4.

.

Решение: Интегрант и терминант задачи имеют вид:

.

Выпишем необходимые условия локального экстремума:

а) уравнение Эйлера

;

б) условия трансверсальности

,

.

Общее решение уравнения Эйлера имеет вид:

.

Продифференцируем полученную функцию по :

.

Постоянные найдем из условий трансверсальности:

;

.

Решая систему линейных уравнений второго порядка относительно , получим:

.

Исследуем полученное решение. Для этого возьмем произвольную допустимую функцию и рассмотрим разность

.

Заметим, что . Поэтому

.

Следовательно, .

Ответ: . ●

Пример 5.

.

Решение: Выпишем интегрант задачи и терминант задачи:

, .

Необходимые условия локального экстремума:

а) уравнение Эйлера

;

б) условия трансверсальности

,

.

Так как интегрант не зависит явно от , то уравнение Эйлера имеет интеграл энергии:

.

Тогда

.

Из условий трансверсальности найдем постоянные :

;

.

Откуда получаем следующие значения для : .

Единственная допустимая экстремаль имеет вид: .

Проведем исследование полученного решения. Для этого возьмем произвольную допустимую функцию и рассмотрим разность

.

С учетом уравнения Эйлера проинтегрируем по частям первое слагаемое, стоящее под знаком интеграла и учтем условия трансверсальности:

.

Тогда

.

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

Ответ: . ●

Задачи для самостоятельного решения.

9.2. . 9.3. . 9.4..

Занятие 10. Изопериметрическая задача.

 

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

(з)

, (1)

. (2)

Здесь - заданные числа, отрезок фиксирован и конечен, . Ограничения (1) называются изопериметрическими. Функции , удовлетворяющие условиям (1), (2), называются допустимыми.

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

. ▲

Определение. Функция называется лагранжианом задачи, а числа - множителями Лагранжа. ▲

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

. ■

Рассмотрим примеры решения изопериметрических задач.

Пример 1.

.

Решение: Составим Лагранжиан задачи:. Выпишем необходимое условие экстремума – уравнение Эйлера:

.

Если , то из уравнения Эйлера получим, что , следовательно, вектор множителей Лагранжа получается нулевым. Поэтому . Положим . Тогда

.

Неизвестные постоянные найдем из граничных условий и изопериметрического условия:

,

,

.

Откуда получаем: . Единственная допустимая экстремаль задачи имеет вид: .

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

,

,

.

Рассмотрим разность :

.

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

.

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

.

Тогда

при .

Ответ: . ●

В качестве следующего примера приведем классическую изопериметрическую задачу о нахождении замкнутой кривой, имеющей заданную длину и охватывающую наибольшую площадь. Еще до Аристотеля (IV век до н.э.) было известно, что среди всех изопериметрических (имеющих равную длину) кривых наиболее вместимой является окружность. Изопериметрическая задача содержится также в легенде о царице Дидоне. Описываемые события легенда относит к 825 году до н.э.

Финикийская царица Дидона со своей свитой, спасаясь от преследований, покинула родной город и отправилась в путь на корабле на Запад вдоль берегов Средиземного моря. Выбрав на африканском побережье удобное место, Дидона и ее спутники решили основать в выбранном месте свой город. Местным жителям эта идея не понравилась, но, тем не менее, финикийской царице удалось уговорить местного предводителя, и он неосторожно согласился уступить Дидоне клочок земли, «который можно окружить бычьей шкурой». Хитрая финикиянка разрезала шкуру на тонкие ремни, связала их в один длинный ремень и, окружив им значительную территорию, заложила на ней город Карфаген.

Таким образом, Дидона «решала» классическую изопериметрическую задачу о наибольшей вместимости. Если предположить, что Дидона хотела сохранить выход к морю, то получим первую задачу Дидоны: среди всех кривых длины с концами на фиксированной прямой, найти ту, которая ограничивает фигуру наибольшей площади (рис. 10.1). В рамках рассматриваемой в этом занятии постановки задачи решим вторую задачу Дидоны, в которой оба конца кривой закреплены на прямой.

 

Рис. 10.1

 

Пример 2. Задача Дидоны.

 

.

Решение: Составим Лагранжиан задачи:.

Выпишем уравнение Эйлера:

.

Случай 1: . Тогда (в противном случае обращается в ноль вектор множителей Лагранжа), следовательно,

.

С учетом граничных условий:

,

,

Откуда следует, что .

Из изопериметрического условия тогда получим:

.

Таким образом, если , то .

Случай 2: . Тогда

.

Из последнего уравнения выразим :

.

Проинтегрируем по последнее уравнение:

.

Получили уравнение окружности.

Найдем неизвестные постоянные из ограничений задачи:

,

.

Откуда получаем:

, . (3)

Учитывая изопериметрическое условие, получим:

. (4)

Введем обозначение: . Тогда равенство (4) примет вид: .

Последнее уравнение имеет отличное от нуля решение, если

.

При выполнении этого условия из равенства (4) находим , а затем из уравнения (3) определяем . Подведем итоги.

 

Если , то в задаче имеется единственная экстремаль, лежащая в верхней полуплоскости и являющаяся дугой окружности, проходящей через точки , с центром на оси (рис. 10.2).

Если , то .

Если , то в задаче нет допустимых функций.

Если , то в задаче нет допустимых экстремалей. ●

 

Пример 3.

.

Решение: Лагранжиан задачи имеет вид:

.

Уравнение Эйлера:

.

Если , то из уравнения Эйлера получим , т.е. обращается в ноль вектор множителей Лагранжа. Следовательно, . Положим . Тогда уравнение Эйлера примет вид:

. (5)

Корни характеристического уравнения для соответствующего однородного дифференциального уравнения равны . Поэтому общее решение однородного уравнения имеет вид: . Частное решение уравнения (5) следует искать в виде: . Подставляя эту функцию в уравнение (5), получим . Тогда

.

Неизвестные постоянные найдем из граничных условий и изопериметрического условия:

 

,

,

.

Откуда получаем: .

Таким образом, в задаче имеется единственная допустимая экстремаль .

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

.

Рассмотрим разность

.

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

Ответ: . ●

 

 

Пример 4.

.

Решение: Составим Лагранжиан задачи: .

Выпишем уравнение Эйлера:

.

Если , то из уравнения Эйлера получим , что противоречит условию отличия от нуля вектора множителей Лагранжа. Так как множители Лагранжа определяются с точностью до коэффициента пропорциональности, то положим . Тогда

.

Постоянные определим из условий задачи. Учитывая краевые условия, получим:

.

.

Откуда следует, что

.

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

.

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

и .

 

Проведем исследование полученных функций.

Для экстремали рассмотрим допустимую функцию . Функция и удовлетворяет следующим условиям:

,

.

Тогда

.

Откуда следует, что функция доставляет в задаче абсолютный минимум и .

Для экстремали рассмотрим допустимую функцию . Функция и удовлетворяет следующим условиям:

,

.

Тогда

.

Откуда следует, что функция доставляет в задаче абсолютный максимум и .

Ответ: , ;

, . ●

 

Задачи для самостоятельного решения.

 

Решить изопериметрические задачи:

10.1..

10.2. .

10.3. .

10.4. .

10.5. .

10.6. .

10.7.

.

10.8. .

10.9.Среди всех плоских кривых длины , концы которой закреплены в заданных точках , найти ту, у которой ордината центра тяжести минимальна:

.

Занятие 11. Задача с подвижными концами.

 

Задачей с подвижными концами называется следующая экстремальная задача в пространстве :

(з)

. (1)

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

Определение. Элемент называется допустимым, если , и выполнены условия (1) на концах. ▲

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

. ▲

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

выполнены условия:

а) стационарности по - уравнение Эйлера для интегранта

;

б) трансверсальности по для терминанта

;

в) стационарности по подвижным концам (выписывается только для подвижных концов отрезка интегрирования)

,

. ■

 

Рассмотрим примеры решения задач с подвижными концами.

 

Пример 1. Решить задачу с подвижными концами:

.

Решение: Составим функцию Лагранжа задачи

.

Выпишем необходимые условия локального экстремума:

а) уравнение Эйлера для интегранта

;

б) условия трансверсальности для терминанта

,

;

в) условие стационарности функции Лагранжа по

.

Если , то из б) следует, что , т.е. вектор множителей Лагранжа обращается в ноль. Поэтому . Положим . Тогда

.

Найдем неизвестные величины :

;

;

;

.

Решая полученную систему уравнений, находим с учетом условия :

.

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

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

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

Покажем, что .

Для допустимой последовательности элементов имеем:

при .

Возьмем другую допустимую последовательность элементов . Тогда

при .

Ответ: ; . ●

 

Пример 2. Решить задачу с подвижными концами:

.

Решение: Составим функцию Лагранжа задачи

.

Выпишем необходимые условия локального экстремума:

а) уравнение Эйлера для интегранта

;

б) условия трансверсальности для терминанта

,

;

в) условие стационарности функции Лагранжа по

.

Если , то из б) следует, что , т.е. вектор множителей Лагранжа обращается в ноль. Поэтому . Положим . Тогда

.

Найдем неизвестные величины :

 

;

;

;

;

.

 

Решая полученную систему уравнений, находим с учетом условия :

.

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

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

;

.

Рассмотрим разность :

.

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

Покажем, что . Действительно, для допустимой последовательности элементов , где

,

получим:

при .

Ответ: , , . ●

Пример 3. Решить задачу с подвижными концами:

.

Решение: Составим функцию Лагранжа задачи

.

Выпишем необходимые условия локального экстремума:

а) уравнение Эйлера для интегранта

;

б) условия трансверсальности для терминанта

,

;

в) условие стационарности функции Лагранжа по

.

Если , то из б) следует, что , т.е. вектор множителей Лагранжа обращается в ноль. Поэтому . Положим . Тогда

.

Найдем неизвестные величины :

;

;

;

;

Решая полученную систему уравнений, находим с учетом условия :

.

Следовательно, .

Исследуем полученное решение. Рассмотрим разность , где - допустимый элемент, удовлетворяющий ограничениям задачи:

.

Согласно неравенству Коши-Буняковского

.

С учетом последнего неравенства

.

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

Покажем, что . Для этого рассмотрим допустимую последовательность элементов , где . Тогда

при .

Ответ: , .●

Пример 4. Решить задачу с подвижными концами:

.

Решение: Составим функцию Лагранжа задачи

.

Выпишем необходимые условия локального экстремума:

а) уравнение Эйлера для интегранта

;

б) условия трансверсальности для терминанта

,

;

в) условие стационарности функции Лагранжа по

.

Если , то из б) следует, что , т.е. вектор множителей Лагранжа обращается в ноль. Поэтому . Положим . Тогда

.

Найдем неизвестные величины :

;

;

;

;

.

Решая полученную систему уравнений, находим с учетом условия :

.

Следовательно, .

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

;

.

Рассмотрим разность :

.

Для допустимого элемента , где , сходящегося к при , получим:

.

Откуда следует, что разность положительна при и отрицательна при .

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

Для последовательности элементов , где имеем:

при .

Рассмотрим последовательность элементов , где

Получим, что при .

Ответ: . ●

Пример 5. Найти допустимые экстремали в задаче с подвижными концами:

.

Решение: Составим функцию Лагранжа задачи

.

Выпишем необходимые условия локального экстремума:

а) уравнение Эйлера для интегранта

;

б) условия трансверсальности для терминанта

,

;

в) условие стационарности функции Лагранжа по

.

Если , то из б) следует, что , т.е. вектор множителей Лагранжа обращается в ноль. Поэтому . Положим . Тогда

.

Найдем неизвестные величины :

 

;

; (2)

; (3)

. (4)

 

Из равенств (2) и (3) выразим через :

.

Подставим полученные выражения в равенство (4):

,

Откуда следует, либо , либо

. (5)

 

Получаем два экстремальных элемента: и , где определяется однозначно из равенства (5). Заметим, что .

 

Ответ: и ,

где определяется однозначно из равенства . ●

 

 

Задачи для самостоятельного решения.

Решить задачи с подвижными концами:   11.1..

Занятие 12. Задача Лагранжа.

 

Все задачи, рассмотренные ранее, являются частными случаями или могут быть сведены к задаче, поставленной Лагранжем в сочинении «Аналитическая механика» в 1788 году. Для ее решения Лагранж использовал метод неопределенных множителей, который впоследствии стали называть методом множителей Лагранжа.

Постановка задачи. Рассмотрим пространство - множество вектор-функций , где функции имеют непрерывные производные на конечном отрезке .

Задачей Лагранжа называется следующая экстремальная задача:

,

. (1)

Здесь , - заданный конечный отрезок,

Условие (1), называемое дифференциальной связью, может быть наложено не на все координаты вектор-функции , а только на некоторые, например, на первые координат:

.

Обозначим , где

.

Если дифференциальная связь отсутствует, то и . Так как вместо в функции можно подставить , то в дальнейшем считаем, что .

Определение. Элемент , для которого выполнены все указанные условия и ограничения, называется допустимым. ▲

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

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

Тогда найдутся множители Лагранжа такие, что для функции Лагранжа задачи

,

где

выполнены условия:

а) стационарности по - уравнение Эйлера для лагранжиана

:

;

б) трансверсальности по для терминанта

:

;

в) стационарности по (только для подвижных концов отрезка интегрирования):

,

;

г) дополняющей нежесткости:

;

д) неотрицательности: . ■

 

Рассмотрим примеры решения задач.

 

Пример 1. Решить задачу классического вариационного исчисления:

.

Решение: Рассматриваемая задача не является изопериметрической, так как отсутствует граничное условие для функции в точке . Будем решать поставленную задачу как задачу Лагранжа. Составим функцию Лагранжа задачи:

.

Выпишем необходимые условия локального экстремума:

а) уравнение Эйлера для лагранжиана

;

б) условия трансверсальности для терминанта

,

.

Если , то из а) и б) следует, что , т.е. вектор множителей Лагранжа обращается в ноль. Поэтому . Положим . Тогда из уравнения Эйлера получим

.

Найдем неизвестные константы из ограничений задачи и условий трансверсальности:

;

;

;

.

Решая полученную систему уравнений, находим:

.

Таким образом, в задаче имеется единственная допустимая экстремаль

.

Проведем исследование полученного решения. Возьмем допустимую функцию . Из условий задачи получим ограничения для функции :

 

;

.

Оценим разность :

.

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

При этом .

 

Покажем, что . Действительно, для допустимой последовательности функций получим

при .

Ответ:

. ●

 

Пример 2. Решить задачу классического вариационного исчисления:

Решение: Сведем поставленную задачу к задаче Лагранжа. Для этого вместо функции введем вектор-функцию , где . Тогда получим задачу:

. (2)

Здесь условие (2) записано в виде дифференциальной связи.

 

Составим функцию Лагранжа задачи

.

Выпишем необходимые условия локального экстремума:

а) система уравнений Эйлера для лагранжиана

,

;

б) условия трансверсальности для терминанта

 

,

,

,

.

 

д) условие неотрицательности .

 

Если , то из а) следует, что , а из б) следует, что , т.е. все множители Лагранжа равны нулю. Поэтому . Положим . Тогда

.

Так как , то

Найдем неизвестные величины :

,

,

.

Следовательно, . Откуда получаем единственную допустимую экстремаль .

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

.

Следовательно, , .

Покажем, что . Действительно, для допустимой последовательности элементов получим:

при .

Ответ: , . ●

Пример 3. Решить задачу классического вариационного исчисления:

.

Решение: Составим функцию Лагранжа задачи

.

Выпишем необходимые условия локального экстремума:

а) уравнение Эйлера для лагранжиана

;

б) условия трансверсальности для терминанта

,

;

в) условие стационарности функции Лагранжа по

.

д) неотрицательности .

Если , то из а) и б) следует, что , т.е. вектор множителей Лагранжа обращается в ноль. Поэтому . Положим . Тогда из уравнения Эйлера получим:

.

Найдем неизвестные величины из условий б), в) и ограничений задачи:

 

,

, (3)

,

. (4)

 

Из (3) и (4) следует равенство . Откуда получаем либо , либо .

Случай 1: .

В этом случае .

Случай 2:

.

Откуда получаем экстремальный элемент .

Проведем исследование полученных решений. Рассмотрим допустимый элемент , где . Из ограничений задачи получим условия на и :

,

. (5)

Для первой экстремали условие (5) примет вид: .

Для второй экстремали получим:

.

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

.

Следовательно, .

Оценим разность для второй экстремали:

.

Для функции , удовлетворяющей условиям , , имеем:

.

Откуда следует, что при , при . Т.е.

.

Покажем, что . Для этого рассмотрим допустимую последовательность элементов , где . Тогда

при .

Ответ: ,

, . ●

Пример 4. Решить задачу классического вариационного исчисления:

.

Решение: Приведем задачу к форме задачи Лагранжа. Положим . Тогда исходная задача примет вид:

,

Составим функцию Лагранжа задачи

.

Выпишем необходимые условия локального экстремума:

а) система уравнений Эйлера для интегранта :

,

;

б) условия трансверсальности для терминанта

:

,

,

,

;

в) условие стационарности функции Лагранжа по :

;

д) условие неотрицательности: .

Так как и , то .

Если , то из б) следует, что , а из в) получаем , т.е. вектор множителей Лагранжа обращается в ноль. Поэтому . Положим . Тогда

.

Найдем неизвестные величины :

,

,

,

,

,

,

.

Решая полученную систему уравнений, находим:

.

Следовательно, .

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

,

,

,

.

Следовательно, .

Ответ: . ●

 

Задачи для самостоятельного решения.

12.1.. 12.2. . 12.3. .

Занятие 13. Задача оптимального управления.

 

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

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

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

,

, (1)

, (2)

где , , , – заданный конечный отрезок, – произвольное множество, принадлежащее пространству , – множество точек непрерывности управления ,

,

– пространство кусочно‑непрерывных на отрезке вектор‑функций,

– пространство непрерывных на отрезке вектор-функций, имеющих кусочно-непрерывную производную.

Условие (1) называется дифференциальной связью, оно должно выполняться во всех точках непрерывности вектор-функции .

В отличие от задачи Лагранжа имеется ограничение (2) типа включения, а фазовая переменная может иметь меньшую гладкость.

Определение. Элемент , для которого выполнены все указанные условия и ограничения, называется допустимым или допустимым управляемым процессом. ▲

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

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

Тогда найдутся множители Лагранжа

такие, что для функции Лагранжа задачи

где

,

выполнены условия:

а) стационарности по – уравнение Эйлера для лагранжиана

:

;

б) трансверсальности по для терминанта

:

,

;

в) оптимальности по :

;

г) стационарности по (только для подвижных концов отрезка интегрирования):

,

;

д) дополняющей нежесткости:

;

е) неотрицательности: . ■

 

 

Пример 1. Решить экстремальную задачу:

.

Решение: Приведем задачу к виду задачи оптимального управления. Для этого введем управление . Сначала решим задачу на минимум, а затем – на максимум.

I..

Составим функцию Лагранжа задачи:

.

Выпишем необходимые условия локального минимума:

а) уравнение Эйлера для лагранжиана

;

б) условия трансверсальности для терминанта

,

;

 

в) условие оптимальности по :

;

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

г) условие неотрицательности:

.

Если , то из уравнения Эйлера следует, что , тогда из условия трансверсальности получим , т.е. все множители Лагранжа обращаются в ноль. Поэтому .

Положим . Тогда из уравнения Эйлера получим:

.

Так как , то и на отрезке .

Условие оптимальности принимает вид:

.

Графиком функции является парабола, ветви которой направлены вверх, а вершина имеет координаты (рис. 13.1). Поэтому

 

 

С учетом того, что , получаем:

 

 

Рис. 13.1

 

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

.

В итоге получаем единственно возможную экстремаль

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

;

.

Оценим разность :

.

При справедливо двойное неравенство . Так как и не убывает на отрезке , то . Следовательно, и .

II. Приступим к решению задачи на максимум, сведя предварительно ее к задаче на минимум:

.

Функция Лагранжа имеет вид:

.

Выпишем необходимые условия локального минимума:

а) уравнение Эйлера для лагранжиана

:

;

б) условия трансверсальности для терминанта

:

,

в) условие оптимальности по :

;

г) условие неотрицательности:

.

Аналогично пункту I можно показать, что . Положим . Тогда из уравнения Эйлера получим: . Так как , то и при .

Условие оптимальности принимает вид:

.

Графиком функции является парабола, ветви которой направлены вниз, а вершина имеет координаты (рис. 13.2). Поэтому .

Так как , то .

Выполним непосредственную проверку полученного решения. Рассмотрим допустимую функцию . Из ограничений задачи получим:

,

.

Оценим разность :

.

 

Рис. 13.2

 

Так как , то . А так как и не убывает на отрезке в силу условия , то на отрезке , следовательно, . Таким образом, и .

Ответ:

;

. ●

 

Пример 2. Решить экстремальную задачу:

.

Решение: Сведем поставленную задачу к задаче оптимального управления. Для этого вместо функции введем вектор-функцию и управление , где , Тогда получим задачу:

.

Составим функцию Лагранжа задачи:

Выпишем необходимые условия локального экстремума:

а) система уравнений Эйлера для лагранжиана

:

,

;

б) условия трансверсальности для терминанта

:

,

,

,

;

в) условие оптимальности:

г) условие неотрицательности: .

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

Положим . Тогда . Так как , то . Тогда из второго уравнения Эйлера

.

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

Рис. 13.3

 

Из условия оптимальности получим:

Найдем неизвестные величины из краевых условий для функции и условия непрерывности в точках и :

,

,

,

.

Откуда находим . Тогда

Найдем неизвестные величины из краевых условий для функции и условия непрерывности в точках и :

,

,

.

Решая полученную систему линейных уравнений относительно , находим: , следовательно,

Проведем исследование полученного решения. Рассмотрим допустимую функцию . Из ограничений задачи получим условия на функцию :

.

Последнее неравенство перепишем в виде: . Тогда

при , и ,

при .

Оценим разность :

,

так как на каждом из отрезков произведение меньше или равно нулю.

Ответ:

. ●

 

Задачи для самостоятельного решения.

Решить экстремальные задачи:

 

13.1..

13.2. .

13.3. .

13.4. .

13.5..

13.6. .

13.7. .

Занятие 14. Задача оптимального управления (продолжение).

 

Пример 1. Решить экстремальную задачу:

.

Решение: Приведем поставленную задачу к задаче оптимального управления. Для этого вместо функции введем вектор-функцию и управление , где , Тогда получим задачу:

,

.

Составим функцию Лагранжа задачи:

.

Выпишем необходимые условия локального экстремума:

а) система уравнений Эйлера для лагранжиана :

,

;

б) условия трансверсальности для терминанта

:

,

,

,

;

в) условие оптимальности:

г) условие стационарности функции Лагранжа по :

;

д) условие неотрицательности: .

Так как , то условие стационарности г) можно записать в виде:.

Если , то , либо . В последнем случае в силу условия оптимальности опять приходим к равенству .

Из системы уравнений Эйлера получаем: . Если при этом , то из условий трансверсальности следует , т.е. все множители Лагранжа равны нулю. Если , то при , поэтому . Так как , то приходим к равенствам , откуда , что противоречит условию . Аналогично придем к противоречию в случае . Поэтому .

Положим . Тогда . Так как , то либо , либо . Разберем отдельно эти два случая.

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

и .

Из условия оптимальности получаем:

Найдем из краевых условий и условия непрерывности функции в точке :

,

,

.

Тогда

Найдем из краевых условий и условия непрерывности функции в точке :

,

,

.

Получаем экстремальный элемент

Случай 2. , . В силу уравнений Эйлера функция является линейной: и . В некоторой точке интервала функция должна менять знак. Так как , то при и при .

Из условия оптимальности получаем:

Найдем из краевых условий и условия непрерывности функции в точке :

,

,

.

Тогда

Найдем из краевых условий и условия непрерывности функции в точке :

,

,

.

Т.е., во втором случае нет допустимых экстремалей.

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

.

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

.

Поскольку , то

, (1)

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

Аналогично, с учетом условий на правом конце отрезка интегрирования

.

Так как , то

, (2)

причем равенство здесь возможно только, если во всех точках непрерывности .

Из (1) и (2) следует, что , следовательно, . Отсюда .

Ответ: . ●

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

.

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

Пример 2. Решить экстремальную задачу:

.

Решение: Сведем поставленную задачу к задаче оптимального управления. Для этого введем вектор-функцию и управление , где , . Тогда получим задачу:

.

Составим функцию Лагранжа задачи:

.

Выпишем необходимые условия локального экстремума:

а) система уравнений Эйлера для лагранжиана

:

,

;

б) условия трансверсальности для терминанта

:

,

,

,

;

в) условие оптимальности:

;

г) условие неотрицательности: .

Если , то из условий а) и б) следует, что . Условие оптимальности примет вид: .

Если , то , а из б) следует, что , т.е. все множители Лагранжа равны нулю. Если , то при , следовательно, , тогда решения задачи на минимум мы не получим. Если , то при , следовательно, .

Так как , то . Далее, используя краевые условия для функции , получим противоречивую систему равенств:

,

.

Следовательно, . Положим . Тогда условие оптимальности примет вид:

Из уравнений Эйлера и условий трансверсальности получаем .

Если , то . Используя краевые условия задачи, придем к противоречию.

Если , то и опять придем к противоречию.

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

 

Рис. 14.1

 

Найдем неизвестные величины из краевых условий задачи и непрерывности функций в точке :

;

;

;

;

;

.

Решая полученную систему уравнений, находим: , . Откуда получаем

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

Рассмотрим допустимую функцию . В силу ограничений задачи получим условия на функцию :

.

В частности при .

Оценим разность :

.

Справедливо равенство:

.

Учитывая, что и полагая , получим:

.

Следовательно, и .

Ответ:

. ●

 

Задачи для самостоятельного решения.

14.1.. 14.2. . 14.3..

4.6.

В точке субдифференциал представляет собой квадрат с вершинами в точках

.

4.7.

4.8.

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

4.9. .

4.10. .

4.11. .

4.12. Если , то ;

если , то

.

4.13. .

4.14. .

4.15. .

4.16. .

5.1. .

5.2. .

5.3. .

5.4. ,

.

5.5. ,

.

5.6. .

5.7. .

5.8. 10500 руб. и 12600 руб.

5.9. (2; 0; 14).

5.10. (3; 6).

6.1. .

6.2. .

6.3. .

6.4. .

6.5. .

6.6. .

6.7. .

6.8. .

6.9. .

7.1. .

7.2. .

 

7.3. .

7.4. .

7.5..

8.1. .

8.2. .

8.3. .

8.4. .

8.5. .

8.6. .

8.7. .

8.8. .

8.9.,где-произвольная постоянная.

8.10. .

8.11. две экстремали.

9.1. .

9.2. .

9.3. .

9.4. .

9.5. .

9.6. .

9.7. .

9.8..

9.9..

9.10. .

9.11. Две экстремали.

10.1. .

10.2. .

10.3. .

10.4. .

10.5. .

10.6. .

10.7. .

10.8. ,

.

10.9.Допустимые экстремали:, где константа определяется из условия . Если , то имеются две допустимые экстремали, если , то одна допустимая экстремаль , если , то допустимых экстремалей нет.

11.1. .

11.2. .

11.3.

.

11.4.

.

11.5. .

11.6. .

11.7., где определяется однозначно из равенства .

11.8..

11.9..

11.10..

12.1. .

12.2. .

12.3.

.

12.4. .

12.5. .

12.6. .

12.7. .

12.8.

.

12.9. .

12.10. .

13.1..

 

13.2. .

 

13.3. .

 

13.4. .

 

13.5. .

13.6. .

 

13.7. .

14.1. .

14.2. .

14.3. .

14.4. .

14.5..

 

СПИСОК ЛИТЕРАТУРЫ

1. Алексеев В.М., Тихомиров В.М., Фомин С.В. Оптимальное управление. – М.: Наука, 2005. – 384 с.

2. Алексеев В.М., Галеев Э.М., Тихомиров В.М. Сборник задач по оптимизации. Теория. Примеры. Задачи. – М.: Физматлит, 2005. – 256 с.

3. Васильев Ф.П. Методы оптимизации. . – М.: Факториал Пресс, 2002. – 824 с.

4. Галеев Э.М. Оптимизация. Теория. Примеры. Задачи. – М.: Едиториал УРСС, 2002. – 304 с.

5. Вся высшая математика. Т.6. / М.Л.Краснов и др. - М.: Едиториал УРСС, 2003. – 256 с.

6. Магарил–Ильяев Г.Г., Тихомиров В.М. Выпуклый анализ и его приложения. – М.: Едиториал УРСС, 2000. – 176 с.

7. Пантелеев А.В., Летова Т.А. Методы оптимизации в примерах и задачах. – М.: Высшая школа, 2002. – 544 с.

8. Сборник задач по математике для втузов. Ч.2. / под общ. ред. А.В. Ефимова и А.С. Поспелова; М.: Физматлит. - 2009. – 432 с.

9. Сборник задач по математике для втузов. Ч.3 / под общ. ред. А.В. Ефимова и А.С. Поспелова; М.: Физматлит. - 2007. – 544 с.

10. Фихтенгольц Г.М. Курс дифференциального и интегрального исчисления. Т. 3. - М.: Наука, 1969. – 656 с.