Динамическое программирование
Задачи динамического программирования: задача распределения инвестиций, задача замены оборудования, задача Джонсона
xf1(x)f2(x)f3(x)
16.345
25.267
34.34.67.8
4563
5*76.38.2
Решить онлайн
Примеры решений Задача Джонсона Симплекс метод Метод прогонки Задача замены оборудования Задача распределения инвестиций Параметры сетевой модели Задача коммивояжера Многоканальные СМО

Пример решения задачи о замене оборудования

Рассмотрим задачу о замене оборудования на следующем примере. В начале планового периода продолжительностью N = 4 года имеется оборудование, возраст которого t, причем оборудование не должно быть старше 6 лет (примем t = 2 года).
ИЗВЕСТНЫ: ТРЕБУЕТСЯ:
Разработать оптимальную политику в отношении имеющегося оборудования, т.е. на начало каждого года планового периода установить, сохранить в этом году оборудование или продать его по остаточной стоимости s, или купить новое оборудование, чтобы ожидаемая прибыль за N лет достигла максимальной величины.
1. Составить матрицу максимальных прибылей Fn(t) за 4 года;
2. Сформулировать по матрице максимальных прибылей оптимальные стратегии замены оборудования возрастов t1 и t2 лет в плановом периоде, продолжительностью 4 и 3 года.
Таблица соответствия стоимости продукции и затрат от возраста
Возраст t 0 1 2 3 4 5 6
Ст.продукции r(t) 27 26 26 25 24 23 21
Ст.расходов u(t) 15 15 16 16 16 17 19

Решение находим с помощью калькулятора.
Математическая модель задачи:
Z = ΣFi(xi)→max

Экономический смысл переменных:
N - плановый период эксплуатации оборудования;
ZC - прибыль в случае сохранения оборудования;
ZЗ - прибыль в случае замены оборудования;
S0 - первоначальное состояние системы;
SHi - предполагаемый возраст оборудования в начале i-го периода, т.е. после того, как мы примем решение сохранить или заменить его;
Si - возраст в конце i-го периода;
r(t) - прибыль от эксплуатации;
u(t) - расходы на эксплуатацию;
s - остаточная стоимость оборудования;
p - стоимость нового оборудования;
t - возраст оборудования;
fi - доход на i-ом шаге;
Fi - максимальный доход на i-ом шаге.

Прибыль, если в начале года выбрано управление «сохранение» оборудования:
Zc = r(t) - u(t)
Прибыль в случае «замены»:
ZЗ = s - p + r(0) - u(0)

Состояние системы (S) характеризуется возрастом оборудования
t = 0, 1, …. Значение t = 0 соответствует новому оборудованию.
В формулах максимальная прибыль на очередном шаге определяется с учетом всех возможных состояний системы, в которых она может находиться сразу после принятия решения в начале данного года.
Основное функциональное уравнение на последнем N-ом шаге:
FN(SN-1, xN) = max ZN(SN-1, xN)

При произвольном шаге (i<N) основное функциональное уравнение принимает вид
Fi(Si-1, xN) = max {Zi(SHi, xi) + Fi+1(Si)}
Прибыль на i-ом шаге будет определяться следующей парой формул:
- при управлении «сохранение»
Fi(SHi, xi) = r(Si, xi) - u(SHi)
- при управлении «замена»
Zi(SHi, xi) = s - p + r(0) - u(0)
Для нашего примера расчет начинается с последнего, четвертого года планового периода:
F4(S3, x4) = max Z4(SH3, x4)
при этом:
- в случае «сохранения» оборудования:
Z4(SH4, x4) = r(SH4) - u(SH4)
- в случае «замены»:
Z4(SH4, x4) = 4 - 13 + 27 - 15 = 3
Составляется 1-ая таблица, рассматриваемая все возможные НАЧАЛЬНЫЕ состояния оборудования, т.е. его возраст S3 = 1 - 6 лет, начиная с конца - последнего шага.

Таблица 1. F4(S3, x4) = max Z4(SH3, x4)
Шаг 4

Возраст S3 в конце 3-го шага Управление x4 Предполагаемый возраст SH4 в начале 4-го шага Прибыль Z4 Max доход на F4 шаге
1 Сохранение 1 11 11
Замена 0 3
2 Сохранение 2 10 10
Замена 0 3
3 Сохранение 3 9 9
Замена 0 3
4 Сохранение 4 8 8
Замена 0 3
55 Сохранение 5 6 6
Замена 0 3
6 Сохранение 6 2 3
Замена 0 3

