| Министерство образования и науки
российской федерации
федеральное агентство по образованию
Федеральное государственное образовательное учреждение
высшего профессионального образования
«Чувашский государственный университет имени И. Н. Ульянова»
Методы оптимизации
Методические указания к лабораторным работам
Чебоксары 2006
УДК 519.852
Составители: П.В. Желтов,
В.П. Желтов,
С.С. Покалев,
А.П. Димитриев
Методы оптимизации
: Метод. указания к лабораторным работам / Сост. П.В. Желтов и др.; Чуваш. ун-т. Чебоксары, 2006. 24 с.
Составлены в соответствии с государственным образовательным стандартом высшего профессионального образованиия направления подготовки дипломированного специалиста 230100 - Информатика и вычислительная техника специальности 230102 -Автоматизированные системы обработки информации и управления, утвержденным 27.03.2000 (регистрационнный номер 224 тех/дс) и веденным с 1 сентября 2000.
Содержат алгоритмы некоторых методов оптимизации и задания к лабораторным работам.
Для студентов III курса специальности 230102 – «Автоматизированные системы обработки информации и управления»
Утверждено Методическим советом университета
Отв. редактор: канд. физ.-мат. наук доцент Л.В. Желтова
5-7677-0528-3
Лабораторная работа 1
Одномерная оптимизация
А. Алгоритмы одномерной оптимизации.
1. Выбрать начальную точку x
0
, положить k
= 0.
2. На k
-й итерации определить точку f
¢(xk
) и f
²(xk
), вычислить
 .
3. Тест на остановку: если выполнено, то конец. Иначе: положить k
¬ k
+ 1 и вернуться к 2.
Б. Метод секущих.
1. Выбрать начальную точку x
0
, положить k
= 0.
2. На k
-й итерации определить точку f
¢(xk
).
Вычислить
 .
3. Тест на остановку: если выполнено, то конец. Иначе: положить k
¬ k
+ 1 и вернуться к 2.
В. Метод Фибоначчи.
1. Задать число итераций N
, интервал [A
,B
] и точность E
, F
(0):=0; F
(1)=1.
Вычислить числа Фибоначчи:
 F
