Главная | Обратная связь

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

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

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

X0=a00-a01x1-a02x2-....-a0nxn,

при условии

xn+1=an+1,0-an+1,1x1-an+1,2x2-...-an+1,nxn,

xn+m=an+m,0- an+m,1x1-an+m,2x2-...-an+m,nxn,

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

Заметим, что xn+1, . ., хn+m —

слабые переменные, a x1 ... ., хn — исходные

переменные задачи (1). Если наряду с огра­ничениями (1) потребовать, чтобы все

хj , (j'=1, . . ., т) были целыми, то задача будет называться задачей целочисленного про­граммирования. Существует большое количество задач, особенно комбинаторных, которые можно сформулировать как задачи цело­численного программирования.

Ограничения (1) определяют выпуклую область OABCD в n-мер­ном

пространстве, как показано на рис. 13.1. Узлы целочисленной решетки на рис. 13.1 изображены точками. Такие точки, рас­положенные внутри области OABCD, являются допустимыми решениями задачи целочисленного программирования. Оптималь­ные решения задачи линейного программирования всегда распола­гаются на границе области решений. В данном случае граничные точки не являются даже допустимыми решениями, поскольку ни одна из них не целочисленна.

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

Рис, 13.1.

Обычно в ограничения задачи (1) включаются в тривиальные соотношения xj=—(—Xj) (j'=1, ...,n), а задача в матричной форме принимает вид х = А (-хn), (2), где х — вектор-столбец с компонентами Х0, x1, . . ., xn, xn+1, . . .,xn+m А — соответствующая матрица размера (п + т +

1) * (n + 1) и (—хn) — вектор с компонентами (1, —x1,—x2, . . ., —xn), представляющими собой небазисные переменные исходной таблицы.

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

Причины представления переменных в виде (—x1), (—x2, .

. . . . ., (—xn)) — чисто исторические, но это стало обычной

прак­тикой в целочисленном программировании. Будем использовать αj

(j = 0, 1, . . ., п) для обозначения j-го столбца

текущей таб­лицы и aij (i = 0, 1, . . ., п + т;

j = 0, 1, . . ., n) для обозна­чения элемента 1-й строки и 7-го столбца

таблицы. Предполагается, что все a,ij в исходной таблице целые.

Следовательно, все слабые переменные xn+1, . . ., Х

n+m должны быть также неотрицатель­ными целыми числами.

При изложении алгоритма для решения целочисленных задач будем следовать работе Гомори. Вначале задача целочислен­ного программирования рассматривается как линейная программа и алгоритм решает ее с помощью прямого или двойственного симплекс-метода. В конце работы алгоритма аij≥0 (i = 1, ... . . ., п + т) и a0j≥ 0 (j'= 1, . . ., n). (Для получения исходного двойственного допустимого решения введем дополнительное огра­ничение xn+m+1 == М — X1 —x2 — . . . — xn≥ 0, где M — до­статочно большая константа, и проделаем одну итерацию с этой строкой и лексикографически минимальным столбцом в качестве ведущего.) Если аi0 ≥ 0 и целые для всех i, то получено оптимальное решение целочисленной задачи. В этом случае решение получается сразу, без использования ограничений целочисленности. Если аi0≥ 0, но не все целые, добавим к ограничениям (1) еще одно. Новое ограничение записывается внизу таблицы так, чтобы она перестала быть прямо допустимой, т. е. аi0 <О для i == п + т + 1. Затем используется двойственный симплекс-метод с целью сделать все аi0≥ 0. Если аi0 получаются нецелыми, в таблицу добавляются новые ограничения до тех пор, пока аi0 (i = 1, . . ., n, . . ., n + m) не станут все целыми и неотрица­тельными.

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

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

Каждый раз после проведения итерации симплекс-метода происходит изменение множества небазисных переменных. Таб­лица также меняется. Будем использовать t для обозначения t-й. таблицы. Матричное уравнение (2) запишется как Хt = Аt (-хtn), (3) где х° — вектор-столбец с n + т + 1 компонентами, А° — матри­ца размера (п + т + 1)*(n + 1) и (—х0n) — вектор с компо­нентами (1, —x1, . . ., —xn), представляющими собой текущие небазисные переменные, взятые со знаком минус. Если в матрице А а0i≥0 (j = 1, . . ., n), а00 ≡ 0 (mod 1) 1 } и аi0 ≥ 0 (i=1, . . ., п+т) — целые неотрицательные числа, то получено оптимальное решение целочисленной задачи.

Если аi0 не все целые, введем дополнительное ограничение. Рассмотрим

такое уравнение из (3), в котором аi0m нецелое. Опуская индексы строки, имеем (4) x=a0+∑aj(-xj) где xj в правой части — текущие небазисные переменные и a0 — нецелое. Поскольку требуется, чтобы х было целым, или х ≡[1]0 (mod1), правая часть уравнения (4) также должна удовлетворять условию 0≡a0+∑aj(-xj) (mod1). (5)

Это условие должно выполняться при допустимом целочисленном решении. Поскольку требуется, чтобы xj ,были целыми, можно алгебраически складывать с (5) отношения 0≡f0+∑jfi(-xi) (mod1) (0<f0<1, 0≤fj<1). (6)

Условие (6) эквивалентно следующему: ∑fjxj≡f0 (mod1). (7)

В соотношении (7) f0 – константа, меньшая единицы ,и поскольку f j≥0 и xj≥, левая часть всегда положительна. Т.к. (7) – отношение сравнения по модулю 1, левая часть может принрмать только значения вида f0, f0+1,.., т.е. ∑fjxj≥f0 (8)

Неравенство (8) можно представить в виде уравнения с помощью введения неотрицательной целочисленности слабой переменной S=-f0+∑fjxj≥0. (9)

Это уравнение можно приписать внизу таблицы и использовать в качестве ведущей строки. Таким образом, переменная s войдет в базис с отрицательным значением

(—fо)- После итерации слабая переменная s станет небазисной с нулевым

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

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