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

 

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

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

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

 

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

 

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

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