Анализ таблицы показывает, что заменять оборудование выгодно только в том случае, если его возраст уже равен 6 годам, т.е. по условиям оборудование нельзя использовать далее.
Теперь анализируем ситуацию перед третьим годом исследуемого периода.
F3(S2, x4) = max {Z3(SH3, x3) + F4(S3)}
при этом:
- в случае «сохранения оборудования»
Z3(SH3, x3) = r(SH3) - u(SH3)
- в случае «замены»
Z3(SH3, x3) = 4 - 13 + 27 - 15 = 3
Следует оптимизировать расходы за последний и предпоследний годы (за двухлетний период).
Оптимальная прибыль за 4-ый год берется из таблицы 1.
Учтем, что SH2 - возраст оборудования в начале третьего года сразу после принятия решения о его «сохранении» или «замене»;
S3 - возраст оборудования к концу третьего года.
Данные в колонку F4 переносятся из предыдущей таблице в соответствии со значением параметра S3.
Таблица 2. F3(S2, x4) = max {Z3(SH3, x3) + F4(S3)} Шаг 3
S1 x3 SH2 Z3 из таблицы 1 Возраст S3 в конце 3 шага F4 Z3 + F4 F3
1 Сохранение 1 11 2 10 21 21
Замена 0 3 1 11 14
2 Сохранение 2 10 3 9 19 19
Замена 0 3 1 11 14
3 Сохранение 3 9 4 8 17 17
Замена 0 3 1 11 14
+4 Сохранение 4 8 5 6 14 14
Замена 0 3 1 11 14
5 Сохранение 5 6 6 3 9 14
Замена 0 3 1 11 14
6 Сохранение 6 2 - - - 14
Замена 0 3 1 11 14

Также проводится условная оптимизация на начало второго года (шаг 2) и составляется таблица 3.
Таблица 3. F2 (S1,x4) = max {Z2(SH2, x2) + F3(S2)} Шаг 2
S1 x2 SH1 Z2 S2 F3 Z2 + F3 F2
1 Сохранение 1 11 2 19 30 30
Замена 0 3 1 21 24
2 Сохранение 2 10 3 17 27 27
Замена 0 3 1 21 24
3 Сохранение 3 9 4 14 23 24
Замена 0 3 1 21 24
4 Сохранение 4 8 5 14 22 24
Замена 0 3 1 21 24
5 Сохранение 5 6 6 14 20 24
Замена 0 3 1 21 24
6 Сохранение 6 2 - - - 24
Замена 0 3 1 21 24

Также проводится условная оптимизация на начало первого года (шаг 1) и составляется таблица 4, которая завершает условную оптимизацию.
Таблица 4. F1 (S0, x4) = max {Z1(SH1, x1) + F2(S1)} Шаг 1
S1 x2 SH1 Z2 S2 F3 Z2 + F3 F2
1 Сохранение 1 11 2 19 30 30
Замена 0 3 1 21 24
2 Сохранение 2 10 3 17 27 27
Замена 0 3 1 21 24
3 Сохранение 3 9 4 14 23 24
Замена 0 3 1 21 24
4 Сохранение 4 8 5 14 22 24
Замена 0 3 1 21 24
5 Сохранение 5 6 6 14 20 24
Замена 0 3 1 21 24
6 Сохранение 6 2 - - - 24
Замена 0 3 1 21 24

С помощью таблиц условной оптимизации можно сформулировать оптимальную политику в отношении оборудования любого возраста не старше 6 лет в течение 4-х летнего периода.
Для наглядности основные результаты, содержащиеся в последних столбцах четырех последних построенных таблиц, оформляются в виде сводной таблицы, которая называется матрицей максимальных прибылей, и выделяются элементы, ниже которых расположены показатели суммарной прибыли, соответствующие выбору управления «ЗАМЕНА».
Элементы, расположенные выше линии выделения, находятся в области «СОХРАНЕНИЯ» оборудования.
Матрица максимальных прибылей
t ГОДЫ
1-4 2-4 3-4 4
0 42 - - -
1 38 30 21 11
2 34 27 19 10
3 33 24 17 9
4 33 24 14 8
5 33 24 14 6
6 33 24 14 3

Сформулируем оптимальную политику в отношении оборудования, возраст которого 2 года.
В матрице прибылей для t = 2 в первой колонке стоит суммарная прибыль 34 д.ед. за четыре года, при этом выбор управления «СОХРАНЕНИЕ».
К началу второго года возраст оборудования составит 3 года, поэтому в следующей колонке выбирается строка, соответствующая возрасту 3 года.
Оптимальная прибыль за второй - четвертый годы - 24 д.ед., и мы находимся в области «ЗАМЕНЫ» оборудования, следовательно, к началу 3-го года оборудование будет иметь возраст 1 год.
Прибыль за третий - четвертый годы для такого оборудования равна 21 д.ед., за последний четвертый год - 10 д.ед. (при возрасте t = 2).

ВЫВОД: рекомендуется замена оборудования в начале 2-го года эксплуатации.

Перейти к онлайн решению своей задачи

Динамическая оптимизация
В условиях задачи производственного планирования найти оптимальные сроки начала строительства каждого из объектов так, чтобы суммарный срок строительства всех объектов был бы минимальным.
Объекты / Стадии№1№2№3№4
A12543
A21426
A33434
Решение онлайн в Word
Учебно-методический
√ курсы переподготовки и повышения квалификации
√ вебинары
√ сертификаты на публикацию методического пособия
Подробнее
Библиотека материалов
√ Общеобразовательное учреждение
√ Дошкольное образование
√ Конкурсные работы
Все авторы, разместившие материал, могут получить свидетельство о публикации в СМИ
Подробнее
Курсовые на заказ