Постановка задачи динамического программирования. Задачи распределения ресурсов.

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

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

{spoiler=Подробнее}

В задачах динамического программирования экономический процесс зависит от времени [от нескольких периодов (этапов) времени], поэтому находится ряд оптимальных решений (последовательно для каждого этапа), обеспечивающих оптимальное развитие всего процесса в целом. Задачи динамического программирования называются многоэтапными или многошаговыми.

Динамическое программирование представляет собой математический аппарат, позволяющий осуществлять оптимальное планирование многошаговых управляемых процессов и процессов, зависящих от времени. Экономический процесс называется совокупность решений, принимаемых на каждом этапе для влияния на ход процесса. В экономических процессах управление заключается в распределение и перераспределении средств на каждом этапе.         Например, выпуск продукции любым предприятием - управляемый процесс, так как он определяется изменением  состава оборудования, объемом поставок сырья, величиной финансирования и т.д.     Совокупность решений, принимаемых в начале каждого года  планируемого периода по обеспечению предприятия сырьем, замене оборудования, размером финансирования и т.д., является управлением. Казалось бы, для получения максимального объема выпускаемой продукции проще всего вложить максимально возможное количество средств и использовать на полную мощность оборудование. Но это привело бы к быстрому изнашиванию оборудования и, как следствие, к уменьшению выпуска продукции. Следовательно, выпуск продукции надо спланировать так, чтобы избежать нежелательных эффектов.  Необходимо предусмотреть мероприятия, обеспечивающие пополнение оборудования по мере изнашивания, т.е. по периодам  времени. Последнее хотя и приводит к уменьшению первоначального объема выпускаемой продукции, но обеспечивает в дальнейшем возможность расширения производства. Таким  образом, экономический процесс выпуска продукции можно считать состоящим из нескольких этапов (шагов), на каждом из которых осуществляется влияние на его развитие.

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

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

Пример. Пусть планируется деятельность некоторой системы S промышленных предприятий Р₁ , Р₂, ..., Р_n  на  некоторый период времени Т, состоящий из  k  хозяйственных  лет t_i (i=1,2,...,k), причем

Т=åt_i.

В начале периода Т на развитие предприятий выделены основные средства D. В начале  каждого хозяйственного года производится финансирование  всей  системы  предприятий ,  т.е. выделяется доля основных средств. Известны первоначальное состояние системы. S₀, характеризуемое количество средств, уже вложенных    в предприятия, и конечное состояние S_k, характеризуемое всей дополнительно вложенной суммой D. Как следует распределить по предприятиям  и годам основные средства D, чтобы к концу периода T суммарный доход W от всей системы предприятий был максимальным?

         Решение. Обозначим через x_{i j} сумму, выделяемую в начале i-го года j-му предприятию (i=1, 2,..., k; j=1, 2,..., n). Предположим, что средства на i-м этапе распределены, т.е. выбрано определенное управление U_i , которые состоит в том, что в начале i-го предприятию P₁ выделены средства x_{i 1} , предприятию P₂ - средства на х_i - м этапе. Совокупность выделенных средств (управлений) на k шагах выразится системой векторов n-мерного векторного пространства

U₁=(x₁₁; x₁₂; ...; x_1n),

U₂=(x₂₁; x₂₂; ...; x_2n),

. . . . . . . . . . . . . .

U_k=( x_k1; x_k2; ...; x_kn).

    Суммарный доход за k лет зависит от совокупности управлений, т.е. является функцией от U₁, U₂, ..., U_k:

W=W(U₁, U₂, ..., U_k).

Задача состоит в следующем: на каждом этапе необходимо выбрать такое управление, чтобы суммарный доход от всей системы предприятий был максимальным.

Общая постановка задачи динамического программирования.

    Пусть некоторая физическая управляемая система S находится в первоначальном состоянии S₀ Î S₀^~. С течением времени ее состояние S_kÎ S_k^~. С процессом изменения состояния системы связан некоторой численный критерий W. Необходимо так организовать процесс, чтобы критерий достиг оптимального значения.

         Обозначим множество возможных управлений U .Тогда задача состоит в том ,чтобы из множества возможных управлений U  найти такое управление U^*, которая позволит перевести систему S  из начального состояния S₀ ÎS₀^~ в конечное S_kÎS_k^~ так, критерий W (U) принимает оптимальное значение  W*.

         Геометрическая интерпретация задачи динамического программирования.

         Состояние физической системы  S можно описать числовыми параметрами, например расходом горючего и скоростью,     количеством    вложенных средств и так далее. Назовем эти параметры координатами системы; тогда состояние системы можно изобразить точкой S, а переход из одного состояния S₁ в другое S₂- траекторией точки S. Управление U означает выбор определенной траектории перемещения точки S и S₁ в S₂, то есть установление определенного закона движения точки S.

         Совокупность состояний, в которые может переходить система, называется областью возможных состояний. В зависимости от числа параметров, характеризующих состояние системы, область возможных состояний системы может быть различной.

