3.1. Задача производства и хранения продукции

Напомним, что проблема заключается в нахождении плана производства, который удовлетворяет потребности всех периодов с минимальными затратами (см. Главу 1). Математическая модель имеет вид

Рис. 3.1.

Любое допустимое решение задачи соответствует потоку в сети, изображенной на Рис. 3.1, где вершина 0 – источник, PT - стоимость единицы потока по дуге (0,t), HT - стоимость единичного потока по дуге (t, t+1), и стоимость запуска производства FT учитывается в случае положительного потока XT >0 по дуге (0,t).

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

Лемма 3.1.

1) Существует такое оптимальное решение, в котором ST-1XT=0 для всех T=1,…,N. (Запуск производства осуществляется только, когда запас нулевой.)

2) Существует такое оптимальное решение, в котором, если XT>0, то Для некоторого K ³ 0. (Если производство запущено в период T, то количество произведенного продукта Точно соответствует суммарным потребностям за некоторый период [t, t+k].

Доказательство. Предположим моменты запуска производства выбраны оптимально (известно какие дуги (0,t) имеют положительный потока). Так как в сети нет ограничений на пропускные способности дуг, положительные дуговые потоки в оптимальном решении формируют дерево. Следовательно, только одна из дуг, имеющих концевой вершину T, может иметь положительный поток. Значит ST-1XT=0. Отсюда следует также утверждение 2).¨

Обозначим Тогда и переменные S можно исключить. Целевая функция примет вид

Где

Пусть H(k) – минимальные затраты, связанные с удовлетворением потребностей периодов 1,...,k. Если T £ k - последний период, когда осуществлялось производство (то есть XT=dTk), то, очевидно, функционал H(t-1) также должен принимать минимальное значение. Это очевидное свойство позволяет записать Рекуррентные соотношения для прямого хода ДП:

(3.1)

Величина H(n) является оптимальным значением целевой функции исходной задачи. На последнем шаге прямого хода ДП находится условно-оптимальное значение последней переменной T(N), которое является оптимальным.

Обратный ход ДП восстанавливает оптимальное решение по условно-оптимальному T(K), в котором достаточно определить значение K. Так как T(N) Известно, полагаем K=T(N). Тогда T(K) – предпоследний момент, когда осуществлялось производство. Повторяя аналогичные операции, найдем оптимальные моменты запуска производства. Объемы производства и запасы в каждый период восстанавливаются однозначно.

Описанный алгоритм ДП является полиномиальным, его трудоемкость – O(n2). Приведем

Пример 3.2. Рассмотрим индивидуальную задачу с N=4, d=(2,4,5,1), p=(3,3,3,3), h=(1,2,1,1) и F=(12,20,16,8). Вычислим C=(8,7,5,4) И (d11 ,d12 ,d13 ,d14)=(2,6,11,12), а также значение константы .

Прямой ход. Применив рекуррентные соотношения (3.1), получим

H(0)=0.

H(1)=f1+c1d1=12+8×2=28.

H(2)=Min{H(0)+f1+c1d12,H(1)+f2+c2d2}=Min{12+8×6, 28+20+7×4}=

Min{60, 76}=60. T(2)=1.

H(3)=100. T(3)=1.

H(4)=106. T(4)=3.

Обратный ход. Из условно-оптимального решения T(4)=3 получаем y4=x4=0, y3=1, x3=d3+d4=6. Далее, так как T(2)=1, то y2=x2=0, y1=1, x1=d1+d2=6. Значит оптимальное решение x=(6,0,6,0), y=(1,0,1,0), s=(4,0,1,0), а минимальные затраты равны H(4) – =106 – 37=69.¨

Проблему производства и хранения продукции можно свести к задаче поиска кратчайшего пути в следующем графе. Пусть ориентированный граф задан вершинами {0,1,...,n} и дугами (i, j), i<j. Длина FI+1+cI+1DI+1,J дуги (i, j) равна стоимости запуска производства и производства продукции в период i+1 для удовлетворения потребностей периодов I+1,…,j. Для Примера 3.2 соответствующий граф изображен на Рис. 3.2.

Рис. 3.2.

H(k) есть длина кратчайшего пути из вершины 0 в вершину K, и так как граф ациклический, такой путь находится за O(n2) элементарных операций. На Рис. 3.2 кратчайший путь из 0 в 4 указан жирными линиями. Он имеет длину 106 и состоит из двух дуг (0,2) и (2,4). Следовательно, продукт, произведенный в первый период удовлетворяет потребности периодов 1 и 2, а продукт, произведенный в период 3, удовлетворяет потребности периодов 3 и 4.

< Предыдущая		Следующая >