Постановка задачі

Серед оптимізаційних задач часто трапляються такі, що вимагають цілочисельності всіх або декількох змінних, та які одержали назву задач цілочисельного або частково цілочисельного програмування. В цілочисельному програмуванні змінні можуть набувати лише цілих значень. До таких задач відносяться задачі про розкрій матеріалу при умові одержання мінімуму відходів, задачі про перевезення неподільного вантажу та інші.

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

Задача цілочисельного лінійного програмування формулюється таким чином:

Знайти розв’язок Х *=(х ₁*;...; х_n *) який максимізує або мінімізує значення функції мети

Q (x)= p ₁ x ₁+…+ p_nx_n (2.22)

при умовах

a ₁₁ x ₁+ a ₁₂ x ₂+…+ a _{1 n}x_n £ b ₁, (2.23)

a ₂₁ x ₁+ a ₂₂ x ₂+…+ a _{2 n}x_n £ b ₂,

…

a_{m 1} x ₁+ a_{m 2} x ₂+…+ a_mnx_n £ b_m,

x ₁³0, x ₂³0, …, x_n ³0,

x_i – цілі числа. (2.24)

Порівнюючи цю задачу зі звичайною задачею лінійного програмування (2.3), (2.4), легко побачити, що ці задачі відрізняються лише умовою (2.24).

Як зазначалося раніше, екстремум задачі лінійного програмування досягається в точці, розташованій на межі області допустимих значень. Для задачі цілочисельного лінійного програмування точка оптимального значення не обов’язково буде належати межі області допустимих розв'язків. Тому методи розв'язування задач лінійного програмування не придатні для задач цілочисельного лінійного програмування. Так, наприклад, якщо задачу (2.22)-(2.23) розв'язувати симплекс-методом, не враховуючи умову цілочисельності (2.24), то при заокругленні нецілих значень оптимального плану можна одержати план, відмінний від оптимального, або план, який взагалі не задовольняє системі обмежень. Отже, для розв'язування задач з вимогою цілочисельності необхідно розглядати особливі методи оптимізації. До таких методів відносяться метод відтинаючих площин, метод віток і границь та метод Гоморі.