ЭЛЕКТРОННЫЙ ЛАБОРАТОРНЫЙ ПРАКТИКУМ
ПО УЧЕБНОМУ ПРЕДМЕТУ
"ЭКОНОМИКО-МАТЕМАТИЧЕСКИЕ МЕТОДЫ"
№22. Решение задач управления запасами с использованием детерминированной однопродуктовой модели
Цель: научить использовать детерминированную однопродуктовую модель в решении задач управления запасами.
Оборудование: практикум, тетрадь для лабораторных и практических работ.
Литература:
- Плотников А. Д. Математическое программирование: экспресс-курс. - Мн.: Новое знание, 2007. С. 147-156.
- Таха, Хемди. Введение в исследование операций - М.: Издательский дом "Вильямс", 2005. С. 446-465.
Время выполнения: 2 часа.
ВОПРОСЫ ВХОДНОГО КОНТРОЛЯ:
- Сформулируйте общую задачу линейного программирования.
- Приведите формулировку принципа оптимальности Беллмана.
- Приведите формулировку принципа вложения.
- Назовите виды задач, решаемых с помощью методов динамического программирования.
КРАТКИЕ ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ:
В основу динамического программирования положены два принципа.
1) Принцип оптимальности (Беллмана) - утверждает, что какой бы ни был способ достижения данного шага, последующие шаги должны обеспечить оптимальное значение функции цели для оставшейся части шагов. Например, если отыскивается минимальный путь между пунктом отправления и пунктом назначения, то принцип оптимальности означает, что любой подпуть минимального пути является минимальным путем между соответствующими пунктами. Этот принцип влечет появление рекуррентных соотношений для нахождения оптимального решения.
2) Принцип вложения - утверждает, что природа задачи не меняется при изменении количества шагов. Это значит, что решение задачи, принятое на очередном шаге, является наилучшим с точки зрения всего процесса в целом, и последовательность решений, полученная при рассмотрении нарастающей последовательности шагов, приводит к решению исходной задачи.
Схема решения задачи методом динамического программирования
Первым рассматривается последний шаг того реального явления, для которого решается задача оптимизации. Решения, принятые на последнем шаге, принимают исходя из предположений о результатах предшествующих шагов. Завершив рассмотрение последнего шага, приступают к рассмотрению предпоследнего шага. В этом случае также, исходя из предположений о результатах предшествующих шагов, принимают такое решение на данном шаге, чтобы совокупное решение для двух последних шагов было оптимальным. Повторив такие исследования для нарастающей последовательности шагов, можно найти решение исходной задачи в целом
МЕТОДИЧЕСКИЕ УКАЗАНИЯ:
Задача управления запасами
Фирма планирует производство и уровень запасов производимой продукции на период, равный 6 месяцам. Спрос на продукцию фирмы в каждом месяце планового периода соответственно равен: D1=5, D2=2, D3=3.
Dt — спрос на продукцию фирмы в t-м месяце.
Предполагается, что запас продукции фирмы на начало планового периода равен 2. Затраты на производство и хранение продукции определяются по формуле
где xt - выпуск продукции в t-м месяце; it - уровень запасов продукции на конец t-ro месяца; h - некоторая постоянная. В данном случае полагаем h=1.
Требуется спланировать уровень производства и уровень запасов продукции, обеспечивающий минимальные затраты при условии, что уровень запасов продукции на конец планового периода должен быть равен 0.
Решение.
Составим реккурентное соотношение, учитывающее специфику задачи. Будем использовать следующие обозначения:
fn(i) - минимальные затраты в течение n последних отрезков планового периода при начальном уровне запасов i;
xn(i) - объем выпуска продукции, позволяющий достичь fn(i);
dn - спрос на продукцию на n-ом отрезке от конца планового периода.
В общем виде рекуррентное соотношение для минимальных затрат имеет вид:
fn(i) = min {4x + 1(i + x - dn) + fn-1(i + x - dn)},
где (i + x - dn) - величина запаса продукции на конец n-го отрезка.
При n = 0 имеем f0(0) = 0. Здесь i = 0, т. е. запас продукции на начало четвертого месяца, когда закончится плановый период, равен нулю.
При n = 1 уровень запасов на начало планового периода не может превышать величины спроса на продукцию на конец третьего месяца (т. е. 3), так как запас продукции по окончании планового периода равен нулю. Минимальные затраты вычисляем по формуле
f1(i) = 4x + 1(i + x - 3) + f0(0),
где i + x - 3 = 0 - уровень запасов на конец планового периода.
Отсюда имеем: i + x = 3, i = 0, 1, 2, 3.
i |
x1(i) |
f1(i) |
0 |
3 |
12 |
1 |
2 |
8 |
2 |
1 |
4 |
3 |
0 |
0 |
При n = 2 минимальные затраты вычисляем по формуле
f2(i) = 4x + 1(i + x - 2) + f1(i + x - 2).
| i\x | 0 | 1 | 2 | 3 | 4 |
5 | x2(i) |
f2(i) |
| 0 | - | - | 8 + 0 + 12 | 12 + 1 + 8 | 16 + 2 + 4 | 20 + 3 + 0 | 2 | 20 |
| 1 | - | 4 + 0 + 12 | 8 + 1 + 8 | 12 + 2 + 4 | 16 + 3 + 0 | - | 1 | 16 |
| 2 | 0 + 0 + 12 | 4 + 1 + 8 | 8 + 2 + 4 | 12 + 3 + 0 | - | - | 0 | 12 |
| 3 | 0 + 1 + 8 | 4 + 2 + 4 | 8 + 3 + 0 | - | - | - | 0 | 9 |
| 4 | 0 + 2 + 4 | 4 + 3 + 0 | - | - | - |
- | 0 | 6 |
| 5 | 0 + 3 + 0 | - | - | - | - |
- | 0 | 3 |
При n = 3 минимальные затраты вычисляем по формуле
f3(i) = 4x + 1(i + x - 5) + f2(i + x - 5).
Здесь величина х не может быть меньше 3, чтобы вместе с начальным запасом, равным 2, удовлетворить спрос на первом месяце планового периода.
| i\x | 3 | 4 | 5 | 6 | 7 |
8 | x2(i) |
f2(i) |
| 2 | 12 + 0 + 20 | 16 + 1 + 16 | 20 + 2 + 12 | 24 + 3 + 9 | 28 + 4 + 6 | 32 + 5 + 3 | 3 | 32 |
СОДЕРЖАНИЕ РАБОТЫ:
Вариант №1
Фирма планирует производство и уровень запасов производимой продукции на период, равный 6 месяцам. Спрос на продукцию фирмы в каждом месяце планового периода соответственно равен: D1=5, D2=2, D3=2, D4=3, D5=4, D6=2,
Dt — спрос на продукцию фирмы в t-м месяце.
Предполагается, что запас продукции фирмы на начало планового периода равен 2. Затраты на производство и хранение продукции определяются по формуле
где xt - выпуск продукции в t-м месяце; it - уровень запасов продукции на конец t-ro месяца; h - некоторая постоянная. В данном случае полагаем h=1.
Требуется спланировать уровень производства и уровень запасов продукции, обеспечивающий минимальные затраты при условии, что уровень запасов продукции на конец планового периода должен быть равен 0.
Вариант №2
Фирма планирует производство и уровень запасов производимой продукции на период, равный 6 месяцам. Спрос на продукцию фирмы в каждом месяце планового периода соответственно равен: D1=2, D2=3, D3=2, D4=3, D5=5, D6=3,
Dt — спрос на продукцию фирмы в t-м месяце.
Предполагается, что запас продукции фирмы на начало планового периода равен 2. Затраты на производство и хранение продукции определяются по формуле
где xt - выпуск продукции в t-м месяце; it - уровень запасов продукции на конец t-ro месяца; h - некоторая постоянная. В данном случае полагаем h=1.
Требуется спланировать уровень производства и уровень запасов продукции, обеспечивающий минимальные затраты при условии, что уровень запасов продукции на конец планового периода должен быть равен 0.
Вариант №3
Фирма планирует производство и уровень запасов производимой продукции на период, равный 6 месяцам. Спрос на продукцию фирмы в каждом месяце планового периода соответственно равен: D1=4, D2=3, D3=3, D4=2, D5=3, D6=3,
Dt — спрос на продукцию фирмы в t-м месяце.
Предполагается, что запас продукции фирмы на начало планового периода равен 2. Затраты на производство и хранение продукции определяются по формуле
где xt - выпуск продукции в t-м месяце; it - уровень запасов продукции на конец t-ro месяца; h - некоторая постоянная. В данном случае полагаем h=1.
Требуется спланировать уровень производства и уровень запасов продукции, обеспечивающий минимальные затраты при условии, что уровень запасов продукции на конец планового периода должен быть равен 0.
Вариант №4
Фирма планирует производство и уровень запасов производимой продукции на период, равный 6 месяцам. Спрос на продукцию фирмы в каждом месяце планового периода соответственно равен: D1=4, D2=4, D3=2, D4=2, D5=3, D6=3,
Dt — спрос на продукцию фирмы в t-м месяце.
Предполагается, что запас продукции фирмы на начало планового периода равен 2. Затраты на производство и хранение продукции определяются по формуле
где xt - выпуск продукции в t-м месяце; it - уровень запасов продукции на конец t-ro месяца; h - некоторая постоянная. В данном случае полагаем h=1.
Требуется спланировать уровень производства и уровень запасов продукции, обеспечивающий минимальные затраты при условии, что уровень запасов продукции на конец планового периода должен быть равен 0.
Вариант №5
Фирма планирует производство и уровень запасов производимой продукции на период, равный 6 месяцам. Спрос на продукцию фирмы в каждом месяце планового периода соответственно равен: D1=4, D2=5, D3=3, D4=2, D5=2, D6=3,
Dt — спрос на продукцию фирмы в t-м месяце.
Предполагается, что запас продукции фирмы на начало планового периода равен 2. Затраты на производство и хранение продукции определяются по формуле
где xt - выпуск продукции в t-м месяце; it - уровень запасов продукции на конец t-ro месяца; h - некоторая постоянная. В данном случае полагаем h=1.
Требуется спланировать уровень производства и уровень запасов продукции, обеспечивающий минимальные затраты при условии, что уровень запасов продукции на конец планового периода должен быть равен 0.
Вариант №6
Фирма планирует производство и уровень запасов производимой продукции на период, равный 6 месяцам. Спрос на продукцию фирмы в каждом месяце планового периода соответственно равен: D1=4, D2=3, D3=2, D4=4, D5=3, D6=3,
Dt — спрос на продукцию фирмы в t-м месяце.
Предполагается, что запас продукции фирмы на начало планового периода равен 2. Затраты на производство и хранение продукции определяются по формуле
где xt - выпуск продукции в t-м месяце; it - уровень запасов продукции на конец t-ro месяца; h - некоторая постоянная. В данном случае полагаем h=1.
Требуется спланировать уровень производства и уровень запасов продукции, обеспечивающий минимальные затраты при условии, что уровень запасов продукции на конец планового периода должен быть равен 0.
Вариант №7
Фирма планирует производство и уровень запасов производимой продукции на период, равный 6 месяцам. Спрос на продукцию фирмы в каждом месяце планового периода соответственно равен: D1=4, D2=4, D3=2, D4=3, D5=3, D6=3,
Dt — спрос на продукцию фирмы в t-м месяце.
Предполагается, что запас продукции фирмы на начало планового периода равен 2. Затраты на производство и хранение продукции определяются по формуле
где xt - выпуск продукции в t-м месяце; it - уровень запасов продукции на конец t-ro месяца; h - некоторая постоянная. В данном случае полагаем h=1.
Требуется спланировать уровень производства и уровень запасов продукции, обеспечивающий минимальные затраты при условии, что уровень запасов продукции на конец планового периода должен быть равен 0.
Вариант №8
Фирма планирует производство и уровень запасов производимой продукции на период, равный 6 месяцам. Спрос на продукцию фирмы в каждом месяце планового периода соответственно равен: D1=4, D2=5, D3=2, D4=3, D5=2, D6=3,
Dt — спрос на продукцию фирмы в t-м месяце.
Предполагается, что запас продукции фирмы на начало планового периода равен 2. Затраты на производство и хранение продукции определяются по формуле
где xt - выпуск продукции в t-м месяце; it - уровень запасов продукции на конец t-ro месяца; h - некоторая постоянная. В данном случае полагаем h=1.
Требуется спланировать уровень производства и уровень запасов продукции, обеспечивающий минимальные затраты при условии, что уровень запасов продукции на конец планового периода должен быть равен 0.
Вариант №9
Фирма планирует производство и уровень запасов производимой продукции на период, равный 6 месяцам. Спрос на продукцию фирмы в каждом месяце планового периода соответственно равен: D1=5, D2=2, D3=2, D4=4, D5=2, D6=3,
Dt — спрос на продукцию фирмы в t-м месяце.
Предполагается, что запас продукции фирмы на начало планового периода равен 2. Затраты на производство и хранение продукции определяются по формуле
где xt - выпуск продукции в t-м месяце; it - уровень запасов продукции на конец t-ro месяца; h - некоторая постоянная. В данном случае полагаем h=1.
Требуется спланировать уровень производства и уровень запасов продукции, обеспечивающий минимальные затраты при условии, что уровень запасов продукции на конец планового периода должен быть равен 0.
Вариант №10
Фирма планирует производство и уровень запасов производимой продукции на период, равный 6 месяцам. Спрос на продукцию фирмы в каждом месяце планового периода соответственно равен: D1=4, D2=2, D3=3, D4=4, D5=2, D6=3,
Dt — спрос на продукцию фирмы в t-м месяце.
Предполагается, что запас продукции фирмы на начало планового периода равен 2. Затраты на производство и хранение продукции определяются по формуле
где xt - выпуск продукции в t-м месяце; it - уровень запасов продукции на конец t-ro месяца; h - некоторая постоянная. В данном случае полагаем h=1.
Требуется спланировать уровень производства и уровень запасов продукции, обеспечивающий минимальные затраты при условии, что уровень запасов продукции на конец планового периода должен быть равен 0.
Вариант №11
Фирма планирует производство и уровень запасов производимой продукции на период, равный 6 месяцам. Спрос на продукцию фирмы в каждом месяце планового периода соответственно равен: D1=3, D2=3, D3=3, D4=3, D5=3, D6=3,
Dt — спрос на продукцию фирмы в t-м месяце.
Предполагается, что запас продукции фирмы на начало планового периода равен 2. Затраты на производство и хранение продукции определяются по формуле
где xt - выпуск продукции в t-м месяце; it - уровень запасов продукции на конец t-ro месяца; h - некоторая постоянная. В данном случае полагаем h=1.
Требуется спланировать уровень производства и уровень запасов продукции, обеспечивающий минимальные затраты при условии, что уровень запасов продукции на конец планового периода должен быть равен 0.
Вариант №12
Фирма планирует производство и уровень запасов производимой продукции на период, равный 6 месяцам. Спрос на продукцию фирмы в каждом месяце планового периода соответственно равен: D1=4, D2=2, D3=4, D4=3, D5=2, D6=3,
Dt — спрос на продукцию фирмы в t-м месяце.
Предполагается, что запас продукции фирмы на начало планового периода равен 2. Затраты на производство и хранение продукции определяются по формуле
где xt - выпуск продукции в t-м месяце; it - уровень запасов продукции на конец t-ro месяца; h - некоторая постоянная. В данном случае полагаем h=1.
Требуется спланировать уровень производства и уровень запасов продукции, обеспечивающий минимальные затраты при условии, что уровень запасов продукции на конец планового периода должен быть равен 0.
Вариант №13
Фирма планирует производство и уровень запасов производимой продукции на период, равный 6 месяцам. Спрос на продукцию фирмы в каждом месяце планового периода соответственно равен: D1=3, D2=4, D3=4, D4=2, D5=3, D6=3,
Dt — спрос на продукцию фирмы в t-м месяце.
Предполагается, что запас продукции фирмы на начало планового периода равен 2. Затраты на производство и хранение продукции определяются по формуле
где xt - выпуск продукции в t-м месяце; it - уровень запасов продукции на конец t-ro месяца; h - некоторая постоянная. В данном случае полагаем h=1.
Требуется спланировать уровень производства и уровень запасов продукции, обеспечивающий минимальные затраты при условии, что уровень запасов продукции на конец планового периода должен быть равен 0.
Вариант №14
Фирма планирует производство и уровень запасов производимой продукции на период, равный 6 месяцам. Спрос на продукцию фирмы в каждом месяце планового периода соответственно равен: D1=2, D2=3, D3=2, D4=3, D5=5, D6=3,
Dt — спрос на продукцию фирмы в t-м месяце.
Предполагается, что запас продукции фирмы на начало планового периода равен 2. Затраты на производство и хранение продукции определяются по формуле
где xt - выпуск продукции в t-м месяце; it - уровень запасов продукции на конец t-ro месяца; h - некоторая постоянная. В данном случае полагаем h=1.
Требуется спланировать уровень производства и уровень запасов продукции, обеспечивающий минимальные затраты при условии, что уровень запасов продукции на конец планового периода должен быть равен 0.
Вариант №15
Фирма планирует производство и уровень запасов производимой продукции на период, равный 6 месяцам. Спрос на продукцию фирмы в каждом месяце планового периода соответственно равен: D1=4, D2=4, D3=2, D4=2, D5=3, D6=3,
Dt — спрос на продукцию фирмы в t-м месяце.
Предполагается, что запас продукции фирмы на начало планового периода равен 2. Затраты на производство и хранение продукции определяются по формуле
где xt - выпуск продукции в t-м месяце; it - уровень запасов продукции на конец t-ro месяца; h - некоторая постоянная. В данном случае полагаем h=1.
Требуется спланировать уровень производства и уровень запасов продукции, обеспечивающий минимальные затраты при условии, что уровень запасов продукции на конец планового периода должен быть равен 0.
Вариант №16
Фирма планирует производство и уровень запасов производимой продукции на период, равный 6 месяцам. Спрос на продукцию фирмы в каждом месяце планового периода соответственно равен: D1=4, D2=3, D3=2, D4=4, D5=3, D6=3,
Dt — спрос на продукцию фирмы в t-м месяце.
Предполагается, что запас продукции фирмы на начало планового периода равен 2. Затраты на производство и хранение продукции определяются по формуле
где xt - выпуск продукции в t-м месяце; it - уровень запасов продукции на конец t-ro месяца; h - некоторая постоянная. В данном случае полагаем h=1.
Требуется спланировать уровень производства и уровень запасов продукции, обеспечивающий минимальные затраты при условии, что уровень запасов продукции на конец планового периода должен быть равен 0.
Вариант №17
Фирма планирует производство и уровень запасов производимой продукции на период, равный 6 месяцам. Спрос на продукцию фирмы в каждом месяце планового периода соответственно равен: D1=4, D2=5, D3=2, D4=3, D5=2, D6=3,
Dt — спрос на продукцию фирмы в t-м месяце.
Предполагается, что запас продукции фирмы на начало планового периода равен 2. Затраты на производство и хранение продукции определяются по формуле
где xt - выпуск продукции в t-м месяце; it - уровень запасов продукции на конец t-ro месяца; h - некоторая постоянная. В данном случае полагаем h=1.
Требуется спланировать уровень производства и уровень запасов продукции, обеспечивающий минимальные затраты при условии, что уровень запасов продукции на конец планового периода должен быть равен 0.
Вариант №18
Фирма планирует производство и уровень запасов производимой продукции на период, равный 6 месяцам. Спрос на продукцию фирмы в каждом месяце планового периода соответственно равен: D1=4, D2=2, D3=2, D4=4, D5=2, D6=3,
Dt — спрос на продукцию фирмы в t-м месяце.
Предполагается, что запас продукции фирмы на начало планового периода равен 2. Затраты на производство и хранение продукции определяются по формуле
где xt - выпуск продукции в t-м месяце; it - уровень запасов продукции на конец t-ro месяца; h - некоторая постоянная. В данном случае полагаем h=1.
Требуется спланировать уровень производства и уровень запасов продукции, обеспечивающий минимальные затраты при условии, что уровень запасов продукции на конец планового периода должен быть равен 0.
ВОПРОСЫ ВЫХОДНОГО КОНТРОЛЯ:
- Сформулируйте общую задачу линейного программирования.
- Приведите формулировку принципа оптимальности Беллмана.
- Приведите формулировку принципа вложения.
- Назовите виды задач, решаемых с помощью методов динамического программирования.
- Опишите алгоритм решения задачи управления запасами.
ДОМАШНЕЕ ЗАДАНИЕ:
Выучить алгоритм решения задачи задачи управления запасами методом динамического программирования.