Задачі вибору найкоротшого шляху

Нехай буде задана мережа ( рис.7.2.). кожній орієнтованій дузі якій відповідає визначена відстань. Необхідно знайти найкоротший шлях від 1-го вузла мережі у її заданій j-й вузол. До цієї задачі відомої в дослідженні операцій як задача вибору найкоротшого шляху зводиться такі практичні задачі як задача про заміну обладнання, задача про календарне планування комплексу робіт та ін.

Як правило. У мережі виділяють один вузол, який є кінцевим (пункт, або станція призначення, стік). Задача полягає у пошуку найкоротшого шляху у цій кінцевий вузол (на рис. 7.2 кінцевим є вузол № 8) деякого іншого вузла мережі (наприклад, з вузла № 1).

Рис. 7.2 Мережа пунктів

Величина с_ij визначає відстань від і-го вузла мережі до j-го вузла цієї мережі.

Величини с_ij можуть вимірюватися в одиницях, відмінних від одиниць довжини. Так, наприклад, с_ij може являти собою вартість проїзду від і-го до j-го вузла мережі. Тоді задача полягає в пошуку шляху мінімальної вартості. Величина с_ij може також визначати час переїзду від і-го до j-го вузла мережі. При цьому необхідно зробити шлях з мінімальною тривалістю переїзду.

При розв’язані прикладних задач, які зводяться до задачі вибору найкоротшого шляху, часто зустрічаються ситуації, коли с_ij¹ с_ji. Крім цього, як правило, не виконується так звана нерівність трикутника: с_ij ≤ с_ik + c_kj для усіх або деяких індексів i, j, k.

Існують мережі, які мають цикли кожний з яких являє собою замкнений шлях (шлях, що виходить з деякого вузла мережі, та який в нього повертається). Так, у мережі, яка подана на рис. 7.2., багато циклів один з яких містить вузли №№ 2, 3, 5, 6 і 7. Як правило, в задачах дослідження операцій значення с_ij позитивні та загальна “довжина” циклу теж позитивна. Тобто, розвязання задачі вибору найкоротшого шляху не може мати циклів.

Припустимо, що для мережі, яка подана на рис. 7.2, необхідно знайти найкоротший шлях від вузла № 1 (джерело) до вузла № 8(стік). Встановимо зв'язок цієї задачі з класичною транспортною задачею.

Розглянемо транспортну задачу з проміжними пунктами, мережа якої подана на рис 7.2. При цьому припустимо, що а) у вузлі № 1 є надлишкова одиниця товару; б) у вузлі №8 є одиниця нестачі товару; в) вузли №№ 2-7 є проміжними пунктами з нульовими чистими запасами. Необхідно розробити план перевезень товару між вузлами мережі, який при мінімальних транспортних затратах дозволить у кожному пункті підтримувати нульовий чистий запас товару.

Вважаємо, що кожній орієнтованій дузі мережі відповідає змінне моделі х_ij, що являє собою кількість товару, яка повинна бути відправлена з і-го пункта (складу) у j-й.

Для кожного проміжного пункту вводимо х_кк з відповідним йому коефіцієнтом с_кк = 0 у цільовій функції, а величину чистого запасу позначимо через Т_к. Якщо множина пар індексів (і, j), яка відповідає орієнтованим дугам мережі (рис.7.2), позначити І, то задачу. Яка розглядається, можна записати так:

Транспортна таблиця для задачі (4.4) аналогічна транспортній задачі (див табл.7.3).

Табл. 7.4

Транспортна таблиця для задачі пошуку найкоротшого шляху

Розглянемо декілька прикладів, які пов’язані із задачею вибору найкоротшого шляху.

Приклад 7.2. Розглянемо задачу, яку в літературі з дослідження операцій називають задачею про заміну обладнання.

Припустимо, що деяке транспортне агентство розробляє план аренди транспортного обладнання на період діяльності (n-1) років, де n>1. Агенство може виконувати свої обов’язки щодо перевезення вантажів , коли візьме в аренду транспортну одиницю на початку j- року, де Якщо j < n, то на початку j-го року агентство замінює цю транспортну одиницю нового та експлуатує її до початку k-го року, де k ≤ n і т.д. Величина затрат с_ij на обладнання, яке взяте в оренду на початку i-го року і яке замінене в кінці j-го року, де 1 ≤ і < j ≤ n включає орендну плату плюс очікувані розходи на ремонт та обслуговування.

Необхідно так скласти план заміни обладнання, щоб мінімізувати сумарні затрати на його аренду, ремонт і обслуговування на протязі планового періоду.

Мережа задачи, що розглядається, при n = 6 надана на рис. 7.3.

Рис. 7.3. Мережа задачі про заміну обладнання

Кожний проміжний пункт (вузли з номерами 2-6) відповідає року, в який може бути здійсненна заміна транспортної одиниці. Транспортна таблиця для цієї задачі надана в табл. 7.4.

Табл. 7.4

Транспортна таблиця для задачі заміни транспортної одиниці

Можна показати, що мережа, яка подана на рис. 7.3, не має циклів. Такі мережі називаються ациклічні.

Запитання і завдання до самоконтролю

1. Охарактеризуйте сутність транспортної задачі з проміжними пунктами.

2. Розкрийте етапи перетворення транспортної задачі з проміжним пунктами у класичну транспортну задачу.

3. Опишіть сутність задачі вибору найкоротшого шляху.

4. Охарактеризуйте сутність задачі про заміну обладнання.

5. Побудуйте транспортну таблицю транспортної задачі з проміжними пунктами: а)

б)

в)

• ⇐ Назад
• -1
• 0
• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 1314