ТЕМА 8. ЦІЛОЧИСЕЛЬНЕ ПРОГРАМУВАННЯ. МЕТОДИ ПЕРЕРІЗІВ ГОМОРІ

8.1. Постановка задачі цілочисельного програмування (ЗЦП) та область її застосування.

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

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

Існує й інша причина неспроможності округлення. Найчастіше цілочисельні змінні виражають кількість неподільних предметів (людей, машин, одиниць продукції). Але можливі й інші типи цілочисельних змінних. Так, рішення про фінансування деякого проекту представляється деякою булевою змінною X, що може прийняти одне з двох значень:

У даному випадку дробові значення не мають смислу.

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

1. Задача оптимального розкрою матеріалів.

2. Задача про призначення.

3. Задача про оптимальне використання устаткування.

4. Задача комівояжера.

5. Задача календарного планування.

8.2. Методи розв'язання задач цілочисельного лінійного програмування (ЗЦЛП).

Для розв'язання ЗЦЛП можуть застосовуватися такі основні групи методів:

1. Методи перерізу (методи відтинаючих площин).

2. Комбінаторні методи.

3. Графічний.

4. Еврістичні.