Принцип поэтапного построения оптимального управления.

         Динамическое программирования представляет собой поэтапное планирование многошагового процесса, при котором на каждом этапе, учитывая развитие всего процесса, оптимизируют только один шаг, т.е. при принятии решения  учитывается будущее. Однако в каждом процессе имеется  последний k-й  шаг, принятие   решения на котором не зависит от будущего. Поэтому на этом шаге выбирают управление, позволяющее получить наибольший эффект. Спланировав этот шаг, к нему можно  присоединить предпоследний (k-1)-й шаг, к которому, в свою очередь, (k-2)-й и т.д. В конечном итоге приходят в начальное состояние системы S₀. Процесс динамического программирования  как бы “разворачивается” от конца к началу.

         Для того чтобы спланировать k-й шаг, надо знать состояние системы на (k-1)-м шаге. Если состояние системы на (k-1)-м шаге неизвестно,  то, исходя из характера данного процесса, делают различные предположения о возможных состояниях системы на этом шаге. Для каждого предположения выбирают оптимальное управление на последнем, k-м, шаге. Такое оптимальное управление называется условно оптимальным.

         Пусть планируется k-шаговый процесс. Сделаем  ряд предположений о возможных состояниях системы на (k-1)-м шаге. Обозначим эти состояния через S_k-1,1,S_k-1,2  ,...,S_k-1,r. На последнем шаге найдем для каждого из них условно оптимальное  управление

U*_k,1(S_k-1,1),U*_k,2 (S_k-1,2),...,U*_k,r(S_k-1,r).

          Таким образом, k-й шаг спланирован. Действительно, какое бы состояние ни  имела система на предпоследнем шаге, уже известно какое управление следует применить на последнем шаге. Аналогично поступаем  на (k-1)-м шаге, только условно оптимальные управления необходимо выбирать, учитывая уже выбранные условно   оптимальные управления  на  k-м шаге, и т. д. В итоге приходим к        первоначальному состоянию S₀ Î S₀^~.

    Для первого шага (в отличие от всех остальных) предположений о возможном состоянии системы не делаем, так как состояние S₀ известно, а находим оптимальное управление ,учитывая все условно оптимальные управления, найденные для второго шага. Проходя от S₀ к S_k, получаем искомое оптимальное управление для всего процесса.

Задача распределения ресурсов

          В задаче распределения средств  предполагается, что полный доход зависит только от начального количества средств x и числа этапов N и не зависит от времени начала процесса. Допустим, что в результате деления средств x на величины y  и  x - y на k-м году получен доход g_k(x, y) и для дальнейшего распределения осталось количество средств r_k (x, y). Необходимо определить управление, позволяющее максимизировать полный доход N-этапного процесса.

         Предположим, что функции g_k(x, y)  и r_k (x, y) непрерывны как функции от x и y для x³0 ва 0£y£x, a  r_k (x, y) в этой области  удовлетворяет двойному неравенству 0£ r_k (x, y) £ax, a£1 для k=1, 2,...

Пусть f_kN(x) - полный доход от N-этапного процесса, начинающегося с величины x, на k-м году, если соблюдался принцип оптимальности. Тогда для одноэтапного процесса при N=1 f₁(x)=max g_k(x, y),

0£y£x

при N³2, рассуждая аналогично, получаем

f_kN(x)=max {g_k(x, y)+f_{k+1,  n-1}[r_k (x, y)]}

         Двойные индексы значительно усложняют вычисления, один индекс. Положим, что каждому этапу соответствуют значения k=1, 2, ..., N, и определим функцию f_k(x) как полный доход от процесса, начинающегося с величины x на k-м этапе и заканчивающегося на N-м этапе, если соблюдается принцип оптимальности. Тогда имеем следующие функциональные уравнения:

при k=N f₁(x)=max g_k(x, y),

0£y£x

при k=N-1, N-2,..., 2,1

f_kN(x)=max {g_k(x, y)+f_k+1,  N-1[r_k (x, y)]}

0£y£x

         Пример. Для развития двух отраслей производства, I и II, на 5 лет выделено x средств. Количество средств y, вложенных в отрасль I, позволяет получить за один год доход j(y)=y²   и уменьшается до величины y(y)=0,75y. Количество средств x - y, вложенных в отрасль II, позволяет получить за один год доход x( x - y)=2( x - y)² и уменьшается до величины r( x - y)=0,3( x - y).

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

         Решение. Период времени продолжительностью 5 лет разобъем  на 5 этапов, поставив в соответствие каждому году один этап, т.е. N=5, k=1, 2, 3, 4, 5. Хотя рассматривается непрерывный процесс, величины x и y для наглядности на каждом этапе будем отмечать индексами.

Отыскание оптимального решения начинаем с 5-го этапа, в начале которого необходимо распределить остаток средств x₄. Для этого следует определить функций, входящих в уравнение:

         Используя метод дифференциального исчисления, находим значение y₅, при котором функция,заключения в квадратные скобки, на отрезке [0,х₄] принимает наибольшее значение. Учитывая, что х₄ для 5-го этапа есть величина постоянная, получаем:

         Точка y₅=(2/3)х₄ является точкой минимума.

         Определим значение функции на концах отрезка [0,х₄]:

         g₅(х_4, у₅) = 2х  _при у₅ = 0,

         g₅(х_4, у₅) = х    _при у₅ = х₄.

      Так как 2х > х > (2/3) х , то функция g₅(х₄­, у₅) принимает макси-мальное значение на отрезке [0,х₄] при у₅ = 0, следовательно, f₅(х₄) = 2х .

{/spoilers}