Page 225 - 4685

Якщо n = n, то задачу називають повністю цілочисельною; якщо n < п –
1
1
частково цілочисельною (ЧЦП).
Припустимо, що задача має многогранник рішень:

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

первинному многограннику рішень; будь-яка його кутова точка ціла;
2) оскільки цільова функція досягає оптимуму в кутовій точці, то
побудовою многогранника забезпечується цілочисельність оптимального
рішення.
Вирішення задач цілочисельного програмування трудомістке, тому по
можливості краще не накладати обмежень цілочисельності змінних. У ряді
випадків задачу цілочисельного програмування вирішують таким чином: як
безперервну задачу лінійного програмування; округлюють змінні; перевіряють
допустимість закругленого рішення; якщо рішення допустиме, то воно
приймається як цілочисельне.
При необхідності точного рішення застосовують спеціальні методи, де
враховується, що множина рішень будь-якої цілочисельної задачі скінченна.
Наприклад, в задачі зі змінними х , х : 0 < х ≤ 4; 0 < x ≤ 5. Кількість можливих
1
j
1
2
рішень 20. Отже, можливий повний перебір можливих поєднань цілочисельних
х , х і вибір найкращого в сенсі цільової функції. Трудомісткість цього методу
1
2
зростає зі зростанням кількості змінних і області граничних умов, тому в
реальних задачах застосовують методи, в яких не розглядають всі можливі
альтернативи. Поширені – методи відсікань і методи повернення, серед яких
найбільш відомий метод гілок і кордонів.

МЕТОД ГІЛОК І КОРДОНІВ

Задача лінійного програмування вирішується без врахування
цілочисельності. Далі розглядають одну зі змінних x , на яку накладають
j
обмеження цілочисельності, але яка набула дробового значення. На основі
отриманого рішення складають додаткові обмеження: х ≤[x *] і x ≥ [x *] + 1, де
j
j
j
j
221