Челябинск

ЮЖНО-УРАЛЬСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

ПРОГРАММА И МЕТОДИЧЕСКИЕ УКАЗАНИЯ

К РЕШЕНИЮ ЗАДАЧ ПО МЕТОДАМ ОПТИМИЗАЦИИ

ПРИНЦИП ЛАГРАНЖА В ГЛАДКИХ

КОНЕЧНОМЕРНЫХ ЗАДАЧАХ”

Составили: Бигильдеев С.И., Ухоботов В.И.

ЧЕЛЯБИНСК

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

Зададим функции , i=0,1,…,m, …,k и некоторое множество . Рассматривается следующая задача:

Определение 1.1. Точка называется точкой абсолютного минимума задач , если она удовлетворяет ограничениям (I.2),(I.3),(I.4) и для любой точки , удовлетворяющей этим же ограничениям, выполняется неравенство .

Замечание. Точки абсолютного минимума задачи будем, следуя [1], обозначать absmin .

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

Определение 1.2. Точка называется точкой локального минимума задач , если она удовлетворяет ограничениям (1.2),(1.3),(1.4) и существует некоторая окрестность точки , что для любой точки из этой окрестности и удовлетворяющей ограничениям (I.2),(I.3),(I.4), выполнено неравенство .

Замечание. Точки локального минимума задачи будем обозначать locmin .

Пример 1. На рис.1 точка – точка абсолютного минимума функции , а точка – точка локального минимума.

Упражнение. Доказать, что если Î absmin , то Î locmin .

2.Существование решения.

После того, как реальная задача формализована в виде задачи , естественно возникает вопрос о существовании решения. Этот вопрос обычно решается с помощью теоремы Вейерштрасса (см. [1], стр.23; [2], стр.95).

Теорема Вейерштрасса. Пусть функции (i=0,.....,k) являются непрерывными и существует число , при котором множество

является замкнутым непустым и ограниченным. Тогда существует точка Î absmin .

3.Необходимые условия локального минимума.

Установив, с помощью теоремы Вейерштрасса или каким-то другим способом, факт существования точки абсолютного минимума, переходим к следующему этапу решения задачи – отбор всех точек, “подозреваемых” в экстремальности. Это осуществляется с помощью необходимых условий локального минимума, которые называются правилом множителей Лагранжа (см. [1-4]).

Теорема (см [4],§4). Пусть 1) точка =() является точкой локального минимума задачи и внутренней точкой множества ; 2) функции (i=0,1,...,k) имеют непрерывные частные производные в некоторой окрестности точки .

Тогда существуют числа _, не все равные нулю, такие, что выполнены следующие условия:

1) условие стационарности

(3.1)

2) условие согласования знаков

(3.2)

3) условие пополняющей нежесткости

(3.3)

Замечание. Числа носят название множителей Лагранжа.

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

Тогда условия стационарности можно записать в следующем виде

Замечание. При нахождении точек локального минимума с помощью правила множителей Лагранжа имеем n+k+1 неизвестных , n уравнений (3.1), m уравнений связи (1.2) и k-m уравнений (3.3). Таким образом, число неизвестных больше на единицу, чем число уравнений, которые имеются для их определения. Однако, условия (3.1), (3.2), (3.3) не изменятся, если все множители Лагранжа умножить на одно и то же положительное число, то есть они определяются с точностью до положительного коэффициента пропорциональности. Поэтому особый интерес представляет случай . Тогда можно считать, что . В общем случае нельзя считать, что (см. пример из [2] стр. 48).

4.Достаточные условия и ответ задачи.

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

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

5.Программа решения задач.

Рекомендуется при решении задач на нахождение минимальных значений придерживаться следующей программы (см. [2], стр.94).

1.Формализация задачи.

2.Существование решения.

3.Необходимые условия:

3.I.Составление функции Лагранжа.

3.2.Применение правила множителей Лагранжа.

3.3.Решение вопроса ?

3.4.Решение уравнений.

4.Достаточные условия.

5.Ответ.

6.Пример решения задач.

Пример 1. Доказать неравенство между средним арифметическим и средним геометрическим, а именно, если , то

Решение.I. Формализация задачи. Зафиксируем число α > 0 и рассмотрим задачу

2. Существование решения. Множество

является замкнутым и ограниченным, а функция является непрерывной. По теореме Вейерштрасса существует точка absmin .

3. Необходимые условия.

3.I. Составим функцию Лагранжа.

3.2. Применение правила множителей Лагранжа. Напишем условие стационарности (3.1)

(6.1)

условие согласия знаков (3.2)

