Решение задачи 2 (алгоритм обратной прогонки)
В предыдущем решении задачи 2 вычисления проводились последовательно: от первого этапа до третьего. Такая последовательность вычислений известна как алгоритм прямой прогонки. Этот же пример может быть решен с помощью алгоритма обратной прогонки, в соответствии с которым вычисления проводятся от третьего этапа до первого.
Алгоритмы прямой и обратной прогонки приводят к одному и тому же решению. Несмотря на то, что алгоритм прямой прогонки представляется более логичным, в специальной литературе, посвященной динамическому программированию, неизменно используется алгоритм обратной прогонки. Причина этого в том, что в общем случае алгоритм обратной прогонки может быть более эффективным с вычислительной точки зрения.
Рекуррентное уравнение для алгоритма обратной прогонки в задаче 2 имеет вид:
где для . Соответствующей последовательностью вычислений будет
Этап 3.Так как узел 7 ( = 7) связан с узлами 5 и 6 (х3 = 5 и 6) в точности одним маршрутом, альтернативы для выбора отсутствуют, а результаты третьего этапа можно подытожить следующим образом.
Этап 2.Так как маршрута (2,6) не существует, соответствующая альтернатива не рассматривается. Используя значения , полученные на третьем этапе, можем сравнить допустимые альтернативные решения, как показано в следующей таблице.
| +
| Оптимальное решение
|
|
|
|
|
| 12+9=21
| –
|
|
|
| 8+9=17
| 9+6=15
|
|
|
| 7+9=16
| 13+6=19
|
|
| Оптимальное решение второго этапа означает следующее. Если вы находитесь в узле (городе) 2 или 4, кратчайший путь к узлу 7 проходит через узел 5, а если находитесь в узле 3, кратчайший путь к узлу 7 проходит через узел 6.
Этап I.Из узла 1 имеем три альтернативных маршрута: (1,2), (1,3) и (1,4). Используя значения , полученные на втором этапе, вычисляем данные следующей таблицы.
| +
| Оптимальное решение
| =2
| =3
| =4
|
| *
|
| 7+21=28
| 8+15=23
| 5+16=21
|
|
| Оптимальное решение на первом этапе показывает, что кратчайший путь проходит через город 4. Далее из оптимального решения на втором этапе следует, что из города 4 необходимо двигаться в город 5. Наконец, из оптимального решения на третьем этапе следует, что город 5 связан с городом 7. Следовательно, полным маршрутом, имеющим кратчайшую длину, является 1-4-5-7, и его длина равна 21 км.
Пример задачи 3 «замена оборудования»
Компания планирует оптимальную политику замены имеющегося в настоящее время трехлетнего механизма на протяжении следующих 4 лет (n=4), т.е. вплоть до начала пятого года. Приведенная таблица содержит относящиеся к задаче данные. Компания требует замены механизма, который в эксплуатации 6 лет. Стоимость нового механизма равна 100 000 долл.
Возраст t (года)
| Прибыль r(t) ($)
| Ст-ть обслуживания c(t) ($)
| Остаточная ст-ть s(t)($)
|
|
|
| –
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Решение задачи 3
Определение допустимых значений возраста механизма на каждом этапе является нетривиальной задачей. На рис. 10.4 представлена рассматриваемая задача замены оборудования в виде сети. В начале первого года имеется механизм трехлетнего возраста. Можем либо заменить его (3), либо эксплуатировать (С) на протяжении следующего года. Если механизм заменили, то в начале второго года его возраст будет равен одному году, в противном случае его возраст будет 4 года. Такой же подход используется в начале каждого года, начиная со второго по четвертый.
Если однолетний механизм заменяется в начале второго или третьего года, то заменивший его механизм к началу следующего года также будет однолетним. К тому же, в начале 4-го года 6-летний механизм обязательно должен быть заменен, если он еще эксплуатируется; в конце 4-го года все механизмы продаются (П) в обязательном порядке. На схеме сети также видно, что в начале второго года возможны только механизмы со сроком эксплуатации 1 или 4 года. В начале третьего года механизм может иметь возраст 1, 2 или 5 лет, а в начале четвертого — 1,2,3 или 6 лет.
Рисунок 10.4 – Маршруты
Решение данной задачи эквивалентно нахождению маршрута максимальной длины (т.е. приносящего максимальную прибыль) от начала первого года к концу четвертого в сети. При решении этой задачи используем табличную форму записи (числовые данные в таблице кратны тыс. долл.).
Этап 4.
| | | | t
| C
| З
| Оптимум
| +s(t+1)-
| +s(t)+s(1)- -I
|
| Решение
|
| 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
| 4.8
| З
| Этап 3.
| | | | t
| C
| З
| Оптимум
| - +
| +s(t)- -I+
|
| Решение
|
| 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.
| | | | t
| C
| З
| Оптимум
| - +
| +s(t)- -I+
|
| Решение
|
| 19.0-0.6+67.1=85.5
| 20+80-0.2-100+85.7=85.5
| 85.5
| С или З
|
| 19.0-0.6+67.3=85.7
| 20+80-0.2-100+79.8=79.6
| 85.7
| З
| Этап 1.
| | | | T
| C
| З
| Оптимум
| - +
| +s(t)- -I+
|
| Решение
|
| 17.2-1.5+35.5=51.2
| 20+50-0.2-100+85.5=55.3
| 55.3
| З
| В начале первого года оптимальным решением при t = 3 является замена механизма. Следовательно, новый механизм к началу второго года будет находиться в эксплуатации 1 год. При t = 1 в начале второго года оптимальным решением будет либо использование, либо замена механизма. Если он заменяется, то новый к началу третьего года будет находиться в эксплуатации 1 год, иначе механизм будет иметь возраст 2 года. Описанный процесс продолжается до тех пор, пока не будет определено оптимальное решение для четвертого года (рис. 10.5).
Рисунок 10.5 – Последовательность получения оптимального решения
Следовательно, начиная с первого года эксплуатации механизма, альтернативными оптимальными стратегиями относительно замены механизма будут (3, С, С, 3) и (3, 3, С, С). Общая прибыль составит 55 300 долларов.
Не нашли, что искали? Воспользуйтесь поиском по сайту:
©2015 - 2024 stydopedia.ru Все материалы защищены законодательством РФ.
|