Беллман Р. Прикладные задачи динамического программирования (2013) (1246769), страница 26
Текст из файла (страница 26)
Следовательно, можно найти ~м„(С) для всех допустимых значений Е В зависимости от наших пока неопределенных решений на предшествующих ша~ах мы могли бы прийти к последнему шагу с чем у~одно — от машины, купленной в предыдущий период и прослужившей один год, до очень старой машины, с которой начинался процесс. Построив функцию Ум,(Г), мы можем использовать уравнение (3.27) для определения функции ум, 1(1). Продолжая эту процедуру, получим функцию У,(1), оптимальный доход процесса, начавшегося в 1-й год.
Выписывая политику, использованную при максимизации (3.27), мы получим политику замены, которая обеспечивает максимальную прибыль. 18. ПРИМЕР Решим следующий простой пример. Рассмотрим пропесс, длящийся 10 лет. Пусть затраты на замену машины, доход, затраты на содержание машин, произведенных в течение каждого иэ этих 1О лет в зависимости от возраста машин, равны: 5 Р. Быйыыыы, С.
Дрейфус 162 сглаживании и состлвлииив расписаний 1гл. гп Машина, произведенная в У-й год Возраст машины 0 1 2 3 4 5 6 7 8 9 Доход ...... 90 85 80 75 ?О ?О 70 60 60 60 Затраты на содержание ... 20 20 25 25 30 30 35 40 45 50 Затраты на замену ...... 200 220 240 250 255 260 265 270 270 270 Машина, произведенная во 2-й год Возраст машины..
0 1 2 3 4 5 6 7 8 Доход ........ 100 90 80 75 70 65 65 65 6о Затраты на содержание ....... 15 20 20 25 25 30 30 35 35 Затраты на замену 200 220 240 250 255 260 265 270 270 Машина, произведенная в З-й год Возраст машины.... 0 ! 2 3 4 5 6 7 Доход ............ 110 105 100 95 90 80 70 60 Затраты на содержание .
15 15 20 20 25 25 30 30 Затраты на замену .... 200 220 240 250 255 260 265 270 Машина, произведенная в 4-й год Возраст машины.......... 0 ! 2 3 4 5 6 Доход ................ 115 11О 100 90 80 70 60 Затраты на содержание..... 15 15 20 20 25 25 30 Затраты на замену ........ 210 215 220 225 230 235 240 Машина, произведенная в 5-й год Возраст машины....... 0 1 2 3 4 5 Доход.............. 120 115 115 110 105 100 Затраты на содержание .. 10 10 15 15 20 20 Затраты на замену ..... 210 215 220 225 230 235 Машина, произведенная в 6-й год Возраст машины.......
0 1 2 3 4 Доход.............. 125 120 110 105 110 Затраты на содержание .. 10 1О 1О !5 15 Затраты на замену ..... 210 220 230 240 250 ПРИМвР Машина, произведенная в 7-й год Возраст машины....... 0 1 2 3 Лоход.............. 135 125 110 105 Затраты на содержание .. 10 1О 1О 10 Затраты на замену ..... 210 220 230 240 Машина, произведенная в 8-й год Возраст машины....... 0 1 2 Лоход.............. 140 135 125 Затраты на содержание .. 5 1О 1О Затраты на замену .....
220 230 240 Машина, произведенная в 9-й год Возраст машины ........ 0 1 Лоход . '.............. 150 140 Затраты на содержание.... 5 10 Затраты на замену....... 220 225 Машина, произведенная в 10-й год Возраст машины........ 0 Лохах ........ 155 Затраты на содержание... 5 Затраты на замену...... 220 Кроме того, мы начинаем процесс, имея машину, называемую исходной машиной, прослужившую, скажем, уже три года, со следующими характеристиками: Возраст ..... 3 4 5 6 7 8 9 10 11 12 Лоход ......
60 60 50 50 50 40 40 40 30 30 Затраты на содержание ... 55 55 55 60 60 60 60 65 ' 65 70 Затраты на замену ...... 250 260 270 280 280 290 290 300 300 310 Построим таблицу длв тт«(!). Чтобы вычислить ~щ(1), сравним разницу между доходом и затратами на содержание старой машины (машины, произведенной в 9-9 год и прослужившей один год) с затратами на ее замену*). Получим: (Р: 155 — 5 — 2251 (1) х ~к: 140 — 10 ~=130, (3.28) «) Точнее, затратами на замену старой машины с учетом дохода и расхода на содержание новой машины. (Прин.
ред.) 6' !54 сглаживании и составлвнив васпислний [гл, и ГР: 155 — 5 — 2401 Хта(2)=!пах[К', !25 !О ~=1!5. (3.29) Заполним теперь всю таблицу значений функции гта(!) (см. таблицу 3.1). Таблица 3.1 /то (П Политика /то П) Политика !30 115 95 85 80 6 ЗО 7 30 8 30 9 1О 12 40 К К К К К К К К К К Вычислим первые два значения 7а(!) и составим полную таблицу, определяющую политику. Лля удобства вычислений положим а = 1, хотя в действительности а следует взять достаточно малым, чтобы отразить как неопределенность наших сведений относительно будущего, так и обесценивание доллара. Г Р: 150 — 5 — 230 + 130 "! У,(!)= ' ~~ ., !35 10+!!5 1=240, ГР: 150 — 5 — 230+1301 (2)=шах 1К'.
1 0 — 10+Оп (3.30) Таким же образом, используя уравнение (3,27), имеем ~аблицу 3.2 доходов для нашей гипотетической машины. Проследим, как получается последнее число ~т (3) = 310, ибо оно и означает суммарный доход, которого можно добигься при оптимальной политике, Мы начинаем в первый год, имея исходную машину, которую можно заменить или сохранить. Если мы заменим исходную машину, затратив 250 долларов, то новая машина (произведенная в первый год) даст 70 долларов чистого дохода за первый год службы плюс будуший доход (490 долларов), как машина, прослужившая один !од и мы должны сохранить старую машину. Вряд ли можно ожидать, что оптимальной окажется политика, предписывающая покупку новой машины на последнем шаге процесса.
Аналогично 165 ПРИМВР Таблица 3.' /а 11) ~ Политика ! с Политика СС~С Поли~ила !а 09 Политика ~ /л ГП Политика ул н) 435 385 370 285 К К К К 2 3 б с ( тли) ( политика 1 с С 11) с Ст Ш Политика Политика 3 310 ! 440 К 2 425 К 5 280 490 285 к К и начинаюшая второй год работы. Поэтому чистый выигрыш равен 310 долларам. Если мы сохраним исходную машину, мы получим в этот год на 5 долларов больше и, получив ва все будущие годы 285 долларов, будем иметь общий доход в 290 долларов. Так как 310 ) 290, мы решаем купить новую машину. Если мы выбрали такую политику, то, очевидно, второй год мы начнем, имея машину, прослужившую олин год, и, как видно иа таблицы, ее надо сохранить.
1 2 3 6 7 8 11 240 195 175 165 75 ?О 60 25 25 465 295 265 245 240 210 К К К К К К К К Р К К К Р Р Р ! 2 3 4 5 6 310 275 260 !45 125 110 !05 75 К К К Р К Р Р Р 385 360 2!5 !90 !75 !70 145 К К К К Р Р Р 166 сГлАжиВАние н составление РАсписАниИ 1гл. н! Таблица 33 Политика ! Доаод Год Р— 13 К 6 К К Р В качестве побочного результата нашего анализа мы получаем, что если бы нам пришлось сохранить исходную машину в течение первого года, например, из-за отсутствия достаточного капитала для замены, то оптимальная политика состояла бы в сохранении старой машины в течение пяти лет. Эта политика как раз и дает прибыль в 290 долларов. Так как чистый выигрыш от замены старой машины на новую составляет 20 долларов, владелец машины должен решать, будет ли экономически выгодным вкладывать 250 долларов ради выигрыша 20 долларов.
Вычисления такого рода по сравнению всех вариантов и выбору наилучшего графика замены легко можно сделать вручную за час с небольшим. Вдобавок эти вычисления снабдят нас некоторой дополни- тельноИ ценноИ информациеИ. При машинном счете на один этап понадобится несколько секунд. 19. ДРУГИЕ ПОСТАНОВНИ ЗАДАЧИ Описанный здесь метод решения является достаточно общим и допускает большое разнообразие постановок задачи о вамене оборудования.
Для создания математической модели Третий год мы начнем, имея машину, проработавшую два года, и, следуя таблице, мы снова сохраняем ее. Возвращаясь теперь к исходному моменту, мы видим, что оптимальная политика состоит в покупке новой машины в первый год, сохранении ее в течение пяти лет с последующей заменой ее на новую, которую следует сохранять уже до конца процесса. Лля проверки наших выводов мы можем привести доходы от этой политики, сведенные в таблицу 3.3. 167 19) дввгив постановки задачи нет надобности делать кзкие-нибудь нереальные предположения. Нзпример, если желзтельно определить функцию дм(т,х), определяющую стоимость замены машины возраста 1 машиной возраста х в Ф-й год, то в рассмотрение может быть включена третья возможность — покупка использованной машины.
Рекуррентное соотношение в этом случае имеет вид Покупка новой машины гл (О) — пл (0) — ох Я+ а~х,-~ Покупка машины возраста х Лч(1) = шах гн(х) — пл(х) — дм(Х, х)+ а~х 1(х+ 1) Сохранение старой машины гч(Г) — ттл (Г)+ пУмф~ (Г+ 1) Если мы допускаем для х значение 0 и сх(1)=йх(У, О), то юкупку новой машины можно считать частным случаем покупки машины возраста х. Мы можем включить в рассмотрение также возможность капитального ремонта, если предположим, что машина возраста 1, прошедшая капитальный ремонт, имеет характеристики машины возраста г', р(д Здесь т есть функция срока службы Г, а также усилий, затрачиваемых на ремоип Лля того чтобы возмоткность ремонта включить в рассмотрение самым общим образом, увеличим размерность задачи.
Введем функцию уя,(тп Гя) — величина суммарного дохода на год М от машины возраста Гп прошедшей последний капитальный ремонт после гя лет службы при оптимальной политике в оставшейся части процесса *). Теперь мы должны определить все наши издержки в зависимости как от возрастз машины уи так и времени я) Точнее, функпия ух(ÄÄ) есть величина суммарного дохода за период, начинающийся с года У, при наличии а начале этого года машины возраста Г„прошелшей последний капитальный ремонт после г, лет службы, при оптимальной политике за весь указанный период.
(1Урилг. ред.) 168 сглаживания и составлзниз глсписьний [гл. ш последне~о кзпитзльного ремонтз. Сделав это, мы сможем написать с помощью аналогичного метода рекуррентное соотношение Р: гч(0, 0) — пч(0, 0) — см (Сн Ся) + + аУм ч ~ (1, 0) К: гл (8ь гт) — им (гь 1,) + +аул~+~(с -~-1, т) 0 гл (Е1 Е!) нл (~1 13) — О, (гь гя)+ АД вЂ” (-1, С,) Лг(сь гя)=шах (з.зз) где Оь (Сь Ся) — затраты на капитальный ремонт в год Лг машины воараста Ен прошедшей последний капитальный ремонт в возрасте 1,. Метод численного решения этой задачи аналогичен методу, изложенному в й 17, за исключением того, что теперь мы вычисляем последовательность функций двух переменных.
Такие вычисления для значений 1, и г„ допустимых в данной задзче, легко проводятся на вычислительной машине вне какой бы то ни было зазисимосги от длины анализируемого процесса. Можно было бы сформулировать эту задачу в рамках стохастической модели, когда максимизируется ожидаемый доход. В такой модели следует внести вероятность аварии как функцию возраста машины, характера ее использования и подобного рода других факторов. Задача состоит в отыскании политики замены, максимизирующей некоторый критерий предпочтения. Задачи такого типа являются частными случаями марковских процессов решения, рассматриваемых в главе !Х. Мы увидим, что если с помощью метода функциональных уравнений установлено существование некоторых устойчивых или асимптотически устойчивых политик, то мы можем отказаться от функционзльных уравнений и использовзть другие методы для получения приближенных решений.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
