3.6.2. Методи розв’язку лінійних задач цілочислового програмування.

Основою існуючих методів цілочислового програмування є ідея Данціга. Зміст якої у наступному: якщо необхідно розв’язати ЗЛП, усі або частина змінних якої повинні задовольняти умову цілочисленості, то можливо, при розв’язуванні задачі без урахування умови цілочисловості, випадково буде отримано потрібний розв’язок. Однак, імовірність даного випадку досить мала. У більшості випадків розв’язок не задовольнятиме умову цілочисленості. Тоді до існуючої задачі долучають додаткове обмеження, яке не виконується для отриманого плану задачі, проте задовольняє будь-який цілочисловий розв’язок. Таке додаткове обмеження називають «правильним відтинанням».

Методи відтинання базуються на операції поступового «звуження» області допустимих розв’язків розглядуваної задачі. Пошук цілочислового розв’язку починається з отримання оптимального плану задачі з «послабленими» обмеженнями - без урахування вимоги цілочисловості змінних. Далі у модель включаються додаткові обмежень, що враховують умову цілочисленності змінних, область допустимих розв’язків послабленої задачі поступово зменшують доти, доки змінні оптимального розв’язку не набудуть цілочислових значень. Практично, існуючу систему обмежень задачі доповнюється новим обмеженням і знову розв’язується «посилена» ЗЛП. Якщо її розв’язок знову не задовольняє умови цілочисловості, то будується нове лінійне обмеження, що обмежує отриманий розв’язок, не зачіпаючи цілочислових планів. Процес приєднання додаткових обмежень повторюють доти, доки не буде знайдено цілочислового оптимального плану, або доведено, що його не існує.

Геометрично це означає, що якщо точка А (рис.3.7.) многокутника допустимих розв’язків ОВАС є оптимумом і одночасно є точкою координатної сітки, то А – розв’язок цілочислової задачі. У притилежному випадку до ЗЛП додається ще одна умова («зріз»), така, що всі допустимі точки координатної сітки задовольняють її, а сама точка А – ні. Тобто сама точка А і її окіл «відтинаються» від допустимої області ЗЛП.

Для розв’язування цілочислових задач лінійного програмування розроблені різноманітні методи: метод відтинання; метод розгалуджень; наближені методи; доведення цілочисленості всіх базисних роз’язків відповідної ЗЛП для окремих класів задач (транспортна задача).

Розглянемо деякі з найбільш вживаних методів розв’язування задач цілочислового програмування.