( I
) =F
(I
– 1) + F
(I
– 2) I
= 2, N
;
x
1
:= A
; x
2
= A
+ (B
– A
)F
(N
– 1) + E(– 1)N
/ F
(N
); x
3
:= B
;
F
2
= f
(x
2
); k
:=1; выбрать начальную точку x
0
, положить k
= 0.
2. x
4
= x
1
– x
2
+ x
3
; F
4
= f
(x
4
).
Если F
4
< F
2
, то если x
2
< x
4
то x
1
:= x
4
, перейти к 3.
Иначе: если x
2
< x
4
, то x
1
:= x
2
; x
2
:= x
4
; F
2
:= F
4
, перейти к 3.
Иначе: x
3
:= x
2
; x
2
:= x
4
; F
2
:= F
4
перейти к 3.
3. Тест на остановку: положить k
:= k
+ 1, если k
£ N
, то перейти к 2. Иначе: конец.
Г. Метод золотого сечения.
1. Выбрать интервал [A
, B
].
T
1 := 0.38196600113; T
2 := 1 – T
1; x
0
:= A
; x
1
:= A
+ T
1(B
– A
);
x
2
:= A
+ T
2
(B
– A
); x
3
:= B
; F
1
:= f
(x
1
); F
2
:= f
(x
2
).
2. Если F
2
< F
1
, то выполнить
I
:= x
3
– x
1
; x
0
:= x
1
; x
1
:= x
2
; x
2
:= x
0
+ T
2
I
; F
1
:= F
2
; F
2
:= f
(x
2
).
Идти к 3.
I
:= x
2
– x
0
; x
3
:= x
2
; x
2
:= x
1
; F
2
:= F
1
; x
1
:= x
0
+ T
1
I
; F
1
:= f
(x
1
).
Идти к 3.
3. Тест на остановку: если выполнено, то конец. Иначе: положить k
:= k
+ 1 и вернуться к 2.
Д. Квадратичная интерполяция.
1. Выбрать первые три точки x
1
, x
2
, x
3
и вычислить значение функции в этих точках F
1
, F
2
, F
3
. Выполнить квадратичную интерполяцию.
2. Вычислить точку минимума:
DN
:= (x
2
– x
3
)F
1
;
DN
:= DN
+ (x
3
– x
1
)F
2
+ (x
1
– x
2
)F
3
;
NM
:= (x
2
x
2
– x
3
x
3
)F
1
;
NM
:= NM
+ (x
3
x
3
– x
1
x
1
)F
2
;
NM
:= NM
+ (x
1
x
1
– x
2
x
2
)F
3
;
x
4
= NM
/ (2 DN
).
Вычислить значение функции F
4
= f
(x
4
).
Упорядочить точки и заменить три лучшие точки. Найти новый интервал.
3. Тест на остановку: если выполнено, то конец. Иначе: положить k
:= k
+ 1 и вернуться к 2.
Е. Метод дихотомии.
1. Выбрать интервал [a
0
, b
0
].
Вычислить с
0
= (a
0
+ b
0
) / 2; d
0
= (a
0
+ c
0
) / 2; e
0
= (c
0
+ b
0
) / 2.
2. Исключить два из четырех подинтервалов, поскольку точка оптимума не может содержаться в них, и оставить только два смежных подинтервала [aK
, cK
] и [cK
, bK
] (отрезок [aK
, bK
] половинной длины).
Вычислить dK
= (aK
+ cK
) / 2 и eK
= (cK
+ bK
) / 2 и значение функции в двух этих точках.
3. Тест на остановку: если выполнено, то конец. Иначе: положить k
:= k
+ 1 и вернуться к 2.
Ё. Метод дихотомии с производными.
1. Определить начальный интервал [amin
, amax
], для которого g'(amin
) < 0, g'(amax
) > 0; k
:= 1.
2. На k
-й итерации: вычислить  ; вычислить g'(ak
). Если g'(ak
)>0, то amax
:= ak
и перейти к 3. Иначе: amin
:= ak
и перейти к 3.
3. Тест на остановку: если выполнено, то конец. Иначе: положить k
:= k
+ 1 и вернуться к 2.
Ж. Кубическая интерполяция.
1. Выбрать начальный интервал [a
, b
], содержащий точку минимума, при этом должно быть выполнено f
'(x
) < 0, f
'(b
) < 0.
2. Вычислить
 .
