Работа По теме: «Целочисленное программирование» (стр. 3 из 6)
Именно алгоритмы целочисленного программирования, которые будут описаны ниже, реализуют методы систематического введения дополнительных ограничений с целью сведения исходной допустимой области к выпуклой оболочке ее допустимых целочисленных точек.
Как только это будет сделано, можно решать модифицированную задачу линейного программирования любым обычным методом, и полученное базисное оптимальное решение автоматически будет целочисленным. Представленный ниже целочисленный алгоритм обладает следующими свойствами: 1) все дополнительные ограничения сохраняют допустимые точки исходной целочисленной задачи; 2) за конечное число шагов создается достаточное количество дополнительных ограничений для того, чтобы оптимальное решение модифицированной задачи было целочисленным; 3) дополнительные ограничения (гиперплоскости) проходят по крайней мере через одну целочисленную точку, хотя и не обязательно находящуюся внутри выпуклой оболочки; 4) каждое новое ограничение сокращает область допустимых решений исходной задачи целочисленного программирования. Следует подчеркнуть, что оптимальное решение исходной задачи может быть получено прежде, чем допустимая область сократится до размеров выпуклой оболочки. К тому же, поскольку оптимальное целочисленное решение определяется пересечением п гиперплоскостей, таких гиперплоскостей существует не более, чем это необходимо; некоторые из них могут быть ограничениями исходной задачи.
Рис, 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 – константа, меньшая единицы ,и поскольку fj≥0 и xj≥, левая часть всегда положительна. Т.к. (7) – отношение сравнения по модулю 1, левая часть может принрмать только значения вида f0, f0+1,……, т.е.
∑fjxj≥f0 (8)
Неравенство (8) можно представить в виде уравнения с помощью введения неотрицательной целочисленности слабой переменной
S=-f0+∑fjxj≥0. (9)
Это уравнение можно приписать внизу таблицы и использовать в качестве ведущей строки. Таким образом, переменная s войдет в базис с отрицательным значением (—fо)- После итерации слабая переменная s станет небазисной с нулевым значением. Ведущая строка превратится в тождество s ≡ (—1) (—s) и может быть исключена. Будем называть переменную s в уравнении (9) слабой переменной Гомори. Ниже будет обсуждено, что произойдет, если сохранять все дополнительные строки, соответствующие слабым переменным Гомори.
Дадим доказательство конечности алгоритма. Доказательство будет проведено в предположении, что известна некоторая нижняя граница значения Х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 становится нецелым, следует выбрать нулевую строку в качестве производящей.)