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

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

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

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

Если r = n, то задача будет полностью целочисленной; если r < n, то частично целочисленной.

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

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

где х_k – базисная переменная в уравнении;

h_kj – коэффициенты при неизвестных (коэффициенты разложений векторов условий по базису опорного решения);

х_j – свободные переменные в системе уравнений;

f_k – правая часть уравнения (координата оптимального решения), которая является дробным числом.

Разобьем каждый коэффициент и свободный член этого уравнения на два слагаемых: целую и дробную части. Целая часть числа а – это наиболее близкое к нему целое число, не превосходящее самого числа. Целую часть числа, а будем обозначать [a]. Дробная часть числа, а находится как разность этого числа и его целой части. Дробная часть числа всегда неотрицательна и меньше единицы. Дробную часть числа, а будем обозначать {a}. Тогда

a = [a] + {a}.

Например, для числа целая часть , дробная часть равна . Для числа целая часть , дробная часть равна .

Наше уравнение запишем в следующем виде:

.

На его основании имеем следующее дополнительное ограничение

.

Заменяя это неравенство уравнением и добавляя его к ранее решенной задаче, получаем новую задачу. Решаем ее симплексным методом. Если новое оптимальное решение не будет целочисленным, то по последней симплексной таблице составляем снова дополнительное ограничение. Если в оптимальном плане несколько дробных х_k, то дополнительное ограничение составляют для max{x_k}. Процесс присоединения дополнительных ограничений повторяют до тех пор, пока не найден целочисленный оптимальный план, либо будет доказано, что задача не имеет целочисленных планов. Это имеет место в случае, если для дробного х_k все коэффициенты при других неизвестных в этой строке окажутся целыми.

Пример. Найти наибольшее значение функции при ограничениях

x_i ≥ 0, x_i – целые, i = 1, 2, 3, 4, 5.

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

	х1	х2	х3	х4	х5
х1	1	0	0
х2	0	1	0
х3	0	0	1
Z	0	0	0

.

Полученное решение нецелочисленное: - не целые числа. Выберем из них число с дробной наибольшей частью: Итак, выбираем правую часть соответствующую переменной х₁. Из таблицы выписываем строку, содержащую переменную х₁:

; , , .

Следовательно, дополнительное ограничение имеет вид , или, при замене его уравнением, , где х₆ – балансовая переменная, х₆ ≥ 0.

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

	х1	х2	х3	х4	х5	х6
х1	1	0	0			0
х2	0	1	0			0
х3	0	0	1			0
	0	0	0			-1
z	0	0	0			0

Находим опорное решение и проверяем его на оптимальность.

	х1	х2	х3	х4	х5	х6
х1	1	0	0	0	0	1	2
х2	0	1	0		0
х3	0	0	1		0
х5	0	0	0		1
z	0	0	0		0		6

Все оценки неотрицательны. Следовательно, решение оптимальное: , но оно не является целочисленным. Составляем второе дополнительное ограничение для второй строки последней симплексной таблицы:

Ограничение имеет вид:

или

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

	х1	х2	х3	х4	х5	х6	х7
х1	1	0	0	0	0	1	0	2
х2	0	1	0		0		0
х3	0	0	1		0		0
х5	0	0	0		1		0
	0	0	0		0		-1
z	0	0	0		0		0	6

Находим опорное решение и проверяем его на оптимальность.

	х1	х2	х3	х4	х5	х6	х7
х1	1	0	0	0	0	1	0	2
х2	0	1	0	0	0	-1	1	2
х3	0	0	1	0	0			1
х5	0	0	0	0	1	-3	2	0
х4	0	0	0	1	0	2	-3	2
z	0	0	0	0	0			5

Отсюда видно, что является оптимальным решением третьей задачи, а так как оно целочисленное, то - оптимальное решение исходной задачи: z_опт = 5.