2.9. Целочисленное программирование

Значительная часть экономических задач, которые относятся к ЗЛП, требует целочисленного решения. Среди них задачи, где переменные означают количество единиц неделимой продукции – распределение производственных домов между предприятиями, раскрой материалов, загрузка оборудования, распределение машин по маршрутами, самолетов по рейсами, производство неделимой продукции.

Если единица составляет малую часть всего объема производства, то оптимальное решение вычисляют с помощью обычного симплекс-метода, округлят его до целых единиц согласно содержанию задачи. В противном случае округление может привести к решению, которое не является оптимальным целочисленным решением.

Задача целочисленного программирования формируется как ЗЛП, но включает дополнительное требование: значения переменных в оптимальном решении должны быть целыми неотрицательными числами.

Найти минимальное значение линейной функции

при ограничениях

– целые числа

Методы целочисленной оптимизации разделяют на точные и приближенные. К точным методам относятся методы отсечения и комбинаторные. Это универсальные методы дискретной оптимизации. Трудности машинной реализации точных методов привели к появлению приближенных методов, которые различают по направлениями: разработка алгоритмов, которые учитывают специфику задачи; использование случайных поисков в объединении с локальной оптимизацией.

Рассмотрим метод отсечения - метод Гоморри, основная идея которого:

• задачу решить, не обращая внимание на условие целочисленности. Если получен целочисленный план, то задача решена.

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

а) полученное не целочисленное решение нарушает это ограничение;

б) любой целочисленный допустимый план исходной задачи удовлетворяет и новому ограничению.

• новую задачу решают симплекс-методом и т.д.

Геометрически добавление каждого нового ограничения отвечает проведению прямой, которая отсекает от многоугольника решений некоторую часть с оптимальной точкой с нецелыми координатами, но не задевает ни одной из целочисленных точек многоугольника решений. Все точки с целочисленными координатами остаются в новом многоугольнике решений. На основе этой идеи американских математик Р.Гоморри предложил сходящийся алгоритм решения задач дискретного линейного программирования.

Замечание. Если ЗЛП без условия целочисленности не имеет решений, целочисленная ЗЛП тоже не имеет решений.

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

(2.9.1)

(2.9.2)

Решение. Приведем задачу к канонической форме, вводя дополнительные переменные x₃, x₄ в систему ограничений (2.9.1). ЗЛП (2.9.1), (2.9.2) в канонической форме имеет вид (2.9.3):

(2.9.3)

Решим ЗЛП симплекс-методом.

Первая симплекс-таблица имеет вид:

Таблица 2.9.1

Первая симплексная таблица

Б	С		1	-1	0	0	С.О.
	0	3	1	2	1	0	3/2
	0	3	2	1	0	1	3/1
z - строка		0	-1	1	0	0

Решение, соответствующее первой симплексной таблице, таково:

х₁ = 0, х₂ = 0, х₃ = 3, х₄ = 3.

Оно оптимальным не является, поэтому перейдем к следующей симплекс-таблице

Таблица 2.9.2

Вторая симплексная таблица

Б	С		1	-1	0	0
	-1	3/2	1/2	1	1/2	0
	0	3/2	3/2	0	-1/2	1
z - строка		-3/2	-3/2	0	-1/2	0

Второй симплексной таблице соответствует опорный план:

. (2.9.4)

Он является оптимальным и единственным, так как в z-строке нет положительных оценок. Значение целевой функции min z = – 3/2.

В полученном плане (2.8.4) две компоненты не целые, поэтому для нахождения целочисленного решения применим метод Гоморри. Поскольку не целые компоненты полученного решения одинаковы, то производить отсечение можно по любой строке.

Например, для строки имеем:

. (2.9.5)

Замечание. , где – целая часть , это целое ближайшее к число, которое его не превосходит; – дробная часть числа . , .

Неравенство (2.9.5) примет вид

или

. (2.9.6)

Для введения дополнительного ограничения (2.9.6) во вторую симплексную таблицу, введем в него новую дополнительную переменную:

.

Новое ограничение запишем во вторую симплексную таблицу, получим третью симплексную таблицу:

Таблица 2.9.3

Третья симплексная таблица

Б	С		1	-1	0	0	0
	-1	3/2	1/2	1	1/2	0	0
	0	3/2	3/2	0	-1/2	1	0
-	-	1	1	0	1	0	-1
z - строка		-3/2	-3/2	0	-1/2	0	0

Замечание. Генеральный элемент выбирают из следующих соображений:

если , то есть генеральный элемент; если , то есть генеральный элемент.

В нашем случае . Таким образом, вектор введем в базис и получим четвертую симплекс-таблицу.

Таблица 2.9.4

Четвертая симплексная таблица

Б	С		1	-1	0	0	0
	-1	1		1	0	0	1/2
	0	2	2	0	0	1	-1/2
	0	1	1	0	1	0	-1
z - строка		-1	-1	0	0	0	-1/2

Этой симплексной таблице соответствует опорный план:

.

Он является целочисленным, оптимальным и единственным, так как в z-строке нет положительных оценок. Значение целевой функции .

Пример 2.9.2. Решить задачу целочисленного линейного программирования (2.9.1), (2.9.2) графически.

Решение. Для графического решения этой задачи построим область допустимых решений, соответствующую системе ограничений (2.9.1), которая представлено на рисунке 5. Из рисунка 5 видно, что это четырехугольник АВСО. Изобразив вектор-градиент ОN, находим нецелочисленное решение: точка А(0;3/2).

Построим в полученной область допустимых решений дополнительное ограничение (2.9.6). Дополнительному ограничению отвечает прямая : , однако из первого равенства системы (2.9.3) имеем .

Тогда , следовательно , значит прямая : .

Дополнительное ограничение от области допустимых решений отсекло треугольник АВА₁, содержащий не целое решение, и, новая области допустимых решений представляет собой четырехугольник А₁ВСО. Оптимальным решением является А₁(0;1) и .

Рисунок 5 – Графический метод решения ЗЛП (2.9.1), (2.9.2).

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

Замечание. Если в строке с нецелым числом в столбце содержатся только целые числа, то задача не имеет решения.