Контрольные работы по методам оптимизации (стр. 1 )

МИНИСТЕРСТВО ОБЩЕГО И ПРОФЕССИОНАЛЬНОГО

ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ

САМАРСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

Кафедра МиБИ

КОНТРОЛЬНЫЕ РАБОТЫ

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

Издательство “Самарский университет”

Содержание

1.  ЛАБОРАТОРНАЯ РАБОТА № 1 «Алгоритм поиска промежутка локализации

точки оптимума функции »………………………………………………………………… 3

2.  ЛАБОРАТОРНАЯ РАБОТА № 2 «Методы первого порядка: алгоритм деления отрезка пополам»………………………………………………………………………………............ 4

3.  ЛАБОРАТОРНАЯ РАБОТА№ 3 «Методы многомерной оптимизации. Методы покоординатного поиска»………………………………………………………… 4

4.  ЛАБОРАТОРНАЯ РАБОТА № 4 «Задача линейного программирования. Отыскание базисных решений и опорных планов в задаче линейного программирования»………………………………………………………………………… 6

5.  ЛАБОРАТОРНАЯ РАБОТА № 5 «Решение задачи ЛП симплекс - методом искусственного базиса»……………………………………………………………………. 12

ЛАБОРАТОРНАЯ РАБОТА № 1

Алгоритм поиска промежутка локализации точки оптимума функции

Начальные данные: , , где - начальный шаг, х – начальная точка, m - коэффициент увеличения шага.

1 шаг: Вычисляем значение функции в двух точках и .

2 шаг: Если , то переход на шаг 3, иначе переход на шаг 4.

3 шаг: Меняем направление поиска промежутка локализации, т. е. и возвращаем на 1 шаг.

4 шаг: Если , переход на шаг 5, иначе переход на шаг 6:

5 шаг: Проводим вычисления:

5.1 Вычисляем значение функции в старой точке ; ;

5.2. Пересчитываем промежуток: ;

5.3. Вычисляем значение функции в точке , ;

5.4. Переход на шаг 4.

6 шаг: Если , то переход на шаг 7, иначе переход на шаг 8.

7 шаг: Концы промежутка локализации вычисляем по формуле:

; .

8 шаг: Концы промежутка локализации вычисляем по формуле:

;.

В результате работы алгоритма получаем интервал [a, b], содержащую точку оптимума и точку x Î[a, b].

Задание

Определите промежуток локализации минимума функции j(x) = (x – d) ( x – 1)3. В качестве начальных данных взять x = 1, Dx = 1, m =2

Варианты заданий

№ варианта	1	2	3	4	5	6	7	8	9	10	11	12	13
d	5	7	8	8	1	3	3	1	2	-5	-7	-8	-8
l	6	8	9	10	4	5	4	3	4	-6	-8	-9	-10
№ варианта	14	15	16	17	18	19	20	21	22	23	24	25
d	-1	-3	-3	-1	-2	0	0	2	-2	-4	3	4
l	-4	-5	-4	-3	-4	-5	5	6	-6	0	6	9

Результаты расчетов поместить в таблицу, имеющую вид:

x	Fx	Dx	y	Fy

Значения a и b получены в результате алгоритма выписываются ниже таблицы.

ЛАБОРАТОРНАЯ РАБОТА № 2

Методы первого порядка: алгоритм деления отрезка пополам

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

2 шаг: Если то переход на шаг 7, иначе переход на шаг 3.

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

4 шаг: Если переход на шаг 7, иначе переход на шаг 5.

5 шаг: Если переход на шаг 6, иначе переход на шаг 7.

6 шаг:

6.1. Вычисляем середину отрезка :

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

6.3. Если , то переход на шаг 6;

6.4. Если , то ;

6.5. Если , то ;

7 шаг: .

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

ЛАБОРАТОРНАЯ РАБОТА № 3

Методы многомерной оптимизации.

Методы покоординатного поиска

Рассматривается задача поиска безусловного минимума функции f(x), зависящей от нескольких переменных, т. е. поиск такой точки x* Rn , что

Метод простого покоординатного поиска заключается в следующем. Берем начальную точку x0 и вектор λ величин шагов по каждому направлению, и полагаем x*=x0. Из точки x* пытаемся перейти в точку x’ изменением только первой координаты на величину λ[1]. Если эта попытка удачная, т. е. f(x’)<f(x*), то увеличиваем величину шага λ[1] в α > 1 раз, λ[1]:= λ[1]*α и переходим в точку x’, полагая x*=x’. Если попытка неудачная, т. е. f(x’)≥f(x*), то изменяем величину и направление шага λ[1], полагая λ[1]:= λ[1]*β, где -1<β<0. Затем переходим к следующему координатному направлению, т. е. начинаем двигаться по следующей координате. По окончании спуска по всем n координатным направлениям оцениваем │x0-x*│ и │ λ │. Если эти величины меньше заданного числа ε, то процесс прекращаем, иначе полагаем x0= x’. и процесс начинаем сначала. Эта процедура вполне оправдывает название метода. С ее помощью мы построим последовательность точек, которой соответствует монотонно-убывающая последовательность значений функции. Обрывая ее на некотором шаге можно приближенно принять  значение функции за ее наименьшее значение в рассматриваемой области.

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

