9.3. Основними недоліками розглянутого методу гілок і границь є:

1. Відсутність правил для вибору змвнної, яка ініціює процес розгалужень.

2. Відсутність правил для вибору послідовностірозв’язання породжених задач.

3. Необхідність повністю розв’язувати задачу лінійного програмування. Цей недолік є найбільш серйозний, особливо при розв’язанні задач великої розмірності. Разом з тим, існують модифікації методу гілок і границь, які  замість розв’язання ЗЛП застосовують процедуру “оцінки” верхньої границі цільової функції (в задачах максимізації) або нижньої (в задачах мінімізації). Така оцінка потребує порівняно невеликого обсягу обчислень. Дійсно, для кожного неоптимального розв’язку нам досить знати величину цільової функції, яку воно забезпечує. Основна ідея полягає в оцінюванні штрафів, тобто величин зміни цільової функції, пов’язаної із введенням обмежень типу xk£ [bk],  xk³[bk] до оптимальної симплекс-таблиці підзадачі, що є точкою розгалуження.

Незважаючи на вказані недоліки, метод гілок і границь на сьогоднішній день є найбільш надійним засобом розв’язання ЗЦЛП, що зустрічаються на практиці. Однак це не означає, що він може бути застосований до будь-якої задачі цілочисельного лінійного програмування. Розв’язання задач методом галузей і границь на ЕОМ припускає активну участь людини в процесі пошуку оптимуму.

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-9) продовжують доти, поки  перетворена матриця витрат буде міститиелементи, відмінні від нуля та знака нескінченності.

Приклад 6.4.  Необхідно визначити оптимальний маршрут обробки деталей. Нижче наведена матриця Ci j витрат на переналадку.

Таблиця 6.8

          1          2          3          4

1                 80        120       90

2        60                 90        80

3        130       110                70

4        100       50        120       

Розв’язок. У кожному рядку матриціci j знайдемо мінімальний елемент hi.

Таблиця 6.9

          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¢i j: 

Таблиця 6.10 

          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¢¢i j, приведена по рядках і стовпцях, міститься в табл. 6.11.

Таблиця 6.11

          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¢¢ij  рядок 2, стовпець 1 та елемент (1,2), прийдемо до матриці, представленої в табл. 6.12.

Таблиця 6.12

                      2          3          4          hi

          1                   10        10        10

C(1)i j =         3          40                 0          0

          4          0          40                 0

 

Виконаємо приведення матриціc(1)i j по рядках:

Таблиця 6.13

                      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)i j по стовпцях непотрібно, оскільки кожний її стовпець містить щонайменше один нульовий елемент. Тепер можна обчислити оцінку підмножини, яка містить перехід (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, отримаємо таку матрицю:

                      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, що співпадає з раніше отриманою величиною. Процес пошуку оптимального розв’язку можна наочно податиу вигляді дерева розв’язків (рис. 1).

 

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