3.5. Цілочислові задачі лінійного програмування.

Якщо до задачі лінійного програмування, наприклад виду (3.1 - 3.3) додати ще умову за якою усі або декілька змінних можуть приймати лише цілі значення, то отримаєма задачу цілочислового лінійного програмування.

Увесь клас задач цілочислового програмування можна умовно поділити на два типи: загально цілочислове програмування – лінійне програмування з вимогою цілочисленності для усіх змінних задачі та чатково цілочислове (змішано-цілочислове) програмування – лінійне програмування з вимогою цілочисленності тільки для деяких, але не всіх змінних задачі. Якщо усі змінні задачі лінійного програмування можуть приймати лише два значення 0 і 1, то говорять про бульове програмування, якщо це справедливо лише для деяких змінних, то говорять про змішано-бульове програмування.

Математична модель загальної цілочислової задачі лінійного програмування має вигляд:

(3.19)

; (3.20)

(3.21)

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