Алгоритм нелокального случайного поиска на минимум целевой функции

Найти min Z = Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru

при условии аj ≤ xj ≤ bj; j = 1 ÷ n,

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

1. Выписываем область допустимых значений ω( аj ≤ xj ≤ bj ); где j=1÷n.

2. Подготавливаем начальный вектор Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru1, а2, ..., аn) = Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru (x1нижняя граница, x2нижняя граница,…,xnнижняя граница) = Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru ( x10, x20, ..., xn0 ), координатами служат нижние границы измерения координат из области допустимых решений ω.

3. Вводим целевую функцию Z = Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru .

4. Вычисляем целевую функцию при Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru = Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru , Z = f( Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru ).

5. Вводим счетчик неудачных испытаний S = 0, N = 1000 – контрольное число.

6. Формируем массив случайных чисел λ.

7. Формируем случайный вектор Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru , где Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru Î w, координаты которого вычисляются по правилу xj1 = xjнижняя граница j ּxjверхняя граница = аj + λj ּbj.

8. Вычисляем целевую функцию при Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru = Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru , Z = f( Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru ).

9. Сравниваем f( Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru ) и f( Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru ).

10. Если испытание удачное, то есть если f( Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru ) <f( Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru ), то переход к пункту 11, иначе переход к пункту 12.

11. Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru = Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru и Z =f( Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru ) = f( Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru ).

12. Переход к пункту 7.

13. Если f( Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru ) ≥ f( Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru ), то ведем счет неудачных испытаний S = S + 1.

14. Сравниваем S с N, где N – контрольное число неудачных испытаний. Если S ≤ N, то переходим к пункту 7, иначе переход к пункту 15.

15. Конец вычислений. Запись ответа Z =f( Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru ) и Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru .

Пример 18

Найти minZ = (x1 - 2)2+(x2 - 1)2

Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru при условиях

0 ≤ x1 ≤ 3,

0 ≤ x2 ≤ 2.

I итерация.

1. Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru Выписываем область допустимых решений ω:

ω 0 ≤ x1 ≤ 3,

0 ≤ x2 ≤ 2.

2. Подготавливаем начальный вектор Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru (x1нижняя граница, x2нижняя граница), Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru (0,0).

3. Вводим целевую функцию Z= (x1 - 2)2+(x2 - 1)2

4. Вычисляем целевую функцию при Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru = Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru , Z =f( Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru ) = Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru + Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru = 5

Вводим счетчик неудавшихся испытаний S = 0.

5. Формируем массив случайных чисел

λ(0,11; 0,17; 0,20; 0,09; 0,15; 0,71; … )

6. Формируем случайный вектор Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru

Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru = xj нижняя граница + λj ּ xj верхняя граница

Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru = 0 +0,11*3 = 0,33

Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru = 0 +0,17*2 = 0,34

Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru = (0,33; 0,34) Î ω

Схема алгоритма случайного поиска на минимум целевой функции

Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru

7. Вычисляем целевую функцию при Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru = Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru ; Z = f( Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru ); Z = f( Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru ) = (x1 - 2)2+(x2 - 1)2= Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru + Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru = (1,67)2 + (0,66)2 = 2,79 + 0,44 = 3,23

8. Сравниваем f( Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru ) и f( Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru ), 3,23 < 5, испытание удачное.

9. Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru = Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru (0,33; 0,34); Z =f( Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru ) =f( Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru ) = 3,23

II итерация

1. Формируем случайный вектор Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru

Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru = 0 + 0,20*3 = 0,60

Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru = 0 + 0,09*2 = 0,18

Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru ( 0,60; 0,18) Î ω

2. Вычисляем Z =f( Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru ) = Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru + Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru = (1,40)2 + (0,82)2 = 1,96 + 0,67 = 2,63

3. Сравним f( Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru ) и f( Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru )

2,63 < 3,23, испытание удачное.

4. Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru = Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru (0,60; 0,18)

Z=f( Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru ) = f( Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru ) = 2,63

и т. д.

Индивидуальные задания 8

Решить задачи 1-15 методом нелокального случайного поиска, в четных номерах находить максимум целевой функции, а в нечетных – минимум.

1. Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru

2. Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru

3. Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru

4. Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru

5. Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru

6. Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru

7. Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru

8. Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru

9. Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru

10. Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru

11. Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru

12. Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru

13. Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru

14. Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru

15. Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru

Особенности метода локального случайного поиска

Отличие алгоритма локального случайного поиска от алгоритма нелокального случайного поиска только в формировании случайного вектора Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru . Координаты вектора случайных чисел вычисляются по формуле: Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru = xj0 +Pj Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru , где Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru - заданное для данной задачи число, например,

Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru =1, т. е. Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru = Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru + Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru · 1.

Вектор Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru сам является случайным вектором, координаты которого принадлежат какому-то заданному интервалу, Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru ≤ PjАлгоритм нелокального случайного поиска на минимум целевой функции - student2.ru . Например, интервалу [-1, 1]. Координаты вектора Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru формируютсяпо формуле Pj =A+ λjּB, где λj - число из массива случайных чисел λ.

Следовательно, Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru = xj0 + (A+ λjּB) · Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru .

В этой задаче можно значение Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru менять по формуле Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru = Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru до какого-то заданного предела e.

Индивидуальные задания 9

Решить задачи 1-15 индивидуального задания 8 методом локального случайного поиска, в четных номерах находить максимум целевой функции, а в нечетных – минимум. .

Метод штрафных функций

Штрафная функция – это взвешенная сумма квадратов невязок, т.е. штраф за невыполнение ограничений. Задача с ограничениями в этом случае сводится к задаче без ограничений.

Алгоритм решения задач выпуклого программирования методом штрафных функций при решении задачи на минимум целевой функции

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

Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru

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

Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru

координатами которого служат нижние границы изменения координат из области допустимых решений w. Задаем число М для задания функции штрафов. Например, М=100. Формируем массив случайных чисел Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru Вводим счетчик S=0 – счетчик неудачных попыток.

2. Находим функцию штрафов

Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru

Выражение в круглых скобках – штрафы за невыполнение ограничений.

3. Вычисляем функцию штрафов в точке Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru

4. Формируем случайный вектор Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru , где Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru Î w, координаты которого вычисляются по правилу Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru ,

где li – число из массива случайных чисел.

5. Находим функцию штрафов в точке Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru .

6. Сравниваем Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru и Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru Если Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ruАлгоритм нелокального случайного поиска на минимум целевой функции - student2.ru , то испытание удачное и переходим к пункту 7, иначе переход к пункту 8.

7. Начальному вектору Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru придаем значение Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru ( Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru = Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru ) и полагаем штраф Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru = Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru .

Переход к пункту 4.

8. Если Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru > Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru , то вектор Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru и штраф Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru остаются прежними, но ведем счет неудавшихся попыток S = S + 1.

9. Если S ≤ N, где N – контрольное число, например, N=1000, то переходим к пункту. Иначе переход к пункту 10.

10. Конец вычислений. Запись ответа координат вектора Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru и штрафа Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru .

Замечание. При больших значениях М (М®¥) Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru ®0, т.е. штраф Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru стремится к значению целевой функции. Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru ® Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru , а

Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru . Параметр М в процессе решения может меняться от малой величины до большой.

При решении задачи на максимум целевой функции штраф равен

Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru

Пример 19

Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru

1. Находим область допустимых решений w:

0 ≤ х1 ≤ 4 х10 = х1 нижняя граница = 0;

0 ≤ х2 ≤ 4 х20 = х2 нижняя граница = 0;

М = 10 Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru

