8.5. Недоліки методів перерізу Гоморі.

Розглянутим у пп. алгоритмам розв’язання цілочисельних задач ЛП властиві такі недоліки:

1. Помилки округлення, що виникають у процесі обчислень на ЕОМ, можуть призвести до одержання неоптимального цілочисельного розв’язку. Роздільний запис у пам'яті ЕОМ чисельників і знаменників різних дробів виключає операції над десятковими дробами. Однак у цьому випадку кількість розрядів у чисельниках і (або) у знаменниках може перевищити можливості запам'ятовуючого пристрою.

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

 Від першого із зазначених недоліків вільний так званий цілком цілочисельний алгоритм. Від другого - дробові прямі алгоритми, що, на відміну від двоїстих алгоритмів Гомори, дозволяють використання в якості початкового деякого допустимого розв’язку. Однак згадані методи перерізів не мають переваг обчислювального характеру, властивих алгоритмам Гоморі.

У випадках, коли умова цілочисельності накладається не на всі змінні задачі, варто використовувати так званий дробовий алгоритм для частково цілочисельних задач.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 
25 26 27 28 29 30  Наверх ↑