Тема 4. Линейное целочисленное программирование

4.1. Постановка задачи

Целочисленная задача линейного программирования заключается в следующем:

Найти максимум (минимум) функции

(4.1)

при условиях

(4.2)

(4.3)

x_jZ, (4.4)

4.2. Геометрическая интерпретация задачи целочисленного программирования

Рассмотрим следующую задачу. В цеху предприятия решено установить дополнительное оборудование, для размещения которого выделено 19/3м­²­ площади. На приобретение оборудования предприятие может израсходовать 10000 д.е., при этом оно может купить оборудование двух видов. Комплект оборудования І вида стоит 1000 д.е., а ІІ вида - 3000 д.е. Приобретение одного комплекта оборудования І вида позволяет увеличить выпуск продукции в смену на 2 ед., а одного комплекта оборудования ІІ вида - на 4 ед. Для установки одного комплекта оборудования І вида требуется 2м² площади, а оборудования ІІ вида - 1 м² площади.

Определить такой набор дополнительного оборудования, который дает возможность максимально увеличить выпуск продукции.

Решение

Составим математическую модель задачи. Обозначим через х₁ количество комплектов оборудования І вида и через х₂ количество оборудования ІІ вида, которое приобретет предприятие. Тогда переменные х₁ и х₂ должны удовлетворять следующим неравенствам:

(4.5)

Если предприятие приобретет указанное количество оборудования, то общее увеличение выпуска продукции составит

F=2x₁+4x₂ (4.6)

По своему экономическому содержанию переменные х₁ и х₂ могут принимать лишь целые неотрицательные значения, т.е.

(4.7)

x₁, x₂ Z (4.8)

Таким образом, приходим к следующей математической задаче: найти максимальное значение линейной функции (6) при выполнении условий (5), (7), (8). Задача является задачей целочисленного программирования. Так как число неизвестных задачи равно двум, решим ее графически.

Х2
12
11
10
9
8
7
6
5
4		А	Е	B
3		К
2			М	N
1					F C
	0
		1	2	3	4	5	6	7	8	9	10	11	12	Х1

Построим сначала многоугольник решений задачи, состоящей в определении максимального значения линейной функции (6) при выполнении условий (5) и (7). Координаты всех точек построенного многоугольника решений ОАВС удовлетворяют системе линейных неравенств (5) и условию неотрицательности переменных (7). Вместе с тем условию (8), т.е. условию целочисленности переменных, удовлетворяют координаты лишь 12 точек. Чтобы найти точку, координаты которой определяют решение исходной задачи, заменим многоугольник ОАВС многоугольником OKEMNF, содержащим все допустимые точки с целочисленными координатами и таким, что координаты каждой из вершин являются целыми числами. Значит, если найти точку максимума функции (6) на многоугольнике OKEMNF, то координаты этой точки и определят оптимальный план задачи.

Для этого построим вектор и перпендикулярную к нему прямую 2x₁+4x₂=0 (F=0).

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

В данном случае искомой является точка Е(1:3), в которой целевая функция принимает максимальное значение F_max=F(1;3)=14. Следовательно, координаты точки Е определяют оптимальный план исходной задачи. В соответствии с этим планом предприятию следует приобрести один комплект оборудования І вида и три комплекта оборудования ІІ вида, что обеспечит увеличение выпуска продукции на 14 единиц в смену.