Алгоритм простого покоординатного поиска

Шаг 1. Задать начальную точку x0, число ε > 0 для остановки алгоритма, начальную величину шагов по первому координатн6ому направлению λ[1] , ускоряющий множитель α > 1 и коэффициент -1<β<0. Положить x*=x0.

Шаг 2. Для k:=1 до n выполнить

Начало 2

s:=ek (здесь далее ek – k-ый орт, т. е. k-ое координатное направление);

x’:=x*+ λ[k]*s;

F(x’):=φ(x’);

Если F(x’)<F(x*) (т. е. шаг удачный) , то

Начало 3

x*:=x’; F(x*):=F(x’) (т. е. осуществляем переход в новую точку); λ[k]:= λ[k]*α (увеличиваем величину шага);

Конец 3;

Иначе λ[k]:= λ[k]*β.

Конец 2.

Шаг 3. Проверить условия окончания:

a)  если (│x0-x*│>ε) и (│λ│≥ε), то x0:=x*; F(x0):=F(x*); перейти к шагу 2.

b)  Если (│λ│<ε), то xmin:=x*, min f(x):= φ(x*).

Конец алгоритма.

Алгоритм исчерпывающего покоординатного поиска

Ставится задача поиска безусловного минимума функции f(x), зависящей от нескольких переменных, т. е. поиск такой точки x* Rn , что

Этот метод во многом похож на метод простого покоординатного поиска. В нем также происходит движение каждый раз по одной из координат. Отличие состоит в том, что при удачном переходе из точки x* в x’ осуществляется дальнейший спуск по этому координатному направлению до тех пор, пока шаг не станет неудачным. Тогда осуществляется переход к следующему координатному направлению. При этом шаг уменьшается в β раз.

Шаг 1. Задать начальную точку x0, число ε > 0 для остановки алгоритма, начальную величину шагов по первому координатн6ому направлению λ[1] , ускоряющий множитель

α > 1 и коэффициент -1<β<0. Положить x*=x0.

Шаг 2. Для k:=1 до n выполнить

Начало 2

s:=ek ;

x’:=x*+ λ[k]*s;

F(x’):=φ(x’);

Пока F(x’)<F(x*) (т. е. шаг удачный) , выполнить

Начало 3

x*:=x’; F(x*):=F(x’) (т. е. осуществляем переход в новую точку); λ[k]:= λ[k]*α (увеличиваем величину шага);

x’:=x*+ λ[k]*s;

F(x’):=φ(x’);

Конец 3;

λ[k]:= λ[k]*β;

Конец 2.

Шаг 3. Проверить условия окончания:

c)  если (│x0-x*│>ε) и (│λ│≥ε), то x0:=x*; F(x0):=F(x*); перейти к шагу 2.

d)  Если (│λ│<ε), то xmin:=x*, min f(x):= φ(x*).

Конец алгоритма.

Алгоритм экстремального покоординатного поиска

Ставится задача поиска безусловного минимума функции f(x), зависящей от нескольких переменных, т. е. поиск такой точки x* Rn , что

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

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

Шаг 1. Задать начальную точку x0, число ε > 0 для остановки алгоритма. Положить x*=x0.

Шаг 2. Для k:=1 до n выполнить

Начало 2

s:=ek ;

λ[k]=argmin (x*+ λ[k]*s);

λ

x’:=x*+ λ[k]*s;

x*:=x’;

Конец 2.

Шаг 3. Проверить условия окончания:

e)  если (│x0-x*│>ε) и (│λ│≥ε), то x0:=x*; F(x0):=F(x*); перейти к шагу 2. Условие (│λ│≥ε) можно не проверять, так как оно эквивалентно условию (│x0-x*│>ε).

f)  Если (│λ│<ε), то xmin:=x*, min f(x):= φ(x*).

Конец алгоритма.

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

ЛАБОРАТОРНАЯ РАБОТА № 4

Задача линейного программирования. Отыскание базисных решений и опорных планов в задаче линейного программирования

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

от n вещественных переменных при наложенных ограничениях:

,

, где

aij, bij и cj – заданные постоянные величины.

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

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

Общая задача имеет несколько форм записи.

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

минимизировать (максимизировать) линейную функцию

при ограничениях

, , где

;

;

– скалярное произведение.

Векторы

состоят соответственно из коэффициентов при неизвестных и свободных членов.

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

при ограничениях

, ,где

– матрица-строка;

, – матрица-столбец;

– матрица коэффициентов системы ограничений.

Задание

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

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

2.Выбрать базис. Привести задачу к выбранному базису.

3. Среди базисных решений выбрать решение, не являющееся опорным планом.

Пример:

Приведем задачу к каноническому виду:

Запишем симплекс таблицу:

	4	2	1	1	1	0
	2	1	-1	-1	0	-1

Выберем в качестве базисных переменные , .