4.2. динамическое программирование

4.2. динамическое программирование

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

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

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

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

Многие процессы с последовательным принятием решений описываются как комбинаторные задачи. Для примера рассмотрен процесс, состоящий из n этапов, в каждом из которых принимается К решений. Для каждого возможного решения, принимаемого на n-м этапе, имеется K возможных решений, принимаемых на (n — — 1)-м этапе, а для каждого возможного решения, принимаемого на (n — 1)-м этапе, существует КГ возможных решений, получаемых на (n — 2)-м этапе, и т.д. Таким образом, для определения оптимального решения должно быть проанализировано Kn возможных решений. Для получения оптимального результата по заданному критерию последовательно рассматривается каждый этап, для которого выбирается наилучшие из K решений. В результате на n этапах рассматривается nK возможных решений. Следовательно, динамическое программирование приводит к тем же результатам, что

nK n

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

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

Если предположить, что К = 3, n = 5, то комбинаторный подход требует для анализа Kn = 35 = 243 комбинации. Метод поэтапного расчета, применяемый в динамическом программировании, потребует анализа 15 комбинаций (3 х 5). Если К = 3, а n = 100, то комбинаторный подход потребует 3100 решений, тогда как, используя метод динамического программирования, необходимо проанализировать лишь 300 комбинаций (3 х 100).

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

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

4.2.2. Постановка и решение задачи оптимального распределения инвестиций

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

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

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

Межотраслевое распределение инвестиций должно сопровождаться распределением вложений внутри отрасли и, в частности, между предприятиями, выпускающими однородную продукцию. Критерием для оптимального распределения инвестиций могут служить максимальная прибыль, максимальный суммарный прирост продукции, максимальное снижение себестоимости, максимальная занятость населения и т.п.

Задача оптимального распределения инвестиций по своей природе комбинаторная. Например, при определении фондоотдачи от 10 млрд руб. в четыре отрасли промышленности необходимо перебрать все распределения числа 10 на четыре группы. При условии распределения только из целых чисел необходимо подсчитать 286 комбинаций: (10, 0, 0, 0); (9, 1, 0, 0); (9, 0, 1, 0); (9, 0, 0, 1) .;

(8, 1, 1, 0); (8, 1, 0, 1); (8, 0, 1, 1); (8, 2, 0, 0); (8, 0, 2, 0); (8, 0, 0, 2); (4, 3, 2, 1); ... (4, 2, 2, 2); ...

Если требуется дополнительно определить оптимальное решение задачи в случае, когда инвестиции в целом составляют 9, 8, 7, . 1 млрд руб., то необходимо провести большой объем вычислительной работы.

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

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

т.д.) между объектами формулируется следующим образом: найти

значения неизвестных x1, x2, ... xn, т.е. план распределения,

удовлетворяющий условиям:

І*; = K, (4.1)

xj > 0 (xj — целые числа), обращающие в максимум функцию

F„ (K) = if (*) — max, (4.2)

;=1

где xj — сумма возможных вложений по j-му объекту (отрасль, предприятие, цех, участок); f(x) — фондоотдача по предполагаемому j-му объекту, т.е. функция отдачи капитальных вложений (прибыль, прирост продукции и т.д.).

Алгоритм, предложенный Беллманом, справедлив для функций f(x) любого вида и является одним из простейших примеров применения динамического программирования. Идея алгоритма состоит в том, что последовательно решаются задачи оптимального распределения средств между первыми j объектами (здесь j принимает значения 1, 2, 3, n). Последняя из этих задач является решением поставленной.

В задаче по распределению средств между объектами всегда предполагаются известными значения функций fj(x) при всех возможных значениях аргументов (табл. 4.7).

Функция f(x) непрерывная в области определения от 0 до К. Функции принимают значение, соответствующее оптимальному распределению x (x = 1, 2, 3, К) средств между первыми j объектами, через ij.(x). Следовательно, известен столбец чисел Fj(1), Fj(2), ., Fj(K), а для каждого числа определен соответствующий план распределения ресурсов.

Для примера приведена задача оптимального распределения К средств между первыми (j + 1) объектами. Пусть на первые j объектов отводится x средств. Тогда на (j + 1)-й объект распределяются оставшиеся (К — x) средства. На первые j объектов x средств распределены оптимальным образом, т.е. определено значение Fj(x). Отсюда значение показателя качества распределения всех средств на первые (j + 1) объекты:

Fj + 1(K) = F(x) + / + 1(K 1). (4.3)

В зависимости от значения x функция принимает различную величину. Оптимальному распределению соответствует такая величина x, при которой выражение (4.3) принимает максимальное значение. Следовательно,

Fj + 1(K) = max {Fj(x) + / + -x)} (4.4) при 0 < x < К.

Столбцы чисел Fj(x) и Fj + 1(К —x) известны, поэтому можно легко определить значение функции Fj + 1(К —x). Решив последовательно К задач при различных значениях x (x = 1, 2, К), определяют столбец чисел Fj + Fj + 1(2); Fj + 1(К) и, соответственно, для каждого из этих чисел план распределения ресурсов. Таким образом, решена задача оптимального распределения числа средств от 1 до К между первыми ( j + 1) объектами. При j = 1 задача имеет простейшее решение, соответствующий столбец чисел F1(1); F1(2); F1(K) совпадает с первым столбцом табл. 4.4.

