Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Скачиваний:
17
Добавлен:
13.02.2015
Размер:
704.51 Кб
Скачать

Симплексный метод

Симплексом в n-мерномпространстве называется выпуклый многоугольник с n+1 вершино

n=2 треугольник

n=3 тетраэдр

11

 

 

 

Алгоритм

 

 

 

 

 

(0)

 

 

 

 

 

 

 

 

 

 

1. Дана функция 2x переменныхf ( x ), точность ε, параметр h, начальное приближениеx

2. Вычисляем координаты вершин симплекса

 

 

 

 

 

 

 

(1)

(0)

(2)

(0)

 

h

(3)

(0)

 

0

 

x

x

x

x

 

 

x

x

 

 

 

 

 

 

 

0

 

 

 

 

h

 

 

 

 

 

 

 

 

 

(1)

 

(2)

 

 

 

 

 

 

 

 

 

 

(3)

 

 

 

 

 

 

 

 

 

 

 

 

3. Вычисляем значения функции

F1 f ( x

)

F2 f ( x

) F3

f ( x

)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

худ

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

4. Определяем худшую вершину

 

x

, Fхуд

и координаты отраженной вершины,

она будет лежать на прямой исходящей из худшей вершины и проходящей через

 

 

середину противоположной грани

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

отр

ср

 

ост1 ост2

 

ср

худ

ост1

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

x

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

x

x

0.5*( x

x

 

);

V x

x

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

ср

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

отр

худ

 

 

отр

ост1

ост2

худ

 

 

 

 

 

 

 

 

 

 

 

 

 

x

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

x

x

2

V;

x

x

 

x

 

x

 

худ

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

ост2

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

отр

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

x

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Fотр

 

 

 

 

 

 

 

 

x

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

f ( x

)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

12

5. Сравниваем значения функции

FотрFхуд

6. Условие выполняется. За новый симплекс принимаем симплекс с вершиной

отр

худ

 

x

вместо x

и повторяем с пункта 3

7.Условие не выполняется. Проверяем условие окончания h< ε

8.Условие окончания выполняется. Выводим координаты и значение функции лучшей вершины

(0)

 

9. Условие не выполняется. За x

принимаем лучшую вершину последнего

симплекса, уменьшаем длину грани h=h/3 и повторяем с пункта 2.

13

начало

(0)

x ,h, || f ( x )

(1)

 

(0)

(2)

(0)

h

(3)

(0)

0

 

(1)

(2)

(3)

x

x

:

x

x

 

 

: x

x

 

:

F1 f ( x ) :

F2 f ( x

) : F3 f ( x )

 

 

 

 

 

 

0

 

 

h

 

 

 

 

 

 

Fxud:=F1: kx:=1

 

 

i:=1шаг 2 до 3

(0)

(kl)

Fi>Fxud

x

x

 

 

 

Fxud:=Fi: kx:=i

 

 

i:=1 шаг 1 до 3

|| h ||<0

Fi<Fl

 

 

 

(kl)

Fl:=Fi: kl:=i

x

,Fl

конец

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

(kx)

 

 

 

 

 

 

 

 

 

 

 

 

 

x

: Xot :

Fk : Fot

 

 

s : 0

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

i:=1шаг 1 до 3

 

i≠kx

 

 

(i)

s : s

x

 

 

(kx)

 

Xot s

x

: Fot f (Xot)

Fot<Fxud

Fl:=F1: kl:=1

Пример:

 

f (x , x

2

) 8x

2

4x x

2

5x

2

1

 

 

1

1

 

2

 

 

 

1

 

 

 

 

 

h=1, eps=0.2

x

0

 

 

 

14

 

 

 

 

 

 

 

 

 

 

 

 

 

1

 

 

 

 

 

x1

x2

f(x1,x2)

h

точки симплекса и примечания

 

1

1.00

1.00

17.0

 

1

симплекс т.1,2,3

т.2

худшая отражаем

 

2

2.00

1.00

45.0

 

 

 

 

 

 

3

1.00

2.00

36.0

 

 

 

 

 

 

4

0.00

2.00

20.0

 

 

удачно симплекс 1,3,4

т.3 худшая

 

 

 

 

 

 

 

 

отражаем

 

 

 

5

0.00

1.00

5.00

 

 

удачно симплекс 1,4,5

т.4 худшая

 

 

 

 

 

 

 

 

отражаем

 

 

 

6

1.00

0.00

8.00

 

 

удачно симплекс 1,5,6

т.1 худшая

 

 

 

 

 

 

 

 

отражаем

 

 

 

7

0.00

0.00

0.00

 

 

удачно симплекс 5,6,7

т.6 худшая

 

 

 

 

 

 

 

 

отражаем

 

 

 

8

-1.00

1.00

9.00

 

 

неудачно 1>0.2 h=h/3 = 0.33

 

1

0.00

0.00

0.00

 

0.33

симплекс т.1,2,3, т.2 худшая отражаем

 

2

0.333

0.00

0.889

 

 

 

 

 

3

0.00

0.333

0.556

 

 

 

 

 

4

-0.333

0.333

1.00

 

 

неудачно 0.33>0.2

h=h/3 = 0.11

 

1

0.00

0.00

0.00

 

0.11

симплекс т.1,2,3 т. 2 худшая отражаем

 

2

0.111

0.00

0.0988

 

 

 

 

 

3

0.00

0.111

 

 

0.00

 

 

 

 

0.0617

 

f ( x ) 0.000

 

 

 

 

Ответ:

x

 

 

 

 

 

15

4

-0.111

0.111

0.111 0.00

неудача 0.11<0.2

ответ т. 1

20

36

x2

9

5

17 45

0.89

0

0.56

8

 

 

1.00

 

x1

16

Соседние файлы в папке Лекции по VBA

Калькулятор

Сервис бесплатной оценки стоимости работы

  1. Заполните заявку. Специалисты рассчитают стоимость вашей работы
  2. Расчет стоимости придет на почту и по СМС

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

Номер вашей заявки

Прямо сейчас на почту придет автоматическое письмо-подтверждение с информацией о заявке.

Оформить еще одну заявку