Розв'язок задачі цілочисельного програмування графічним методом
Графічний метод для розв'язку задачі цілочисельного програмування доцільно використовувати в тому випадку, коли число невідомих в задачі такого типу дорівнює двом. Перший крок при використанні графічного методу полягає в побудові багатокутника розв'язків без урахування умови цілочисельності. Далі, виходячи з того, що умову цілочисельності змінних задовольняють не всі координати точок області допустимих рішень, замінимо область допустимих рішень ослабленої задачі (без умови цілочисельності) на опуклий багатокутник, що містить тільки допустимі точки з цілочисельними координатами. Після цього, для того, щоб знайти максимум або мінімум цільової функції на опуклій області, як і у випадку задачі лінійного програмування, будують вектор градієнт . Далі, пересуваючи пряму
в напрямку вектора
, знаходимо точку, в якій цільова функція приймає оптимальне значення. Потім визначаємо координати точки екстремуму функції і обчислюємо значення цільової функції в цій точці.
Графічний метод — приклад:
Для виготовлення товару A і В підприємство використовує два види сировини. Норми витрат сировини на виробництво одного товару кожного виду, ціна одиниці товару A та B, а також загальна кількість сировини наведені в наступній таблиці:

Таблиця даних задачі цілочисельного програмування
Необхідно скласти такий план випуску даної продукції, щоб прибуток від її реалізації був максимальним.
Нехай та
— кількість комплектів товару типу А та В відповідно. Тоді економіко-математична модель даної задачі запишеться у наступному вигляді:
Оскільки число невідомих даної задачі цілочисельного програмування дорівнює двом, то її рішення будемо відшукувати графічно. Для цього побудуємо багатокутник розв'язкув задачі без умови цілочисельності. В результаті отримаємо:

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

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

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