Розділ «9. Додаткові економічні задачі динамічного програмування»

Почнемо знаходити умовно оптимальні рішення на кожному кроці, починаючи з четвертого. При цьому використаємо позначення: Е - старе обладнання експлуатується, З - старе обладнання замінюється на нове. Результати розв'язування помістимо в таблиці 9.2.-9.5.

Таблиця 9.2. Результати розв'язування прикладу 9.1. Крок 4

Таблиця 9.3. Результати розв'язування прикладу 9.1. Крок 3

Таблиця 9.4. Результати розв'язування прикладу 9.1. Крок 2

Таблиця 9.5ю Peзyльтaти poзв'язyвaння пpиклaдy 9.1. Kpoк 1

Послідовність отримання оптимального розв'язку є такою. На початку першого року оптимальним розв'язком при t = 3 є заміна обладнання (табл.9.5). Отже, на початок другого року обладнання матиме вік один рік. При t = 1 на початку другого року оптимальним розв'язком буде або експлуатація обладнання, або його заміна (табл.9.4). Якщо на початок другого року прийняти рішення продовжити експлуатувати обладнання, то на початок третього року воно матиме вік два роки. При t = 2 на початку третього року оптимальним розв'язком буде експлуатація обладнання (табл.9.3). Тому на початок четвертого року обладнання матиме вік три роки. При t = 3 на початку четвертого року оптимальним розв'язком буде заміна обладнання (табл.9.2). Отже, в цьому випадку, починаючи з першого року, оптимальною стратегією є: З, Е, Е, З.

Якщо на початок другого року прийняти рішення замінити обладнання, то на початок третього року обладнання матиме вік один рік. При t = 1 на початку третього року оптимальним розв'язком буде експлуатація обладнання (табл.9.3). Тому на початок четвертого року обладнання матиме вік два роки. При t = 2 на початку четвертого року оптимальним розв'язком буде експлуатація обладнання (табл.9.2). Отже, тепер, починаючи з першого року, альтернативною оптимальною стратегією є: З, З, Е, Е.

В обох випадках загальний умовний прибуток складає 55,3 тис. у.о.

9.2. Задача визначення найкоротших шляхів в транспортних мережах

Розглянемо задачу про визначення найкоротшої відстані від будь-якого пункту (вершини) до інших у заданій транспортній мережі.

Нехай на деякій поверхні задана скінченна кількість точок р1, p2,…,pn, які з'єднані дугами (зв'язками) (рi, pj), що не перетинаються. Сукупність точок і дуг, які їх з'єднують, називатимемо мережею. Мережу будемо називати достатньо зв'язною, якщо для будь-яких двох точок існує шлях (сукупність вершин і дуг, що їх з'єднують), по якому можна пройти з однієї точки в іншу. При цьому, дві точки мережі називатимемо сусідніми, якщо існує дуга, що їх з'єднує.

Постановка задачі. Нехай задана достатньо зв'язна мережа, кожній дузі якої, що виходить із точки рі входить у точку pj, поставлене у відповідність деяке дійсне невід'ємне число lij - її довжину, причому lij = lji. Треба визначити найкоротші шляхи в мережі від довільної точки до всіх інших і вказати відповідні їм відстані.

Для розв'язування задачі використаємо метод динамічного програмування, згідно з яким будемо відшукувати найкоротші шляхи не від фіксованої точки до всіх інших, а найкоротші шляхи від усіх інших точок до фіксованої (заданої) через сусідні точки. Дугу, що міститься в найкоротшому шляху, позначатимемо стрілкою в напрямку до фіксованої точки. Вершини мережі позначатимемо кружечками (цифра всередині кружечка вказує номер точки), а в дужках біля них записуватимемо найкоротші відстані від цих точок до фіксованої точки. Відповідні найкоротші відстані називатимемо характеристиками точок.

Нехай

Алгоритм розв'язування задачі. Алгоритм складається з початкового кроку та загального, що повторюється m -1 разів.

Початковий крок. Біля кружечка, що позначає точку Pi , записуємо нуль - характеристику цієї точки, оскільки відстань від точки Pi до неї самої дорівнює нулю. Визначаємо сусідні з Pi точки і біля кружечків, якими позначені ці точки, записуємо їх характеристики, тобто 0 + lij, якщо Рj є сусідньою точкою, а на дугах ставимо стрілки, спрямовані в сторону точки Pi . Після цього відмічаємо точку Pi символом + , який означатиме, що операція над цією вершиною завершена.

Загальний крок. Припустимо, що ми вже виконали г кроків: знайшли характеристики всіх точок, найменша кількість дуг до яких від фіксованої

характеристики сусідніх із нею точок (крім точки рir і змінюємо при потребі їхні характеристики і напрям стрілок.

Якщо ж при визначенні характеристик сусідніх із Рir точок виявиться, що характеристика якоїсь сусідньої точки раніше не обчислювалася, то на відповідній дузі, що виходить із цієї точки, ставимо стрілку в напрямку до точки рir.

Нарешті, відзначимо, що ( r +1) - ий крок виконуватимемо доти, доки послідовно не будуть перебрані всі вершини мережі, тобто точки р(г) (і = 1,2,..., k).