Page 43 - 4168

x = ціле , (3.23)
k
де k = 1, 2 ... l;
l - кількість цілочислових змінних.
Оптимізаційні задачі, в яких шукані змінні або їх частина
повинні бути цілими числами, вирішуються методами
цілочислового програмування.
Введення додаткових обмежень по цілочисельності змін-
них істотно збільшує об'єм обчислень і ускладнює обчислюва-
льну процедуру при пошуку оптимального розв’язку. Проте в
заданому діапазоні цілочислова змінна має меншу кількість
значень, чим безперервна. Зокрема, в діапазоні 0 < х < 3 ціло-
числова змінна х має чотири значення (х = 0, 1, 2, 3), а безпере-
рвна змінна - нескінченну кількість значень.
Спроба розв’язати цілочислову оптимізаційну задачу ме-
тодом повного перебору значень змінних приводить до дуже
великого об'єму обчислень. Так, наприклад, в задачі з трьома
цілочисловими змінними і діапазоном їх зміни 0 < x k < 10, k =
3
1, 2, 3 кількість цілочислових розв’язків складе 11 =1331. Яс-
но, що для реальних оптимізаційних задач метод повного пе-
ребору не прийнятний.
Інша спроба розв’язку цілочислової задачі полягає в
розв’язку цієї задачі без накладення обмежень вигляду (3.1). В
цьому випадку вирішується звичайна задача з безперервними
змінними, а отримані безперервні змінні округляються до ці-
лих чисел.
Проте округлення безперервних змінних до найближчих
цілих чисел може привести до неприпустимого розв’язку або
дати декілька допустимих розв’язків. Проте і в цьому випадку
немає гарантії, що серед розв’язків буде оптимальний цілочис-
ловий розв’язок.
Існують різні методи розв’язку цілочислових оптиміза-
ційних задач: метод відсікань (Гоморі), метод Беллмана, метод
віток і меж. Зокрема, метод віток і меж заснований на переборі
допустимих розв’язків не окремих розв’язків, а їх груп. Такий
підхід скорочує загальний об'єм обчислень.
Оптимальним розв’язком цілочислової задачі може ви-
явитися такий розв’язок, в якому змінні не є
найближчими до оптимального розв’язку неперервної задачі.

43