Рефераты - Афоризмы - Словари
Русские, белорусские и английские сочинения
Русские и белорусские изложения
 
У нас есть несколько работ на данную тему. Вы можете создать свою уникальную работу объединив фрагменты из уже существующих:
  1. Динамическое программирование (задача о загрузке) 32 Кб.
  2. Линейное и динамическое программирование 42 Кб.
  3. Динамическое программирование 14.3 Кб.
  4. Динамическое программирование 23.6 Кб.
  5. Динамическое программирование и дифференциальное и интегральное исчисление в образах 62.3 Кб.
  6. Динамическое программирование 34.9 Кб.
  7. Динамическое программирование 43.4 Кб.

Динамическое программирование

Работа из раздела: «Экономико-математическое моделирование»

 Курсовая работа по теории оптимального управления экономическими системами.
                Тема : Задача динамического программирования.

                      I.Основные понятия и обозначения.

Динамическое программирование – это математический метод поиска
оптимального управления, специально приспособленный к многошаговым
процессам. Рассмотрим пример такого процесса.
  Пусть планируется деятельность группы предприятий на N лет. Здесь шагом
является один год. В начале 1-го года на развитие предприятий выделяются
средства, которые должны быть как-то распределены между этими
предприятиями. В процессе их функционирования выделенные средства частично
расходуются. Каждое предприятие за год приносит некоторый доход, зависящий
от вложенных средств. В начале года имеющиеся средства могут
перераспределяться между предприятиями : каждому из них выделяется какая-то
доля средств.
  Ставится вопрос : как в начале каждого года распределять имеющиеся
средства между предприятиями, чтобы суммарный доход от всех предприятий за
N лет был максимальным?
  Перед нами типичная задача динамического программирования, в которой
рассматривается управляемый процесс – функционирование группы предприятий.
Управление процессом состоит в распределении (и перераспределении) средств.
Управляющим воздействием (УВ) является выделене каких-то средств каждому из
предприятий в начале года.
  УВ на каждом шаге должно выбираться с учетом всех его последствий в
будущем. УВ должно быть дальновидным, с учетом перспективы. Нет смысла
выбирать на рассматриваемом шаге наилучшее УВ, если в дальнейшем это
помешает получить наилучшие результаты других шагов. УВ на каждом шаге надо
выбирать “c заглядыванием в будущее”, иначе возможны серьезные ошибки.
  Действительно, предположим, что в рассмотренной группе предприятий одни
заняты выпуском предметов потребления, а другие производят для этого
машины. Причем целью является получение за N лет максимального объема
выпуска предметов потребления. Пусть планируются капиталовложения на первый
год. Исходя их узких интересов данного шага (года), мы должны были бы все
средства вложить в производство предметов потребления, пустить имеющиеся
машины на полную мощность и добиться к концу года максимального объема
продукции. Но правильным ли будет такое решение в целом? Очевидно, нет.
Имея в виду будущее, необходимо выделить какую-то долю средств и на
производство машин. При этом объем продукции за первый год, естественно,
снизится, зато будут созданы условия, позволяющие увеличивать ее
производство в последующие годы.
  В формализме решения задач методом динамического программирования будут
использоваться следующие обозначения:
  N – число шагов.
  [pic]– вектор,описывающий состояние системы на k-м шаге.
  [pic]– начальное состояние, т. е. cостояние на 1-м шаге.
  [pic]– конечное состояние, т. е. cостояние на последнем шаге.
  Xk – область допустимых состояний на k-ом шаге.
  [pic]– вектор УВ на k-ом шаге, обеспечивающий переход системы из
состояния xk-1 в состояние xk.
  Uk –  область допустимых УВ на k-ом шаге.
  Wk – величина выигрыша, полученного в результате реализации k-го шага.
  S – общий выигрыш за N шагов.
   [pic]– вектор оптимальной стратегии управления или ОУВ за N шагов.
  Sk+1([pic]) – максимальный выигрыш, получаемый при переходе из любого
состояния [pic][pic]в конечное состояние [pic] при оптимальной стратегии
управления начиная с (k+1)-го шага.
  S1([pic]) – максимальный выигрыш, получаемый за N шагов при переходе
системы из начального состояния [pic] в конечное [pic] при реализации
оптимальной стратегии управления [pic]. Очевидно, что S = S1([pic]), если
[pic] –фиксировано.
  Метод динамического программирования опирается на условие отсутствия
последействия и условие аддитивности целевой функции.
  Условие отсутствия последействия. Состояние [pic], в которое перешла
система за один k-й шаг, зависит от состояния [pic] и выбранного УВ [pic] и
не зависит от того, каким образом система пришла в состояние [pic], то есть
                                    [pic]

  Аналогично, величина выигрыша Wk зависит от состояния [pic] и выбранного
УВ [pic], то есть
                                    [pic]

  Условие аддитивности целевой функции. Общий выигрыш за N шагов
вычисляется по формуле
                                    [pic]

  Определение. Оптимальной стратегией управления [pic] называется