Вычислить точку минимума  .
3. Тест на остановку: если выполнено, то конец. Иначе: положить a
= x
, если f
'(x
) < 0, и b
= x
, если f
'(x
) > 0. Вернуться к 2.
З. Метод Голдстейна.
1. Определить amin
= 0, amax
= +¥. Найти g
'(0) = Ñf
T
(x
)d
и присвоить переменной a начальное значение (первую тестированную точку).
2. Вычислить g
(a) = f
(x
+ ad
). Если g
(a) £ g
(0) + m
1
ag
'(0), то перейти к 3. Иначе: положить amax
= a и перейти к 3.
3. Вычислить g
'(a) = Ñf
T
(x
+
ad
)d
, затем сравнить g
'(a) и f
(0) + m
2
ag
'(0). Если g
'(a) ≥ g(0) + m
2
ag
'(0), то конец. Иначе: перейти к 4.
4. Положить amin
= a.
5. Найти новое значение для a в интервале [amin
, amax
] и вернуться к 2.
И. Метод Вольфе–Пауэлла.
1. Определить amin
= 0, amax
= +¥. Найти g
'(0) = Ñf
T
(x
)d
и присвоить переменной a начальное значение (первую тестированную точку).
2. Вычислить g
(a) = f
(x
+ ad
). Если g
(a) £ g
(0) + m
1
ag
'(0), то перейти к 3. Иначе: положить amin
= a и перейти к 3.
3. Вычислить g
'(a) = Ñf
T
(x
+
ad
)d
, затем сравнить g
'(a) и m
3
g
'(0). Если g
'(a)≥m
3
g
'(0), то конец. Если g
'(a) < m
3
g
'(0), то перейти к 4.
4. Положить amin
= a.
5. Найти новое значение для a в интервале [amin
, amax
] и вернуться к 2.
Наиболее употребительные критерии окончания
процесса вычислений
|xn
– xn
–1
| < e (метод Ньютона);
K
£ N
(метод Фибоначчи);
I
£ e, I
- длина нового интервала (метод золотого сечения);
|x
1
– x
2
| < e (кубическая интерполяция);
|Ñf
| < e - (кубическая интерполяция), где e - заданная точность.
Контрольные вопросы и задания
1. Для каких функций метод Ньютона–Рафсона имеет конечную сходимость?
2. Какова скорость сходимости метода Ньютона вблизи точки минимума?
3. Приведите пример отсутствия глобальной сходимости метода Ньютона.
4. Какое преимущество имеет метод секущих по сравнению с методом Ньютона?
5. Получите формулу секущих из формулы Ньютона, приближая вторую производную.
6. Почему начальные точки в методе хорд должны быть выбраны достаточно близко к оптимуму?
7. Почему метод Фибоначчи приводит к наименьшему возможному интервалу для конечного числа N
вычислений значений функций?
8. Какое условие обеспечивает независимость длины полученного интервала от результата теста?
9. Как относятся длины последовательных интервалов в методе золотого сечения?
10. Покажите асимптотическую сходимость метода золотого сечения к методу Фибоначчи.
11. Укажите преимущество метода квадратичной интерполяции по сравнению с методами Ньютона и секущих.
12. Для каких функций применима квадратичная интерполяция?
13. Когда применяется метод дихотомии без производных?
14. Насколько уменьшается длина интервала в методе дихотомии?
15. Выведите зависимость длины интервала от количества вычислений значения функции.
16. К каким функциям применим метод дихотомии с производной?
17. Обеспечена ли глобальная сходимость для метода дихотомии?
18. Для каких функций применяется кубическая интерполяция?
19. Как применяется кубическая интерполяция для нахождения минимума, для функций нескольких переменных?
20. В каких алгоритмах применяются методы Голдстейна, а в каких метод Вольфе–Пауэлла?
Задания к лабораторной работе
1. Найти минимум функции:
а) F
(x
) = 2N
(x
– N
)2
+ 16(x
– N
);
б) F
(x
) = 40 + 90(x
– N
)2
;
в) 
с точностями EPS
= 1E–3, 1E–10, 1E–15.
2. Построить график функции N
= 3 на терминале вблизи точки минимума.
Отчет о работе
1. Титульный лист.
2. Задания к лабораторной работе.
3. Алгоритмы численного нахождения минимума.
4. График зависимостей количества итерации от точности решения.
5. Краткий анализ результата поиска минимума указанных выше функций.
6. Вывод по работе.
Список методов
1. Метод Ньютона.
2. Метод секущих.
3. Метод Фибоначчи.
4. Метод золотого сечения.
5. Квадратичная интерполяция.
6. Метод дихотомии.
7. Метод дихотомии с производной.
8. Кубическая интерполяция.
9. Метод Голдстейна.
10. Метод Вольфе–Пауэлла.
Выбор метода решения
1. Порядковый номер студента в журнале по модулю 10.
2. Номер метода +5 по модулю 10.
Список рекомендуемой литературы
1. Карманов В.Г. Математическое программирование. М.: Наука, 1960.
2. Банди Б. Метод оптимизации: Вводный курс: Пер. с англ. М.: Радио и связь, 1988.
Лабораторная работа 2
Методы прямого поиска оптимума
для функции N
переменных
Алгоритмы методов прямого поиска оптимума
для функции
N
переменных
А. Метод покоординатного спуска.
1. Выбрать точку x
0
, k
= 0.
2. На k
-й итерации: из точки xk
произвести поиск минимума вдоль направления оси x
1
и найти точку xk
1
. Произвести поиск из точки xk
1
в направлении к оси x
2
и определить точку xk
2
. Выполнить эту процедуру по всем координатам.
Б. Симплексный метод.
1. Выбрать базовую точку x
0
. Задать масштабный множитель a. Вычислить
 .
Определим остальные вершины симплекса:
 i
