Беллман Р. Прикладные задачи динамического программирования (2013) (1246769), страница 63
Текст из файла (страница 63)
Тогда, обращаясь к определению ~,(1, 1), получим рекуррентное соотношение 400 мднкоаскив пнопвссы РГ ШГния 1гл х! Это уравнение задает ожидаемые издержки при каждом допустимом решении в виде суммы непосредственной стоимости и ожидаемых издержек оптимального производства оставшихся шин после выполнения решения и дает возможность выбора наилучшей альтернативы. Задача решается следуюшим образом: сначала вычисляется стоимость одной шины 71 !1, /), затем значение г1 ишшльзуется для вычисления уя с помоптью уравнения !11.18), ге в свою очередь используется для вы шсления 74 и т.
д. !8. ЧИСЛОВОЙ ПРИМЕР 7!ля иллюстрации выберем следующие гипотетические числа; =оО стоимость устройства.......... с, убытки, связанные с производством одной бракованной шины.........., г, стоимость труда но остановке машины .. с, убытки из-зз потери производственного ВРЕМЕНИ . . . .
. , . . . . . . - Ст Вероятности выпускз шины без дефектов Номер пронзве- 0 1 2 З денной шины к 4 5 6 04 1 02 0 Вероятность р„! 0,9 ! 0,6 0,6 Последовательные итерации рекуррентного соотношения !1!.18) дают следующие результаты: 1. Для пронессов производства более чел1 !о шин оптимальная политика сходится к !а) замене любого устройства, .которое произвело шесть шин, !б) замене другого устройства в то же самое время, если оно иаготонило пять или более шин, когда машина остановлена для предварительной замены или же из-за неисправности. 2.
Издержки на производство каждой дополнительной шины сходятся к 16,94, после того как произведено примерно 47 шин. 191 двтгой пянмеР 19. ДРУГОЙ ПРИМЕР Таблица !!4 Средняя стоимость шины: 6,364. Политикж г а ! ь л О )Р— ! Р— 1 Р— 2 Р— 2 Р— !)Р— !)/~ — ! !Р— 1~а — ! 1 Р— 1)Р— 1)Р— 2 Р— 2 2 )Р— 2 Р— 2 Р— 3)Р— 3 3 (Р— 2(Р— 2 Р— 3(Р— 3 4 ) l2 — 1( Р— 1 ! Р— 3~ )Р— 3 Р— 3 5 Р— 1!гт' — 1(Р— 1)Р— 3 Р— 2 6 )Р— 1 Р— 1 12 — 1)12 — 2 Р— 2 Р— 2 А' — 2 1 — означает производнгь, а если сломалось одно из устройств, то заменить только это устройство.
2 — означает производить, а если неиспрзвно более новое устройство, то заменить оба; если более старое, то заменить только его. 3 — означает производить, а если одно из двух устройств неисправно, то заменить оба. 1 — означает немедленную замену более старого устройства. 2 — означает немедленную замену обоих устройств. 1 — число шин, произведенных ранее первым устройством. ! — число шии, произведенных ранее вторым устройством. Здесь Р— Лля того чтобы показать, что оптимальная политика не обязагельно будет такой простой, снизим стоимость нового устройства с оО единиц до 1О и вычислим новые ожидаемые издержки, а также опгимальную политику. (См.
табл. 11.4.) МАРКОВСКИЕ ПРОЦЕССЫ РЕШЕНИЯ [Гл. х! 402 Как видно из приведеннои выше таблицы, мы зеперь следуем в корне отличной политике. Политика, полученная итерацией уравнения (11.18), не имеет уже простой формы: заменять более старое устропство, когда оно произвело лт шин, и одновременно заменять другое устройство, если оно произвело более чем и шин.
В действительности использование какоя-либо политики такого типа даст средние издержки на шину, превышающие 6,364. Каждыя из указанных выше числовых расчегов требуег только однои минуты машинного времени при работе на машине Джонниак. 20. ЗАДАЧА О ЗАМЕНЕ АВТОМАШИНЫ Метод Ховарда дает иной подход к задачам этого типа. Полезгю проследить, как с его помощью формулируется и решаегся задача о замене. Лля того чтобы продемонстрировать эти идеи, рассмотрим задачу замены автомашины за временной интервал в деся1ь лет. Мы условимся анализировать нашу текущую ситуацина каж.ые три месяца и в этот момент принимать решение о сохранении имеющейся автомашины нли о ее продаже.
Состояние системы 1 описывается сроком службы машины в единицах времени, равных трем месяцам; г може~ принимать значения от 1 до 40. Чтобы ограничи~ь число состояний, автомашины возраста 40 будут считазься навсегда имеющими эгот возраст (машина рассматривается как в основном изно~иенная). В каждом состоянии имеются следующие альтернативы: первая альтернатива, 1=1, сохранить имеющуюся машину на следующий квартал; другие альтернативы, л) 1, купить машину возраста Уг — 2, где л — 2 не более 39.
Тогда мы имеем сорок состояний с сорока одной альтернативой в каждом состоянии, так что всего имеется 41'а возможных политик. Примем слелующие обозначения: С вЂ” закупочная цена машины возраста 1, Тг — продажная цена машины возраста 1, Е; — ожидаемая величина эксплуатационных расходов на машину возраста 1, пока она не достигнет возраста 1+ 1, р; — вероятность того, что машина возраста 1 не потребует до возраста 1+ 1 слишком больших издеракек на ремонт, 20) влдлчл о злмщщ лвтомлшипы Определенные выше вероятное~и с необходимостью ограничивают число состояний.
Машина любого возраста, обладающая безнадежными поломками, немедленно приписывается к состоянию 40. Естественно, Р,» — О. Основными уравнениями, управляющими системой, когда она находится в 1-и состоянии, являются следующие: если !а=1 (т. е, сохраняется имеющаяся машина), то У+ оа = Ег т Ргоы~ + (! — Р~) о»о Если же т) 1 (машина обменивается на машину возраста и — 2), то у+и,= Т, — С», — Е»»+р» сп»,+(1 — Р„,)пы. Нетрудно переписать эти урзвнения в наших прежних обозначениях. Например, д,"= — Е; при я=1, /=1+ 1 р; = ! — Р; /=40 при (г=1, 0 при других / йч = Т; — С», — Е„, и ри lг > 1, » /=lг — 1 /=40 при А) 1.
прп других / Р»-я Ргт = ! Р»-я 0 Реальные данные, использованные в задаче, приведены в таблице 11.6 и на графике, изображенном на рис. 89. Разрывы в функциях издержек и продажных цен введены для того, чтобы учесть характерные годовые эффекты. Задача замены автомашины была решена методом, использующим системы уравнений, за семь итераций. Последовательности политик, средних выигрышей и переходных значениИ приведены в таблицах 11.6 — 11.8. Оптимальная политика, полученная при седьмой итерации, заключается в следующем. [гл.
хч 404 мьвкозскив пиоцвсгы Рвшзния Если вы имеете машину возраста болыпего, чем '/, года, но меньшего, чем 6'/, лет, то сохраните ее. Если вы имееге мзшину любого другого возраста, обменяйте ее на т.рехлетнюю машину. Это, по-видимому, вполне согласуется с нашими интуитивными представлениями относительно экономики владения автомзшиной. Отметим, что в случзе, если мы собираемся АЯ7 й д IУ /агж Ф' аз тгдиаУю а Рис.
89. данные задачи о замене автомашины. произвести обмен, эта программа на любой итерации предписывает заменять старую машину машиной, возраст которой не зависит от возраста имеюшейся машины. Это именно тот результат, который подсказывается логикой ситуаций. Если мы будем следовать нашей опгимальной политике, то мы сохраним машину, пока она не прослужит 6'/, лет, а затем купим машину трех лет.
Однако допустим, что когда нашей машине исполнилось 4 года, некто предложил обменять на нее свою машину возраста 1 год за сумму, равную а. Следует ли нам принять его предложение? Чтобы ответить на этот вопрос, мы должны посмотреть на переходные значения. На каждой итерации в целях упрошения вычислений значение в состоянии 40 было положено равным нулю. В таблице 11.8 даны также значения прн наилучшей политике, когда 405 201 ЗАДАЧА 0 ВАМВНВ АВТОК!АШИПЫ Таблица Данные задачи е замене') Ожндаень|е екснауасацнонные расходы е,.
Продажное цена Т! Закунаенаа цена с,. Воарасх н пе- риодах а Зероясносеь Р, ') Бены даны в долл арак. 0 ! 2 3 4 6 7 10 1! 12 13 14 15 16 17 18 19 20 21 22 23 24 2о 26 27 28 29 ЗО 31 32 33 36 37 38 39 40 2000 1840 1680 1560 1300 1220 1150 1080 900 840 780 730 600 560 520 480 440 420 400 380 360 345 330 315 300 290 280 265 250 240 230 220 210 200 190 180 170 160 150 140 !30 1600 1460 1340 1230 1050 980 910 840 710 650 600 550 480 430 390 360 330 310 290 270 255 240 225 210 200 190 180 !70 160 150 145 140 135 130 120 115 !10 !05 95 8? 80 50 53 56 59 62 65 68 71 75 78 81 84 87 90 93 96 100 1ОЗ 1Об 109 112 115 118 12! 125 !29 133 137 141 145 150 155 160 167 175 182 190 205 220 235 250 1,000 0,999 0,998 0,997 0,996 0,994 0,991 0,988 0,985 0,983 0,980 0,975 0,970 0,96о 0,960 0,955 0,950 О 945 0,940 0,935 0,930 0,925 0,919 0,9!О 0,900 0,890 0,880 0,865 0,850 0,820 0,790 0,760 0,730 0,660 0,590 0,5!О 0,430 0,300 0,200 0,100 0 их копскпт.
прот!ясса! ртштппя !тл, хт Таб чпца 116 Результаты по задаче о замене автомашины *) Итерация ! И терацин 2 Итерация 3 Сне»ва- нне выигрыш — 493,39 выигрыш — 432,44 выигрыш — шГЬОО решение ~ значение ренгеиие ~ значение значение решение 1 ! Купитьзб 1373,61 1380,00 1260,00 1150,00 1036,63 939,95 847,60 760,00 695,44 Купить 19 » 19 ъ 19 Сохранить Купить 19 Сохраггить » » » Зб ~ 125З,61 36 1143,61 36 963,61 36 893,61 36! 823,61 36 753,61 36 623,61 36 56ч,н1 36 513,61 36 463,61 36 393„61 Зб 343,61 2 3 4 б 7 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 ъ 36 » 36 » 36 ъ 36 » 36 » Зб » 36 Сохраним 303,61 273,61 243,61 223,61 203,61 183,61 ! 68,61 875,93 801,00 727,97 бо8,21 592,45 529,72 469,00 411,56 355,95 306,04 260,81 218,18 175,58 140,28 110,64 83,61 54,90 33,00 15,00 0,00 25 26 27 28 29 ЗО 31 32 33 34 35 '36 37 38 39 40 в) Цены в таблицах 115, 11.6, 1!.? даны з долларах.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
