ДИНАМИЧЕСКАЯ ЗАДАЧА УПРАВЛЕНИЯ ПРОИЗВОДСТВОМ И ЗАПАСАМИ. Рассмотрим трехэтапную систему управления запасами с дискретной продукцией и динамическим детерминированным спросом.
Пусть спрос заявки потребителей на нашу продукцию составляют на первый этап d13 единицы, на второй d22, на третий - d33 единицы.
К началу первого этапа на складе имеется 3 единицы продукции, т.е. начальный уровень запаса равен y13. Затраты на хранение единицы продукции на разных этапах различны и составляют соответственно h14, h23, h32. Затраты на производство xj единиц продукции на j-м этапе определяются функцией jxj xj2 2xj 2 т.е. а1 b5 с2. Требуется указать, сколько единиц продукции на отдельных этапах следует производить, чтобы заявки потребителей были удовлетворены, а наши общие затраты на производство и хранение за все три этапа были наименьшими.
Исходные данные задачи можно кратко записать одной строкой d1d2d3abch1h2h3y13231224323Воспользовавш ись рекуррентными соотношениями, последовательно вычисляем F1 y2, F2 y3, Fk yk1, и соответственно находим y2, y3 , k yk1, Положим k 1. Параметр состояния у2 может принимать целые значения на отрезке 0 у2 d2 d3 0 y2 2 3 т.е. у2 0, 1, 2, 3, 4, 5. Каждому значению параметра состояния должна отвечать определенная область изменения переменной x1, характеризуемая условием 0 х1 d1 у2 или 0 х1 3 у2 Из балансового уравнения х1 у1 - d1 у2 непосредственно следует, что объем производства связан со значением параметра состояния у2 соотношением x1 y2 d1 - y1 y2 3 - 3 y2 В этом и состоит особенность первого этапа.
Если задан уровень запаса к началу первого этапа, то каждому значению у2 отвечает единственное значение х1 и потому F1 y2 1 x1, y2 Придавая у2 различные целые значения от 0 до 6 и учитывая предыдущее соотношение, находим y2 0, x1 0, 1 00 02 20 2 40 2 y2 1, x1 1, 1 11 12 22 2 41 11 y2 2, x1 2, 1 22 22 22 2 42 18 y2 3, x1 3, 1 33 32 23 2 43 29 y2 4, x1 4, 1 44 42 24 2 44 42 y2 5, x1 5, 1 55 52 25 2 45 57 Значения функции состояния F1 представлены в табл. 1 Таблица 1 y2012345F1 y221118294257x1y2012345Переходим ко второму этапу.
Полагаем k 2 и табулируем функцию F2 y3 Здесь минимум берется по единственной переменной х2, которая может изменяться в пределах 0 x2 d2 y3 или 0 x2 2 y3 1 где верхняя граница зависит от параметра состояния у3, который принимает значения на отрезке 0 y3 d3 , т.е. 0 y3 3 а аргумент у2 связан с х2 и у3 балансовым уравнением x2 y2 - d2 y3 откуда следует y2 y3 d2 - x2 y3 2 - x2 2 Придавая параметру состояния различные значения от 0 до 3, будем последовательно вычислять 2 x2 а затем определять F2 и. Положим у3 0. Тогда, согласно 1, 0 x2 2, т.е. переменная х2 может принимать значения 0, 1, 2, а каждому значению х2 отвечает определенное значение у2, вычисляемое по формуле 2 у2 2 - х2 Последовательно находим если x2 0, то у2 2 , 2 0,2 02 20 2 F12 2 18 20, x2 1, y2 2 - 1 1, 2 1,2 12 51 2 F11 8 11 19, x2 2, y2 2 - 2 0, 2 2,2 22 52 2 F10 16 2 18, Наименьшее из полученных значений 2 есть F2 0, т.е. F2 y3 0 18, причем минимум достигается при значении х2, равном y3 0 2 Положим у3 1. Тогда, согласно 1, 0 x2 3, т.е. переменная х2 может принимать значения 0, 1, 2, 3, а каждому значению х2 отвечает определенное значение у2, вычисляемое по формуле 2 у2 3 - х2 Последовательно находим если x2 0, то y2 3-0 3, 2 0,1 02 20 2 31 F13 5 29 34, x2 1, y2 3-1 2, 2 1,2 12 21 2 31 F12 8 18 26, x2 2, y2 3-2 1, 2 2,1 22 22 2 31 F11 13 11 24, x2 3, y2 3-3 0, 2 3,1 32 23 2 31 F10 20 2 22, Наименьшее из полученных значений 2 есть F2 1, т.е. F2 y3 1 min 2 x2,1 22, причем минимум достигается при значении х2, равном y3 1 3 Положим у3 2. Тогда, согласно 1, 0 x2 4, т.е. переменная х2 может принимать значения 0, 1, 2, 3, 4, а каждому значению х2 отвечает определенное значение у2, вычисляемое по формуле 2 у2 4 - х2 если x2 0, то y2 4-0 4, 2 0,2 02 20 2 32 F14 8 42 50, x2 1, y2 4-1 3, 2 1,2 12 21 2 32 F13 11 29 40, x2 2, y2 4-2 2, 2 2,2 22 22 2 32 F12 16 18 34, x2 3, y2 4-3 1, 2 3,2 32 23 2 32 F11 23 11 34, x2 4, y2 4-4 0, 2 4,2 42 24 2 32 F10 32 2 40. Наименьшее из полученных значений 2 есть F2 2, т.е. F2 y3 2 min 2 x2,2 min 64, 55, 50, 49, 52 49, x2 причем минимум достигается при значении х2, равном y3 2 3 Положим у3 3. Тогда, согласно 1, 0 x2 5, т.е. переменная х2 может принимать значения 0, 1, 2, 3, 4, 5, а каждому значению х2 отвечает определенное значение у2, вычисляемое по формуле 2 у2 5 - х2 если x2 0, то y2 5-0 5, 2 0,3 02 20 2 33 F15 11 57 68, x2 1, y2 5-1 4, 2 1,3 12 21 2 33 F14 14 42 56, x2 2, y2 5-2 3, 2 2,3 22 22 2 33 F13 19 29 48, x2 3, y2 5-3 2, 2 3,3 32 23 2 33 F12 26 18 44, x2 4, y2 5-4 1, 2 4,3 42 24 2 33 F11 35 11 46. x2 5, y2 5-4 0, 2 5,3 52 25 2 33 F10 46 2 48. Наименьшее из полученных значений 2 есть F2 3, т.е. F2 y3 3 min 2 x2,3 44, причем минимум достигается при значении х2, равном y3 3 3 Результаты табулирования функции F2 y3сведены в табл. 2. Таблица 2 у30123F2 y3 y3232 или 33 Переходим к следующему этапу.
Полагаем k3 и табулируем функцию F3 y4 Вычисляем значение функции состояния только для одного значения аргумента у4 0, так как не хотим оставлять продукцию в запас в конце исследуемого периода. 0y40 y4 0 x3 d3 y4 0 x3 3 y3 y4 d3-x3 y43- x3 3x3, y4 bx3 c h3y4 F2y3 2 x32 2 y4 F2y3 x30 y33 30002 20 2 20 F232 4446 x31 y32 31012 21 220 F225 3439 x32 y31 32022 22 220 F21102232 x33 y30 33032 23 220 F2017 1835 Получаем F3 y4 min 3 x3,0 32, причем минимум достигается при y4 0 2. Таким образом, мы получили не только минимальные общие затраты на производство и хранение продукции, но и последнюю компоненту оптимального решения.
Она равна 2. Остальные компоненты оптимального решения найдем по обычным правилам метода динамического программирования.
Чтобы найти предпоследнюю компоненту, учтем, что х3 у3 - -d3 y4 или 2 у3 - 3 0, oткуда у3 1. Из таблицы 2 значений находим Аналогично, продолжая двигаться в обратном направлении и учтя, что х2 у2 - d2 y3 или 3 у2 - 2 1, получаем у2 0 из таблицы 1 значений х1 находим. Итак, оптимальный план производства имеет вид х1 0, х2 3, х3 2, а минимальные общие затраты составляют 32 единицы.
Полезна самопроверка полученного результата.
Для этого по исходным данным и найденному плану производства заполняем таблицу 5 и убеждаемся, что заявки потребителей на каждом этапе выполняются у1 х1 d1 у2 х2 d2 у3 х3 d3 3 0 3 0 3 2 1 2 3 и что суммарный объем производства и имевшегося к началу первого этапа запаса продукции равен суммарной потребности у1 х1 х2 х3 d1 d2 d3 3 0 3 2 3 2 3 причем это достигается при наименьших возможных затратах на производство и хранение продукции х1 х2 х3 h1у2 h2у3 F3y40 2 17 10 0 3 32 Самопроверка результатов ЭтапыянварьфевральмартИтого за 3 месяцаИмеем продукции к началу месяца, шт.у1 3у2 0у3 1у1 3Производим в течение месяца, шт.х1 0х2 3х3 2х1 х2 х3 5Отпускаем заказчикам, шт.d1 3d2 2d3 3d1 d2 d3 8Остаток к концу месяца храним в течение текущего месяца, шт.у2 0у3 1у4 0Затраты на производство, руб.х12х217х310х1 х2 х3 29Затраты на хранение, руб.h1у2 0h2у3 30h1у2 h2у3 3