, j
=1, 2, …N
.
2. На k
-й итерации: определить  , где x
j
- вершина с наибольшим значением функции. Отразить x
j
относительно xc
. x
= 2
xc
– x
j
;
3. Тест на остановку: если выполнено, то конец. Если не выполнено условие сходимости или некоторая вершина не исключается на протяжении более чем M
= 1,65N
+ 0,05N
2
итерации, то необходимо уменьшить размеры симплекса, построить новый симплекс, выбрав в качестве базовой точку, которой соответствует минимальное значение целевой функции, и перейти к 2.
В. Метод Нелдера–Мида
1. Выбрать x
1
, …, xN
+1
, a, b, g. Вычислить f
1
, …, fN
+1
.
2. Найти xh
, xg
, xz
, fh
, fg
, fz
; fh
- наибольшее, fg
- следующее за ним, fz
- наименьшее значение функции.
3. Найти 
4. Найти xr
, fr
, отразив точку xh
относительно x
0
:
xr
= (1 + a) x
0
– axh
.
5. Если fr
< fz
, то производим растяжение симплекса – находим xe
= gxr
+
(t
– g) x
0
, fe
= f
(xe
).
6. Если fe
< fz
, то xh
:= xe
.
Проверка на сходимость. Если сходимость достигнута, то конец. В противном случае перейти на шаг 2.
7. Если fe
≥ fz
, то xh
:= xr
.
Проверка на сходимость. Если сходимость достигнута, то конец. B противном случае перейти на шаг 3.
8. Если fr
> fz
, нo fr
£ fg
, то xh
:= xr
.
Проверка на сходимость. Если сходимость не достигнута, то возвратиться на шаг 2.
9. Если fr
> fz
и fr
> fg
, то перейти на шаг 10.
10. Если fr
> fh
, то перейти к 11.
Если fr
< fh
, то xh
:= xr
и fh
:= fr
. Перейти к 11.
11. Так как fr
> fh
, то переходим к шагу сжатия:
xc
= b xh
+ (1 – b)x
0
.
12. Если fc
< fh
, то xh
:= xc
, и если сходимость не достигнута, то возвратиться на шаг 2.
13. Если fc
> fh
, то перейти на шаг 14.
 14. Уменьшить размерность симплекса xi
:= (xi
+ xz
)/2. Вычислить fi
для i
= 1, N
+ 1. Проверка на сходимость. Если она не достигнута, возвратиться на шаг 3.
Г. Метод Хука–Дживса:
 1. Определить начальную точку x
0
, приращение Di
, i
= 1, N
.
Коэффициент уменьшения шага a > 1, параметр окончания поиска E
.
2. Провести исследовательский поиск.
3. Если исследовательский поиск удачный (найдена точка с меньшим значением целевой функции), перейти к 5. Иначе перейти к 4.
4. Тест на остановку: если выполнено, то конец. Иначе: уменьшить приращение.
 , перейти к шагу 2.
