Динамическое программирование в задачах распределения однонородных ресурсов.

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

Алгоритм метода динамического программирования был перенесен с задач военного характера на задачи которые стоят перед менеджером распределяющего финансирования ресурсов по исполнителям.

Все действия которые менеджер совершает в процессе распределения однородного ресурса, многоэтапный протекающий во времени.

Алгоритм динамического программирования включают следующие этапы:

Общий этап

Имеется некая управляющая операция (распределение финансов генеральным директором) распадающаяся (естественно или исскуственно) на m шагов.

На каждом шаге осуществляется распределение и перераспределение ресурсов участвующих в операции с целью улучшения ее результатов в целом. Эти распределения ресурсов в МДП (метод динамического программирования) называются управлениями U-операциями.

Эффективность операций в целом (приращение денег в банке) оценивается тем же показателем что и показатель эффективности управления. При этом Э(U) зависит от всей эффективности управления на каждом шаге операций. Тогда Э =Э(U)=Э(U1,U2….Un).

Управление при каждом показатель Э достигается max называется оптимальным управлении Uopt

Задачи динамического программирования заключаются в том, в том чтобы определить на каждом шаге Uiopt, где i=(1,m) и тем самым оптимальное управление в целом.

В большинстве задач МДП

Э = Эj max, где Эj-эффективность операций на этом шаге.

Динамическое программирование при решение задач распределения задач распределения ресурсов осуществляется в два круга. В начале от последнего шага к первому. Затем в обратном направлении от первого к последнему.

На первом круге (от последнего шага к первому) находится условно-оптимальное управлении.

Оно выбирается таким чтобы все предыдущие обеспечивали max Эi+1го шага. Иначе на каждом шаге имеется такое управление Ui которое обеспечивает оптимальное продолжение операции при Эi-1 или Эi+1.Этот принцип выбора управления называется принципом оптимальности Белмона. Так продолжается до первого шага.

Поскольку первый шаг имеет предыдущего, то полученные для него условное Uopt терпит свой условный характер и становится просто оптимальным управлением, играющий роль исходного для второго круга.

Второй круг оптимизации начинается с первого шага для каждого оптимального управления U1opt известно, имея все шаги после него устанавливают Uiopt оптимальное управление становится понятным или известен алгоритм действий который при его реализации на 2м круге обеспечит оптимальность всей операции в целом. На практике встречается много задач по распределению однородных ресурсов решаемых МДП, одно наиболее часто к этому методу приходится прибегать в задачах распределения однородных ресурсов.