Методы безусловной многомерной оптимизации. Шипилов С.А. - 7 стр.

UptoLike

ВУЗ: 

НФИ КемГУ | Новокузнецк

Составители: 

Рубрика: 

7
x
(2)
x
1
R
2
x
(1)
x
(3)
V
1
R
1
V
2
x
2
4.2. Симплексные алгоритмы
4.2.1. Обычный симплекс- метод
Симплексом в пространстве n переменных называют выпуклый много-
гранник, имеющий n+1 вершину. В пространстве двух переменных это тре-
угольник, в пространстве трех переменных - тетраэдр. В обычном симплекс-
методе используется правильный симплекс (все ребра которого равны).
Идея симплекс-метода, которая далее рассматривается на примере дву-
мерного случая, заключается в
следующем. Выбирается начальный симплекс с
вершинами x
(1)
- x
(2)
- x
(3)
. Размещение правильного симплекса в пространстве
может быть осуществлено двумя путями (рис.1).
1. Одна вершина симплекса помещается в начало координат, а остальные
вершины располагаются так, чтобы ребра, выходящие из первой вершины, об-
разовывали одинаковые углы с соответствующими координатными осями. То-
гда для двумерного случая координаты вершин будут равны:
№
вершины
x
1
x
2
x
(1)
0 0
x
(2)
22
13 +
22
13 −
x
(3)
22
13 −
22
13 +
Рис. 1
В общем случае координаты вершин симплекса определяются матрицей:
)11(
2
1
−++= nn
n
P ;
()
11
2
1
−+= n
n
Q
.
2. Центр симплекса помещается в начало координат, а (n+1)-я вершина на
ось x
n
. Остальные вершины располагаются симметрично относительно коорди-
натных осей. В двумерном случае координаты вершин будут равны:
№
вершины
x
1
x
2
x
(1)
2
1
−
32
1
−
x
(2)
2
1
32
1
−
x
(3)
0
3
1
№ вершины x
1
x
2
x
3
…
x
n
1 0 0 0 … 0
2
P Q Q
…
Q
3
Q P Q
…
Q
… … … … … …
n+1
Q Q Q
…
P
Q
P
x
1
x
2
x
(4)
x
(3)
x
(2)
x
(1)
x
ц.т.
Рис. 2 
                                         7
                           4.2. Симплексные алгоритмы
                        4.2.1. Обычный симплекс- метод
      Симплексом в пространстве n переменных называют выпуклый много-
гранник, имеющий n+1 вершину. В пространстве двух переменных это тре-
угольник, в пространстве трех переменных - тетраэдр. В обычном симплекс-
методе используется правильный симплекс (все ребра которого равны).
      Идея симплекс-метода, которая далее рассматривается на примере дву-
мерного случая, заключается в следующем. Выбирается начальный симплекс с
вершинами x(1)- x(2)- x(3). Размещение правильного симплекса в пространстве
может быть осуществлено двумя путями (рис.1).
      1. Одна вершина симплекса помещается в начало координат, а остальные
вершины располагаются так, чтобы ребра, выходящие из первой вершины, об-
разовывали одинаковые углы с соответствующими координатными осями. То-
гда для двумерного случая координаты вершин будут равны:
         №                                      x2               x(4)
                    x1            x2
     вершины                                        x(3)
       x(1)         0              0                           xц.т.
                    3 +1          3 −1
       x(2)
                   2 2           2 2                                   x(2)
                    3 −1          3 +1                             Q
       x   (3)                                   x(1)      P                           x1
                   2 2           2 2
                                                     Рис. 1
      В общем случае координаты вершин симплекса определяются матрицей:
    № вершины      x1     x2    x3     …     xn           1
            1       0     0     0      …      0      P=        ( n + 1 + n − 1) ;
            2      P      Q     Q      …      Q         n    2

           …
            3      Q
                   …
                          P
                          …    …
                                Q      …
                                       …     …
                                              Q
                                                     Q=
                                                           1
                                                         n 2
                                                                   (
                                                                 n +1 −1 .         )
         n+1       Q      Q     Q      …      P
      2. Центр симплекса помещается в начало координат, а (n+1)-я вершина на
ось xn. Остальные вершины располагаются симметрично относительно коорди-
натных осей. В двумерном случае координаты вершин будут равны:
         №                                                x2 x(3)
                    x1         x2
     вершины
                      1          1
        x(1)       −         −
                                                                              V2




                      2        2 3
                    1            1
        x(2)                 −                                               x1
                                                                              R2




                    2          2 3
          (3)                   1               x(1)   R1        V1     x(2)
        x           0
                                 3                      Рис. 2

Страницы