Постановка и геометрическая интерпретация

Элементы целочисленного программирования

Постановка и геометрическая интерпретация

Многие задачи линейного программирования, возникающие в экономике и производстве, требуют решений, у которых компоненты целочисленны, то есть x_j Î Z, j =1, 2, …, n. Например, когда количество выпускаемой продукции измеряется в целых величинах, скажем, поштучно. Так, количество выпускаемых автомобилей, станков не может быть дробным. Раздел линейного программирования, изучающий методы решения таких задач, называется целочисленным линейным программированием, а задачи с таким условием - задачами целочисленного линейного программирования. В математической модели таких задач появляется дополнительное условие: x_j Î Z, j =1, 2, …, n:

c ₁ x ₁+ c ₂ x ₂+…+ c_nx_n ®max(min)

(7.1)

В случае, когда задача имеет только две переменные:

c ₁ x ₁+ c ₂ x ₂ ® max(min)

(7.2)

она имеет простую геометрическую интерпретацию: решением задачи является точка в многоугольнике решений системы ограничений

(7.3)

с целочисленными координатами, в которой достигается экстремум целевой функции задачи. Такие задачи геометрически решаются по следующей схеме:

1. Построить многоугольник решений системы (7.1).

2. В многоугольнике решений, полученном в п.1, отметить точки с целочисленными координатами. Получается область допустимых решений (ОДР) задачи (7.2).

3. Построить линии уровня c ₁ x ₁+ c ₂ x ₂= a целевой функции задачи.

4. В ОДР задачи (7.2), полученной в п.2, выбрать точку, в которой достигается требуемый экстремум.

5. Вычислить значение функции в найденной точке экстремума.

Пример 1. Решить задачу целочисленного программирования геометрическим способом:

2 x ₁+4 x ₂ ® max(min)

Решение. Действуем по вышеприведённой схеме:

1. Строим многоугольник решений системы (подробности опускаем) (Рис.4)

Рис.4

2. В многоугольнике решений, полученном в п.1, отмечаем точки с целочисленными координатами. Это точки (0, 0), (1, 0), (2, 0), (3, 0), (0, 1), (1, 1), (2, 1), (0, 2), (1, 2), (2, 2), (0, 3), (1, 3). Таким образом, ОДР задачи - это множество {(0, 0), (1, 0), (2, 0), (3, 0), (0, 1), (1, 1), (2, 1), (0, 2), (1, 2), (2, 2), (0, 3), (1, 3)} (Рис.5):

Рис.6

3. Cтроим линии уровня 2 x ₁+4 x ₂= a целевой функции задачи, ориентируясь на вектор =(1, 2) нормали этих линий, коллинеарный вектору 2 =(2, 4) (Рис.7):

Рис.7

4. В ОДР задачи, полученной в п.2, выбираем точки, в которых достигаются требуемые экстремумы. Это точки (1, 3) - точка максимума, и (0, 0) - точка минимума.

5. Вычислим значение функции в найденных точках экстремума:

F _{max цел.}= F (1, 3)=2× 1+4× 3=14, F _{min цел.}= F (0, 0)=2× 0+4× 0=0.

Ответ: X _{max цел.}=(1, 3), F _{max цел.}=14; X _{min цел.}=(0, 0), F _{min цел.}=0.