5. Провести поиск по образцу
xp
(
K
+1)
= xK
+ (xK
– xK
–1
).
6. Провести исследующий поиск, используя xp
K
+1
в качестве базовой точки. Пусть xK
+1
- полученная в результате точка.
7). Если выполняется неравенство f
(xK
+1
) < f
(xK
), то положить xK
–1
= xK
и xK
= xK
+1
. Перейти к 5. Иначе: перейти к 4.
Основные обозначения:
xK
- текущая базовая точка;
xK
–1
- предыдущая базовая точка;
xp
K
+1
- точка, построенная при движении по образцу;
xK
+1
- следующая (новая) базовая точка.
Критерии проверки сходимости
1.  ;  ; s < e (метод Нелдера–Мида).
2. h
< e (метод Хука–Дживса), h
–шаг.
Контрольные вопросы
и задания
1. Назовите достоинства и недостатки прямых методов поиска для функций и переменных.
2. В чем преимущество метода Хука–Дживса по сравнению с методом покоординатного спуска?
3. В каких случаях удобно использовать симплексный метод?
4. Обеспечивают ли эти методы глобальную сходимость?
5. Для решения каких задач целесообразно использовать метод Нелдера–Мида?
6. Дайте геометрическую иллюстрацию всех четырех методов оптимизации.
7. Какой из приведенных методов целесообразно использовать для оптимизации технологических процессов в условиях производства?
Задание к лабораторной работе
Найти минимум функций:
1) F
(x
1
, x
2
) = N
(x
2
– x
1
2
)2
+ (N
– x
1
)2
2) F
(x
1
, x
2
, x
3
, x
4
) = (x
1
+ Nx
2
)2
+ N
(x
3
– x
4
)2
+ (x
2
– Nx
3
)4
+
+N
(x
1
– x
4
)4
с точностями EPS
=1E-3, 1E-5, 1E-10, 1E-15.
Отчет о работе
1. Титульный лист.
2. Задание к лабораторной работе.
3. Алгоритмы численного нахождения минимума.
4. Графики зависимости количества итерации от точности решения.
5. Краткий анализ результатов поиска минимума указанных выше функций.
6. Вывод по работе.
Список методов
1. Метод покоординатного спуска.
2. Симплекс метод.
3. Метод Нелдера–Мида.
4. Метод Хука–Дживса.
Выбор метода решения
1. Порядковый номер студента в журнале по модулю 4.
2. Номер первого метода +5 по модулю 4.
Список рекомендуемой литературы
1. Карманов В.Г. Математическое программирование. М.: Наука, 1980.
2. Банди Б. Метод оптимизации: Вводный курс: Пер. с англ. М.: Радио и связь, 1988.
Лабораторная работа 3
Численные методы для оптимизации
дифференцируемых функций
Описание алгоритмов
А. Алгоритм градиента с заранее заданным шагом.
1. Выбрать начальную точку x
0
и число l > 0. Положить k
= 0.
2. На k
-й итерации  , где Ñk
; lk
> 0.
3. Тест на остановку: если выполнен, то конец. Иначе: выполнить k
¬k
+1 и возвратиться к 2.
Б. Алгоритм наискорейшего спуска.
1. Выбрать начальную точку x
0
. Положить k
= 0.
2. На k
-й итерации dk
= – Ñf
(xk
). Найти такое число lk
, что f
(xk
+ lk
dk
) = min{f
(xk
+ ldk
)}. Положить xk
+1
= xk
+ lk
dk
;
3. Тест на остановку: если выполнен, то конец. Иначе: выполнить k
¬k
+1 и возвратиться к 2.
В. Алгоритм сопряженного градиента для квадратичных функций.
1. Выбрать начальную точку x
0
. Определить g
= Ñq
(x
0
) = Ax
0
+ b
.
Положить d
0
= – g
0
, k
= 0.
2. На k
-й итерации определить
 , xk
+1
= xk
+ lk
dk
, gk
+1
= Ñq
(xk
+1
),  , dk
= – gkH
+ bk
dk
.
3. Тест на остановку: если выполнен, то конец. Иначе: выполнить k
¬k
+1 и возвратиться к 2.
Г. Алгоритм Фленча–Ривза.
1. Выбрать начальную точку x
0
. Положить d
0
= – Ñf
(x
0
), K
= 0.
2. На K
-й итерации выбрать l, минимизирующую функцию g
(l)= =f
(xK
K
+ ld
), положить xK
+1
= xK
+ lK
dK
;
 ;
dK
= – Ñf
(xK
+1
)+ bK
dK
.
3. Тест на остановку: если выполнен, то конец. Иначе: выполнить k
¬k
+1 и возвратиться к 2.
Д. Алгоритм метода Ньютона, модифицированного метода Ньютона, метода Марквардта.
1. Выбрать начальную точку x
0
, K
= 0.
2. На K
-й итерации для метода Ньютона - xK
+1
= xK
– [Ñ2
f
(xK
)]–1
Ñf
(xK
);
для модифицированного метода Ньютона xK
+1
= xK
– lK
[Ñ2
f
(xK
)]–1
Ñf
(xK
);
для метода Марквардта xK
+1
= xK
–[mI
+ Ñ2
f
(xK
)]2
Ñf
(xK
), где m0
= 104
; mK
=m0
/K
.
3. Тест на остановку: если выполнен, то конец. Иначе: выполнить k
¬k
+1 и возвратиться к 2.
Е. Алгоритм Давида–Флетчера–Пауэлла (ДФП).
1. Выбрать начальную точку x
0
; положить Н
0
=I
, где I
- единичная матрица; K
=0;
2. На K
-й итерации dK
= – HK
Ñf
(xK
). Найти такое l ³ 0, чтобы
f
(xK
+ lK
dK
) = min{f
(xK
+ ldK
)}.
Положить xK
+1
= xK
+ lK
dK
; sK
= xK
+1
– xK
; gK
= Ñf
(x
K
+1
) – Ñf
(x
K
);
 .