(6.2)

условие дополняющей нежесткости (3.3)

(6.3)

условие связи (3.4)

(6.4)

3.3. Решение вопроса о ? Допустим, что . Тогда из (6.1) следует, что для j=1,....,n. Заметим, что , иначе бы , а в точке значение функции равно .С учетом этого замечания из (6.3) имеем . То есть, набор чисел – нулевой. Итак, .

3.4. Решение уравнений.

Поскольку , то из условия (6.3) следует, что при j=1,…,n. Положим в (6.1) . Тогда будем иметь

Подставив в уравнение связи (6.4) получим

(6.5)

4. Достаточные условия. Поскольку решение задачи существует, то оно удовлетворяет необходимым условиям, а необходимым условиям удовлетворяет единственная точка (6.5). Следовательно точка (6.5) является absmin .

5. Ответ. Имеем, что при

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

Пример 2. (см. [6], стр.141). Требуется спроектировать прямоугольный контейнер заданного объема, длина которого больше заданной величины и израсходовать как можно меньше материала.

Решение.

1. Формализация. Обозначим через -длину, -ширину и -высоту контейнера (см. рис.1)

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

2. Существование решения. Множество

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

3. Необходимые условия.

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

3.2. Применение правила множителей Лагранжа. Запишем условие стационарности

(6.6)

условие дополняющей нежесткости

(6.7)

условие связей

(6.8)

условие согласования знаков

(6.9)

3.3.Допустим, что . Тогда из второго уравнения (6.6) следует, что . Отсюда, учитывая уравнение связи (6.8). получим . Учитывая последнее равенство, из первого уравнения (6.6) получим, что и . Итак, .

3.4.Положим в условиях стационарности (6.6) и рассмотрим два случая.

СЛУЧАЙ 1. Пусть . Тогда имеем

Умножая первое уравнение на , второе на , третье на и учитывая уравнение связи (6.6) получим,

(6.9)

а точка должна удовлетворять ограничению , то есть

(6.10)

Таким образом, случай 1 возможен при выполнении неравенства (6.10).

СЛУЧАЙ 2. Пусть . Тогда из условия дополняющей нежесткости (6.7) имеем . Из второго и третьего уравнения (6.6) (при ) и из (6.8) имеем

(6.11)

Отсюда находим, что

(6.12)

Подставляя эти значения в (6.11) и уравнение (6.6) находим

Условие согласование знаков примет вид

(6.13)

Таким образом, случай 2 возможен при выполнении (6.13).

4. Достаточные условия. Решение рассматриваемой задачи существует. Необходимым условиям удовлетворяет единственная точка (6.9) в случае (6.10)и (6.12) в случае (6.13). Следовательно, она и будет являться решением задачи.

5. Ответ. Если объем куба со стороной не больше заданного объема контейнера, то оптимальный контейнер нужно строить в форме куба; в противном случае контейнер долен иметь вид параллелепипеда длиной , а высота и ширина его равны между собой.

Пример 3 (см. [5], стр.37). Требуется определить параметры ракеты, имеющей не более трех ступеней, чтобы при заданной начальной массе и заданной конечной скорости полезная масса ракеты была максимальна.

Решение. 1. Формализация. Рассмотрим трехступенчатую ракету. Пусть

-масса топлива и корпуса i-ой ступени,

-масса корпуса i-ой ступени,

-масса топлива i-ой ступени.

Здесь . Пусть -полезная масса ракеты. Тогда масса всей ракеты

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

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

Скорость ракеты после отделения третьей ступени равна

Таким образом, имеем задачу

Обозначим

, , (6.14)

тогда и имеем следующую задачу:

Отметим, что если какое-то , то масса i-ой ступени равна нулю.

2. Существоввание решения. Выясним вначале, при каких условиях связи в задаче совместимы. Функция при возрастает, Поэтому при выполнено неравенство

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

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

то связь в задаче выполняется, например, при

Возьмем и рассмотрим множество

Это множество не пусто и ограничено. По теореме Вейерштрасса решение , , задачи существует.

3. Необходимые условия.

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

3.2. Запишем условие стационарности.

Условия дополняющей нежесткости

, ,

Условие связи

(6.15)

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

3.4. Положим в условии стационарности . Умножим i-ое уравнение на и, используя условие дополняющей нежесткости, получим

(6.16)

СЛУЧАЙ 1. Пусть . Тогда из (6.16) следует, что . Из уравнения связи (6.15) находим

(6.17)

СЛУЧАЙ 2. Пусть , . Тогда из условия дополняющей нежесткости имеем, что , а из (6.16) следует равенство . Подставив в уравнение связи (6.17), получим

