Змістова та геометрична інтерпретація задачі цілочислового програмування

 

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

Наведемо математичну постановку задачі цілочислового лінійного програмування у симетричній формі:

знайти

(4.1)

за умови

, , (4.2)

, (4.3)

– цілі, . (4.4)

Наведене формулювання відрізняється від звичайної задачі лінійного програмування лише умовою цілочисловості (4.4). Але ця вимога в загальному випадку суттєво ускладнює процес знаходження оптимального розв’язку задачі.

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

На перший погляд може здатися, що задача введення умови цілочисловості (4.4) спрощує розв’язання задачі, внаслідок того, що її допустима множина розв’язків стає при цьому скінченною множиною точок (якщо допустима область, що задана нерівностями (4.2) – обмежена) і знайти оптимальний розв’язок можна простим перебором всіх можливих варіантів. Але на практиці в багатьох випадках цим скористатися неможливо. Розглянемо найпростіший випадок, в якому змінні можуть приймати лише значення нуля або одиниці. При кількості змінних n = 64 матимемо необхідність виконати 2⁶⁴ (!) обчислень цільової функції, що є практично нездійсненним.

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

Приклад 1. По-перше, отримана точка з цілочисловими координатами може взагалі не належати області допустимих значень, як це показано на рис. 4.1.

Рисунок 4.1 – Оптимальне значення задачі лінійного програмування досягається в точці В(3.9; 1.2), найближча до неї точка – т. D(4, 1), не належить області допустимих значень

Область допустимих значень задачі (4.1) – (4.3) задана трикутником АВС. Оптимальне значення досягається в точці В(3.9; 1.2), округлення координат якої приводить до т. D(4, 1) Ï DАВС. Область допустимих значень цілочислової задачі (4.1) – (4.4) задана многокутником EFGH.

Приклад 2. Ще одна типова ситуація показана на рис. 4.2, на якому дано геометричне подання такої задачі:

знайти

, (4.5)

за умови

(4.6)

(4.7)

– цілі числа. (4.8)

Області допустимих значень для звичайної задачі (4.5) – (4.7) та цілочислової задачі (4.5) – (4.8) являють собою многокутники SABC та DEFGH, відповідно.

Рисунок 4.2 – Оптимальне значення задачі лінійного програмування (4.5) – (4.7) досягається в точці В(3.4; 2.22), найближча до неї точка – т. F(3, 2), але оптимальне значення цілочислової задачі (4.5) – (4.8) досягається в точці G(4; 1)

 

Як буде показано в прикладі 4 оптимальним планом нецілочислової задачі є т. В(3.4; 2.22), оптимальним планом цілочислової задачі є т. G(4; 1). Округленням координат т. В(3.4; 2.22) дістаємо т. F(3, 2), яка насправді знаходиться далеко від оптимального планy.

Приклад 3. Знайти

,

за умови

, – цілі числа.

Розв’язком задачі є т. , а без врахування цілочислової умови x ^*=(1/2,0;9/2). Неважко перевірити, що ніякі варіанти округлення розв’язку x ^* не дають навіть допустимого розв’язку сформульованої цілочислової задачі.