3. Тест на остановку: если выполнен, то конец. Иначе: выполнить k
¬k
+1 и возвратиться к 2.
Ж. Алгоритм Бройдена–Флетчера–Гольдфарба–Шанно (БФГШ).
1. Выбрать начальную точку x
0
. Положить Н
= I
, где I
- единичная матрица; K
= 0.
2. На K
-й итерации dK
= – HK
Ñf
(xK
).
Найти такое l ³ 0, чтобы f
(xK
+ lK
dK
) = min{f
(xK
+ ldK
)}. Положить xK
+1
= xK
+ lK
dK
; sK
= xK
+1
– xK
; gK
= Ñf
(xK
+1
) – Ñf
(xK
),
 .
3. Тест на остановку: если выполнен, то конец. Иначе: выполнить k
¬k
+1 и возвратиться к 2.
Наиболее употребительные критерии для определения
окончания процесса вычислений
1.  (e > 0 задано).
2.  (e > 0 задано).
3. |f
(xK
+1
) – f
(xK
)| < h (h > 0 задано).
Тест должен быть проверен на p
последовательных итерациях, в лабораторной работе взять значение p
= 3.
Контрольные вопросы
и задания
1. В чем основная особенность методов градиента с заданным шагом?
2. Приведите основной недостаток метода наискорейшего спуска на примере некоторых типов функций.
3. Как расположены последовательные направления перемещения метода наискорейшего спуска?
4. Почему метод минимизации должен обеспечить быструю сходимость на квадратичных функциях?
5. Какие направления называются сопряженными?
6. В чем заключается суть методов сопряженных направлений?
7. За какое количество шагов обеспечивается сходимость метода сопряженного градиента для квадратичных функций?
8. В чем отличие метода Флетчера–Ривза от метода сопряженного градиента?
9. Какую информацию необходимо хранить в памяти ЭВМ в методе Флетчера–Ривза?
10. За какое количество итераций сохранится метод Ньютона при применении к строго выпуклой квадратичной функции?
11. Обеспечивается ли метод Ньютона для произвольных функций?
12. Какому требованию должен удовлетворять гессиан в методе Ньютона?
13. Назовите способы получения положительно определенной матрицы в методе Ньютона.
14. Какой общий подход положен в основу квазиньютоновских методов?
15. Какому требованию отвечает аппроксимация обращения гессиана функций в квазиньютоновских методах?
16. Какие формулы коррекции использованы в методах ДФП и БФГШ?
17. Как ведет себя алгоритм ДФП к неточностям в подзадачах одномерной минимизации?
18. В чем отличие алгоритма Бройдена-Флетчера-Гольдфарба-Шанно от алгоритма Давида-Флетчера-Пауэлла?
19. Чему пропорциональна загрузка памяти в квазиньютоновских методах?
20. Оцените объем промежуточных вычислений в квазиньютоновских методах.
Задание
к лабораторной работе
Найти минимум функций:
а) F
(x
1
, x
2
) = N
(x
2
– x
1
2
)2
+ (N
– x
1
)2
;
б) F
(x
1
, x
2
, x
3
, x
4
) = (x
1
+ Nx
2
)2
+ N
(x
3
– x
4
)2
+ (x
2
– Nx
3
)4
+
+N
(x
1
– x
4
)4
с точностями Е
=10-3
,10-5
,10-10
,10-15
.
Отчет о работе
1. Титульный лист.
2. Задание к лабораторной работе.
3. Алгоритмы численного нахождения минимума.
4. Графики зависимости количества итерации от точности решения.
5. Краткий анализ результатов поиска минимума указанных выше функций.
6. Вывод по работе.
Список методов
1. Метод градиента с заранее заданным шагом.
2. Метод наискорейшего спуска.
3. Метод сопряженных направлений.
4. Метод сопряженного градиента для квадратичных функций.
5. Метод Флетчера–Ривза.
6. Метод Ньютона.
7. Метод Давида–Флетчера–Пауэлла.
8. Метод Бройдена–Флетчера–Гольдфарба–Шанно.
Выбор метода решения
1. Порядковый номер студента в журнале по модулю 8.
2. Номер первого метода +5 по модулю 8.
Список рекомендуемой литературы
1. Сухорев А.Г., Тимохов А.В., Федоров В.Б. Курс методов оптимизации. М.: Радио и связь, 1988.
2. Поляк Б.Т. Введение в оптимизацию. М.: Наука, 1983.
3. Гуськин С.А., Омельянов Г.А., Резников Г.А., Сироткин В.С. Минимизация в инженерных расчетах на ЭВМ. М.: Машиностроение, 1981.
4. Банди Б. Метод оптимизации: Вводный курс: Пер. с англ. М.: Радио и связь, 1988.
Лабораторная работа 4
Линейное программирование
Алгоритмы симплекс-методов
А. Симплекс-метод.
1. Ввести размерность задачи. Ввести коэффициенты в канонической форме, базисные переменные и задать небазисные переменные.
2. Найти наименьший из коэффициентов C
'm
+1
, …, C
's
, …,C
'n
. Пусть это коэффициент C
's
. Если C
's
³ 0, то конец, оптимум найден. Иначе: C
's
<0, и переменная Xs
войдет в базис, перейти к 3.
3. Если все a
'
is
£ 0, то конец.
Решение лежит вне заданных границ. Иначе: вычислить B
'i
/ a
'
is
для всех a
'
is
>0 и найти минимум B
'i
/ a
'
is
.
Пусть этот минимум равен br
/ a
'
is
. Тогда Xs
– базисная переменная, а Xr
– свободная переменная.
4. Построить новую каноническую форму, изменить базис и перейти к 2.
Б. Двойственный симплекс-метод.
1. Пусть все коэффициенты целевой функции положительны.
2. Найти отрицательную базисную переменную. Если ее нет, то оптимальное решение найдено; если их более чем одна, надо взять из них наименьшую. Пусть эта базисная переменная в r
-м ограничении, она является переменной для исключения из базиса.
3. В r
-й строке найти отрицательный коэффициент arj
.
4. Если такого коэффициента нет, то не существует допустимого решения задачи. Для отрицательных коэффициентов в этой
строке найти  .
5. Если этот минимум найден в S
-м столбце, переменная Xs
должна быть включена в базис.
6. Провести обычные симплекс-преобразования, выбрав в качестве ведущего элемента a
'
rs
.
В. Улучшенный симплекс-алгоритм.
1. Пусть задача представлена в канонической форме. Базисные переменные Xn
+1
, …, Xn
+
m
равны соответственно b
1
, …, bm
. Обращение базиса есть просто Im
– единичная матрица размерностью m
´m
. Соответствующие симплекс-множители – это p1
= 0, …, pm
= 0, поскольку в целевую функцию Z
не входят базисные переменные.
2. На k
-й итерации базисные переменные – это X
1
, …, Xm
, которые принимают значения b
'1
, …, b
'm
. Обращение базиса – матрица B
–1
размерностью m
´m
, а симплекс-множители равны p1
, …, pm
.
3. Вычислить коэффициенты небазисных переменных в канонической форме целевой функции в текущем базисе:
 ,
