Контрольная работа по «Модели и методы принятия решений»

       МИНИСТЕРСТВО  ОБРАЗОВАНИЯ И НАУКИ УКРАИНЫ

       НАЦИОНАЛЬНЫЙ  ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

       “ХАРЬКОВСКИЙ  ПОЛИТЕХНИЧЕСКИЙ ИНСТИТУТ”

       Кафедра системного анализа и управления 
 
 
 
 
 

       Индивидуальное  домашнее задание

       По  дисциплине: «Модели и методы принятия решений»

       Вариант 6 
 
 

       Выполнил  студент группы ИФ-56б:

       Заика А.Е. 
 

       Проверил:

       проф. Северин В.П.  
 
 
 
 
 
 

       Харьков – 2010 

       Постановка  задачи.

     Необходимо  решить многокритериальную задачу оптимизации: , с ограничениями , из начальной точки поиска, как точки с наихудшим значением первого критерия ( ), используя метод деформируемого многогранника. 

      Описание  метода деформируемого многогранника.

      Этот  метод также называют методом  Нилдера – Мида.

      Метод является развитием метода симплексного поиска и так же состоит из 3-х. основных этапов:

1. построение начального многогранника
2. отражение худшей вершины
3. переход к новому многограннику.

      Основное  отличие данного метода заключается  в расширении третьего этапа за счет применения операций растяжения, сжатия или редукции многогранника. 

      

1. Построение  начального многогранника

      Для этого задается начальная точка  поиска , так как в процессе оптимизации многогранник будет деформироваться, то его необязательно задавать правильным симплексом, как в методе симплексного поиска.

      Наиболее  просто начальный многогранник строится путем смещения начальной точки  параллельно осям координат. При  этом получаем , а вершины получаются путем смещения по формулам:

      

      Рассмотрим  для 

      Во  всех вершинах многогранника вычисляется  значения :

      

      Все значения функции образуют вектор . 

      

2. Отражение худшей вершины

      а) Определение худших и лучших вершин:

      С помощью вектора  найдем индекс , наилучшего значения, то есть

      Обозначим

      Таким образом  - лучшая вершина многогранника.

      Аналогично  определив индекс , наихудшего значения, то есть

      Обозначим

      Таким образом  - худшая вершина многогранника.

      б) Отражение худшей вершины:

      

      

      Вычисляется значение функции в отраженной точке . 

      

3. Переход к  новому многограннику

      Этот  этап включает операцию растяжения, сжатия или редукции многогранника.

1. Растяжение.

       Если лучшее значение функции  , то выполняется растяжение по формуле .

      

      Если  , то точка заменяет худшую вершину многоугольника.

      

      Переходим ко 2-му этапу. 

      

2. Замена  худшей вершины отраженной точкой.

      Если  , но при этом , для .

      То  худшая вершина заменяется отраженной точкой, то есть

      И переходим ко второму этапу (определению худшей и лучшей вершины). 

      

3. Сжатие.

      В зависимости от значения функции  выполняют внутреннее или внешнее сжатие многогранника:

      а) внутреннее сжатие:

      применяется, когда  тогда сжатие и вычисляем . Если, , то худшая вершина заменяется точкой сжатия, то есть

      б) внешнее сжатие:

      Если  , то сжатие проводят по формуле и вычисляют .

      Если  , то худшую вершину заменяют точкой сжатия. 

      

