Розв’язок задачі цілочисельного програмування графічним методом

Графічний метод для розв’язку задачі цілочисельного програмування доцільно використовувати в тому випадку, коли число невідомих в задачі такого типу дорівнює двом. Перший крок при використанні графічного методу полягає в побудові багатокутника розв’язків без урахування умови цілочисельності. Далі, виходячи з того, що умову цілочисельності змінних задовольняють не всі координати точок області допустимих рішень, замінимо область допустимих рішень ослабленої задачі (без умови цілочисельності) на опуклий багатокутник, що містить тільки допустимі точки з цілочисельними координатами. Після цього, для того, щоб знайти максимум або мінімум цільової функції на опуклій області, як і у випадку задачі лінійного програмування, будують вектор градієнт . Далі, пересуваючи пряму в напрямку вектора , знаходимо точку, в якій цільова функція приймає оптимальне значення. Потім визначаємо координати точки екстремуму функції і обчислюємо значення цільової функції в цій точці.

Графічний метод – приклад:

Для виготовлення товару A і В підприємство використовує два види сировини. Норми витрат сировини на виробництво одного товару кожного виду, ціна одиниці товару A та B, а також загальна кількість сировини наведені в наступній таблиці:

Таблиця даних задачі цілочисельного програмування

Необхідно скласти такий план випуску даної продукції, щоб прибуток від її реалізації був максимальним.

Нехай та — кількість комплектів товару типу А та В відповідно. Тоді економіко-математична модель даної задачі запишеться у наступному вигляді:

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

Многокутник розв'язків послабленої задачі

Умові цілочисельності задовольняють лише 6 точок, даного многокутника. Тобто, щоб знайти точку, координати якої будуть розв’язком вихідної задачі, заміимо багатокутник ОАВ багатокутником OKEMNF, який містить всі допустимі точки з цілочисельними координатами.

Багатокутник розв'язків задачі цілочисельного програмування

Для визначення максимального значення цільової функції на багатокутнику OKEMNF побудуємо вектор градієнт і пряму .

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

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