9.4. Алгоритм Літтла.
На теперішній час розроблено безліч модифікацій методу гілок і границь. В економіці широке застосування для розв’язання цілочисельних оптимізаційних задач знайшов так званий модифікований алгоритм Літтла - різновид методу гілок і границь, що передбачає розрахунок штрафів. Вперше цей метод був застосований для розв’язання «задачі комівояжера». Постановка задачі наступна: комівояжеру необхідно побувати в кожному з n географічних пунктів і повернутись у вихідний пункт, при цьому слід обрати найбільш економічний маршрут. Відома матриця Сij витрат на пересування з i-го пункту в j-й.
Модифікований алгоритм Літтла
Крок 1. Виконати приведення матриці витрат по рядках: із елементів кожного i-го рядка відняти приводящу константу hi - мінімальний у цьому рядку елемент.
Крок 2. Аналогічно привести матрицу по стовпцях, віднімаючи з елементів кожного j-го стовпця приводящу константу Hj.
Після виконання двох перших кроків алгоритму Літтла матимемо матрицю, кожний рядок і кожний стовпець якої буде містити щонайменше один нульовий елемент.
Крок 3. Визначити оцінку нижньої межі цільової функції j для вихідної множини G всіх можливих маршрутів (кількість таких маршрутів складає n!). Така оцінка дорівнює сумі приводящих констант: j(G)= . Це означає, що жоден з n! маршрутів не може мати вартість меншу від j(G).
Далі потрібно розбити множину G на дві підмножини, одна з яких (G1) містить у собі деяку пару суміжних пунктів (k, l), а інша (G2) - не містить.
Крок 4. Визначити мінімальний елемент, відмінний від одного нуля, для кожного i-го рядка – ai та для кожного j-го стовпця – bj. Для кожного нульового елементу сpq матриці витрат обчислити “штраф за невикористання”: qpq=ap+bq. Величина штрафу покаже, наскільки зросте цільва функція (суммарні витрати на переналадку) за умови не-включення переходу (p, q) до маршруту обробки деталей. В якості пари деталей (p, q), що визначає процес розгалуження, обирають таку, якій відповідає максимальна величина штрафу .
Крок 5. Обчислити оцінку нижньої межі для підмножини G2, що не містить перехід (k, l). Вона дорівнює сумі оцінки підмножини G, яка ініціює розгалуження та штрафу за невикористання» (k, l):
Крок 6. Тепер необхідно оцінити підмножину G1. Для цього з матриці витрат виключають k-рядок і l-й стовпець. Дійсно, якщо пару деталей вирішено включити в маршрут обробки, то в подальшому аналізі вона розглядатись не буде. Необхідно також у матриці витрат замінити елемент (k,l) знаком «¥». Це дозволить уникнути зациклення, тобто не допустити після переходу від k-ї деталі до l-ї зворотній перехід від l-ї деталі до k-ї.
Для перетвореної матриці слід виконати приведення по рядках і стовпцях і обчислити суму приводящих констант. Знайти оцінку нижньої межі для підмножини G1. Вона дорівнює оцінці множини, яка породжує розгалуження, збільшеній на величину суми приводящих констант для поточної перетвореної матриці:
j(G1)= j(G)+ .
Крок 7. Обрати в якості вихідної підмножини для подальшого розгалуження ту із підмножин G1 і G2 , яка має меншу оцінку j. Перейти до кроку 4.
Процес розгалуження и обчислення значень нижньої межі цільової функції для різних підмножин (повторення кроків 4-7) продовжують доти, поки перетворена матриця витрат буде містити елементи, відмінні від нуля та знака нескінченності.
Приклад 9.2. Необхідно визначити оптимальний маршрут обробки деталей. Нижче наведена матриця C витрат на переналадку.
Таблиця 9.1. Матриця C витрат на переналадку
1 2 3 4
1 80 120 90
2 60 90 80
3 130 110 70
4 100 50 120
Розв’язок. У кожному рядку матриці C знайдемо мінімальний елемент hi.
Таблиця 9.2. Матриця C витрат на переналадку, що містить мінімальні елементи рядків
1 2 3 4 hi
1 80 120 90 80
2 60 90 80 60
3 130 110 70 70
4 100 50 120 50
Аналогічно, виконавши приведення по рядках, перейдемо до матриці C:
Таблиця 9.3 - Матриця C витрат на переналадку, приведена по рядках
1 2 3 4
1 0 40 10
2 0 30 20
3 60 40 0
4 50 0 70
Hj 0 0 30 0
Матриця C, приведена по рядках і стовпцях, міститься в табл. 9.4.
Таблиця 9.4 - Матриця Cвитрат на переналадку, приведена по рядках і стовпцях
1 2 3 4 i
1 0 10 10 10
2 0 0 20 0
3 60 40 0 40
4 50 0 40 40
j 50 0 10 10
Знайдемо оцінку нижньої межі цільової функції для вихідної підмножини G: j(G)= =80+60+70+50+0+0+30+0=290.
Для нульових елементів приведеної матриці обчислимо величини штрафів за невикористання: q12=10+0=10, q21=0+50=50, q23=0+10=10, q34=40+10=50, q42=40+0=40. Максимальна величина штрафу відповідає двом елементам: q21=q34=50. Тому для организації процесу розгалуження можна обрати пару деталей (2,1) або (3,4). Оберемо пару (2,1).
Обчислимо оцінку множини G2:
j(G2(1))=j ( )=j(G)+ql k=290+50=340.
Виключивши з матриці C¢¢ рядок 2, стовпець 1 та елемент (1,2), прийдемо до матриці, представленої в табл. 9.5.
Таблиця 9.5
Таблиця 9.5
2 3 4 hi
1 10 10 10
C(1)i j = 3 40 0 0
4 0 40 0
Виконаємо приведення матриці C(1)i j по рядках:
Таблиця 9.6
2 3 4 i
1 0 0 0
C(1)i j = 3 40 0 40
4 0 40 40
j 40 40 0
Зводити матрицю C¢(1) по стовпцях непотрібно, оскільки кожний її стовпець містить щонайменше один нульовий елемент. Тепер можна обчислити оцінку підмножини, яка містить перехід (2,1): j( )=j(G)+ =290+10=300.
Оскільки j( )<j( ), то на наступній ітерації будемо здійснювати врозгалуження множини .
Обчислимо величини штрафів для нульових елементів: q13=40, q14=0, q34=40, q42=80. Оцінка підмножини, яка не містить переходу (4,2), дорівнюватиме: j( )=j( )+q42=300+80=380.
Виключивши рядок 4 та стовпець 2, отримаємо наступну матрицю:
Таблиця 9.7
3 4
1 0 0
C(2)i j = 3 0
Оцінка підмножини, що містить перехід (4,2), складе: j( )=j( )+ =300+0=300.
Оскільки j( )<j( ), то в якості нової точки розгалуження слід обрати множину j( ), включаючи таким чином перехід (4,2) до оптимального маршруту обробки деталей.
Матриця C(2)i j містить тільки нулі та знаки нескінченності, тому процес обчислення оцінок для нижніх границь закінчено. Очевидно, що третім та четвертим кроками в послідовності обробки деталей можуть бути тільки переходи (1,3) та (3,4), оскільки перехід (3,3) заборонено, про що свідчить символ “¥”, а (1,2) передбачає наявність (3,3). Очевидно й те, що сумарна вартість переналадки дорівнюватиме оцінці останньої точки розгалуження: Тпер= j( )=300 (г.о.).
Таким чином, оптимальним маршрутом обробки буде послідовність: 1®3®4®2®1. Результуючу вартість переналадки при такому маршруті можна визначити, просумувавши відповідні елементи виходної матриці витрат Сij:
Тпер=120+70+50+60=300, що співпадає з раніше отриманою величиною. Процес пошуку оптимального розв’язку можна наочно подати у вигляді дерева розв’язків (рис. 9.2).
Рис. 9.2. Дерево пошуку розв’язку для задачі визначення оптимального маршруту обробки деталей.