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. Дерево пошуку розв’язку для задачі визначення оптимального маршруту обробки деталей.