5.1 Задачі із цілочисельними змінними

 

У викладеному вище матеріалі із розв’язування оптимізаційних задач методами лінійного та нелінійного програмування всі шукані змінні мали безперервний характер. Ці змінні у заданому діапазоні зміни могли приймати будь-які значення.

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

х_k-ціле,     k=1,2,…l,                               (5.1)

де l ‑ кількість цілочисельних змінних, l < n; n ‑ загальна кількість змінних.

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

Введення додаткових обмежень на цілочисельність змінних істотно збільшує обсяг обчислень і ускладнює обчислювальну процедуру при пошуку оптимального розв’язку. Однак у заданому діапазоні зміни змінної цілочисельна змінна має меншу кількість значень, ніж безперервна змінна. Зокрема, у діапазоні  цілочисельна змінна х має чотири значення (х=0,1,2,3), а безперервна змінна ‑ нескінченну кількість значень.

Спроба вирішити цілочисельну оптимізаційну задачу методом повного перебору значень змінних приводить до дуже великого обсягу обчислень. Так, наприклад, у завданні із трьома цілочисельними змінними й діапазоном їхньої зміни  k=1,2,3 кількість цілочисельних розв’язків складе 11³=1331. Зрозуміло, що для реальних оптимізаційних задач метод повного перебору не допустимий.

Інша спроба розв’язку цілочисельних задач полягає в розв’язку цієї задачі без накладання обмежень виду (5.1). У цьому випадку вирішується звичайне завдання з безперервними змінними, а отримані безперервні змінні заокруглюються до цілих чисел.

Існують різні методи розв’язування цілочисельних оптимізаційних задач: метод відсікань, метод Беллмана, метод віток і границь. Зокрема, метод віток і границь заснований на переборі допустимих розв’язків, але на переборі не окремих розв’язків, а їхніх груп. Такий підхід скорочує загальний обсяг обчислень.

Однак не будемо розбиратися у подробицях методів цілочисельного програмування, а доручимо, як щирий користувач, цей розбір комп'ютеру, оскільки програмне забезпечення MS Excel дозволяє вирішувати задачі цілочисельного програмування.

Введення вихідних даних цілочисельної задачі відрізняється від введення вихідних даних задачі з безперервними змінними заданням додаткових обмежень виду (5.1).