В данном подразделе будет рассмотрена линейная задача целочисленного программирования и дано понятие первого алгоритма Гомори, который заложил фундамент теории целочисленного программирования.
Для удобства изложения методов целочисленного программирования используют специфические обозначения, на которых целесообразно прежде всего остановиться. Задачу целочисленного программирования рассмотрим в виде:
|
|
|
|
xj – целое; j = 1, 2,..., nj.
При n1 = n задача (3.23) – (3.26) является полностью, а при n1 < n – частично целочисленной задачей линейного программирования. По аналогии с задачей линейного программирования введем ряд понятий. Множество наборов (х1, х2,..., xn), удовлетворяющих условиям (3.24) – (3.26), называется областью определения или допустимой областью задачи целочисленного программирования и обозначается через Lц. Для сокращенного обозначения задачи (3.23) – (3.26) применяется запись (Lц, c), где с – вектор-столбец, состоящий из элементов сi. Оптимальное решение или оптимальный план обозначается через х (Lц, c). Наряду с оптимальным планом x опт = = (x1опт, x2опт,..., xnопт) будет рассматриваться расширенный оптимальный план
|
|
x ′опт = (x0опт, x1опт,..., xnопт),
где
x0 =.
Сокращенно оптимальный расширенный план обозначается как
х ‘ (Lц, c).
В целочисленном программировании рассматриваются целочисленные многогранники, под которыми понимаются многогранники с целочисленными вершинами, и целочисленные симплекс-таблицы, состоящие из целочисленных элементов. Заметим, что множество точек, ограниченное целочисленным многогранником, не обязательно состоит из целочисленных точек, требуется только целочисленность вершин (крайних точек) многогранника.
Основная идея методов отсечения заключается в построении такой эквивалентной задачи линейного программирования (А, с), при которой исходная задача целочисленного программиро-вания (Lц, c) сводится к ее решению. Иногда это называют линейной аппроксимацией целочислен-ного программирования (Lц, c).
Введем понятие правильного отсечения, физически означающее выбор такой гиперплоскости, которая разделяет оптимальные решения целочисленной линейной задачи х (Lц, c) и задачи линей-ного программирования х (L, c), причем, последняя не удовлетворяет условию целочисленности
х (L, c) Ë Lц.
|
∑ajxj ≤ β
j
выполняется при условиях
|
|
где а – вектор-строка, состоящая из элементов.
|
|
Метод отсечений позволяет построить процедуру последовательного выделения оптимального решения целочисленной задачи по известному решению соответствующей линейной задачи, в которой исключены требования целочисленности. Эта процедура решения задачи (Lц, c) может быть описана следующим образом:
1. На k-м этапе решается вспомогательная задача линейного программирования (Lk, c), k = 0, 1, 2, где L0 = L.
2. Если на k-м этапе оптимальное решение x (Lk, c), удовлетворяет условию целочисленности, то оно будет также оптимальным решением x (L0ц, c) исходной задачи (L0ц, c), так как на всех этапах множества целочисленных точек совпадают, т.е.
L0ц = L1ц = L2ц =...,
что является специальным условием при отсечении.
3. Если на k-м этапе решение не удовлетворяет условиям целочисленности, то x (Lk, c) не является оптимальным решением исходной целочисленной задачи. В этом случае переходят от k-го этапа к (k + 1)-му, добавляя к линейным ограничениям задачи (Lk, c) условие правильного отсечения
|
которое превращает многогранник (множество) Lk в многогранник Lk+1. Каждый конкретный метод имеет свой способ задания отсечения, но в алгоритмах Гомори гарантируется конечное число процедур.
В этом алгоритме впервые была реализована идея метода отсечения. Он дает конечную процедуру решения полностью целочисленной задачи линейного программирования, заданной в виде:
|
|
|
|
xj – целое.