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

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

Максимизировать

X₀=a₀₀-a₀₁x₁-a₀₂x₂-……..-a_0nx_n,

при условии

x_n+1=a_n+1,0-a_n+1,1x₁-a_n+1,2x₂-…….-a_n+1,nx_n,.

_.

x_n+m=a_n+m,0- a_n+m,1x₁-a_n+m,2x₂-…….-a_n+m,nx_n,

x_j≥0 (j=1,…….,n+1,…….,n+m).

Заметим, что x_n+1,.., х_n+m — слабые переменные, a x₁...., х_n — исходные переменные задачи (1). Если наряду с огра­ничениями (1) потребовать, чтобы все х_j, (j'=1,..., т) были целыми, то задача будет называться задачей целочисленного про­граммирования. Существует большое количество задач, особенно комбинаторных, которые можно сформулировать как задачи цело­численного программирования.

Ограничения (1) определяют выпуклую область OABCD в n-мер­ном пространстве, как показано на рис. 13.1. Узлы целочисленной решетки на рис. 13.1 изображены точками. Такие точки, рас­положенные внутри области OABCD, являются допустимыми решениями задачи целочисленного программирования. Оптималь­ные решения задачи линейного программирования всегда распола­гаются на границе области решений. В данном случае граничные точки не являются даже допустимыми решениями, поскольку ни одна из них не целочисленна. Предположим, что область допу­стимых решений сужена до выпуклой оболочки допустимых целых точек внутри допустимой области. На рис. 13.1 эта выпук­лая оболочка показана затененной областью OEFGH. Эту зате­ненную область можно рассматривать как область допустимых решений некоторой другой задачи линейного программирования. Действительно, если к задаче линейного программирования, опре­деляющей допустимую область OABCD, добавить ограничение типа RR', как показано на рис. 13.1, то вновь полученная задача будет иметь OEFGH в качестве области допустимых решений. Такая вновь полученная область обладает двумя важными свой­ствами: во-первых, она содержит все допустимые целочисленные точки исходной задачи линейного программирования (поскольку она является выпуклой оболочкой этих точек), во-вторых, все крайние точки новой области — целочисленны. Поэтому любое базисное оптимальное решение модифицированной задачи линей­ного программирования имеет своими компонентами целые числа и является оптимальным ре­шением исходной задачи цело­численного программирования.

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

Как только это будет сде­лано, можно решать моди­фицированную задачу линей­ного программирования лю­бым обычным методом, и полученное базисное опти­мальное решение автоматически будет целочисленным. Представ­ленный ниже целочисленный алгоритм обладает следующими свойствами: 1) все дополнительные ограничения сохраняют допустимые точки исходной целочисленной задачи; 2) за конеч­ное число шагов создается достаточное количество дополнитель­ных ограничений для того, чтобы оптимальное решение моди­фицированной задачи было целочисленным; 3) дополнительные ограничения (гиперплоскости) проходят по крайней мере через одну целочисленную точку, хотя и не обязательно находящуюся внутри выпуклой оболочки; 4) каждое новое ограничение сокра­щает область допустимых решений исходной задачи целочислен­ного программирования. Следует подчеркнуть, что оптимальное решение исходной задачи может быть получено прежде, чем допустимая область сократится до размеров выпуклой оболочки. К тому же, поскольку оптимальное целочисленное решение определяется пересечением п гиперплоскостей, таких гиперпло­скостей существует не более, чем это необходимо; некоторые из них могут быть ограничениями исходной задачи.

Рис, 13.1.