Решение задачи по оптимальному распределению К ресурсов между (j + 1) — здесь j = 1, 2, n — объектами состоит из (n — 1) однотипных циклов (этапов), в которых определяются значения F1(x), F2(x), ., Fn(x). Оптимальный план распределения средств на первый объект выражается в назначении на этот объект всех имеющихся средств, т.е. полагают

F1(x) = /1(x) (x = 0, 1, 2, К).

Этапы решения задачи следующие:

FX(K) = /1(x), F2(K) = max {/1(x) + /,(К —x)},

F3(K) = max {/2(x) + /3(К —x)},

Fn _ 1(K) = max{/ _ 2(x) + / _ X(K —x)},

Fn(K) = max / _ x(x) + /n(K —x)}.

В каждом цикле используют вычисленный в предыдущем цикле столбец Fj(x) и столбец Fj + 1(x) табл. 4.7. Цикл состоит из К однотипных подциклов, в каждом из которых фиксируют x (x = 1, 2, ., К) и определяют одно число столбца Fj + 1(x), а именно Fj + 1(К). При фиксированном значении аргумента в подцикле выполняют следующие операции:

образуют суммы

F(x) + /j + 1(К —x), x = (0, 1, 2, К)

и из них выбирают максимальную

F + 1(К) = max {F(x) + /j + 1(K —x)}, x = (0, 1, 2, K).

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

План распределения, соответствующий Fj(x), преобразуют в план распределения средств между первыми ( j + 1) объектами путем дополнительного назначения оставшихся (К — х) средств на (j + 1) объект.

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

Решение начинают с образования столбца чисел F1(x), поставив в соответствие план распределения x (x = 0, 1, 2, 3, 4, 5) средств на первый завод (см. табл. 4.9).

В первом цикле определяют столбец чисел F2(x) и соответствующие им оптимальные планы распределения средств на первые два завода.

Значение F2(1):

max [ J = max [ J = 2,5.

ji?(0) + /2(1)J [0 + 2[ '

Значение F2(3):

Значение F2(5):

I ад

max [

ад+/2(5) ад+/2(4) ад+/2(3) ад)+/2(2)

і ад+ад

Результаты вычислений представлены в табл. 4.10.

Во втором цикле определяют столбец чисел F3(x) и соответствующие им планы распределения средств на три завода. Результаты вычислений сведены в табл. 4.11.

Оптимальным является такое распределение лимита капитальных вложений (см. табл. 4.11), при котором первому заводу будет выделено 1 ед., второму — 2, третьему — 2. В этом случае обеспечивается максимум фондоотдачи — 11,5 усл. ед. Возможны случаи, когда использование определенного количества x средств на некоторых объектах j не допускается, т.е. f(x) = 0. Значения остальных неизвестных в плане распределения инвестиций по объектам находятся обычным способом при помощи функционального уравнения (4.4). Алгоритм динамического программирования обеспечивает нахождение оптимального решения задач с ограниченным использованием средств по некоторым объектам.

4.2.3. Определение кратчайшего пути передвижения транспорта между двумя пунктами

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

Для примера рассмотрена простейшая задача отыскания кратчайшего пути в сетевом графике, показывающем перевозку грузов от поставщика 1 к потребителю 6 (рис. 4.1). Решение этой задачи важно для маркетологов.

При комбинаторном подходе к решению задачи подсчитывают все возможные пути от узла 1 к узлу 6 и выбирают кратчайший путь (табл. 4.12).

Путь 1 имеет наименьшее расстояние (7 ед.). Метод динамического программирования в противоположность комбинаторному рассматривает минимальное расстояние передвижения от каждого из узлов до конечного узла.

Наименьшее расстояние между узлом 1 и 6 определяют за ряд этапов, в каждом из которых рассчитывают минимальное расстояние между конечным узлом 6 и 5, 6 и 4, 6 и 3 и т.д., кончая начальным узлом 1. Например, отправляясь от узла 4, можно достичь узла 6, двигаясь или по линии 4—6, или по линии 4—5—6. Для каждого пути расстояние передвижения одно и то же, а именно 6 ед. Значение вычисленного наименьшего расстояния передвижения от узла 4 к 6 используют для подсчета минимального пути передвижения от узлов 2 и 3 к 6 без применения комбинаторного метода. Рассчитывают расстояние с помощью функционального уравнения

f = min (tjj+fj), (4.5)

где ty — расстояние между узлами i и j;

fj — минимальное расстояние, необходимое для передвижения от узла i к конечному узлу j по допустимым маршрутам при использовании оптимальной стратегии.

Функциональные уравнения для узлов сетевого графика (см. рис. 4.2) имеют вид:

/6=0,

/5=min ((5-6+ /б ) = min (2 + 0 ) = 2,

/4 1^4-6 + /б J 16 + 0 J '

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