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

Динамическое программирование является разделом математического программирования, в котором изучаются многошаговые процессы поиска решения. Существует ряд областей практической деятельности, в которых целесообразно искать решение не сразу, а последовательно, шаг за шагом, т.е. поиск решения рассматривается не как единичный акт, а как процесс, состоящий из нескольких этапов. Различные задачи многошаговых процессов поиска решения могут быть описаны некоторым единообразным математическим аппаратом. Таким аппаратом является теория динамического программирования, созданная американским математиком Р. Беллманом и его учениками. В задачах, решаемых методами динамического программирования, имеется физическая система и совокупность моментов времени. В каждый момент времени система характеризуется набором значений параметров состояния:

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

(3.2.1)

Это и есть задача динамического программирования. В задаче (3.1.1) предполагается, что каждое из множеств и состоит из одной точки (из одного вектора), при этом целевая функция интерпретируется как суммарная прибыль, получаемая в результате функционирования системы на протяжении рассматриваемого отрезка времени. Отметим, что применение некоторых управлений может оказаться весьма дорогостоящим. Переменная в задаче (3.2.1) представляет собой вектор , определяющий траекторию системы. Вектор определяет траекторию состояния системы, а вектор – траекторию управлений системой. Все переменные упорядочены (разнесены по времени) и это отражено в ограничениях задачи. Кроме того, рассматриваемая система является системой без последействия т.к. очередное состояние, в которое она переходит, определяется только предыдущим шагом. При решении подобных задач важным является вид целевой функции. Использование сепарабельной целевой функции позволяет вместо решения задачи от большого числа переменных несколько раз решить задачу от одной переменной. Рассмотрим некоторые примеры задач, допускающих постановку в виде задачи динамического программирования.

3.2.1.Задача о замене оборудования

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

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

Если , то . При принимает значение или .

В соответствии с вышеизложенным, . Кроме того,

или .

Суммарная прибыль на рассматриваемом отрезке времени составит

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

(3.2.2)

3.2.2. Задача о распределении ресурса

Имеется некоторый ресурс в количестве и предприятий, между которыми этот ресурс требуется распределить так, чтобы максимизировать суммарную прибыль, даваемую этими предприятиями. Известны функции , , определяющие прибыль каждого из предприятий в зависимости от количества имеющегося на предприятии ресурса. Таким образом, если -е предприятие располагает ресурсом в количестве , то оно обеспечивает прибыль величиной . С учетом введенных обозначений, задача о распределении ресурса может быть сформулирована в виде:

(3.2.3)

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

Предположим, что распределение ресурса осуществляется по шагам: сначала выделяется некоторое количество ресурса одному предприятию, затем другому и т.д. Введем переменную – количество ресурса, выделенное -му предприятию (в динамическом программировании соответствует количеству ресурса, выделенному в -й момент времени или на -м шаге). Тогда прибыль, даваемая -м предприятием, составит . Количество ресурса, остающегося не распределенным к -му моменту времени, обозначим через . В результате вместо задачи (3.2.3) получим следующую задачу динамического программирования:

(3.2.4)

В такой постановке интерпретируются как управления, а – как значения параметра состояния системы.

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

Поиск по сайту: