Исследование операций. М. Вильямс, 2001 2 Общие идеи и принципы
 Скачать 1.79 Mb.
|
|
Детерминированные модели управления запасами [Х. Таха. Введение в исследование операций. М.: «Вильямс», 2001] 2 Нужно минимизировать функцию затрат Суммарные затраты Затраты на приобретение Затраты на оформление Затраты на хранение Потери от дефицита 4 Расшифровка затрат Затраты на приобретение • Определяются стоимостью единицы приобретаемой продукции. Стоимость может быть постоянной или со скидкой. Затраты на оформление • Постоянные расходы, связанные с размещением заказа (для изготовления продукции). Не зависят от размера заказа. Затраты на хранение • Затраты на содержание запаса на складе. Включают процент на инвестиции, прямые складские затраты. Потери от дефицита • Расходы, обусловленные отсутствием запаса необходимой продукции. 5 Классическая задача размера запаса 6 Постановка задачи • Обозначения: – 𝑦 – объем заказа (в единицах продукции); – 𝐷 – интенсивность спроса (единицы продукции в единицу времени); – 𝑡 0 – продолжительность цикла заказа (единицы времени). • Продолжительность цикла заказа: – 𝑡 0 = Τ 𝑦 𝐷 • Дополнительные параметры: – 𝐾 – затраты на оформление; – ℎ – затраты на хранение. • Средний уровень запаса равен Τ 𝑦 2 единиц. • Суммарные затраты в единицу времени 𝑇𝐶𝑈(𝑦) = затраты на оформление в единицу времени + затраты на хранение в единицу времени 7 Решение задачи • 𝑇𝐶𝑈 𝑦 = затраты на оформление+затраты на хранение за цикл 𝑡 0 𝑡 0 • 𝑇𝐶𝑈 𝑦 = 𝐾+ℎ 𝑦 2 𝑡 0 𝑡 0 = 𝐾 ൗ 𝑦 𝐷 + ℎ 𝑦 2 • Для нахождения оптимального значения минимизируем функцию по 𝑦 путем нахождения необходимого условия минимума: 𝜕𝑇𝐶𝑈(𝑦) 𝜕𝑦 = − 𝐾𝐷 𝑦 2 + ℎ 2 = 0. • Решение уравнения дает оптимальный размер заказа: 𝑦 ∗ = 2𝐾𝐷 ℎ • Оптимальное решение формулируется так: – Заказывать 𝑦 ∗ = 2𝐾𝐷 ℎ единиц продукции через каждые 𝑡 0 = ൗ 𝑦 ∗ 𝐷 единиц времени. 8 Наличие реального срока исполнения заказа • Пусть существует реальный срок выполнения заказа 𝐿 (в единицах времени). – Тогда точка возобновления заказа имеет место, когда уровень заказа опускается до 𝐿𝐷 единиц. 9 Время Уровень запаса Средний запас Точки возобновления запаса 𝑦 ∗ 𝐿 𝐿 Пример задачи размещения заказа • В университетском городке горят и перегорают неоновые лампы. • Лампы заказываются с определенной периодичностью. – Лампы заменяются по 100 штук в день. – Стоимость размещения заказа =$100. – Стоимость хранения одной лампы = $0.02 в день. – Срок выполнения заказа от размещения до поставки = 12 дней. • Получается: 𝐷 = 100; 𝐾 = 100; ℎ = 0.02; 𝐿 = 12. • Следовательно: 𝑦 ∗ = 2𝐾𝐷 ℎ = 2 × 100 × 100 0.02 = 1000. • Так как срок выполнения заказа 12 дней, то необходимо вычислить число целых циклов. • Точка возобновления заказа = 200 ламп. • Оптимальная стратегия: – Заказать 1000 ламп, как только уровень их запаса уменьшается до 200 единиц. • Дневные расходы: 𝑇𝐶𝑈 𝑦 = 𝐾 ൗ 𝑦 𝐷 + ℎ 𝑦 2 = 100 ൗ 1000 100 + 0.02 1000 2 = 20 долларов в день. 10 Задача размера заказа с разрывами цен 11 Постановка задачи • Суть: – Продукция может быть приобретена со скидкой, если закупается большая партия: 𝑐 = ቊ 𝑐 1 , если 𝑦 ≤ 𝑞; 𝑐 2 , если 𝑦 > 𝑞, где 𝑐 1 > 𝑐 2 • Следовательно: – Затраты на приобретение продукции в единицу времени: = 𝑐 1 𝑦 𝑡 0 = 𝑐 1 𝑦 ൗ 𝑦 𝐷 = 𝐷𝑐 1 , 𝑦 ≤ 𝑞; 𝑐 2 𝑦 𝑡 0 = 𝑐 2 𝑦 ൗ 𝑦 𝐷 = 𝐷𝑐 2 , 𝑦 > 𝑞. – Используя предыдущие обозначения: 𝑇𝐶𝑈 𝑦 = 𝑇𝐶𝑈 1 𝑦 = 𝐷𝑐 1 + 𝐾𝐷 𝑦 + ℎ 2 𝑦, 𝑦 ≤ 𝑞; 𝑇𝐶𝑈 2 𝑦 = 𝐷𝑐 2 + 𝐾𝐷 𝑦 + ℎ 2 𝑦, 𝑦 > 𝑞. 12 Графики функций затрат • График функции затрат 𝑇𝐶𝑈(𝑦), если идти от минимальных значений аргументов, совпадает с графиком функции 𝑇𝐶𝑈 1 𝑦 до точки 𝑦 = 𝑞, в которой меняется цена продукции, а затем совпадает с графиком функции 𝑇𝐶𝑈 2 𝑦 . • Определение оптимального объема заказа 𝑦 ∗ зависит от того, где находится точка разрыва цены 𝑞 по отношению к указанным на рисунке зонам I, II и III, которые определены как интервалы 0, 𝑦 𝑚 , 𝑦 𝑚 , 𝑄 и 𝑄, ∞ соответственно. • Функции отличаются на постоянную величину 13 I II III 𝑦 𝑚 𝑄 Затраты 𝑦 𝑇𝐶𝑈 1 𝑇𝐶𝑈 2 Решение задачи • Величина 𝑄 (𝑄 > 𝑦 𝑚 ) определяется из уравнения 𝑇𝐶𝑈 2 𝑄 = 𝑇𝐶𝑈 1 𝑦 𝑚 𝑐 2 𝐷 + 𝐾𝐷 𝑄 + ℎ𝑄 2 = 𝑇𝐶𝑈 1 𝑦 𝑚 • Получаем квадратное уравнение: 𝑄 2 + 2 𝑐 2 𝐷 − 𝑇𝐶𝑈 1 𝑦 𝑚 ℎ 𝑄 + 2𝐾𝐷 ℎ = 0. • Оптимальное решение определяется как: 𝑦 ∗ = ቊ 𝑦 𝑚 , если 𝑞 находится в зонах I или III, 𝑞, если 𝑞 находится в зоне II. 14 Три случая оптимального решения • Случай 1: – 𝑞 в зоне I; – 𝑦 ∗ = 𝑦 𝑚 • Случай 3: – 𝑞 в зоне IISI; – 𝑦 ∗ = 𝑦 𝑚 15 • Случай 2: – 𝑞 в зоне II; – 𝑦 ∗ = 𝑞 Затраты 𝑦 𝑇𝐶𝑈 1 𝑦 𝑇𝐶𝑈 2 𝑦 Min 𝑞 𝑦 𝑚 𝑄 Затраты 𝑦 𝑇𝐶𝑈 1 𝑦 𝑇𝐶𝑈 2 𝑦 Min 𝑞 𝑦 𝑚 𝑄 Затраты 𝑦 𝑇𝐶𝑈 1 𝑦 𝑇𝐶𝑈 2 𝑦 Min 𝑞 𝑦 𝑚 𝑄 Пример задачи с разрывами цен • Автомобильная мастерская по замене масла. – Покупает масло по $3 за галлон. – Цена может быть снижена до $2.5 за галлон, если покупается более 1000 галлонов. – За день обслуживается 150 автомобилей, каждый требует 1.25 галлона масла. – Хранение обходится в $0.02 в день за один галлон. – Стоимость размещения заказа $20. – Срок выполнения заказа 2 дня. • Дневное потребление масла – 𝐷 = 150 × 1.25 = 187.5 галлонов в день. 16 Решение примера • 𝐷 = 187.5 • ℎ = $0.02 • 𝐾 = $20 • 𝐿 = 2 • 𝑐 1 = $3 • 𝑐 2 = $2.5 • 𝑞 = 1000. • Этап 1. – 𝑦 𝑚 = 2𝐾𝐷 ℎ = 2×20×187.5 0.02 = 612.37 < 1000 галлонов. • Этап 2. Вычисляем 𝑄. – 𝑇𝐶𝑈 1 𝑦 𝑚 = 𝑐 1 𝐷 + 𝑦 𝑚 + ℎ𝑦 𝑚 2 = = 3 × 187.5 + 20 × 187.5 612.37 + 0.02 × 612.37 2 = 574.75. • Уравнение для 𝑄 имеет вид – 𝑄 2 + 2× 2.5+187.5−574.75 0.02 𝑄 + 2×20×187.5 0.02 = 0 или 𝑄 2 + 10 599.74𝑄 + 375 000 = 0. • Решение уравнения: 𝑄 = 10564.5 > 𝑦 𝑚 17 Решение примера • 𝐷 = 187.5 • ℎ = $0.02 • 𝐾 = $20 • 𝐿 = 2 • 𝑐 1 = $3 • 𝑐 2 = $2.5 • 𝑞 = 1000. • Зона II: 612.37; 10564.5 • Зона III: 10564.5; ∞ • Поскольку 𝑞 = 1000 находится в зоне II: Оптимальный объем заказа равен 𝑦 ∗ = 𝑞 = 1000. • При заданном сроке выполнения заказа в 2 дня точкой возобновления заказа является 2𝐷 = 2 × 187.5 = 375 галлонов. • Оптимальная стратегия: – Заказать 1000 галлонов масла, когда уровень запаса понижается до 375 галлонов. 18 Затраты 𝑦 𝑇𝐶𝑈 1 𝑦 𝑇𝐶𝑈 2 𝑦 Min 𝑞 𝑦 𝑚 𝑄 Многопродуктовая статическая модель с ограниченной вместимостью склада Рассматриваем задачу управления запасами различных товаров, которые хранятся на складе ограниченной вместимости 19 Общие понятия и обозначения • Характер изменения запаса каждого вида характеризуется известным графиком Для товара 𝒊, 𝒊 = 𝟏, … , 𝒏 𝐷 𝑖 Интенсивность спроса 𝐾 𝑖 Стоимость размещения заказа ℎ 𝑖 Стоимость хранения единицы товара в единицу времени 𝑦 𝑖 Объем заказа 𝑎 𝑖 Необходимое пространство для хранения единицы товара 𝐴 Максимальное складское пространство 20 Время Уровень запаса Средний запас Точки возобновления запаса 𝑦 ∗ 𝐿 𝐿 Математическая модель при отсутствии дефицита • Имеет следующий вид: min 𝑇𝐶𝑈 𝑦 1 , … , 𝑦 𝑛 = 𝑖=1 𝑛 𝐾 𝑖 𝐷 𝑖 𝑦 𝑖 + ℎ 𝑖 𝑦 𝑖 2 при ограничениях: 𝑖=1 𝑛 𝑎 𝑖 𝑦 𝑖 ≤ 𝐴; 𝑦 𝑖 ≥ 0, 𝑖 = 1,2, … , 𝑛. 21 Алгоритм решения задачи 1. Вычисляются оптимальные объемы заказов без учета ограничения по вместимости склада: 𝑦 𝑖 ∗ = 2𝐾 𝑖 𝐷 𝑖 ℎ 𝑖 , 𝑖 = 1, … , 𝑛. 2. Осуществляется проверка, удовлетворяют ли найденные значения 𝑦 𝑖 ∗ ограничению по вместимости склада. • Если удовлетворяют, то найдены оптимальные значения и вычисления заканчиваются. • В противном случае – переход к п. 3. Ограничение по вместимости склада должно удовлетворяться в форме равенства. • Используется метод множителей Лагранжа для определения оптимальных объемов заказа. 22 Построение функции Лагранжа на шаге 3 • Функция Лагранжа: 𝐿 𝜆, 𝑦 1 , … , 𝑦 𝑛 = 𝑇𝐶𝑈 𝑦 1 , … , 𝑦 𝑛 − 𝜆 𝑖=1 𝑛 𝑎 𝑖 𝑦 𝑖 − 𝐴 = = 𝑖=1 𝑛 𝐾 𝑖 𝐷 𝑖 𝑦 𝑖 + ℎ 𝑖 𝑦 𝑖 2 − 𝜆 𝑖=1 𝑛 𝑎 𝑖 𝑦 𝑖 − 𝐴 . • Здесь 𝜆 < 0 – множитель Лагранжа. 23 Нахождение значения • Так как функция Лагранжа является выпуклой, то 𝑦 𝑖 и 𝜆 находятся из уравнений: 𝜕𝐿 𝜕𝑦 𝑖 = − 𝐾 𝑖 𝐷 𝑖 𝑦 𝑖 2 + ℎ 𝑖 2 − 𝜆𝑎 𝑖 = 0 𝜕𝐿 𝜕𝜆 = − 𝑖=1 𝑛 𝑎 𝑖 𝑦 𝑖 + 𝐴 = 0 • Второе уравнение показывает, что ограничение по вместимости склада в оптимальной точке должно удовлетворяться в форме равенства • Из первого уравнения следует, что 𝑦 𝑖 ∗ = 2𝐾 𝑖 𝐷 𝑖 ℎ 𝑖 − 2𝜆 ∗ 𝑎 𝑖 • Формула показывает, что 𝑦 𝑖 ∗ зависит от оптимального значения 𝜆 ∗ множителя Лагранжа. • При 𝜆 ∗ = 0 значение 𝑦 𝑖 ∗ является решением задачи без ограничения. • Значение 𝜆 ∗ может быть найдено: – Последовательно уменьшаем 𝜆 на достаточно малую величину и используем её в данной формуле для вычисления соответствующего значения 𝑦 𝑖 ∗ . Искомое значение 𝜆 ∗ приводит к значениям 𝑦 𝑖 ∗ , 𝑖 = 1, … , 𝑛, которые удовлетворяют ограничению по вместимости склада в форме равенства. 24 Пример задачи управления запасами • Данные представлены в следующей таблице. • Уменьшаем 𝜆 с шагом 0.1: • Ограничение по вместимости в форме равенства выполняется в интервале −0.4 < 𝜆 < −0.3. • Используем какой-нибудь метод, получаем 𝜆 ∗ = −0.345. • Это дает: 𝑦 𝑖 ∗ = 6.35; 𝑦 2 ∗ = 7.11; 𝑦 3 ∗ = 11.6. 25 Товар 𝒊 𝑲 𝒊 $ 𝑫 𝒊 (ед. в день) 𝒉 𝒊 $ 𝒂 𝒊 (кв. футов) 1 10 2 0.3 1 2 5 4 0.1 1 3 15 4 0.2 1 Общая площадь склада = 25 кв. футов 𝝀 𝒚 𝟏 𝒚 𝟐 𝒚 𝟑 𝒊=𝟏 𝟑 𝒂 𝒊 𝒚 𝒊 − 𝑨 0 11.5 20.0 24.5 +31.0 -0.1 8.9 11.5 17.3 +12.7 -0.2 7.6 8.9 14.1 +5.6 -0.3 6.7 7.6 12.2 +1.5 -0.4 6.0 6.7 11.0 -1.3 Динамические задачи экономичного размера заказа 1) Уровень запаса контролируется периодически на протяжении конечного числа одинаковых периодов 2) Объем спроса является детерминированным, но он может меняться. 26 27 Уровень запаса контролируется периодически на протяжении конечного числа одинаковых периодов Объем спроса является детерминированным, но он может меняться. Особенности динамических запасов Пример: модели 1 и 2 (планирование потребностей ресурсов) • Пусть на протяжении года квартальный спрос на продукцию равен 100 и 150 единиц соответственно. • Поставки реализуются в конце каждого квартала. • Срок выполнения заказа равен 2 месяца и 1 месяц соответственно. • Для изготовления каждой единицы обеих моделей требуются 2 единицы комплектующих 𝑆, срок изготовления которых равен одному месяцу. 28 Планирование потребностей ресурсов Без учета стоимости размещения заказа С учетом стоимости размещения заказа 29 0 1 2 3 4 5 6 7 8 9 10 11 12 𝑀1 𝑆 100 100 100 100 100 100 100 100 200 200 200 200 200 200 200 200 0 1 2 3 4 5 6 7 8 9 10 11 12 𝑀2 𝑆 150 150 150 150 150 150 150 150 300 300 300 300 300 300 300 300 0 1 2 3 4 5 6 7 8 9 10 11 12 200 200 200 200 300 300 300 300 Комбинированные требования на комплектующие Пример. Временной график. 12 1 2 3 4 5 6 7 8 9 10 11 12 M1 (выпуск) 100 100 100 100 М1 (начало) 100 100 100 100 S(M1) (исп) 200 200 200 200 S(M1) (нач) 200 200 200 200 M2 (выпуск) 150 150 150 150 М2 (начало) 150 150 150 150 S(M2) (исп) 300 300 300 300 S(M2) (нач) 300 300 300 300 S(.) (исп) 200 300 200 300 200 300 200 300 S(.) (нач) 200 300 200 300 200 300 200 300 30 • Квартальный спрос на продукцию равен 100 и 150 единиц соответственно. • Поставки реализуются в конце каждого квартала. • Срок выполнения заказа равен 2 месяца и 1 месяц соответственно. • Для изготовления каждой единицы обоих моделей требуются 2 единицы комплектующих 𝑆, срок изготовления которых равен одному месяцу. Динамическая модель при отсутствии затрат на оформление заказа 31 Общие тезисы • Рассматривается задача календарного планирования производства, рассчитанная на 𝑛 одинаковых периодов. • Возможные объемы производства ограничены, но могут включать уровни (сверхурочные). • Если продукция производится для будущих периодов, то есть затраты на хранение. • Основные предположения модели: • Отсутствие затрат на оформление в любой период планирования • Отсутствие (недопустимость) дефицита • Стоимость производства единица продукции либо постоянна, либо имеет возрастающие предельные затраты (то есть, выпукла) • Стоимость хранения является постоянной величиной 32 Объем производства Затраты I II III IV Общий метод решения • Данную задачу можно сформулировать в виде транспортной задачи: – 𝑘𝑛 пунктов производства (𝑘 – количество возможных уровней производства) – 𝑛 потребителей • Производственные возможности каждого из 𝑘𝑛 пунктов производства определяют объемы поставок. • Объемы потребления определяются объемом спроса для каждого периода. • Себестоимость перевозки определяется суммой затрат используемого производственного процесса и стоимости хранения единицы продукции. • Оптимальное решение определит объемы производства продукции для каждого производственного уровня (минимизирующие суммарные затраты на производство и хранение) 33 Формулирование как транспортной задачи Термины транспортной задачи Термины задачи планирования запасов 𝑘𝑛 пунктов производства (𝑘 – количество возможных уровней производства) Производственные возможности каждого из 𝑘𝑛 пунктов производства определяют объемы поставок 𝑛 потребителей Объемы потребления определяются объемом спроса для каждого периода. Себестоимость перевозки от поставщика к потребителю. Сумма затрат используемого производственного процесса и стоимости хранения единицы продукции. Оптимальное решение Объемы производства продукции для каждого производственного уровня (минимизирующие суммарные затраты на производство и хранение) 34 Пример: задача с каминами • Компания производит специальные вытяжки, которые используются с декабря по март. • Спрос на продукцию сезонный. • Компания предпочитает сверхурочные • Стоимость производства единицы: $6 в обычном режиме; $9 при сверхурочных • Стоимость хранения = $0.10 в месяц за единицу • Для гарантии наличия допустимого решения при отсутствии дефицита требуется, чтобы суммарное предложение продукции (возможности производства) к началу каждого месяца по меньшей мере равнялось суммарному спросу. 35 Месяц Обычный режим работы (ед) Сверхурочные (ед) Спрос (ед) 1 90 50 100 2 100 60 190 3 120 80 210 4 110 70 160 Месяц Суммарное предложение Суммарный спрос 1 90+50=140 100 2 140+100+60=300 100+190=290 3 300+120+80=500 290+210=500 4 500+110+70=680 500+160=660 • 𝑅 𝑖 и 𝑂 𝑖 соответствуют уровням производства в обычном и сверхурочном режиме соответственно. • Избыток введем для балансировки модели • Себестоимость перевозок вычисляется как сумма затрат на производство и хранение • Оптимальное решение получается за один проход 36 1 2 3 4 Избыток 𝑹 𝟏 6 6.1 6.2 6.3 0 90 90 𝑶 𝟏 9 9.1 9.2 9.3 0 50 10 30 10 𝑹 𝟐 6 6.1 6.2 0 100 100 𝑶 𝟐 9 9.1 9.2 0 60 60 𝑹 𝟑 6 6.1 0 120 120 𝑶 𝟑 9 9.1 0 80 80 𝑹 𝟒 6 110 110 𝑶 𝟒 9 70 50 20 100 190 210 160 20 |