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

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

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

 

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

 

s=-fti0-∑ftij(-xtj).                                                           (10)

 

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

     

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

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

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

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

 

S=-ft00-∑ft0(-xtj).

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

 

     at+100=at00-at0s* ft00/ftos

или

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

∑ε (t)<c

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

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

 

    At+110=at10-at1s*ft10/ft1s,

 

где 0<ft1s<l и 0<ft1s<1. Здесь at1s —неотрицательное число, большее ft1s. (Если at1s—отрицательно и αts—лексикографически положителен, то аt0s положительно и, следовательно, аt00 не может

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

 

at+110≤at10-ft10=[at10],

 

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

 

α0t+1=αt0-a10/a1s*αts,

 

Из того, что αts > 0 и a1s <. О, следует, что a0s > 0, т. е. значение a00 строго уменьшится, что противоречит допущению о неизменности значения a00. Если a1j≥ 0 для всех j = 1, . . ., s, ... . . ., n, то задача не имеет допустимых решений. (Заметьте, что ведущий элемент должен быть отрицательным.)

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

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

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

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

 

 

ПОЛНОСТЬЮ ЦЕЛОЧИСЛЕННЫЙ АЛГОРИТМ

 

Здесь будет описан другой алгоритм для решения задач целочисленного программирования. Этот алгоритм назван полностью целочисленным, потому что если исходная таблица состоит из целочисленных элементов, то все таблицы, получающиеся в процессе работы алгоритма, содержат только целочисленные элементы. Подобно двойственному симплекс-методу, алгоритм начинает работать с двойственно допустимой таблицы. Если аi0 (i = 1, . . ., n+m) — неотрицательные целые, то задача решена. Если для какой-нибудь строки аi0 < 0, то составляется новое уравнение и записывается внизу таблицы. Эта строка затем служит ведущей. После этого используется двойственный симплекс-метод. Все элементы дополнительной строки должны быть целыми числами, а ведущий элемент равен —1. Введенная таким образом ведущая строка сохранит таблицу целочисленной. Заметим, что в предыдущем алгоритме в качестве производящей строки выбиралась строка с нецелым аi0. В данном случае производящей строкой становится строка с отрицательным аi0.

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

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

 

при условиях

 

(1)

 

 

Условия (1) могут быть записаны как

 

(2)

 

Предположим, что для t = 0 (т. е. для исходной таблицы) все аij — целые и столбцы αj (j = 1, . . ., n) — лексикографически положительны. Тогда все столбцы на протяжении вычислений остаются лексикографически положительными.

Прежде чем изложить способ получения дополнительного ограничения из производящей строки, введем новое представление чисел. Пусть [x] обозначает наибольшее целое число, не превосходящее х. Для любого числа у (положительного или отрицательного) и положительного λ можно записать

 

(3)

 

где 0≤ry < λ (ry — неотрицательный остаток от деления нацело у на λ). В частности, 1 = [1/ λ ]λ + г. Поэтому если λ> 1, то [1/λ] = 0 и г = 1. Если λ = 1, то [1/λ,] = 1 и г == 0.

Так же как и ранее, вводимое дополнительное неравенство должно выполняться при любом целом решении задачи (1). Рассмотрим некоторое уравнение в t-таблице (опуская индекс строки) с a0 < 0:

 

 

(4)

 

где х — соответствующая компонента вектора х, a xtj — текущие небазисные переменные. Можно выразить x, a0 и аj, используя введенное выше представление (З):

 

(5) и (6)

(j=0,1….,n)

 

Подставив выражения (5) и (6) в (4), и переставив члены, получим

(7)

 

Поскольку rj ≥0, r≥0  и на переменные х и xtj наложено требование неотрицательности, левая часть уравнения (7) всегда неотрицательна. Рассмотрим выражение в правой части, заключенное в фигурные скобки. Коэффициенты в этом выражении представляют собой целые числа, а переменные подчинены требованию целочисленности. Поэтому все выражение в скобках должно быть целым. Обозначим его через s, т. е.

 

  (8)

Целочисленная слабая переменная s является неотрицательной. Действительно, если бы s было отрицательным, т. е. принимало значения —1, —2, . . ., то умножение на λ (λ > r0) сделало бы всю правую часть уравнения (7) отрицательной, в то время как левая часть неотрицательна.

Рассмотрим два случая λ=1 и λ>1. Подставляя в уравнение (8) выражение для x из (4), получим:

S=[a0]+∑[aj] (-xtj)-{a0+∑aj(-xtj)}=-f0-∑fj (-xtj).           (9)

Полученное уравнение есть не что иное, как отсечение Гомори. Для λ>1 имеем [1/λ]=02  и уравнение (8) приобретает вид

 

(10)

Уравнение (10) должно выполняться для любого допустимого целочисленного решения задачи (1). Заметим, что если а0 < О,. то [a0/λ] < 0 в уравнении (10). Поэтому уравнение (10) может использоваться в качестве ведущей строки в двойственном симплекс-методе. В частности, всегда можно выбрать λ достаточно большим, так чтобы ведущий элемент [aj/λ] в строке (10) стал:

равным —1, что позволит сохранить целочисленность таблицы. Выбор соответствующего λ будет влиять на скорость сходимости алгоритма. Прежде всего опишем сам алгоритм. В качестве начального необходимо взять двойственно допустимое решение, которое-можно получить добавлением ограничения xn+m+1 = М — x1 — ... ... —xn,  где М — достаточно большая константа, и проведением одной итерации с добавленной строкой и с лексикографически минимальным столбцом, взятыми в качестве ведущих. Алгоритм состоит из следующих шагов.

Ш а г 0. Начать с двойственно допустимой матрицы А° в уравнении (2), элементы которой — целые числа (как будет видно из дальнейшего, матрица А° может содержать и нецелые элементы).

Шаг 1. Среди строк с аi0 < 0 (i = 1, . . ., n+m) выбрать строку с наименьшим значением i; эта строка станет производящей. (Если аi0≥ 0 (i= 1, . . ., n + m), то задача решена.)

Ш а г 2. Выбрать λ > 0 (правило выбора будет описано дальше) и написать внизу таблицы дополнительную строку

Эта строка выбирается в качестве ведущей.

Ш а г 3. Провести шаг двойственного симплекс-метода, вычеркнуть дополнительную строку и вернуться к шагу 1.

Доказательство конечности. Доказательство конечности проводится в предположении, что существует нижняя граница целевой функции x0. Использование двойственного метода гарантирует выполнение условия

 

Если a00 уменьшается, то уменьшается на целое число, поскольку все числа остаются целыми, и, следовательно, через конечное число шагов a00 станет меньше x0. Если алгоритм бесконечен, то a00 должно оставаться Неизменным для всех t > to. Рассмотрим тогда компоненту a10, столбца α0. Если a10 уменьшается, то на целое число. Когда a10 становится отрицательным, первая строка должна быть выбрана в качестве производящей. Если а1j< О для всех j, то задача неразрешима.

Теперь опишем правило выбора λ в шаге 2 полностью целочисленного алгоритма. Пусть производящая строка имеет вид

и дополнительная строка

Для любого аj<0 всегда можно выбрать λ  достаточно большим, чтобы [aj/λ]|==—1. Согласно лексикографическому двойственному симплекс-методу, ведущий столбец αs выбирается по правилу

Поскольку [as/λ]=-1 и [aj/λ] – отрицательные числа, т.е. -1, -2,…….., -μj, имеем

 

(11)

Таким образом, αs должен быть лексикографически минимальным столбцом. Последнее означает, что среди всевозможных столбцов (с avj < 0) ведущий столбец должен быть лексикографически минимальным вне зависимости от того, какое значение λ выбирается.

Теперь рассмотрим два значения К, при каждом из которых выполняется условие [as/λ1]=—l и [as/λ2]=—l. Столбец α0 изменяется следующим образом:

 

Следовательно, чем меньше λ, тем сильнее лексикографически уменьшится нулевой столбец. Значение λ следует выбирать так, чтобы, во-первых, ведущий элемент стал равным —1 и, во-вторых, чтобы λ давало максимальное уменьшение столбцу α0. Правило формулируется следующим образом.

 

Шаг 0. Пусть строка с номером v является производящей.

Шаг 1. Пусть αs, — лексикографически минимальный столбец среди столбцов с αvj< 0.

Шаг 2. Для каждого с αvj< 0 , пусть μi—наибольшее целое, такое ,что αs<αj/μj

Шаг 3. Пусть [μj=-avj/λj]. Тогда

 

 

Шаг 4. Положить λ = max λj  для аvj < 0.

 

Правило выбора λ, описанное выше, позволяет сделать ведущий элемент равным —1, при этом будет сохраняться двойственная допустимость таблицы и в то же время нулевой столбец будет максимально лексикографически уменьшаться. Следует заметить, что отсечение Гомори не является самым «сильным» возможным неравенством. Оно также может быть «сильнее» или «слабее» самого производящего неравенства. Например, пусть производящей строкой будет 

X= -4-3 (-x1) – 5 (-x2)                                             (12)

Если использовать λ=2, то получим отсечение

S= -2-2 (-x1) – 3 (-x2)≥0                                           (13)

Для λ=3 имеем

S= -2-1 (-x1) – 2 (-x2)≥0                                            (14)

Для λ=4

S=-1-1 (-x1)-2 (-x2)≥0                                                 (15)

 

Как видно, неравенство (14) сильнее, чем (12), (12) сильнее, чем (13), а (13) сильнее, чем (15).