двигателей, чем необходимо, но в этом случае двигатели должны надлежащим образом храниться до их отгрузки потребителю. Стоимость хранения одного двигателя также меняется от года к году и оценивается в 20 ООО долл. для первого года, 30 ООО долл. - для второго, 40 ООО долл. - для третьего и 50 000 - для четвертого. В начале первого года компания имеет один двигатель, готовый к отгрузке. Разработайте оптимальный план производства двигателей.
10.3.3. Задача замены оборудования
Чем дольше механизм эксплуатируется, тем выше затраты на его обслуживание и ниже его производительность. Когда срок эксплуатации механизма достигает определенного уровня, может оказаться более выгодной его замена. Задача замены оборудования, таким образом, сводится к определению оптимального срока эксплуатации механизма.
Предположим, что мы занимаемся заменой механизмов на протяжении п лет. В начале каждого года принимается решение либо об эксплуатации механизма еще один год, либо о замене его новым. Обозначим через r(t) и с(г) прибыль от эксплуатации г-летнего механизма на протяжении года и затраты на его обслуживание за этот же период. Далее пусть s(t) - стоимость продажи механизма, который эксплуатировался t лет. Стоимость приобретения нового механизма остается неизменной на протяжении всех лет и равна /.
Элементы модели динамического программирования таковы.
1. Этап / представляется порядковым номером года /, / = 1, 2, п.
2. Вариантами решения на /-м этапе (т.е. для /-го года) являются альтернативы: продолжить эксплуатацию или заменить механизм в начале /-го года.
3. Состоянием на /-м этапе является срок эксплуатации t (возраст) механизма к началу /-го года.
Пусть f{t) - максимальная прибыль, получаемая за годы от / до п при условии, что в начале /-го года имеется механизм r-летнего возраста. Рекуррентное уравнение имеет следующий вид.
Компания планирует определить оптимальную политику замены используемого в настоящее время трехлетнего механизма на протяжении следующих 4 лет (п = 4), т.е. вплоть до начала пятого года. Приведенная таблица содержит относящиеся к задаче данные. Компания требует обязательной замены механизма, который находится в эксплуатации 6 лет. Стоимость нового механизма равна 100 000 долл.
где/„(.) = 0.
Пример 10.3.3
Возраст t (года) | Прибыль r(t) (долл.) | Стоимость обслуживания c(t) (долл.) | Остаточная стоимость s(t) (долл.) |
| 20 000 | | |
| 19 000 | | 80 000 |
| 18 500 | 1200 | 60 000 |
| 17 200 | 1500 | 50 000 |
| 15 500 | 1700 | 30 000 |
| 14 000 | 1800 | 10 000 |
| 12 200 | 2200 | 5 000 |
Определение допустимых значений возраста механизма на каждом этапе является нетривиальной задачей. На рис. 10.6 представлена рассматриваемая задача замены оборудования в виде сети. В начале первого года имеется механизм, эксплуатирующийся 3 года (на графике рис. 10.6 по оси Y откладывается возраст механизма). Мы можем либо заменить его (3), либо эксплуатировать (С) на протяжении следующего года. Если механизм заменили, то в начале второго года его возраст будет равен одному году, в противном случае его возраст будет 4 года. Такой же подход используется в начале каждого года, начиная со второго по четвертый.
1 2 3 4 5
Год принятия решения
Рис. 10.6. Схема возможной замены механизма для примера 10.3.3
Если однолетний механизм заменяется в начале второго или третьего года, то заменивший его механизм к началу следующего года также будет однолетним. К тому же, в начале 4-го года 6-летний механизм обязательно должен быть заменен, если он еще эксплуатируется; в конце 4-го года все механизмы продаются (77) в обязательном порядке. На схеме сети также видно, что в начале второго года возможны только механизмы со сроком эксплуатации 1 или 4 года. В начале третьего года механизм может иметь возраст 1, 2 или 5 лет, а в начале четвертого - 1,2,3 или 6 лет.
Решение данной задачи эквивалентно поиску маршрута максимальной длины (т.е. приносящего максимальную прибыль) от начала первого года к концу четвертого в сети, показанной на рис. 10.6. При решении этой задачи используем табличную форму записи. (Числовые данные в таблице кратны тысячам долларов.)
Этап 4.
| | | | Оптимум |
| K0 + s(f+l)-c(0 | КО) + s(f) + | s(1)-c(0)-/ | «Ч | Решение |
| 19,0 + 60-0,6 = 78,4 | 20 +80 + 80 - | 0,2-100 = 79,8 | 79,8 | |
| 18,5 + 50- 1,2 = 67,3 | 20 + 60 + 80 - | -0,2- 100 = 59,8 | 67,3 | |
| 17,2 + 30-1,5 = 45,7 | 20 + 50 + 80 - | -0,2-100 = 49,8 | 49,8 | |
| Необходима замена | 20 + 5 + 80 - | -0,2-100 = 4,8 | | |
Этап 3. |
| | | | Оптимум |
| К0-с(0 + Мг+1) | КО) + s(0 - | с(0)-/+М1) | «0 | Решение |
| 19,0-0,6 + 67,3 = 85,7 | 20 + 80 - 0,2 - | 100 + 79,8 = 79,6 | 85,7 | |
| 18,5-1,2 + 49,8 = 67,1 | 20 + 60 - 0,2 - | 100 + 79,8 = 59,6 | 67,1 | |
| 14,0-1,8 + 4,8 = 17,0 | 20 + 10-0,2- | -100 + 79,8 = 9,6 | 17,0 | |
Этап 2. |
| | | | Оптимум |
| К0-с(0 + Гз(г+1) | К0) + s(0 - | с(0)-/+гз(1) | | Решение |
| 19,0-0,6 + 67,1 =85,5 | 20 + 80 - 0,2 - | 100 + 85,7 = 85,5 | 85,5 | С или 3 |
| 15,5-1,7 + 19,6 = 33,4 | 20 + 30 - 0,2 - | 100 + 85,7 = 35,5 | 35,5 | |
Этап 1. |
| | | | Оптимум |
| К0-ф) + 6(г+1) | КО) + s{0 - | с(0)-/+6(1) | | Решение |
| 17,2-1,5 + 35,5 = 51,2 | 20 + 50 - 0,2 - | 100 + 85,5 = 55,3 | 55,3 | |
На рис. 10.7 показана последовательность получения оптимального решения. В начале первого года оптимальным решением при / = 3 является замена механизма. Следовательно, новый механизм к началу второго года будет находиться в эксплуатации 1 год. При t = 1 в начале второго года оптимальным решением будет либо использование, либо замена механизма. Если он заменяется, то новый к началу третьего года будет находиться в эксплуатации 1 год, иначе механизм будет иметь возраст 2 года. Описанный процесс продолжается до тех пор, пока не будет определено оптимальное решение для четвертого года.