Выпишем массив случайных чисел Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru : Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru (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. Формируем функцию штрафов:

Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru

3. Вычисляем функцию штрафов в точке Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru (0;0).

Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru

4. Формируем случайный вектор Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru :

Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru = х1 нижняя граница+ lj·х1 верхняя граница

Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru = 0+0,44 · 4 = 1,76

Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru = х2 нижняя граница+ l2·х2 верхняя граница

Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru = 0+ 0,19· 4 = 0,76

Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru (1,76; 0,76) Îw

5. Вычисляем функцию штрафов в точке Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru :

wZ( Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru ) = (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( Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru ) и Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru :

21,5392 < 162. Испытание удачное.

7. Начальному вектору Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru придаем значение Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru , т.е. Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru (1,76; 0,76).

Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru = Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru = 21,5392.

8. Формируем новый случайный вектор Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru :

Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru = 0+ 0,36 · 4 = 1,44

Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru = 0 + 0,91 · 4 = 3,64

Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru (1,44; 3,64) Ï w, т.к. 1,44 + 3,64 = 5,08, а по условию х1 + х2 ≤ 4.

5,08 > 4.

9. Формируем случайный вектор Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru :

Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru = 0 + 0,25· 4 =1

Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru = 0 + 0,31 · 4 = 1,24

Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru (1; 1,24) Î w

10. Вычисляем функцию штрафов в точке Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru :

wZ( Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru ) = (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( Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru ) и Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru :

31,0036 > 21,5392. Испытание неудачное.

12. Ведем счет неудавшихся попыток: S = S + 1; S = 0 + 1; S = 1.

13. S < 3, где 3 – контрольное число неудачных попыток для ручного счета.

14. Формируем новый случайный вектор Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru :

Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru = 0 + 0,11 · 4 =0,44

Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru = 0 + 0,14 · 4 = 0,56

Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru (0,44; 0,56) Î w

15. Вычисляем функцию штрафов в точке Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru :

wZ( Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru ) = (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( Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru ) и Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru :

90,5072 > 21,5392. Испытание неудачное.

17. Ведем счет неудавшихся попыток: S = S + 1; S = 1 + 1; S = 2.

18. S < 3, где 3 – контрольное число неудачных попыток для ручного счета.

19. Формируем новый случайный вектор Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru :

Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru = 0 + 0,17 · 4 =0,68

Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru = 0 + 0,24 · 4 = 0,96

Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru (0,68; 0,96) Î w

20. Вычисляем функцию штрафов:

wZ( Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru ) = (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( Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru ) и Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru :

55,8 > 21,5392. Испытание неудачное.

22. Ведем счет неудавшихся попыток: S = S + 1; S = 2 + 1; S = 3.

23. S = 3, где 3 – контрольное число неудачных попыток для ручного счета. Следовательно, испытание прекращаем и выписываем ответ:

X* = Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru (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+ Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru x1) + 9(x22- Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru x2);

Z = 9(x12+2· Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru x1+( Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru ))+9(x22- Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru x2)= 9(x12+2· Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru x1+( Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru ))+9(x22- Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru x2) - - 9· Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru - Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru ;

Z = 9(x1+ Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru )2+9(x2- Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru )2-4-1==9(x1+ Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru )2+9(x2- Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru )2-5

C11=C22=9 ─ линии уровня концентрические окружности с центром в точке O1( Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru ; Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru ).

Min Z=3 в оптимальном решении точке Х*(0;1).

Формируем начальный вектор Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru 0:

x10 =X1 нижняя граница =0;

x20 =X2 нижняя граница =1.

Тогда Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru 0(0;1) – нижняя граница координат.

2. Пусть M = 0,01, N=3 –число неудачных испытаний для ручного счета.

Массив случайных чисел Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru

Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru (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 ( Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru 0)= Z(0,1)=12-6=3

4. Вычисляем функцию штрафов

WZ(x) = f(x)+М(φ1( Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru ))2+M(φ2( Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru ))2+…+ M(φm(X))2

5. Вычисляем функцию штрафов в точке Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru (0;0).

WZ( Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru 0) = 9x12+9x22+12x1- 6x2+0,01(x1-4)2+0,01(x2-5)2 +0,01(1-x2)2

WZ( Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru 0) = 3+0,01·16+0,01·16 +0,01·0 = 3,32.

6. Формируем случайный вектор Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru :

Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru = х1 нижняя граница+ lj·х1 верхняя граница

Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru = 0+0,44 · 4 = 1,76

Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru = х2 нижняя граница+ l2·х2 верхняя граница

Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru = 1+ 0,19· 5 = 1,95

Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru (1,76; 1,95) Îw

5. Вычисляем функцию штрафов в точке Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru :

wZ( Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru ) = 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( Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru ) и Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru :

71,66224 > 3,32. Испытание неудачное.

12. Ведем счет неудавшихся попыток: S = S + 1; S = 0 + 1; S = 1.

13. S < 3, где 3 – контрольное число неудачных попыток для ручного счета.

14. Формируем новый случайный вектор Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru :

Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru = 0 + 0,36 · 4 =1,44

Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru = 1 + 0,91 · 5 = 5,55

Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru (1,44; 5,55) Ï w Испытание неудачное.

12. Ведем счет неудавшихся попыток: S = S + 1; S = 1 + 1; S = 2.

13. S < 3, где 3 – контрольное число неудачных попыток для ручного счета.

14. Формируем новый случайный вектор Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru :

Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru = 0 + 0,25 · 4 =1,0

Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru = 1 + 0,31 · 5 = 2,55

Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru (1,0;2,55) Îw

15. Вычисляем функцию штрафов в точке Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru :

wZ( Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru ) = 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( Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru ) и Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru :

64,39655 > 3,32. Испытание неудачное.

12. Ведем счет неудавшихся попыток: S = S + 1; S = 2 + 1; S = 3.

13. S = 3, где 3 – контрольное число неудачных попыток для ручного счета. Процесс решения прекращаем.

Оптимальным решением является Х* = Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru 0(0;1), WZ( Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru 0) =3,32;

min Z = Z ( Алгоритм нелокального случайного поиска на минимум целевой функции - student2.ru *)= 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).

Наши рекомендации