Лекция №10. Динамическая модель задачи складирования
Постановка задачи: емкость склада ограничена некоторой величиной с. В каждом из n промежутков времени запасы могут пополняться с затратами n на единицу продукции и расходоваться с получением дохода n за единицу продукции, причем решение о пополнении или расходовании запасов принимается однократно в каждом промежутке времени. Определить оптимальную стратегию в управлении запасами из условия максимизации суммарной прибыли при заданном начальном уровне запасов.
Уточним постановку задачи. Возможны три варианта в очередности пополнения и расходования запасов в каждом из промежутков времени: 1 вариант – пополнение предшествует расходу; 2 вариант – расход предшествует пополнению и 3 вариант – очередность любая.
В 3 варианте выбор оптимальной стратегии означает не только определение размера пополнения и расхода, но и выбор оптимальной очередности в каждом из промежутков времени.
k = k-1 + x k – y k - уравнение состояния
Так как заданным является начальный уровень запасов на складе 0, процесс разворачивают от конца к началу, рекуррентные соотношения имеют вид:
Переменные xk и yk должны удовлетворять условиям неотрицательности:
xk 0 yk 0
Ограничения зависящие от варианта очередности:
1 вариант - k-1 + xk с , yk k-1 + xk
2 вариант - k-1 – yk + xk с , yk k-1
3 вариант - по обстановке 1 или 2.
Первое неравенство обусловлено емкостью склада, второе – условием, в соответствии с которым расходы не могут превышать наличные запасы. Расчеты (условная оптимизация) по рекуррентным соотношениям упрощается ввиду того, что максимизируется линейная функция, которая на каждом шаге может исследоваться лишь в угловых точках многоугольника ограничений.
Ограничения на управления представляют собой выпуклый четырехугольник и для условной оптимизации достаточно рассмотреть значения функции Z только в угловых точках.
1 вариант. k-1 + xk с , yk k-1 + xk
y
С (с -
k-1;
с)
B (0;
k-1)
D (с -
k-1;
0)
A (0; 0)
x
2 вариант. k-1 – yk + xk с , yk k-1
y
С*
(с;
k-1)
B (0;
k-1)
D (с -
k-1;
0)
A (0; 0)
x
Начальное состояние 0 задано, условную оптимизацию разворачиваем от конца к началу
(В)
(С)
(A)
(B)
(C)
(D)
Если использовать случай (3), то к рассматриваемым добавляется точка С*.
