Інформаційні технології та моделювання бізнес-процесів - Томашевський О.М. - 9.4. Оптимальний розподіл завдань між комп'ютерами мережі

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

Нехай на деякій поверхні задана скінченна кількість точок р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).

Приклад 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. Задача розподілу кредитних коштів банку з мінімальною величиною ризику

Нехай для кредитування банк може виділити т грошових одиниць коштів, обсяг кожної з яких становить S умовних одиниць. Відомо, що

банк має можливість кредитувати п позичальників Р1,Р2,...,Рn. При цьому для кредитування одного позичальника банк може виділити не більше одного кредиту, розмір якого може становити к грошових одиниць коштів, де k = 1, 2,...,m. Розмір кредиту і позичальник становлять відповідну величину ризику. Задача полягає в такому розподілі кредитів банку серед позичальників, за якого сумарна величина ризику була б мінімальною.

Оптимальний розподіл кредитів серед позичальників P1,P2,...,Рn визначаємо наступним чином.

треба надати позичальнику Р1. Сумарна величина мінімального ризику становить Fn(m) одиниць.

Задача оптимального розподілу інвестиційних коштів банку для фінансування проектів. Нехай для інвестування проектів банк може виділити т грошових одиниць коштів, обсяг кожної з яких становить 5 умовних одиниць. Відомо, що банк має можливість вкласти кошти у виконання n проектів P1,P2,...,Pn. При цьому для фінансування одного проекту банк може виділити не більше однієї інвестиції, розмір якої може становити к грошових одиниць коштів, де k = 1,2,...,m . В залежності від розміру вкладених коштів в той чи інший проект банк одержує відповідний прибуток. Задача полягає в такому розподілі коштів банку між проектами, при якому сумарна величина прибутку була б найбільшою.

Оптимальний план розподілу коштів банку між проектами P1, P2,…, Pn, визначаємо за наступним алгоритмом.

треба вкласти у виконання проекту Р1 .

Максимальний прибуток від розподілу коштів між проектами становить Fn (m) одиниць.

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

Нехай треба розподілити т завдань однакової складності між и

комп'ютерами К1,К2,...,Кn мережі (комп'ютери можуть мати неоднакову потужність). Відомо час розв'язування завдань на кожному комп'ютері. Задача полягає в такому розподілі завдань між комп'ютерами, щоб загальний час розв'язування завдань був мінімальним.

Резюме

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

Ключові слова

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