где pi
- текущие симплекс-множители, aij
- исходные коэффициенты из уравнения.
4. Величины C
'j
вычисляются для каждой небазисной переменной. Найти наименьший из коэффициентов C
'm
+1
, …, C
'n
.
5. Если C
's
³ 0, то минимум функции Z
найден, конец. Иначе: C
's
< 0, и переменная Xs
войдет в базис.
6. Определить переменную, которая будет заменена переменной Xs
. С этой целью вычислить a
's
= B
–1
*as
.
7. Определить строку базисной переменной, предназначенной для исключения из базиса  .
Заменить старый базис X
1
, …, Xr
, …, Xm
на новый X
1
, …, Xs
, …, Xm
. Новые значения базисных переменных равны
 ; Xi
= bi
+
= b
'i
– ais
*br
+
; (i
¹ r
).
8. Cформировать матрицу:
 - r
-я строка
5-я строка
9. Вычислить (новое обращение) =Е
 (исходное обращение).
10. Найти новые симплекс-множители. Исходные значения симплекс-множителей  .
11. Новые значения симплекс множителей
 .
Вернуться к 2.
Контрольные вопросы и задания
1. Как определяется направление возрастания целевой функции в графическом методе решения задачи линейного программирования (ЛП)?
2. Дайте характеристику стандартной формы задач линейного программирования.
3. Приведите основные правила для преобразования задачи ЛП к стандартному виду.
4. Каким соотношением задается отрезок в n
-мерном пространстве?
5. Дайте определение экстремальной точки.
6. Какое множество называется выпуклым?
7. Докажите, что если ограничения имеют допустимое решение, то они имеют и базисное решение.
8. Докажите, что допустимая область является выпуклым множеством.
9. Докажите, что базисные допустимые решения соответствуют вершинам выпуклого множества.
10. Докажите, что если целевая функция имеет конечный минимум, то, по крайней мере, одно оптимальное решение является базисным.
11. Дайте характеристику канонической формы задачи ЛП.
12. Выведите основные соотношения для симплекс-метода.
13. Назовите основные шаги симплекс-метода.
14. Какой базис называется вырожденным?
15. Рассмотрите изменения значений правых частей.
16. Рассмотрите изменения коэффициентов целевой функции.
17. Как решается задача ЛП при появлении дополнительных переменных?
18. Опишите решение задачи ЛП при включении дополнительных ограничений.
19. Приведите основные шаги двойственного симплекс-метода.
20. Приведите основные шаги улучшенного симплекс-метода.
21. Основные правила перехода к двойственной задаче.
22. Докажите, что двойственной задачей к двойственной задаче есть прямая задача.
23. Докажите, что Z
³ W
, где W
– целевая функция двойственной задачи.
24. Докажите, что если прямая задача имеет конечное решение, то двойственная задача имеет конечное решение W
max
= Z
min
.
25. Докажите, что значения симплекс-множителей оптимального решения двойственной задачи являются значениями переменных в оптимальном решении прямой задачи.
Задание к лабораторной работе
Составить диету, содержащую 20 единиц белков, 30 единиц углеводов, 10 единиц жиров и 40 единиц витаминов, из пяти продуктов. Как дешевле всего достичь этого при указанных в таблице ценах на 1 кг (или на 1 л) продуктов?
Таблица
| Хлеб
|
Соя
|
Сушеная рыба
|
Фрукты
|
Молоко
|
| Белки
Углеводы
Жиры
Витамины
|
2
12
1
2
|
12
0
8
2
|
10
0
3
4
|
1
4
0
6
|
2
3
4
2
|
| Цена
|
12
|
36
|
32
|
18
|
10
|
Отчет о работе
1. Титульный лист.
2. Задание к лабораторной работе.
3. Алгоритм метода.
4. Программа решения задачи.
5. Краткий анализ результатов вычисления.
6. Выводы по работе.
Список методов
1. Симплекс-метод.
2. Улучшенный симплекс-метод.
3. Двойственный симплекс-метод.
Выбор методов решения
1. Порядковый номер студента в журнале по модулю 3.
2. Номер первого метода +2 по модулю 3.
Список рекомендуемой литературы
1. Карманов В.Г. Математическое программирование. М.: Наука, 1980.
2. Банди Б. Метод оптимизации: Вводный курс: Пер. с англ. М.: Радио и связь, 1988.
Оглавление
| Лабораторная работа 1. Одномерная оптимизация…………...
|
3
|
| Лабораторная работа 2. Методы прямого поиска оптимума для функции N
переменных…………………………………….
|
9
|
| Лабораторная работа 3. Численные методы для оптимизации дифференцируемых функций…………………………………..
|
13
|
| Лабораторная работа 4. Линейное программирование……….
|
18
|
Методы оптимизации
Методические указания к лабораторным работам
Отв. за выпуск О.М. Садовникова
Подписано в печать 20.10.06. Формат 60×84/16. Бумага газетная. Гарнитура Times. Печать оперативная. Усл. печ. л. 1,39. Уч.-изд. л. 1,25. Тираж 50 экз. Заказ № 676.
Чувашский государственный университет
Типография университета
 428015 Чебоксары, Московский просп., 15
Министерство образования и науки
российской федерации
федеральное агентство по образованию
Федеральное государственное образовательное учреждение
высшего профессионального образования
«Чувашский государственный университет имени И. Н. Ульянова»
Методы оптимизации
Методические указания к лабораторным работам
Чебоксары
2006
|