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

І снує доволі широке коло задач математичного програмування, в економіко-математичних моделях яких одна або кілька змінних мають набувати цілих значень. До них належать задачі, у яких змінні означають кількість одиниць неділимої продукції. Наприклад, коли йдеться про кількість верстатів у цеху, тварин у сільському господарських підприємствах тощо.Наведені задачі називаються задачами цілочислового програмування. До цілочислового програмування належать також задачі оптимізації, в яких змінні набувають лише двох значень – 0 або 1.

Задача цілочислового програмування формується так само, як і задача лінійного програмування, але включає додаткову вимогу, яка полягає в такому: змінні, які становлять оптимальний розв’язок, мають бути цілими невід’ємними числами.

→min(max)

при обмеженнях: хj – цілі числа ( )Параметри , , ( ) вважаються цілими числами.

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

Зауважимо, що геометрично множина допустимих планів будь-якої лінійної цілочислової задачі являє собою систему точок з цілочисловими координатами, що знаходяться всередині опуклого багатокутника допустимих розв’язків відповідної не цілочислової задачі. Отже для розглянутого на рисунку випадку множина допустимих планів складається з 9 точок, які утворені перетинами сім’ї прямих, що паралельні осям Ох1 та Ох2 і проходять через точки з цілими координатами 0, 1, 2. Для знаходження цілочислового оптимального розв’язку пряму, що відповідає цільовій функції, пересуваємо у напрямку вектора нормалі до перетину з кутовою точкою утвореної цільової сітки. Координати цієї точки і є оптимальним цілочисловим роз’язком задачі. Отже, точка М(2;2) – цілочисловий розв’язок данної задачі.

Очевидно, особливість геометричної інтерпретації цілочислової задачі у зіставленні зі звичайною задачею лінійного програмування полягає лише у визначенні множини допустимих розв’язків. Областю допустимих розв’язків загальної задачі лінійного програмування є опуклий багатокутник, а вимога цілочисловості розв’язку призводить до такої множини допустимих розв’язків, яка є дискретною і утворюється тільки з окремих точок. Якщо у разі 2 змінних розв’язок задачі можна відшукати графічним методом, тобто, використовуючи цілочислову сітку, можна досить просто знайти оптимальний план, то в іншому разі необхідно застосовувати спеціальні методи.