Алгоритм нелокального случайного поиска на минимум целевой функции
Найти min Z = 
при условии аj ≤ xj ≤ bj; j = 1 ÷ n,
где – выпуклая функция.
1. Выписываем область допустимых значений ω( аj ≤ xj ≤ bj ); где j=1÷n.
2. Подготавливаем начальный вектор 
(а1, а2, ..., аn) = (x1нижняя граница, x2нижняя граница,…,xnнижняя граница) = ( x10, x20, ..., xn0 ), координатами служат нижние границы измерения координат из области допустимых решений ω.
3. Вводим целевую функцию Z = .
4. Вычисляем целевую функцию при 
= , Z = f( ).
5. Вводим счетчик неудачных испытаний S = 0, N = 1000 – контрольное число.
6. Формируем массив случайных чисел λ.
7. Формируем случайный вектор 
, где Î w, координаты которого вычисляются по правилу xj1 = xjнижняя граница +λj ּxjверхняя граница = аj + λj ּbj.
8. Вычисляем целевую функцию при = , Z = f( ).
9. Сравниваем f( ) и f( ).
10. Если испытание удачное, то есть если f( ) <f( ), то переход к пункту 11, иначе переход к пункту 12.
11. = и Z =f( ) = f( ).
12. Переход к пункту 7.
13. Если f( ) ≥ f( ), то ведем счет неудачных испытаний S = S + 1.
14. Сравниваем S с N, где N – контрольное число неудачных испытаний. Если S ≤ N, то переходим к пункту 7, иначе переход к пункту 15.
15. Конец вычислений. Запись ответа Z =f( ) и .
Пример 18
Найти minZ = (x1 - 2)2+(x2 - 1)2
при условиях
0 ≤ x1 ≤ 3,
0 ≤ x2 ≤ 2.
I итерация.
1. Выписываем область допустимых решений ω:
ω 0 ≤ x1 ≤ 3,
0 ≤ x2 ≤ 2.
2. Подготавливаем начальный вектор (x1нижняя граница, x2нижняя граница), (0,0).
3. Вводим целевую функцию Z= (x1 - 2)2+(x2 - 1)2
4. Вычисляем целевую функцию при = , Z =f( ) = 
+ 
= 5
Вводим счетчик неудавшихся испытаний S = 0.
5. Формируем массив случайных чисел
λ(0,11; 0,17; 0,20; 0,09; 0,15; 0,71; … )
6. Формируем случайный вектор
= xj нижняя граница + λj ּ xj верхняя граница
= 0 +0,11*3 = 0,33
= 0 +0,17*2 = 0,34
= (0,33; 0,34) Î ω
Схема алгоритма случайного поиска на минимум целевой функции
7. Вычисляем целевую функцию при = ; Z = f( ); Z = f( ) = (x1 - 2)2+(x2 - 1)2= 
+ 
= (1,67)2 + (0,66)2 = 2,79 + 0,44 = 3,23
8. Сравниваем f( ) и f( ), 3,23 < 5, испытание удачное.
9. = 
(0,33; 0,34); Z =f( ) =f( ) = 3,23
II итерация
1. Формируем случайный вектор
= 0 + 0,20*3 = 0,60
= 0 + 0,09*2 = 0,18
( 0,60; 0,18) Î ω
2. Вычисляем Z =f( ) = 
+ 
= (1,40)2 + (0,82)2 = 1,96 + 0,67 = 2,63
3. Сравним f( ) и f( )
2,63 < 3,23, испытание удачное.
4. = (0,60; 0,18)
Z=f( ) = f( ) = 2,63
и т. д.
Индивидуальные задания 8
Решить задачи 1-15 методом нелокального случайного поиска, в четных номерах находить максимум целевой функции, а в нечетных – минимум.
1. 
2. 
3. 
4. 
5. 
6. 
7. 
8. 
9. 
10. 
11. 
12. 
13. 
14. 
15. 
Особенности метода локального случайного поиска
Отличие алгоритма локального случайного поиска от алгоритма нелокального случайного поиска только в формировании случайного вектора . Координаты вектора случайных чисел вычисляются по формуле: = xj0 +Pj 
, где - заданное для данной задачи число, например,
=1, т. е. = + 
· 1.
Вектор сам является случайным вектором, координаты которого принадлежат какому-то заданному интервалу, 
≤ Pj ≤ 
. Например, интервалу [-1, 1]. Координаты вектора формируютсяпо формуле Pj =A+ λjּB, где λj - число из массива случайных чисел λ.
Следовательно, = xj0 + (A+ λjּB) · .
В этой задаче можно значение менять по формуле = 
до какого-то заданного предела e.
Индивидуальные задания 9
Решить задачи 1-15 индивидуального задания 8 методом локального случайного поиска, в четных номерах находить максимум целевой функции, а в нечетных – минимум. .
Метод штрафных функций
Штрафная функция – это взвешенная сумма квадратов невязок, т.е. штраф за невыполнение ограничений. Задача с ограничениями в этом случае сводится к задаче без ограничений.
Алгоритм решения задач выпуклого программирования методом штрафных функций при решении задачи на минимум целевой функции
Решить задачу выпуклого программирования
1. Находим область допустимых решений w, т.е. нижнюю и верхнюю границы изменения переменной. Подготавливаем начальный вектор
координатами которого служат нижние границы изменения координат из области допустимых решений w. Задаем число М для задания функции штрафов. Например, М=100. Формируем массив случайных чисел 
Вводим счетчик S=0 – счетчик неудачных попыток.
2. Находим функцию штрафов
Выражение в круглых скобках – штрафы за невыполнение ограничений.
3. Вычисляем функцию штрафов в точке 
4. Формируем случайный вектор 
, где Î w, координаты которого вычисляются по правилу 
,
где li – число из массива случайных чисел.
5. Находим функцию штрафов в точке 
.
6. Сравниваем 
и 
Если ≤ 
, то испытание удачное и переходим к пункту 7, иначе переход к пункту 8.
7. Начальному вектору 
придаем значение ( = ) и полагаем штраф = .
Переход к пункту 4.
8. Если > , то вектор и штраф остаются прежними, но ведем счет неудавшихся попыток S = S + 1.
9. Если S ≤ N, где N – контрольное число, например, N=1000, то переходим к пункту. Иначе переход к пункту 10.
10. Конец вычислений. Запись ответа координат вектора и штрафа .
Замечание. При больших значениях М (М®¥) 
®0, т.е. штраф 
стремится к значению целевой функции. ® 
, а
. Параметр М в процессе решения может меняться от малой величины до большой.
При решении задачи на максимум целевой функции штраф равен
Пример 19
1. Находим область допустимых решений w:
0 ≤ х1 ≤ 4 х10 = х1 нижняя граница = 0;
0 ≤ х2 ≤ 4 х20 = х2 нижняя граница = 0;
М = 10 
Выпишем массив случайных чисел 
: (0,44; 0,19; 0,36; 0,91; 0,25; 0,31; 0,11; 0,14; 0,17; 0,24; 0,16; 0,47; …).
S = 0 – счетчик неудачных попыток.
2. Формируем функцию штрафов:
3. Вычисляем функцию штрафов в точке (0;0).
4. Формируем случайный вектор :
= х1 нижняя граница+ lj·х1 верхняя граница
= 0+0,44 · 4 = 1,76
= х2 нижняя граница+ l2·х2 верхняя граница
= 0+ 0,19· 4 = 0,76
(1,76; 0,76) Îw
5. Вычисляем функцию штрафов в точке :
wZ( ) = (1,76 – 1)2 + (0,76 – 1)2 + 10 · (1,76 + 0,76 – 4)2 = (0,76)2 +
+ (-0,24)2 + 10 · (1,48)2 =0,5776 + 0,0576 +20,904 = 21,5392
6. Сравниваем wZ( ) и 
:
21,5392 < 162. Испытание удачное.
7. Начальному вектору придаем значение , т.е. (1,76; 0,76).
= = 21,5392.
8. Формируем новый случайный вектор :
= 0+ 0,36 · 4 = 1,44
= 0 + 0,91 · 4 = 3,64
(1,44; 3,64) Ï w, т.к. 1,44 + 3,64 = 5,08, а по условию х1 + х2 ≤ 4.
5,08 > 4.
9. Формируем случайный вектор :
= 0 + 0,25· 4 =1
= 0 + 0,31 · 4 = 1,24
(1; 1,24) Î w
10. Вычисляем функцию штрафов в точке :
wZ( ) = (1 – 1)2 + (1,24 – 1)2 + 10 · (1 + 1,24 – 4)2 = 02 +
+ (0,24)2 + 10 · (1,76)2 =0 + 0,0576 +30,946 = 31,0036.
11. Сравниваем wZ( ) и :
31,0036 > 21,5392. Испытание неудачное.
12. Ведем счет неудавшихся попыток: S = S + 1; S = 0 + 1; S = 1.
13. S < 3, где 3 – контрольное число неудачных попыток для ручного счета.
14. Формируем новый случайный вектор :
= 0 + 0,11 · 4 =0,44
= 0 + 0,14 · 4 = 0,56
(0,44; 0,56) Î w
15. Вычисляем функцию штрафов в точке :
wZ( ) = (0,44 – 1)2 + (0,56 – 1)2 + 10 · (0,44 + 0,56 – 4)2 =(0,56)2 +
+ (0,44)2 + 10 · (3)2 =0,3136 + 0,1936 +90 = 90,5072.
16. Сравниваем wZ( ) и :
90,5072 > 21,5392. Испытание неудачное.
17. Ведем счет неудавшихся попыток: S = S + 1; S = 1 + 1; S = 2.
18. S < 3, где 3 – контрольное число неудачных попыток для ручного счета.
19. Формируем новый случайный вектор :
= 0 + 0,17 · 4 =0,68
= 0 + 0,24 · 4 = 0,96
(0,68; 0,96) Î w
20. Вычисляем функцию штрафов:
wZ( ) = (0,68 – 1)2 + (0,96 – 1)2 + 10 · (0,68 + 0,96 – 4)2 =(0,32)2 +
+ (0,04)2 + 10 · (2,36)2 =0,1024 + 0,0016 +55,696 = 55,8.
21. Сравниваем wZ( ) и :
55,8 > 21,5392. Испытание неудачное.
22. Ведем счет неудавшихся попыток: S = S + 1; S = 2 + 1; S = 3.
23. S = 3, где 3 – контрольное число неудачных попыток для ручного счета. Следовательно, испытание прекращаем и выписываем ответ:
X* = (1,76; 0,76) ; min Z =21,5392.
Пример 20
min Z=9x12+9x22+12x1-6x2
0≤x≤4
1≤ x2≤5
Изобразим решение на графике.
Для этого преобразуем целевую функцию:
Z=9x12+12x1+9x22-6x2 = 9(x12+ 
x1) + 9(x22- 
x2);
Z = 9(x12+2· x1+( 
))+9(x22- 
x2)= 9(x12+2· x1+( ))+9(x22- 
x2) - - 9· 
- 
;
Z = 9(x1+ )2+9(x2- 
)2-4-1==9(x1+ )2+9(x2- )2-5
C11=C22=9 ─ линии уровня концентрические окружности с центром в точке O1( 
; ).
Min Z=3 в оптимальном решении точке Х*(0;1).
Формируем начальный вектор 
0:
x10 =X1 нижняя граница =0;
x20 =X2 нижняя граница =1.
Тогда 0(0;1) – нижняя граница координат.
2. Пусть M = 0,01, N=3 –число неудачных испытаний для ручного счета.
Массив случайных чисел
(0,44;0,19;0,36;0,91;0,25;0,31;0,11;0,14;0,17;0,24;0,16;0,47…)
S= 0 - счетчик неудачных испытаний
3. Вычислим Z ( 0)= Z(0,1)=12-6=3
4. Вычисляем функцию штрафов
WZ(x) = f(x)+М(φ1( ))2+M(φ2( ))2+…+ M(φm(X))2
5. Вычисляем функцию штрафов в точке (0;0).
WZ( 0) = 9x12+9x22+12x1- 6x2+0,01(x1-4)2+0,01(x2-5)2 +0,01(1-x2)2
WZ( 0) = 3+0,01·16+0,01·16 +0,01·0 = 3,32.
6. Формируем случайный вектор :
= х1 нижняя граница+ lj·х1 верхняя граница
= 0+0,44 · 4 = 1,76
= х2 нижняя граница+ l2·х2 верхняя граница
= 1+ 0,19· 5 = 1,95
(1,76; 1,95) Îw
5. Вычисляем функцию штрафов в точке :
wZ( ) = 9(1,76)2 + 9(1,95)2 + 12·1,76-6·1,95+0,01 · (1,76 – 4)2 +0,01 · (1,95 –5)2 +0,01 · (1-1,95)2 = 71,66224.
11. Сравниваем wZ( ) и :
71,66224 > 3,32. Испытание неудачное.
12. Ведем счет неудавшихся попыток: S = S + 1; S = 0 + 1; S = 1.
13. S < 3, где 3 – контрольное число неудачных попыток для ручного счета.
14. Формируем новый случайный вектор :
= 0 + 0,36 · 4 =1,44
= 1 + 0,91 · 5 = 5,55
(1,44; 5,55) Ï w Испытание неудачное.
12. Ведем счет неудавшихся попыток: S = S + 1; S = 1 + 1; S = 2.
13. S < 3, где 3 – контрольное число неудачных попыток для ручного счета.
14. Формируем новый случайный вектор :
= 0 + 0,25 · 4 =1,0
= 1 + 0,31 · 5 = 2,55
(1,0;2,55) Îw
15. Вычисляем функцию штрафов в точке :
wZ( ) = 9· 12 + 9(2,55)2 + 12·1,0 - 6·2,55+0,01 · (1,0 – 4)2 +0,01 · (2,55 – 5)2 +0,01 · (1 - 2,55)2 = 64,39655.
11. Сравниваем wZ( ) и :
64,39655 > 3,32. Испытание неудачное.
12. Ведем счет неудавшихся попыток: S = S + 1; S = 2 + 1; S = 3.
13. S = 3, где 3 – контрольное число неудачных попыток для ручного счета. Процесс решения прекращаем.
Оптимальным решением является Х* = 0(0;1), WZ( 0) =3,32;
min Z = Z ( *)= Z(0,1)=12-6=3
Замечание. При решении на компьютере контрольное число неудавшихся попыток следует взять большим, например, 1000.
Индивидуальные задания 10
Решить задачи 1-15 индивидуального задания 8 методом штрафных функций, в четных номерах находить минимум целевой функции, а в нечетных – максимум или по указанию преподавателя.
КВАДРАТИЧНОЕ ПРОГРАММИРОВАНИЕ (КП)
Графический метод
Задача называется задачей квадратичного программирования, если целевая функция содержит переменные во второй степени, а система ограничений - линейные выражения.
Пусть задача квадратичного программирования имеет две переменные X1 и X2.
Z(X1,X2)= C11X12+C12X1X2+C22X22+C1X1+C2X2 +C0
aI1 X1 +aI2X2.≤ aI 0 , i=1÷n, X1≥0, X2≥0
ОДР задач КП является либо выпуклый многоугольник, либо выпуклая неограниченная область с конечным числом вершин (как в линейном программировании). А линия уровня целевой квадратичной функции - кривая: либо окружность, либо эллипс, либо гипербола, либо парабола. Для всех линий уровня полагаем, что C12=0, чтобы не делать преобразований целевой функции и не выполнять поворот осей.
1 случай. а) C11=C22>0.
Целевую функцию Z(X1,X2)= C11X12 +C22X22+C1X1+C2X2 +C0 приводим к виду Z(X1,X2)= C11(X1 -a)2 +C22 (X2-b)2+C0 . Линии уровня концентрические окружности с центром в точке O`(a,b).
б) C11=C22<0.
Целевую функцию Z(X1,X2)= C11X12 +C22X22+C1X1+C2X2 +C0 приводим к виду Z(X1,X2)= C11(X1-a)2 +C22 (X2-b)2+C0 . Линии уровня мнимые концентрические окружности с центром в точке O`(a,b).