совокупность УВ [pic], то есть [pic], в результате реализации которых
система за N шагов переходит из начального состояния [pic] в конечное [pic]
и при этом общий выигрыш S принимает наибольшее значение.
  Условие отсутствия последействия позволяет сформулировать принцип
оптимальности Белмана.
  Принцип оптимальности. Каково бы ни было допустимое состояние
системы[pic][pic]  перед очередным i-м шагом, надо выбрать допустимое УВ
[pic] на этом шаге так, чтобы выигрыш Wi на i-м шаге плюс оптимальный
выигрыш на всех последующих шагах был максимальным.
  В качестве примера постановки задачи оптимального управления продолжим
рассмотрение задачи управления финансированием группы предприятий. Пусть в
начале i-го года группе предприятий [pic] выделяются соответственно
средства:  [pic][pic]совокупность этих значений можно считать управлением
на i-м шаге, то есть [pic]. Управление [pic] процессом в целом представляет
собой совокупность всех шаговых управлений, то есть [pic].
  Управление может быть хорошим или плохим, эффективным или неэффективным.
Эффективность управления  [pic] оценивается показателем S. Возникает
вопрос: как выбрать шаговые управления  [pic], чтобы величина S обратилась
в максимум ?
  Поставленная задача является задачей оптимального управления, а
управление, при котором показатель S достигает максимума, называется
оптимальным. Оптимальное управление [pic] многошаговым процессом состоит из
совокупности оптимальных шаговых управлений:

                                    [pic]
  Таким образом, перед нами стоит задача: определить оптимальное управление
на каждом шаге  [pic](i=1,2,...N) и, значит, оптимальное управление всем
процессом [pic].

               II. Идеи метода динамического программирования

Мы отметили, что планируя многошаговый процесс, необходимо выбирать УВ на
каждом шаге с учетом его будущих последствий на еще предстоящих шагах.
Однако, из этого правила есть исключение. Среди всех шагов существует один,
который может планироваться без 'заглядыва-ния в будущее'. Какой это шаг?
Очевидно, последний — после него других шагов нет. Этот шаг, единственный
из всех, можно планировать так, чтобы он как таковой принес наибольшую
выгоду. Спланировав оптимально этот последний шаг, можно к нему
пристраивать предпоследний, к предпоследнему — предпредпоследний и т.д.
  Поэтому процесс динамического программирования на 1-м этапе
разворачивается от конца к началу, то есть раньше всех планируется
последний,
  N-й шаг. А как его спланировать, если мы не знаем, чем кончился
предпоследний? Очевидно, нужно сделать все возможные предположения о том,
чем кончился предпоследний, (N — 1)-й шаг, и для каждого из них найти такое
управление, при котором выигрыш (доход) на последнем шаге был бы
максимален. Решив эту задачу, мы найдем условно оптимальное управление
(УОУ) на N-м шаге, т.е. управление, которое надо применить, если (N — 1)-й
шаг закончился определенным образом.
  Предположим, что эта процедура выполнена, то есть для каждого исхода
  (N — 1)-го шага мы знаем УОУ на N-м шаге и соответствующий ему условно
оптимальный выигрыш (УОВ). Теперь мы можем оптимизировать управление на
предпоследнем, (N — 1)-м шаге. Сделаем все возможные предположения о том,
чем кончился предпредпоследпий, то есть (N — 2)-й шаг, и для каждого из
этих предположений найдем такое управление на (N — 1)-м шаге, чтобы выигрыш
за последние два шага (из которых последний уже оптимизирован) был
максимален. Далее оптимизируется управ чение на (N — 2)-м шаге, и т.д.
  Одним словом, на каждом шаге ищется такое управление, которое обеспечивает
оптимальное продолжение процесса относительно достигнутого в данный момент
состояния. Этот принцип выбора управления , называется принципом
оптимальности. Само управление, обеспечивающее оптимальное продолжение
процесса относительно заданного состояния, называется УОУ на данном шаге.

    Теперь предположим, что УОУ на каждом шаге нам известно: мы знаем, что
делать дальше, в каком бы состоянии ни был процесс к началу каждого шага.
Тогда мы можем найти уже не 'условное', а дейсгвительно оптимальное
управление на каждом шаге.                        |
  Действительно, пусть нам известно начальное состояние процесса. Теперь мы
уже знаем, что делать на первом шаге: надо применить УОУ, найденное для
первого шага и начального сосюяния. В результате этого управления после
первого шага система перейдет в другое состояние; но для этого состояния мы
знаем УОУ и г д. Таким образом, мы найдем оптимальное управление процессом,
приводящее к максимально возможному выигрышу.
  Таким образом, в процессе оптимизации управления методом динамического
программирования многошаговый процесс 'проходится' дважды:
  — первый раз — от конца к началу, в результате чего находятся УОУ| на
каждом шаге и оптимальный выигрыш (тоже условный) на всех шагах,  начиная с
данного и до конца процесса;
  . второй раз — от начала к концу, в результате чего находятся оптимальные
                     управления на всех шагах процесса.
