Постановка задачі цілочислового програмування (ЗЦЛП)
Серед економічних задач часто зустрічаються задачі з вимогою цілочисельності всіх або частини змінних, які одержали назву ЗЦЛП або частково цілочислового програмування. В ЦЛП змінні набувають іншого вигляду не неперервно, а за допомогою деяких цілих значень. До цілочислових задач зараховують задачі про розкрій матеріалу при умові одержання мінімуму відходів, задачі про перевезення неподільного вантажу та ряд інших.
В даній темі ми обмежимося лише розглядом ЗЦЛП, яка формулюється наступним чином: знайти план , за якого цільова функція
(1.41)
досягає найбільшого або найменшого значення при обмеженнях
; (1.42)
, ; (1.43)
– цілі числа. (1.44)
Порівнюючи дану модель ЗЦЛП із звичайною моделлю ЗЛП, бачимо, що вони відрізняються лише умовою (1.44).
Як ми вже знаємо, екстремум для ЗЛП досягається в крайній точці опуклої множини або в точці, яка є опуклою лінійною комбінацією крайніх точок. Для ЗЦЛП точкою екстремуму може бути будь-яка точка області допустимих розв’язків. Тому методи розв’язування ЗЛП не придатні для ЗЦЛП. Так, наприклад, якщо задачу (1.41)–(1.44) розв’язувати СМ, не враховуючи умову цілочисельності (1.44), то при заокругленні нецілих змінних оптимального плану можна одержати план, який не є оптимальним, або план, який взагалі не задовольняє системі обмежень. Отже, для розв’язування задач з вимогою цілочисельності необхідно розглядати особливі методи оптимізації, що ми і зробимо надалі.