Графическое решение задачи целочисленного программирования

Полностью целочисленную задачу с двумя переменными можно решить графически, учитывая, что допустимое множество задачи (6.52)…(6.55) состоит из точек целочисленной координатной сетки, принадлежащих допустимому множеству Х задачи линейного программирования без дополнительного требования (6.55).

Пример 6.11. Решить целочисленную задачу линейного программирования графическим методом.

На плоскости (х ₁, х ₂) построим допустимое множество Х рассматриваемой задачи линейного программирования без требования целочисленности (многоугольник ABCD на рис. 6.17) и отметим точки множества Х с целочисленными координатами. Совокупность этих точек представляет собой допустимое множество полностью целочисленной задачи.

Рис. 6.17. Графическая иллюстрация решения задачи

Перемещая линию уровня целевой функции в направлении убывания , находим крайнее положение этой линии, в котором она еще имеет непустое пересечение с множеством . В этом положении линия уровня проходит через точку В (0;4), поэтому решение задачи имеет вид

Отметим, что, как видно из рис. 6.17, точкой минимума в данной задаче без требования целочисленности является точка C (5;4/5), т.е. Отсюда следует, что точкой минимума целевой функции на допустимом множестве целочисленной задачи не обязательно является ближайшая к решению х * обычной (нецелочисленной) задачи точка множества Х с целочисленными координатами.