Решение типовых задач теории оптимизации

Введение

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

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

Одним из наиболее общих подходов к решению задачи поиска экстремума (локального максимума или минимума) функции при наличии связующих ограничений на ее переменные (или, как еще говорят, задачи условной оптимизации) является метод Лагранжа. Данный метод используется в задачах 1, 6, 7, 8 данной курсовой работы.

Задача 1. Решить задачу выпуклого программирования

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

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

1)Рассмотрим случай :

?

Получаем нулевые , нулевой Лагранжиан решение отсутствует

)Рассмотрим случай:

2.1) Пусть :

??

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

.2) Пусть :

??

??

?

- не может быть точкой минимума

.3) Пусть :

??

?

? - не может быть точкой минимума

.4) Пусть :

??

??

??

- не может быть точкой минимума.

Таким образом точка (25/7, -48/7) является точкой глобального минимума функции .

Задача 2. Решить задачу линейного программирования графическим методом. Во всех вариантах

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

Построим график для новой системы уравнений и нанесем линию уровня:

Для получения координат точки максимума исследуемой функции линию положения нужно передвигать вправо (т.к. функция прямо пропорциональна x1) и вниз (т.к. функция обратно пропорциональна x2) до крайнего положения.

Точка максимума находится на пересечении двух прямых, задаваемых уравнениями:

Таким образом, точка M(1, 1/2) является точкой максимума данной функции.

Задача 3. Решить задачу № 2 симплекс-методом, используя в качестве первоначальной крайней точки

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

;

?ijx1x2?ix3122x42-21x5-121f(x)-420pjИщем среди коэффициентов pi (коэффициентов целевой функции) pi<0, берем соответствующий этому элементу столбец (кроме столбца свободных членов). Для выбора опорного элемента необходимо найти, какой из них удовлетворит условию минимума отношения свободного члена к данному элементу: , причем

После выбора опорного элемента совершаем пересчет таблицы:

опорный элемент заменяем на единицу, деленную на опорный элемент;

опорную строку делим на опорный элемент;

опорный столбец делим на опорный элемент и умножаем на минус единицу;

остальные элементы считаем по "правилу определителя" (при этом беря со знаком "+" произведение, содержащее опорный элемент) и делим на опорный элемент

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

?ijx1x2?i?ijx4x2?i?ijx4x3?ix3122x3-1/233/2x2-1/631/2x42-21?x11/2-11/2?x11/31/31x5-121x5-1/213/2x5-1/3-1/31f(x)-420f(x)2-22f(x)5/32/33

Таким образом, мы получили сходный ответ с полученным во второй задаче: точка с координатами x1=1, x2=1/2, x3=2/3, x4=-1/6, x5=1,

.

.

Задача 4. Решить простейшую задачу классического вариационного исчисления

Воспользуемся уравнением Эйлера-Лагранжа для решения простейшей задачи:

.

Предположим, что:

Подставим в исходное уравнение:

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

- экстремаль

Исследуем экстремаль на предмет доставления функции максимума/минимума:

Проинтегрируем по частям: , где:

- точка является точкой максимума.

Задача 5. Решить задачу Больца

- Интегрант

- Терминант

Воспользуемся уравнением Эйлера-Лагранжа для решения задачи Больца:

.

- экстремаль

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

Посчитаем каждый элемент:

Тогда условия трансверсальности запишутся:

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

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

Проинтегрируем по частям: , где:

А также воспользуемся условием: и в подстановке 0 и 1 (для подсчета значения элемента ):

,

- отрицательный результат - следовательно является точкой максимума.

Задача 6. Решить изопериметрическую задачу

; ,

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

.

1) - нет решений (Лагранжиан не м. б. равен нулю)

)

Воспользуемся краевыми условиями для нахождения констант:

,

- Воспользуемся уравнением для нахождения :

Исследуем экстремаль на предмет доставления функции максимума/минимума:

Проинтегрируем по частям: , где:

Так как , тоже должна быть равна нулю, следовательно

- точка минимума.

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

Выпишем, как положено, функцию Лагранжа:

Воспользуемся уравнением Эйлера-Лагранжа для решения задачи с подвижными концами:

.

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

Посчитаем каждый элемент:

Тогда условия трансверсальности запишутся:

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

Пусть Тогда также равны нулю - нет решений.

Пусть , тогда:

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

,

В уравнение стационарности также подставим , используя уравнение, написанное выше:

Рассмотрим , тогда а - что является недопустимым значением

Рассмотрим , тогда и

Итак, мы получили:

,

;,

Исследуем экстремаль на предмет доставления функции максимума/минимума:

Воспользуемся и h(0)=0 (в силу наложенного ограничения на левый конец).

Также, стоит выразить значение из уравнения , помня, что , а

Итак:

- следовательно найденная точка является точкой минимума.

Задача 8. Решить задачу Лагранжа

; , ,

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

; , ,

Запишем функцию Лагранжа:

1)Воспользуемся уравнением Эйлера-Лагранжа для решения задачи с Лагранжа. Оно запишется отдельно относительно x1 и x2 и образует, таким образом, систему уравнений:

2)Воспользуемся условиями трансверсальности:

- уравнения, записанные относительно x1

- уравнения, записанные относительно x2

,

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

Тогда, пусть :

Из уравнения

Из

Из получим:

, сделаем замену

Решим однородное уравнение:

,

Теперь решим неоднородное:

Пусть . Подставим:

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

Таким образом, очевидно:

,

,

Получаем:

, ,

Исследуем экстремаль функции на предмет доставления ей максимума/минимума:

Интегрируем по частям:

.

Таким образом, разница оказалась больше равна нулю. Это значит, что точка является точкой минимума.

Заключение

лагранж вариационный исчисление изопериметрический

В курсовой работе получены решения семи типовых задач теории оптимизации: двух конечномерных (задачи выпуклого программирования и линейного программирования) и пяти задач вариационного исчисления (простейшей задачи вариационного исчисления, задачи Больца, изопериметрической задачи, задачи с подвижными концами и задачи Лагранжа)

В результате работы над настоящей курсовой работой были достигнуты следующие цели:

1. расширен объем и углублены теоретические знания по дисциплине "Методы оптимизации";

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

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

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

Список использованных источников

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

. Алексеев В.М., Галеев Э.М., Тихомиров В.М. Сборник задач по оптимизации. Москва : Наука, 1984.

. Галеев Э.М., Тихомиров В.М. Оптимизация: теория, примеры, задачи. Москва.: Эдиториал УРСС, 2000.

. Галеев Э.М. Оптимизация: теория, примеры, задачи. Москва : УРСС, 2002.

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

. Шатина А.В. Методы оптимизации. Практические занятия. М.: МИРЭА, 2012,

. Методы оптимизации. 4-ый курс. Контрольные задания для студентов факультета Кибернетики. М.: МИРЭА, 2010.