Можно сказать, что процедура построения оптимального управления
методом динамического программирования распадается на две стадии:
предварительную и окончательную. На предварительной стадии для каждого шага
определяется УОУ, зависящее от состояния системы (достигнутого в результате
предыдущих шагов), и условно оптимальный выигрыш на всех оставшихся шагах,
начиная с данного, также зависящий от состояния. На окончательной стадии
определяется (безусловное) оптимальное управление для каждого шага.
Предварительная (условная) оптимизация производится по шагам в обратном
порядке: от последнего шага к первому; окончательная (безусловная)
оптимизация — также по шагам, но в естественном порядке: от первого шага к
последнему. Из двух стадий оптимизации несравненно более важной и
трудоемкой является первая. После окончания первой стадии выполнение второй
трудности не представляет: остается только 'прочесть' рекомендации, уже
заготовленные на первой стадии.

             III.  Пример задачи динамического программирования
                    Выбор состава оборудования технологической линии.
  Есть технологическая линия , то есть цепочка, последовательность
операций.
  На каждую операцию можно назначить оборудование только каго-то одного
вида, а оборудования, способного работать на данной  операции,  -
несколько видов.

                         Исходные данные для примера

|i          |1         |2         |3         |
|j          |1   |2   |1   |2   |1   |2   |
|           |10  |8   |4   |5   |8   |9   |
|[pic]      |12  |8   |4   |6   |9   |9   |
|           |20  |18  |6   |8   |10  |12  |

  Стоимость сырья
  Расходы , связанные с использованием единицы оборудования j-го типа на i-
ой операции[pic]
  Производительности, соответственно, по выходу и входу [pic] и [pic] для
j-готипа оборудования, претендующего на i-ую операцию.

                                  Решение:
  Для того, чтобы решить данную задачу методом динамического
программирования введем следующие обозначения:
  N = 3 – число шагов.
  [pic] - Технологическая линия.
  [pic]=  (0,0,0)
  [pic]= (                   )
  [pic] – выбор оборудования для i-ой операции.
  Ui – область допустимых УВ на i-м шаге.
  [pic]т.е.[pic]
  Wi – оценка минимальной себестоимости, полученная в результате реализации
i-го шага.
  S – функция общего выигрыша  т. е. минимальная себестоимость .



                           - вектор – функция, описывающая переход системы
из состояния               в состояние  [pic]  под действием УВ.

  [pic] - вектор УВ на i-ом шаге, обеспечивающий переход системы из
состояния xi-1 в состояние xi , т.е. оптимальный выбор оборудования за N
шагов.
  Si+1([pic]) – максимальный выигрыш ( в нашем случае минимальная
себестоимость), получаемый при переходе из любого состояния [pic][pic]в
конечное состояние [pic] при оптимальной стратегии управления начиная с
(k+1)-го шага.
  S1([pic]) – максимальный выигрыш, получаемый за N шагов при переходе
системы из начального состояния [pic] в конечное [pic] при реализации
оптимальной стратегии управления [pic]. Очевидно, что S = S1([pic]), если
[pic]= 0.

  Запишем вектора допустимых значений



  Запишем вектора допустимых управляющих воздействий



  Запишем вектор – функцию, описывающую переход системы из состояния
           в состояние  [pic]  под действием УВ.



  Запишем основное функциональное уравнение



  1) Обратный проход
  Для  i=3



  Учитывая то, что этот шаг у нас последний и следующей операции
  уже не будет, а также то, что мы на обратном проходе, вместо функции
            возьмем стоимость сырья

  при [pic]
            =



  при [pic]
            =

  т. е.

  Для   i=2



  при [pic]
                         =


  при [pic]
                         =


  при [pic]
                           =


  при [pic]
                          =

  т. е.

  Для  i=1



  при [pic]
                       =


  при [pic]
                     =



  при [pic]
                       =


  при [pic]
                       ==


  при [pic]
                             =


  при [pic]
                               =


  при [pic]
                              =


  при [pic]
                                 =

  т. е.

  2) Прямой проход
     Учитывая то, что                                  и   [pic]= (0,0,0)
     имеем
       i=1



      i=2



     i=3



     Таким образом оптимальный выбор составаоборудования технологической
     линии предполагает следующее:
     На  1-ую операцию назначим оборудование 2-го вида
     На  2-ую операцию назначим оборудование 1-го вида
     На  3-ью операцию назначим оборудование 2-го вида
     Оценка минимальной себестоимости составит 105,5.

-----------------------
[pic]

[pic]

[pic]

[pic][pic][pic]

[pic][pic]
[pic]

[pic]

[pic][pic]
[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]125,3
[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]
[pic]

[pic]
[pic]

[pic]

[pic]

[pic]
[pic]

[pic]

[pic]115,2
[pic]

[pic]

[pic]138,04
[pic]

[pic]

[pic]102,8
[pic]

[pic]

[pic]123,1
[pic]

[pic]

[pic]

[pic]

[pic]

[pic]140,2
[pic]

[pic]

[pic]125,3
[pic]

[pic]

[pic]125,3
[pic]

[pic]

[pic]125,3
[pic]

[pic]

[pic]125,3
[pic]

[pic]

[pic]125,3
[pic]

[pic]

[pic]125,3
[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]



ref.by 2006—2022
contextus@mail.ru