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

Приклад 9.2. Відшукаємо найкоротші шляхи від усіх точок до точки з номером 1 у такій мережі (рис.9.1).

Розв'язування. Початковий крок. Точці 1 ставимо у відповідність характеристику нуль і визначаємо характеристики точок 2, 5, 3. Ці характеристики відповідно дорівнюють 4, 15, 6. На дугах (1, 2), (1, 5), (1, 3) ставимо стрілки, спрямовані в сторону точки 1, а саму точку 1 відмічаємо символом + .

Рис.9.1. Представлення мережі у вигляді графу

Крок 1. Беремо точку 2 і визначаємо характеристику сусідньої до неї точки 4. Вона дорівнюватиме 4 +18 = 22 . Тому на дузі (2, 4) ставимо стрілку, спрямовану до точки 2, а точку 2 відмічаємо символом + .

Беремо точку 5 і визначаємо характеристики її сусідніх точок 4, 6, 7. Вони відповідно складатимуть 25, 21, 23. Нова характеристика точки 4 дорівнює 25. Оскільки 25 > 22, то характеристика точки 4 залишається рівною 22. На дугах (5, 6) і (5, 7) ставимо стрілки, спрямовані до точки 5, а точку 5 відмічаємо символом + .

Далі беремо точку 3 і визначаємо характеристику її сусідньої точки 6. Вона становить 13, але для точки 6 раніше вже була обчислена характеристика, яка дорівнює числу 21. Тому, оскільки 13 < 21, за характеристику точки 6 приймемо 13, а стрілку на дузі (5, 6) замінюємо на стрілку на дузі (3, 6), спрямовану до точки 3, після чого точку 3 відмічаємо символом + .

Крок 2. Беремо точку 4 і визначаємо характеристики її сусідніх точок 5, 7, 9. Вони відповідно рівні 32, 30, 36. Раніше обчислені характеристики точок 5 і 7 становлять, відповідно, 15 і 23. Оскільки 32 > 15 і 30 > 23 , то характеристики точок 5 і 7 залишаємо без змін, тобто 15 і 23 відповідно. Після цього на дузі (4, 9) ставимо стрілку, спрямовану до точки 4, яку відмічаємо символом + .

Беремо точку 7 і визначаємо характеристики її сусідніх точок 4, 8, 9, 10. Вони відповідно дорівнюватимуть 31, 29, 30, 32. Але характеристики точок 4 і 9, які були обчислені раніше, є 22 і 36 відповідно. Оскільки 31 > 22, а 30 <36, то характеристика точки 4 залишається рівною 22, а характеристику точки 9 замінюємо на 30. Відповідно до цього стрілку на дузі (4, 9) замінюємо стрілкою на дузі (7, 9), спрямованою до точки 7. Далі на дугах (7, 8) і (7, 10) ставимо стрілки, спрямовані до точки 7, а саму точку 7 відмічаємо символом + .

Далі беремо точку 6 і визначаємо характеристики її сусідніх точок 5 і 8. Вони, відповідно, становлять 19 і 23. Раніше обчислені характеристики цих точок були, відповідно, 15 і 29. Оскільки 19 > 15 , а 23 < 29 , то характеристика 15 точки 5 залишається без зміни, а характеристику точки 8 замінюємо на 23. Тому стрілку на дузі (7, 8) замінюємо стрілкою на дузі (6, 8), спрямованою до точки 6. Точку 6 відмічаємо символом + .

Крок 3. Беремо точку 9 і визначаємо характеристики її сусідніх точок 4, 10 і 12. Вони, відповідно, дорівнюють 44, 32 і 42. Оскільки раніше обчислені характеристики точок 4 і 10 - це значення 22 і 32 відповідно, то маємо: 44 > 22 і 32 = 32 . Тому характеристики точок 4 і 10 залишаємо без змін. На дузі (9, 12) ставимо стрілку в напрямку до точки 9, після чого точку 9 відмічаємо символом + .

Розглянемо далі точку 10 і визначимо характеристики її сусідніх точок 8, 9, 11, 12. Вони, відповідно, будуть 38, 34, 44, 47. Для точок 8, 9, 12 раніше вже були обчислені відповідні характеристики, а саме: 23, 30, 42. Тому, оскільки 38 > 23, 34 > 30 і 47 > 42, характеристики точок 8, 9, 12 залишаємо без змін, а на дузі (10, 11) ставимо стрілку в напрямку до точки 10. Точку 10 відмічаємо знаком + .

Беремо точку 8 і визначаємо характеристики її сусідніх точок 7, 10 і 11. Вони, відповідно, дорівнюють 29, 29 і 31. Раніше для цих точок уже були обчислені характеристики: 23, 32 і 44 відповідно. Оскільки 29 > 23 , а 29 < 32 і 31 < 44 , то характеристика точки 7 залишається без зміни, характеристики точок 10 і 11 заміняться, відповідно, на 29 і 31, а стрілки на дугах (7, 10) і (10, 11) заміняться стрілками на дугах (8, 10) і (8, 11), спрямованими до точки 8. Точку 8 відмічаємо символом + . Оскільки при цьому змінилася характеристика точки 10, яка вже була відмічена символом + , то перераховуємо характеристики її сусідніх точок 9, 11, 12. Одержимо, відповідно, значення 31, 41, 44. Однак, для цих точок раніше вже були обчислені відповідні характеристики 30, 31 і 42. Оскільки 31 > 30, 41 > 31 і 44 > 42, то характеристики точок 9, 11 і 12 залишаємо без змін.

Крок 4. Розглянемо точку 11 і визначимо характеристики її сусідніх точок 10 і 12. Вони дорівнюватимуть, відповідно, 43 і 44. Але раніше обчислені характеристики цих точок, відповідно, дорівнюють 29 і 42. Оскільки 43 > 29 і 44 > 42 , то старі характеристики цих точок залишаємо без змін. Точку 11 відмічаємо символом + .

Нарешті, беремо точку 12, для її сусідніх точок 10 і 11 характеристики, відповідно, дорівнюють 57 і 55. Раніше обчислені для них характеристики, відповідно, становлять 29 і 31. Оскільки 57 > 29 і 55 > 31, то обчислені раніше характеристики точок 10 і 11 залишаємо без змін. Точку 12 відмічаємо символом + .

Отже, ми одержали розв'язок задачі, який показаний на графі стрілками (рис. 9.2).

Рис.9.2. Розв'язок задачі 9.2

Оптимальні шляхи можна зобразити, вказуючи спочатку значення характеристики вершини (відстань до точки 1) і відповідний шлях:

Перевагою цього алгоритму є те, що він у порівнянні з іншими алгоритмами має більшу швидкодію.

9.3. Задача розподілу кредитних коштів банку з мінімальною величиною ризику

9.4. Оптимальний розподіл завдань між комп'ютерами мережі