Глава 2. Основные примеры решения задач

Опыт показывает, что проще всего понять, что такое динамическое программирование, не из определения, а на основе примеров его использования; к ним мы и переходим.

2.1. Задача «Оптимальное управление поставками сырья»

Для ритмичной работы предприятия необходимо систематическое пополнение запаса сырья С, расходуемого при производстве продукции. Потребность в сырье С по месяцам рассматриваемого планового периода выражается числами 150, 50, 100 и 100 ед. Пополнение запаса производится партиями, кратными 50 ед. На начало планового периода на складах предприятия имеется запас сырья в 100 ед. Складские помещения не позволяют хранить одновременно более 300 ед. сырья. К концу планового периода весь запас должен быть израсходован, поскольку предприятие переходит на выпуск новой продукции, для которой сырье С не потребуется. Затраты на пополнение запаса зависят от объема х партии поставки и вписываются функцией Р{х), заданной табл. 10.21. Затраты за хранение сырья зависят от среднего уровня запаса сырья в данном месяце, определяемого по формуле , где D — объем потребления сырья в данном месяце, j — остаток сырья к концу этого месяца. Затраты на хранение описываются функцией , заданной табл. 10.22.

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

Функциональные уравнения Беллмана для рассматриваемой задачи имеют следующий вид:

для п = 1

Если в условии поставленной задачи нумерация месяцев планового периода осуществляется в прямом направлении: от начала периода к его концу, т. е. t = 1, 2, 3, 4, то в уравнениях (10.23), (10.24) используется, как это принято в динамическом программировании, встречная нумерация: от конца к началу, т.е. n = 1, 2, 3, 4. В уравнениях (10.23), (10.24) i — уровень запаса сырья на начало месяца; х — объем партии поставки сырья; d_n — объем потребления сырья в n -м месяце; М — вместимость складских помещений предприятия; f_n(i) — минимальные суммарные затраты на пополнение и хранение сырья за последние n месяцев планового периода при уровне запаса на начало n -го месяца в i ед.; i + х – d_n — уровень запаса сырья на конец n- го месяца (одновременно это и уровень запаса сырья на начало (n-1) -го месяца).

В уравнении (10.24) первое слагаемое в правой части характеризует затраты в n- м месяце на пополнение запаса сырья в объеме х ед., второе — затраты на хранение сырья в этом месяце, если средний уровень запаса составляет (d_n/2+(i + x – d_n)) ед., третье — минимальные суммарные затраты на пополнение и хранение сырья за n-1 последних месяцев планового периода.

Используем функциональные уравнения (10.23), (10.24) для решения поставленной задачи.

Пусть n = 1. Функциональное уравнение (10.23) примет вид

(10.25)

где i — уровень запаса сырья на начало последнего месяца (первого от конца) — может принимать значения 0, 50 или 100, а х будет равняться 100, 50 или 0 соответственно, что и записано в первых двух столбцах табл. 10.23. В последнем столбце в соответствии с уравнением (10.25) приведены суммарные минимальные затраты на пополнение запаса (см. табл. 10.21) и его хранение (см. табл. 10.22).

Переходим к анализу периода, состоящего из двух последних месяцев. Полагая в уравнении (10.24) n=2, получаем соответствующее этому периоду функциональное уравнение Беллмана

(10.26)

Уровень i запаса сырья на начало второго (от конца) месяца может составлять 0, 50, 100, 150 или 200 ед., а объем х — поставки сырья соответственно 200, 150, 100, 50 или 0 ед. (табл. 10.24).

В клетки основного поля таблицы будем вписывать значения суммы трех слагаемых: и f₁ (см. уравнение (10.26)). Первое слагаемое находим по табл. 10.21, второе - по табл. 10.22, а третье берем из последнего столбца табл. 10.23. Некоторые клетки таблицы останутся незаполненными, так как соответствуют недопустимым сочетаниям i и х. Рассмотрим, например, первую строку табл. 10.24. Она соответствует нулевому уровню запаса сырья на начало второго (от конца) месяца. Поскольку в этом месяце потребуется 100 ед. сырья, то первой заполняемой будет клетка, соответствующая поставке в 100 ед. При этом первое слагаемое P₂(100)=40, второе (50) = 8, а третье f₁(0) = 48.

Аналогично заполняются и две следующие клетки. Сравнивая суммарные затраты по заполненным клеткам (96, 118 и 73), заключаем, что в рассматриваемой ситуации (i=0) оптимальной во втором месяце будет поставка в 200 ед., ибо ей соответствуют минимальные суммарные затраты в 73 ден. ед. Аналогичным образом заполняются и остальные строки таблицы.

Функциональное уравнение для n=3 имеет вид

а результаты анализа приемлемых вариантов приведены в табл. 10.25.

Последнему шагу оптимизационного анализа (п = 4) соответствует функциональное уравнение

а результаты помещены в табл. 10.26.

Теперь можно подвести окончательные итоги. Из табл. 10.26 видно, что в четвертом (от конца) месяце оптимальной будет поставка ед. С учетом начального запаса (см. условие задачи) в 100 ед. общий запас в четвертом месяце составит 200 ед. В этом месяце для нужд производства потребуется 150 ед. сырья, так что к началу третьего месяца уровень запаса будет равен 50 ед. Обращаясь к табл. 10.25 (см. вторую строку, отвечающую i=50), замечаем, что такому уровню соответствует поставка ед. Имеющийся запас в 50 ед. будет полностью израсходован в этом месяце, так что к началу второго месяца уровень запаса i=0. Судя по первой строке (i=0) табл. 10.24, во втором месяце необходимо поставить предприятию 200 ед. сырья (). Из них 100 ед. будет израсходовано в этом месяце, а 100 ед. останется на первый месяц; их будет достаточно для удовлетворения потребности производства в этом месяце. Подтверждением тому служат данные, приведенные в табл. 10.23, из последней строки которой ясно, что в первом месяце сырья приобретать не придется ().

Итак, суммарные затраты предприятия на пополнение и хранение запаса сырья будут минимальными и составят 152 ден. ед., если в первом месяце будет приобретено 100 ед. сырья, а в третьем — 200 ед. Во втором и четвертом месяцах пополнять запас не придется.