Компьютерное моделирование. Лабораторный практикум. Алтаев А.А - 37 стр.

UptoLike

ВУЗ: 

ВСГУТУ | Улан-Удэ

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

Рубрика: 

73
будет отрезок (рис. П.1,а), для двух переменных
−
треугольник (рис. П.1,б), при
n=3 − это тетраэдр.
Далее используются следующие обозначения:
x
ij
−
координата
i-й вершины, j − номер переменной, f
i
—
значение целевой функции
i-й вершины. Помимо матрицы
X(N+1,N) и вектора F(N+1) применяются вспомогательные
векторы
XO(N), XC(N), XR(N), XE(N).
В качестве исходных данных задаются:
− n − число переменных;
− координаты первой вершины многогранника
− x
1
j, где nj ,1= ;
− начальный размер многогранника ∆.
Координаты других вершин определяются по
формуле
+=∆+
+≠
=
1,
1,
1
1
jiеслиx
jiеслиx
x
j
j
ij
, 1,2 += ni .
При этом создается равносторонний многогранник,
называемый симплексом. Сам метод по этой причине имеет
третье название
− симплексный метод (не путать с
симплекс-методом, который используется при решении
задач линейного программирования).
Далее вычисляются значения целевой функции в
вершинах
− f
i
.
Дальнейшие действия состоят в перемещении
построенного многогранника в область минимума функции.
Алгоритм перемещения рассмотрим на примере целевой
функции от двух переменных (рис. П.2).
1. Определяется вершина с наибольшим значением
целевой функции. Номер такой вершины обозначим через
H. Таким образом, f
h
= max{f
1
, f
2
,…, f
n
}. Также определяется
вершина
L с наименьшей функцией: f
l
= min{f
1
, f
2
,…, f
n
}.
Комментарий по алгоритму. Основная идея метода
состоит в том, что на каждом шаге очередная «наихудшая»
74
вершина будет заменяться на новую, в которой значение
целевой функции будет меньше. Это позволит смещать
многогранник в направлении минимума.
2. Вычисляются координаты центра тяжести
O всех
вершин многогранника, исключая
H :
n
xx
xo
hj
n
i
ij
j
−
=
∑
+1
.
3. Вычисляются координаты точки
R, лежащей на
продолжении отрезка
HO, причем длины отрезков HO и OR
равны:
xr
j
=2·xo
j
−
x
hj
.
4. Вычисляется целевая функция в точке R − f
r
.
5. Если
f
r
< f
h
, то идти к п. 6, иначе к п. 13.
x
1
R
E
O
C
H
Рис. П.2
x
2
Линии
равного
уровня
функции 
будет отрезок (рис. П.1,а), для двух переменных −                вершина будет заменяться на новую, в которой значение
треугольник (рис. П.1,б), при n=3 − это тетраэдр.                целевой функции будет меньше. Это позволит смещать
      Далее используются следующие обозначения: xij −            многогранник в направлении минимума.
координата i-й вершины, j − номер переменной, fi —                 x2
значение целевой функции i-й вершины. Помимо матрицы                                                 E
X(N+1,N) и вектора F(N+1) применяются вспомогательные
векторы XO(N), XC(N), XR(N), XE(N).
      В качестве исходных данных задаются:
                                                                                             R
         − n − число переменных;
         − координаты первой вершины многогранника
             − x1j, где j = 1, n ;
                                                                                    O
         − начальный размер многогранника ∆.                                                                      Линии
          Координаты других вершин определяются по                                                                равного
      формуле                                                                 C
                                                                                                                  уровня
                   x1 j ,     если i ≠ j + 1                           H
                                                                                                                  функции
            xij =                            , i = 2, n + 1 .
                   x1 j + ∆ , если i = j + 1
                                                                                                             x1
       При этом создается равносторонний многогранник,
называемый симплексом. Сам метод по этой причине имеет
третье название − симплексный метод (не путать с
симплекс-методом, который используется при решении                                      Рис. П.2
задач линейного программирования).                                    2. Вычисляются координаты центра тяжести O всех
       Далее вычисляются значения целевой функции в              вершин многогранника, исключая H :
вершинах − fi .
                                                                                          n+1 
       Дальнейшие действия состоят в перемещении                                          ∑ xij  − xhj
построенного многогранника в область минимума функции.
Алгоритм перемещения рассмотрим на примере целевой                                xo j =  i     
                                                                                                         .
функции от двух переменных (рис. П.2).                                                         n
       1. Определяется вершина с наибольшим значением                   3. Вычисляются координаты точки R, лежащей на
целевой функции. Номер такой вершины обозначим через             продолжении отрезка HO, причем длины отрезков HO и OR
H. Таким образом, fh = max{f1, f2,…, fn}. Также определяется     равны:
вершина L с наименьшей функцией: fl = min{f1, f2,…, fn}.                                   xrj =2·xoj − xhj.
       Комментарий по алгоритму. Основная идея метода                   4. Вычисляется целевая функция в точке R − fr .
состоит в том, что на каждом шаге очередная «наихудшая»                 5. Если fr < fh , то идти к п. 6, иначе к п. 13.

                             73                                                             74

Страницы