Задача о замене оборудования
Известна стоимость нового оборудования C денежных единиц. Эксплуатация оборудования возраста t лет в течение года приносит доход φ(t) денежных единиц. Требуется определить оптимальную политику замены оборудования таким образом, чтобы доход, полученный при эксплуатации нового оборудования в течение n лет, был максимальным.
Рассмотрим задачу об оптимальном использовании скрепера ДЗ-77 на мерзлых грунтах (4-я категория) севера Западной Сибири.
Известен доход по каждому году эксплуатации скрепера (табл.6.5) и оптовая цена 24 тыс. рублей (по состоянию на 1 января 1988 года).
Таблица 6.5
Исходная информация
| Возраст оборудования (лет) | |||||||
| Доход за год (тыс.руб.) |
Требуется определить оптимальную политику замен скрепера таким образом, чтобы доход, полученный за 7 лет эксплуатации, был максимальным.
Предположим, что решение – заменить или оставить оборудование – принимаем в начале каждого года.
Введем функцию Беллмана fk (t)– максимальный доход, который может быть получен при эксплуатации скрепера возраста t в течение k лет при оптимальной политике замены.
Составим первое уравнение Беллмана.
Пусть f1(t) – максимальный доход, который может быть получен при эксплуатации скрепера возраста tв течение 1 года.
Если в начале года примем решение сохранить оборудование, то доход будет равен φ(t).
Если в начале года примем решение заменить скрепер, то должны потратить на покупку нового скрепера С рублей, а доход, который принесет эксплуатация нового скрепера в течении года, равен φ(0).
Таким образом, доход, полученный в случае замены скрепера в течение года, равен: -С+ φ(0).
Отсюда
(6.5)
Выведем функциональное уравнение Беллмана для функции fk+1(t).
Предположим, что в начале первого года эксплуатации скрепера было принято решение сохранить его, тогда доход за 1 год эксплуатации составит φ(t).
По истечении года возраст оборудования будет равен t+1 год, а срок оставшейся эксплуатации скрепера равен k лет. В соответствии с принципом оптимальности, необходимо постараться получить за оставшиеся k лет максимальный доход, т.е. fk (t+1).
Итак, если вначале срока эксплуатации сохранить скрепер, то доход за k+1 год составит сумму φ(t)+ fk (t+1).
Предположим, что в начале рассматриваемого года принято решение заменить скрепер, тогда, потратив С д.ед. на покупку нового скрепера, получим за год эксплуатации доход φ(0). Через год возраст скрепера будет равен одному году, срок оставшейся эксплуатации к лет и максимальный доход, который можно получить за оставшиеся к лет составит fk (1). Значит, за к+1 год в случае «замены» доход будет равен: -С+ φ(0)+ fk (1).
Для определения функции fk+1(t) необходимо выбрать наибольшее из чисел: φ(t)+ fk (t+1); -С+ φ(0)+ fk (1),
т.е. 
(6.6)
Это и есть функциональное уравнение Беллмана. 
.
Поскольку в условии задачи требуется определить максимальный доход за 7 лет эксплуатации скрепера, то необходимо вычислить функции: f1, f2, f3,…, f7.
Расчет по уравнению Беллмана удобно представить в рабочей таблице (табл.6.6).
Таблица 6.6
Расчетная матрица
| Исходная инф-я | f1(t) | Ре-ше-ние | f2(t) | Ре-ше-ние | f3(t) | Ре-ше-ние | f4(t) | Ре-ше-ние | f5(t) | Ре-ше-ние | f6(t) | Ре-ше-ние | f7(t) | Ре-ше-ние | |
| t | φ(t) | ||||||||||||||
| С С С С/3 | - | С С - | - - | С С - - | - - - | С С - - - | - - - - | С С С/3 - - - - | - - - - - | С С - - - - - | - - - - - - | С - - - - - - |
Так как доход (270) от старого оборудования больше, то принимаем в начале года решение сохранить оборудование и записываем в таблицу 6.6 результат f1(0)=270 и «Сохранить».
f1 (t = 1) = max (j (1); 246) = max (256;246) = 256.
Результат f1(1)=256 и решение «Сохранить», т.к. снова доход от старого оборудования больше.
f1 (t = 2) = max (j (2); 246) = max (251; 246) = 251.
Результат f1(2)=251 и решение «Сохранить».
f1(t = 3) = max(j(3); 246) = max(246; 246) = 246.
Результат f1(3) = 246 и решение C/З «Сохранить» или «Заменить».
f1(t =4) = max(j(4); 246) = max(242; 246) = 246.
Результат f1(4)=246 и решение З «Заменить», т.к. доход от нового оборудования больше.
f1(t = 5) = max(j(5); 246) = max(236; 246) = 246.
Результат f1(5)=246 и решение «Заменить».
f1(t = 6) = (230; 246) = 246.
Результат f1(6)=246 и решение «Заменить»
Затем записываем функциональное уравнение Беллмана для f2(t)
(6.7)
Сумма: -С+φ(0)+ f1 (1)=-24+270+256=502 –доход от нового оборудования.
Вычисляя по формуле (6.7) f2(t), принимаем решение и записываем в рабочую таблицу. При t=6 ставим прочерк, так как счет по формуле прекращен – оборудование имеет возраст вне рассматриваемого срока.
Аналогично вычисляем f3(t), f4(t), f5(t), f6(t) и f7(t) по формулам:
; (6.8)
; (6.9)
(6.10)
; (6.11)
(6.12)
Для выбора ответа составим таблицу 6.7 в лексикографическом стиле (построчно).
Таблица 6.7
Результаты расчета
| Год эксплуатации | Возраст оборудования t | Год оставшейся эксплуатации рассматриваемого срока (7 лет) | Функция Беллмана | Решение |
| Первый Второй Третий Четвертый Пятый Шестой Седьмой | f7(0) f6(1) f5(2) f4(3) f3(1) f2(2) f2(1) | сохранить сохранить с/з=сохранить заменить сохранить заменить сохранить |
Выбор ответа, т.е. оптимальная политика замены скрепера определяется следующим образом (см. табл.6.7). Таблица заполняется по строкам. В начале первого года эксплуатации возраст скрепера составит 0 лет, срок оставшейся эксплуатации 7 лет; функция Беллмана f7(0). В табл. 6.6 найдено решение – сохранить. Эта информация записывается в первой строке.
Так как принято решение сохранить скрепер в начале года, то возраст его в начале второго года эксплуатации составит 1 год, срок оставшейся эксплуатации 6 лет, функция Беллмана запишется f6(1), соответствующее решение в таблице 6.6 «сохранить». Так продолжаем заполнять каждую строку, учитывая предыдущее решение. Для удобства рекомендуется использовать оптимальную шкалу замены скрепера. При такой политике замены скрепера доход за 7 лет эксплуатации составит в среднем 1 млн. 781 тыс. рублей.
Оптимальные шкалы эксплуатации оборудования строятся для наглядности полученного результата в таблице 6.7 и удобства практического использования.
Итак, оптимальная политика эксплуатации оборудования:
Если в начале третьего года при равных доходах от старого и нового скрепера принять решение «сохранить», то все равно нужно через год его заменить.
С С С З С З С t (возраст)
0 1 2 3 4 5 6 7
пер вто- тре- четве пя - шес- седь-
вый рой тий ртый тый той мой
год
Если в начале третьего года при равных доходах от старого и нового скрепера принять решение «заменить» , то нужно через два года его заменить
С С З С З С С t (возраст)
0 1 2 3 4 5 6 7
пер вто- тре- четве пя - шес- седь-
вый рой тий ртый тый той мой
год
Вопросы для самоконтроля
1) Каков смысл функции Беллмана в задаче о замене оборудования?
2) Когда принимается решение «сохранить» или «заменить» оборудование?
3) Какова особенность первого уравнения Беллмана в задаче о замене оборудования?
4) В чем суть принципа оптимальности, положенного в основу вывода функционального уравнения Беллмана в задаче о замене оборудования?
5) Как построить шкалу оптимальных решений «сохранить» или «заменить» оборудование?
Применение динамического программирования в вопросах перспективного планирования.
Динамическое программирование представляет собой математический аппарат, позволяющий осуществлять оптимальное планирование многошаговых управляемых процессов. Изучив этот раздел математического программирования, специалист имеет возможность правильно, дальновидно спланировать деятельность предприятия, фирмы и т.д.
Например, цель работы – рассмотреть задачу строительства объектов для удовлетворения некоторой потребности с минимальными затратами. На современном этапе, в условиях рынка, важно знать – как удовлетворить эту потребность. Нужно ли расширять старое предприятие или строить новое? А если строить новое, то какой мощности? Возникает несколько вариантов. Осуществляя последовательный перебор решений, получим оптимальный вариант удовлетворения потребности при минимальных затратах. Для осуществления рационального перебора решений необходимо вывести функциональное уравнение Беллмана. В качестве примера рассмотрим задачу.
На авторемонтном предприятии (АРП) действует один «низкий» пост, но в связи с увеличением автомобильного парка, с каждым годом увеличивается соответственно и потребность в техническом обслуживании (ТО). Для того, чтобы удовлетворить потребность населения в ТО 100 тыс. обслуживаний в год, необходимо расширить старый имеющийся пост или построить новые посты: «высокий», «универсальный», «напольный» или расширить старый пост и построить некоторые новые.
Рассчитать минимальное количество рабочих для выполнения ТО автомобилей на АРП, если известно количество занятых людей на постах (табл. 6.8).
Таблица 6.8
Исходная информация
| Количество обслужи ваний /тыс. в год/ Виды постов | |||||
| 1.Низкий | - | ||||
| 2.Высокий | - | ||||
| 3.Напольный | - | ||||
| 4.Универсальный |
Решение
Укажем возможные варианты:
0 вариант - удовлетворение потребности в обслуживании автомобилей только за счёт расширения действующего поста.
i-тый вариант состоит в удовлетворении потребности за счёт расширения действующего и строительства новых трёх постов. (i=0,1,2,3)
Выведем функцию Беллмана.
ƒi(х) - минимальное количество рабочих, которые должны выполнить хобслуживаний по i-ому варианту. При этом αi(х) - количество обслуживаний, которое выполняет i -тый пост. Обозначим φi(х)- количество рабочих, выполняющих обслуживание на i -том посту.
Предположим, что fi(х) известно, тогда вычислим fi+1(х)
Пусть i+1 пост выполняет t обслуживаний 
, тогда количество занятых рабочих на этом посту равно φ i+1(t). На долю остальных постов останется х - t обслуживаний.
Согласно принципа оптимальности следует спланировать обслуживание таким образом, чтобы количество рабочих было минимальным, т.е. ƒi(х-t). Таким образом, общее количество рабочих составит φ i+1(t)+ƒi(х-t).
При удовлетворении всех потребностей на ТО автомобилей следует выбирать t таким образом, чтобы эта сумма была минимальной, т.е.
(6.13)
Это есть функциональное уравнение Беллмана. Остается найти значения f0, f1, f2, f3.
Составляем рабочую таблицу. Для этого подсчитаем функции Беллмана
Таблица 6.9
Расчетная матрица
| Кол-во обслуж. х (тыс. в год) | Исходная информация | f0(х) | a0(х) тыс. в год | f1(х) | a1(х) тыс. в год | f2(х) | a2(х) тыс. в год | f3(х) | a3(х) тыс. в год | |||
| φ0(х) | φ1(х) | φ2(х) | φ3(х) | |||||||||
| - | - | - | - | - | - | - | - | - | ||||
| 0,40 | ||||||||||||
| - | - | - | - | - | ||||||||
| - | - | - | - | - | ||||||||
| - | - | - | - | - | ||||||||
| - | - | - | - | - | 0,40 | |||||||
| - | - | - | - | - |
ƒ0(х)= φ 0(t), 0 ≤ t ≤ 100
.
Результаты расчета представлены в рабочей таблице 6.9. Прочерк в таблице следует понимать как «невыгодно».
Итак, получили ƒ3(100)=55,т.е. для удовлетворения потребности в 100 тысячах обслуживаний в год необходимо иметь минимум 55 рабочих.
При этом универсальный пост может выполнять α3(100)=40 либо 50 тыс. обслуживаний в год. Выбираем любой вариант. Пусть универсальный пост выполняет 40 тысяч обслуживаний, тогда 100-40=60.α2(60)=20 либо 30, либо 40. Выбираем из них любой вариант. Пусть напольный пост выполняет 30 тыс. обслуживаний, тогда 60-30=30 и α1(30)=30 тыс.
Один из вариантов ответа приведем в таблице 6.10
Таблица 6.10
Результаты расчета
| Виды постов | Кол-во обслуживаний (тыс. в год) | Самоконтроль |
| Кол-во рабочих | ||
| 1. Универсальный 2. Напольный 3. Высокий 4. Низкий | - |
Σ=55