(6.18)

Чтобы эта точка была допустимой, нужно предполагать

(6.19)

Аналогично, получаются две другие точки, если переставить индексы

.

СЛУЧАЙ 3. Пусть .Тогда из условия дополняющей нежесткости имеем . Отсюда и из уравнения связи (6.7) получим

(6.20)

Эта точка будет допустимой, при

(6.21)

Аналогично получаются две другие точки, если переставить индексы

.

4. Достаточные условия. Решение рассматриваемой задачи существует. Необходимым условиям удовлетворяет точка (6.17), три точки вида (6.18) (если выполнено (6.19)) и три точки вида (6.20) (если выполнено (6.21)). Вычислим значение целевой функции в этих точках. Для точки (6.17).

(6.22)

для точки вида (6.18)

(6.23)

для точек вида (6.20)

(6.24)

Выполнены следующие неравенства

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

СЛУЧАЙ А. . Тогда неравенства (6.19) и (6.21) не выполняются. Необходимым условиям минимума удовлетворяет единственная точка (6.17). она и будет оптимальна.

СЛУЧАЙ Б. . Необходимым условиям минимума в этом случае удовлетворяют точки (6.18) и (6.20). покажем, что точкой абсолютного минимума является точка (6.17). Для этого нужно показать, что . Из формул (6.22) и (6.23) имеем

При выражение, стоящее в квадратных скобках не превосходит

.

Таким образом, .

СЛУЧАЙ В. . Необходимым условиям минимума удовлетворяют точки (6.17),(6.18) и (6.20). покажем, что точкой абсолютного минимума является точка (6.17). Для этого, с учетом случая Б, достаточно показать, что . Из формул (6.23) и (6.24) имеем, что

Таким образом, точка (6.17) доставляет абсолютный минимум в задаче .

5.Ответ. Из равенства и из обозначения (6.14) следует, что если обозначить , , , (см. рис.2), то

= = (6.25)

Таким образом, нужно выбрать трехступенчатую ракету и так, чтобы массы удовлетворяли (6.25)

рис.2

ЗАДАЧИ.

Задача 1. Рассмотреть предыдущую задачу для n ступеней.

Задача 2. (см.[7], стр.431). Среди всех вписанных в данный круг радиуса R треугольников найти тот, площадь которого наибольшая.

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

Задача 4. Среди вписанных в данный эллипсоид прямоугольных параллелепипедов (с ребрами, параллельными осям его) найти тот, который имеет наибольший объем.

Задача 5. (задача Апполония, см.[2], стр.96). Найти кратчайшее расстояние от точки до эллипса.

Задача 6. Данное положительное число разделить на положительных сомножителей так, чтобы сумма обратных величин их была наименьшей.

Задача 7. Найти кратчайшее расстояние от точки до плоскости .

Задача 8. Найти кратчайшее расстояние между кривыми .

Задача 9. Доказать неравенство .

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

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

Задача 12. Определить кратчайшее расстояние между двумя прямыми в пространстве: .

Задача 13. Какого максимального объема можно передвинуть шкаф вдоль коридоров (см. рис.2), если площадь его лицевых сторон (передней и двух боковых стенок) равна S, ширина коридоров-h, высота потолков-H.

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

Задача 15. Запорошенное снегом поле имеет форму прямоугольника 3 км 4 км, по сторонам которого идут дороги. Путник может идти по дороге со скоростью U или прямо по снегу со скоростью V<U. Определите, по какому пути в зависимости от U и V должен идти путник, чтобы за кротчайшее время пройти с одного угла поля в противоположный.

ЛИТЕРАТУРА

1. Иоффе А.Д., Тихомиров В.М. Теория экстремальных задач. М.”Наука”.1974

2. Алексеев В.М., Тихомиров В.М., Фомин С.В. Оптимальное управление. М.”Наука”.1979

3. Алексеев В.М., Тихомиров В.М.Принцип Лагранжа и задачи оптимального управления (учебное пособие). Изд-во Московского университета, 1979

4.Пшеничный Б.Н., Данилюк Ю.М. Численные методы в экстремальных задачах. М.”Наука”.1975.

5. Математическое моделирование. М.,”Мир”,1979

6. Щуп Т. Решение инженерных задач на ЭВМ. М.,”Мир”,1982.

7.Фихтенгольц Г.М. Курс дифференциального и интегрального исчисления.

Том 1. Изд-во физ.-мат.лит. Москва 1958- 13 -- 13 -- 13 -

Дата добавления: 2015-08-18