Применение ЭВМ в электроэнергетике: Текст лекций. Медведева С.Н. - 27 стр.

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

Запросы
потребителей
возможности
поставщиков
110 20 40 110
120
6
0
1
20
5
40
2
60
100
3
50
6
0
7
0
4
50
ЦФ=810.
Существует алгоритм определения оптимального решения.
Для каждой клетки определяется оценка свободной клетки. Для
оптимального решения все оценки свободных клеток д.б.
неотрицательны. Для базисного распределения табл. 1 найдем,
например, оценку свободной клетки (1,3). Для этого дадим в эту клетку
единичную поставку. Тогда распределение поставок изменится в
соответствии с таблицей 4.
Запросы
потребителей
возможности
поставщиков
20 110 40 110
60
1
20
2
39
5
1
3
0
120
1
0
6
0
5
39
2
81
100
6
0
3
71
7
0
4
29
Заметим, что изменение распределения д.б. замкнутым.
ЦФ4=20+2*39+3*71+5+5*39+2*81+4*29=789
Изменение ЦФ4-ЦФ1=-1 или =2*(-1)+3*1+5*1+5*(-1)+2*1+4*(-1)=-1
(вторым способом легче считать).
Для достижения оптимального решения увеличиваем поставку в клетке
с отрицательной оценкой до тех пор, пока другая несвободная клетка не
станет равной 0 (смена базиса!).
Далее вновь оценивается решение оптимально ли оно, т.е. оценки всех
свободных клеток д.б. неотрицательны. Если есть отрицательная
оценка, то для той клетки увеличиваем поставки, пока какая-то базисная
клетка не обратится в 0. И т.д. Круг замкнулся.
Для нашей задачи оптимальное решение следующее:
Запросы
потребителей
возможности
поставщиков
20 110 40 110
60
1
10
2
10
5
40
3
0
120
1
10
6
0
5
0
2
110
100
6
0
3
100
7
0
4
0
ЦФ5=760 (min !)
Поиск решений с помощью оптимизационных методов
(продолжение темы)
Метод динамического программирования (ДП).
Динамическое программирование представляет собой
математический аппарат для решения нелинейных оптимизационных
задач. Этим методом решаются задачи оптимального управления
многошаговыми процессами путем сведения многомерной задачи к
последовательности простых одномерных оптимизационных задач.
Целевая функция оптимизации может быть как гладкой, так и
негладкой, что затрудняет использование классических методов
оптимизации.
Специфика метода ДП заключается в том
, что весь процесс
оптимизации разбивается на шаги (этапы), причем каждый раз 
             Запросы                                                              Для достижения оптимального решения увеличиваем поставку в клетке
        потребителей
                           110            20             40            110        с отрицательной оценкой до тех пор, пока другая несвободная клетка не
возможности                                                                       станет равной 0 (смена базиса!).
поставщиков                                                                       Далее вновь оценивается решение оптимально ли оно, т.е. оценки всех
                       6              1              5             2              свободных клеток д.б. неотрицательны. Если есть отрицательная
        120
                                 0              20            40             60   оценка, то для той клетки увеличиваем поставки, пока какая-то базисная
                       3              6              7             4              клетка не обратится в 0. И т.д. Круг замкнулся.
        100
                                 50             0             0              50   Для нашей задачи оптимальное решение следующее:

ЦФ=810.                                                                                        Запросы
                                                                                          потребителей
                                                                                                             20            110            40            110
Существует алгоритм определения оптимального решения.                             возможности
Для каждой клетки определяется оценка свободной клетки. Для                       поставщиков
оптимального решения все оценки свободных клеток д.б.                                                    1             2              5             3
                                                                                           60
неотрицательны. Для базисного распределения табл. 1 найдем,                                                       10             10            40             0
например, оценку свободной клетки (1,3). Для этого дадим в эту клетку                                    1             6              5             2
                                                                                          120
единичную поставку. Тогда распределение поставок изменится в                                                      10             0             0          110
соответствии с таблицей 4.                                                                               6             3              7             4
                                                                                          100
                                                                                                                  0          100               0              0
             Запросы
        потребителей
                           20             110            40            110        ЦФ5=760 (min !)
возможности
поставщиков
                       1              2              5             3                 Поиск решений с помощью оптимизационных методов
         60
                                 20             39            1              0
                                                                                  (продолжение темы)
                       1              6              5             2
        120                                                                           Метод динамического программирования (ДП).
                                 0              0             39             81
                       6              3              7             4                  Динамическое     программирование    представляет   собой
        100                                                                       математический аппарат для решения нелинейных оптимизационных
                                 0              71            0              29
                                                                                  задач. Этим методом решаются задачи оптимального управления
Заметим, что изменение распределения д.б. замкнутым.                              многошаговыми процессами путем сведения многомерной задачи к
ЦФ4=20+2*39+3*71+5+5*39+2*81+4*29=789                                             последовательности простых одномерных оптимизационных задач.
Изменение ЦФ4-ЦФ1=-1 или =2*(-1)+3*1+5*1+5*(-1)+2*1+4*(-1)=-1                     Целевая функция оптимизации может быть как гладкой, так и
(вторым способом легче считать).                                                  негладкой, что затрудняет использование классических методов
                                                                                  оптимизации.
                                                                                      Специфика метода ДП заключается в том, что весь процесс
                                                                                  оптимизации разбивается на шаги (этапы), причем каждый раз

Страницы