Обычно в ограничения задачи (1) включаются в тривиальные соотношения xj=—(—X_j) (j'=1,...,n), а задача в матричной форме принимает вид

х = А (-х_n), (2)

где х — вектор-столбец с компонентами Х₀, x₁,..., x_n, x_n+1,...,x_n+m А — соответствующая матрица размера (п + т + 1) * (n + 1) и (—х_n) — вектор с компонентами (1, —x₁,—x₂,..., —x_n), представляющими собой небазисные переменные исходной таблицы. Задачу целочисленного программирования также можно записать в виде таблицы.

Причины представления переменных в виде (—x₁), (—x₂ ,......, (—x_n)) — чисто исторические, но это стало обычной прак­тикой в целочисленном программировании. Будем использовать α_j(j ⁼ 0, 1,..., п) для обозначения j-го столбца текущей таб­лицы и a_ij (i = 0, 1,..., п + т; j = 0, 1,..., n) для обозна­чения элемента 1-й строки и 7-го столбца таблицы. Предполагается, что все a,ij в исходной таблице целые. Следовательно, все слабые переменные x_n+1,..., Х_n+m должны быть также неотрицатель­ными целыми числами.

При изложении алгоритма для решения целочисленных задач будем следовать работе Гомори. Вначале задача целочислен­ного программирования рассматривается как линейная программа и алгоритм решает ее с помощью прямого или двойственного симплекс-метода. В конце работы алгоритма а_ij≥0 (i = 1,......, п + т) и a_0j≥ 0 (j' = 1,..., n). (Для получения исходного двойственного допустимого решения введем дополнительное огра­ничение x_n+m+1 == М — X₁ —x₂ —... — x_n≥ 0, где M — до­статочно большая константа, и проделаем одну итерацию с этой строкой и лексикографически минимальным столбцом в качестве ведущего.) Если а_i0≥ 0 и целые для всех i, то получено оптимальное решение целочисленной задачи. В этом случае решение получается сразу, без использования ограничений целочисленности. Если а_i0≥ 0, но не все целые, добавим к ограничениям (1) еще одно. Новое ограничение записывается внизу таблицы так, чтобы она перестала быть прямо допустимой, т. е. аi₀<О для i == п + т + 1. Затем используется двойственный симплекс-метод с целью сделать все аi₀≥ 0. Если аi₀ получаются нецелыми, в таблицу добавляются новые ограничения до тех пор, пока аi₀ (i = 1,..., n,..., n + m) не станут все целыми и неотрица­тельными.

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

Каждый раз после проведения итерации симплекс-метода происходит изменение множества небазисных переменных. Таб­лица также меняется. Будем использовать t для обозначения t-й. таблицы. Матричное уравнение (2) запишется как

Х^t = А^t (-х^t_n), (3)

где х° — вектор-столбец с n + т + 1 компонентами, А° — матри­ца размера (п + т + 1)*(n + 1) и (—х⁰_n) — вектор с компо­нентами (1, —x₁,..., —x_n), представляющими собой текущие небазисные переменные, взятые со знаком минус. Если в матрице А а0i≥0 (j = 1,..., n), а₀₀ ≡ 0 (mod 1) ¹} и а_i0 ≥ 0 (i=1,..., п + т) — целые неотрицательные числа, то получено оптимальное решение целочисленной задачи. Если а_i0 не все целые, введем дополнительное ограничение. Рассмотрим такое уравнение из (3), в котором а_i0m нецелое. Опуская индексы строки, имеем

(4) x=a₀+∑a_j(-x_j)

где x_j в правой части — текущие небазисные переменные и a₀ — нецелое. Поскольку требуется, чтобы х было целым, или х ≡[1]0 (mod1), правая часть уравнения (4) также должна удовлетворять условию

0≡a₀+∑a_j(-x_j) (mod1). (5)

Это условие должно выполняться при допустимом целочисленном решении. Поскольку требуется, чтобы x_j,были целыми, можно алгебраически складывать с (5) отношения 0≡f₀+∑_jf_i(-x_i) (mod1) (0<f₀<1, 0≤f_j<1). (6)

Условие (6) эквивалентно следующему:

∑f_jx_j≡f₀ (mod1). (7)

В соотношении (7) f₀ – константа, меньшая единицы,и поскольку f_j≥0 и x_j≥, левая часть всегда положительна. Т.к. (7) – отношение сравнения по модулю 1, левая часть может принрмать только значения вида f₀, f₀+1,……, т.е.

∑f_jx_j≥f₀ (8)

Неравенство (8) можно представить в виде уравнения с помощью введения неотрицательной целочисленности слабой переменной

S=-f₀+∑f_jxj≥0. (9)

Это уравнение можно приписать внизу таблицы и использовать в качестве ведущей строки. Таким образом, переменная s войдет в базис с отрицательным значением (—fо)- После итерации слабая переменная s станет небазисной с нулевым значением. Ведущая строка превратится в тождество s ≡ (—1) (—s) и может быть исключена. Будем называть переменную s в уравнении (9) слабой переменной Гомори. Ниже будет обсуждено, что произойдет, если сохранять все дополнительные строки, соответствующие слабым переменным Гомори.

Дадим доказательство конечности алгоритма. Доказательство будет проведено в предположении, что известна некоторая нижняя граница значения Х₀, т. е. если существует целочисленное решение, то оно больше, чем наперед заданная величина М (М может быть достаточно большой по абсолютной величине отрицательной кон­стантой). Такое предположение не слишком обременительно и всегда выполняется, если выпуклое множество, определяемое условиями (2), ограничено. Сначала изложим сам алгоритм.

Шаг 1. Решить задачу целочисленного программирования так, как если бы это была линейная программа, т. е. с помощью прямого или двойственного симплекс-метода. Если получено оптимальное решение задачи линейного программирования, то a_i0≥0 (i=1,..., m + n) и a_0i≥0(j = 1,..., n). Требуется также, чтобы а^t_j > 0 (j = 1,..., n).

Шаг 2. Если а_i0 — все целые, то задача решена, и решение получено без использования дополнительных ограничений. В про­тивном случае пусть а^t_i0 — первая нецелочисленная компонента в α^t₀. Тогда i-я строка называется производящей строкой. Записать внизу таблицы уравнение

s=-f^t_i0-∑f^t_ij(-x^t_j). (10)

Уравнение (10) называется отсечением Гомори. Проделать шаг двойственного симплекс-метода, используя в качестве ведущей строки отсечение Гомори (10). При этом таблица останется двой­ственно допустимой. Повторять до тех пор, пока все а_i0 (i = 1,..., m+n) не станут целыми неотрицательными. Если а_i0 на некотором шаге остается отрицательным, следующий шаг двойственного метода производится без введения отсечения Гомо­ри. (Если а_i0 становится отрицательным, нулевая строка не выби­рается в качестве производящей. Если a₀₀ становится нецелым, следует выбрать нулевую строку в качестве производящей.)

Изменение элементов а_ij (i = 0, 1,..., n+m; j = 0,......, n) в таблице за одну итерацию называется циклом. Для обозначения циклов используется буква t. Для доказательства конечности не достаточно условий α^t₀ >α₀ ^t+1 >М, поскольку a₀₀ может изменяться каждый раз на ε(t), а ∑ ε (t) = с.

Примером этого может служить ε (t) =1/2t. Другой возможностью является то, что а₀₀ остается равным фиксированному значению, большему нижней границы, в то время как некоторое а_i0 неогра­ниченно уменьшается. Чтобы увидеть, как преодолеваются эти трудности, необходимо в деталях рассмотреть шаги итерации.

При доказательстве будет показано, что либо после конечного числа шагов все компоненты 0-го столбца становятся неотрица­тельными целыми, либо не существует целого решения. Если a₀₀ остается постоянным для всех t ≥ t₀, то a^t₀₀ должно быть целым.

Предположим, что а^t₀₀—нецелое. Пусть а^t₀₀ =n^t₀₀+f^t_00,где n^t₀₀— целое и 0 < f^t₀₀ < 1. Тогда 0-я строка становится производящей и требуется ввести дополнительное ограничение

S=-f^t₀₀-∑f^t₀(-x^t_j).

Если s-й столбец является ведущим, то

a^t+1₀₀=a^t₀₀-a^t_0s* f^t₀₀/f^t_os

или

Другими словами, a₀₀ уменьшится по крайней мере до ближайшего целого. Следовательно, a₀₀ не может уменьшаться на ε(t) при

∑ε (t)<c

Если a₀₀ каждый раз уменьшается до ближайшего целого или на целую величину, то после конечного числа шагов оно станет меньше любого наперед заданного М (М — предпола­гаемая нижняя граница). Если алгоритм бесконечен, то a₀₀ должно оставаться некоторым фиксированным целым числом для t> t₀. Предположим, что это произошло.

Тогда рассмотрим а₁₀. Так же как и a₀₀, a₁₀ не может оставаться нецелым значением. Если бы это было так, то, поскольку a₀₀ — целое, первая строка стала бы производящей и после введения отсечения Гомори и итерации симплекс-метода мы получили бы

A^t+1₁₀=a^t₁₀-a^t_1s*f^t₁₀/f^t_1s,

где 0<f^t_1s<l и 0<f^t_1s<1. Здесь a^t_1s —неотрицательное число, большее f^t_1s. (Если a^t_1s—отрицательно и α^t_s—лексикографически положителен, то а^t_0s положительно и, следовательно, а^t₀₀ не может

не измениться.) Отсюда

a^t+1₁₀≤a^t₁₀-f^t₁₀=[a^t₁₀],

т. е. а₁₀ уменьшается по крайней мере до ближайшего целого. Поэтому а₁₀ либо будет оставаться некоторым фиксированным целым числом, либо после конечного числа шагов станет отрица­тельным. Если а₁₀ станет отрицательным, то первая строка будет ведущей и

α₀^t+1=α^t₀-a₁₀/a_1s*α^t_s,

Из того, что α^t_s > 0 и a_1s <. О, следует, что a_0s > 0, т. е. зна­чение a₀₀ строго уменьшится, что противоречит допущению о неиз­менности значения a₀₀. Если a_1j≥ 0 для всех j = 1,..., s,......, n, то задача не имеет допустимых решений. (Заметьте, что ведущий элемент должен быть отрицательным.)

Таким образом, остается единственная возможность—а₁₀ через конечное число шагов должно стать некоторым неотрица­тельным целым числом и больше не меняться.

Аналогичные рассуждения можно провести и для остальных компонент вплоть до (n+m)-й, что завершит доказательство конечности. Заметим, что нам надо, чтобы только первые n + 1 компонент вектора α₀ были целыми неотрицательными числами, a₀₀ <> 0 и a_ij (i = n+1,…..,n+m) — неотрицательные.

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

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