4. Редукция (уменьшение) многогранника:

      Если  точка сжатия , то полагают , ,

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

      После этого переходят ко второму этапу. Таким образом, этапы 2 и 3 выполняются итерационно, до тех пор, пока многогранник не станет достаточно мал. Для выполнения критерия остановок, на каждой итерации вычисляют размер многогранника:

      

      если  , где заданная допустимая погрешность, то работу метода завершают. 

       ИДЗ Заика минимакс критериев  Метод  Нелдера-Мида

       H = 1  Tol = 0.001  typeExit = h  Nfm = 500  Tm = 600c

       -----------------------------------------------------------------------------------------------

          Ni   Nb   Nf   H         Dx        Df        F1        F2        x1        x2     действие

       -----------------------------------------------------------------------------------------------

           0    1    1   1         7.3       1.85e2    0         2e2       0         0      начало

           1    4    5   1         5.8       1.3e2     0         1.45e2    1.5       1.5    растяжение

           2    4    6   1.5       5.8       1.3e2     0         1.45e2    1.5       1.5    отражение

           3    6    8   1.5       4.3      70.4       0        85         3         4      растяжение

           4    6    9   2.5       4.3      70.4       0        85         3         4      отражение

           5    8   11   2.5       0.2       0.4       0        15         7.5       7.5    растяжение

           6    8   12   4.5       0.2       0.4       0        15         7.5       7.5    отражение

           7    8   14   4.5       0.2       0.4       0        15         7.5       7.5    сжатие

           8    8   16   2.5       0.2       0.4       0        15         7.5       7.5    сжатие

           9    8   18   1.5       0.2       0.4       0        15         7.5       7.5    сжатие

          10    8   20   1         0.2       0.4       0        15         7.5       7.5    сжатие

          11    8   22   1         0.2       0.4       0        15         7.5       7.5    сжатие

          12    9   24   1         0.575     0.15      0        14.75      6.875     7.875  растяжение

          13    9   26   0.625     0.575     0.15      0        14.75      6.875     7.875  сжатие

          14   10   28   0.625     0.1688    0.0875    0        14.6875    7.4688    7.2188 растяжение

          15   10   30   0.6563    0.1688    0.0875    0        14.6875    7.4688    7.2188 сжатие

          16   11   32   0.6563    0.0984    9.38e-3   0        14.6094    7.2109    7.3984 растяжение

          17   11   34   0.4766    0.0984    9.38e-3   0        14.6094    7.2109    7.3984 сжатие

          18   11   36   0.2578    0.0984    9.38e-3   0        14.6094    7.2109    7.3984 сжатие

          19   11   38   0.2578    0.0984    9.38e-3   0        14.6094    7.2109    7.3984 сжатие

          20   12   40   0.1321    0.0303    9.77e-5   0        14.6001    7.3303    7.2698 растяжение

          21   12   42   0.1287    0.0303    9.77e-5   0        14.6001    7.3303    7.2698 сжатие

          22   12   44   0.1287    0.0303    9.77e-5   0        14.6001    7.3303    7.2698 сжатие

          23   12   46  0.1287    0.0303    9.77e-5   0        14.6001    7.3303    7.2698 сжатие

          24   13   48   0.1287    0.0384   -2.45e-3   0        14.5975    7.2616    7.3357 растяжение

          25   13   50   0.0687    0.0384   -2.45e-3   0        14.5975    7.2616    7.3357 сжатие

          26   13   52   0.0687    0.0384   -2.45e-3   0        14.5975    7.2616    7.3357 сжатие

          27   13   54   0.0687    0.0384   -2.45e-3   0        14.5975    7.2616    7.3357 сжатие

          28   13   56   0.0687    0.0384   -2.45e-3   0        14.5975    7.2616    7.3357 сжатие

          29   13   57   0.0403    0.0384   -2.45e-3   0        14.5975    7.2616    7.3357 отражение

          30   13   59   0.0403    0.0384   -2.45e-3   0        14.5975    7.2616    7.3357 сжатие

          31   13   61   0.0243    0.0384   -2.45e-3   0        14.5975    7.2616    7.3357 сжатие

          32   14   63   0.0243    0.0241   -2.84e-3   0        14.5972    7.2759    7.3212 растяжение

          33   14   65   0.0145    0.0241   -2.84e-3   0        14.5972    7.2759    7.3212 сжатие

          34   14   67   0.0145    0.0241   -2.84e-3   0        14.5972    7.2759    7.3212 сжатие

          35   14   68   0.0145    0.0241   -2.84e-3   0        14.5972    7.2759    7.3212 отражение

          36   16   70   0.0115    2.05e-3  -3.06e-3   0        14.5969    7.2989    7.2979 растяжение

          37   16   72   0.0233    2.05e-3  -3.06e-3   0        14.5969    7.2989    7.2979 сжатие

          38   16   74   0.0233    2.05e-3  -3.06e-3   0        14.5969    7.2989    7.2979 сжатие

          39   16   76   0.0233    2.05e-3  -3.06e-3   0        14.5969    7.2989    7.2979 сжатие

          40   17   78   0.0146    6.11e-3  -3.1e-3    0        14.5969    7.2939    7.303  сжатие

          41   17   80   9.51e-3   6.11e-3  -3.1e-3    0        14.5969    7.2939    7.303  сжатие

          42   17   82   5.06e-3   6.11e-3  -3.1e-3    0        14.5969    7.2939    7.303  сжатие

          43   18   84   5.06e-3   3.71e-3  -3.11e-3   0        14.5969    7.2963    7.3006 сжатие

          44   18   86   2.89e-3   3.71e-3  -3.11e-3   0        14.5969    7.2963    7.3006 сжатие

          45   19   88   2.41e-3   4.08e-3  -3.12e-3   0        14.5969    7.2959    7.301  растяжение

          46   19   90   2.05e-3   4.08e-3  -3.12e-3   0        14.5969    7.2959    7.301  сжатие

          47   20   92   9.33e-4   2.79e-3  -3.12e-3   0        14.5969    7.2972    7.2997 растяжение

          47   20   92   9.33e-4   2.79e-3  -3.12e-3   0        14.5969    7.2972    7.2997 конец

       -----------------------------------------------------------------------------------------------

       Достигнута  заданная точность по шагу

       Nf = 92  Na = 92  Nb = 20  Ni = 47  inD = 1

       Df =  -3.12e-3   Dx =   2.79e-3

       H =   9.33e-4   h =   1         dx =   0     

       fx = ((0 14.596878015960705))