Гельруд Я.Д. Линейное программирование. Учебно-методический комплекс
Подождите немного. Документ загружается.
109
случай отыскания оптимального решения задачи целочисленного
программирования, содержащей 100 переменных, каждая из которых может
принимать всего два значения – 0 и 1. Время перебора всех 2
100
возможных
решений на самой быстродействующей ЭВМ намного превышает
продолжительность человеческой жизни.
Практически эффективные алгоритмы. Из всего изложенного выше
очевидно, что общий алгоритм решения задач целочисленного
программирования должен исключать необходимость явного перебора всех
допустимых альтернатив. Требуются методы, обеспечивающие частичный
перебор сравнительно небольшого числа допустимых вариантов и неявный
перебор всех остальных. Напомним, что симплексный метод, применяемый
для решения обычных задач линейного программирования, обладает именно
такими характеристиками. Этот метод предусматривает оценку лишь
небольшого числа всех допустимых базисных решений.
Разработка таких алгоритмов для целочисленных задач представляет собой
область интенсивных исследований специалистов по прикладной математике.
Пока еще преждевременно выделять какие-либо алгоритмы, утверждая, что
они столь же эффективны для целочисленных задач, как симплексный
алгоритм для обычных задач линейного программирования. По существу,
рассматривая любой из
предложенных до сих пор алгоритмов, легко
построить примеры целочисленных задач, для решения которых с помощью
этих алгоритмов требуется объем вычислений, эквивалентный полному
перебору. Поэтому практическую эффективность любого из алгоритмов
нужно в конечном счете оценивать эмпирически, выделяя классы задач, для
которых рассматриваемый алгоритм оказывается наиболее выгодным.
В настоящее время известны два основных
подхода к отысканию точного
оптимального решения задач целочисленного программирования.
1. Методы отсекающих плоскостей (методы отсечения). Предложено
несколько вариантов этого подхода к решению целочисленных задач. Один из
них, излагаемый в следующем разделе, предназначен для полностью
110
целочисленной модели. Исходным моментом является оптимальное решение
соответствующей задачи линейного программирования, полученной в
результате отбрасывания условий целочисленности. На каждой итерации
добавляется линейное ограничение, удовлетворяющее целочисленному
решению исходной задачи, но исключающее текущее нецелочисленное
решение. Вычислительный процесс прекращается, как только будет
достигнуто любое целочисленное решение. Сходимость обеспечивается за
конечное, но иногда очень большое
число итераций.
2. Методы возврата. В этой группе методов также имеются различные
модификации. Первый метод, названный методом «ветвей и границ»,
предназначен для решения частично целочисленных задач. Как и в методе
отсечения, решение задач и начинается с отыскания оптимального решения
соответствующей регулярной задачи линейного программирования. Затем
формируется семейство связанных, но различных
задач линейного
программирования. Ниже на примере задачи коммивояжера рассматривается
несколько вариантов этого подхода.
Существуют другие подходы к решению целочисленных задач, которые
хотя и не гарантируют отыскания оптимального решения, тем не менее в ряде
частных случаев позволяют его находить, а нередко дают решения, близкие к
оптимальному.
Один из таких подходов заключается в
использовании случайной выборки
допустимых решений с последующим улучшением каждого попавшего в
выборку решения в случае, когда возможность улучшения соответствующего
решения удается достаточно просто обнаружить. Если, к примеру, применить
этот подход при решении задачи коммивояжера с п городами, то нужно взять
случайную выборку перестановок городов 2, 3, . . ., п из общего числа (п – 1)!
перестановок
, а затем сравнить длину соответствующих циклов. Другой
подход, получивший название эвристического программирования, сводится к
применению как простых, так и достаточно сложных правил, основанных на
некоторых рациональных соображениях, а также метода проб и ошибок для
111
отыскания допустимого и по возможности близкого к оптимальному решения.
Для задачи коммивояжера простейшим правилом такого рода является переезд
из города j в ближайший город, который еще не посещался. Метод проб и
ошибок в этом случае в известной мере сводится к оценке эффекта
поочередной замены одного города другим в последовательности объезда
городов
в пробном цикле с точки зрения уменьшения общего расстояния
(общей длины цикла).
В ряде практических ситуаций такие методы отыскания решений
оказались достаточно эффективными.
6.4. Алгоритмы отсечения (метод целочисленных форм)
Нижеследующий элементарный пример поясняет основную идею
алгоритма. Рассмотрим задачу:
максимизировать 5x
1
+ 1x
2
(6.4.1)
при ограничениях
2x
1
+ 1x
2
= 3, (6.4.2)
x
1
и x
2
– неотрицательные целые. (6.4.3)
Как легко видеть, x
1
=
3
/
2
есть оптимальное решение задачи линейного
программирования (6.4.1) и (6.4.2) в случае, когда условие (6.4.3) ослаблено и
имеет вид x
1
≥0, x
2
≥ 0. Решение этой задачи недопустимо по условию (6.4.3),
поскольку оно является дробным. Заметим, однако, что из (6.4.2) и (6.4.3)
следует ограничение в виде линейного неравенства
x
1
≤ 1. (6.4.4)
Оптимальное решение задачи линейного программирования (6.4.1), (6.4.2)
и (6.4.4) при x
1
≥ 0, x
2
≥ 0 равно x
1
= 1 и x
2
= 1. Подчеркнем, что это решение
целочисленно. Следовательно, полученное решение задачи линейного
программирования является оптимальным для задачи (6.4.1) – (6.4.3),
поскольку оно допустимо по условию (6.4.3).
112
По существу, оптимальное
решение задачи целочисленного
программирования было найдено путем построения и решения расширенной
задачи линейного программирования, содержащей линейные ограничения,
вытекающие из условий исходной целочисленной задачи. В данном случае
удалось чрезвычайно просто обнаружить ограничение (6.4.4), позволившее
реализовать этот метод на элементарном примере. Излагаемый ниже алгоритм
обеспечивает систематический поиск таких ограничений для любой задачи
целочисленного программирования
.
Предложено несколько вариантов алгоритмов, основанных на методе
отсечения. Достоинством выбранного варианта является простота его
описания.
В алгоритме отсечения вначале рассматривается выпуклое множество,
определенное линейными ограничениями и условиями неотрицательности
переменных исходной задачи, и отыскивается экстремальная точка этого
множества, Если такое решение оказывается нецелочисленным, то добавляют
ограничение, отсекающее текущую экстремальную точку и
уменьшающее
«объем» выпуклого множества. Однако новое ограничение не отсекает ни
одной экстремальной точки выпуклой оболочки, принадлежащей допустимым
целочисленным решениям. В конце концов, вводится такое число
дополнительных ограничений, что экстремальная точка усеченного выпуклого
множества совпадает с экстремальной точкой выпуклой оболочки.
Геометрическая интерпретация работы алгоритма будет пояснена на примере,
приведенном в этом
разделе.
Подробное изложение алгоритма. Допустим, что полностью
целочисленная задача имеет следующий вид
максимизировать
∑
=
n
j
jj
xc
1
(6.4.5)
при ограничениях:
∑
=
n
j
j
j
i
xa
1
= b
i
(i=1,2,…,m), (6.4.6)
113
все x
j
– неотрицательные целые. (6.4.7)
Предположим, что при ограничениях (6.4.6) и (6.4.7) существует
допустимое решение, и что в оптимальном решении целевая функция
принимает конечное значение. Прежде чем сформулировать конкретные шаги
алгоритма, покажем в общем виде, как построить дополнительные линейные
ограничения, которым должно удовлетворять любое решение, допустимое по
условиям (6.4.6) и (6.4.7).
Рассмотрим любое линейное уравнение, которое
можно получить с
помощью алгебраических операций над линейными ограничениями (6.4.6),
например путем сложения двух или более уравнений или умножения
уравнения на отличную от нуля постоянную. Тогда, если некоторое решение
удовлетворяет условию (6.4.6), оно должно также удовлетворять и новому
уравнению. Примем, что выражение
∑
=
n
j
jj
xa
1
= b (6.4.8)
определяет именно такое новое ограничение. Возможно, одна или несколько
величин а
j
и b являются дробными, скажем 2,5 или
10
/
3
. Обозначим символом
[d] целую часть d, т. е. наибольшее целое число, меньшее или равное
действительному числу d. Например,
[2,5]=2, [-2,5]== -3, [
10
/
3
]=3, [-
10
/
3
]= - 4.
Любые значения x
j
, удовлетворяющие ограничению (6.4.6), а,
следовательно, и (6.4.8), должны, очевидно, удовлетворять более слабому
ограничению
∑
=
n
j
jj
xa
1
][ ≤ b (6.4.10)
Поскольку сумма в левой части (6.4.10) должна быть целочисленной,
(6.4.10) можно усилить следующим образом:
∑
=
n
j
jj
xa
1
][ ≤ [b]. (6.4.11)
Наконец, (6.4.11) можно преобразовать в равенство, добавив свободную
114
переменную
∑
=
n
j
jj
xa
1
][ +х = [b]. (целые части), (6.4.12)
Величина х должна быть целой. Таким образом, если к условию (6.4.6)
добавить линейное ограничение (6.4.12), задача все равно останется
полностью целочисленной.
Для упрощения словесного описания алгоритма выполним элементарные
преобразования над (6.4.8) и (6.4.12). Определим значения f
j
и f дробными
частями а
j
и b. (Для примера дробная часть величин 2,5 и -2,5 равна 0,5,
величины
10
/
3
равна
1
/
3
и величины —
10
/
3
равна
2
/
3
) Вычитая (6.4.8) из (6.4.12),
получим ограничение, состоящее только из дробных частей
∑
=
−
n
j
jj
xf
1
)( +х = - f (дробные части). (6.4.14)
В приводимом ниже алгоритме вместо (6.4.12) используется ограничение
(6.4.14).
Рассмотрим пример, показывающий, как работают новые ограничения
(6.4.12) и (6.4.14). В приведенном выше примере умножим обе части (6.4.2) на
1
/
2
, в результате чего получим
1x
1
+
1
/
2
x
2
=
3
/
2
. (6.4.15)
Теперь нужно показать, что применение к этому выражению формулы
(6.4.12) дает
1x
1
+ 0x
2
+ х = 1, (6.4.16)
что эквивалентно ограничению (6.4.4). Применение формулы (6.4.14) дает
–
1
/
2
x
2
+ х = –
1
/
2
(6.4.17)
откуда следует, что x
2
≥ 1.
Алгоритм отсечения состоит из следующих шагов.
Шаг 1. Найти оптимальное решение задачи линейного программирования
с целевой функцией (6.4.5) и линейными ограничениями (6.4.6), не учитывая
условия целочисленности (6.4.7), но требуя, чтобы все x
j
≥ 0.
Шаг 2. Прекратить вычисления, если текущее решение задачи линейного
115
программирования является целочисленным. В противном случае выбрать
какую-нибудь дробную базисную переменную. Составить ограничение
(6.4.14) из уравнения, содержащего эту базисную переменную в текущем
оптимальном решении задачи линейного программирования.
Шаг 3. Добавить к исходной задаче линейного программирования это
новое ограничение, найти новое оптимальное решение задачи с
дополнительным ограничением и вернуться к шагу
2.
Выбор дробной базисной переменной на шаге 2 является достаточно
произвольным. Однако, с практической точки зрения сходимость часто
повышается при выборе переменной с наибольшей дробной частью.
Теоретически доказано, что алгоритм сходится к оптимуму за конечное число
итераций. В конце этого раздела обсуждаются практические аспекты
реализации вычислительной схемы алгоритма. Однако отметим сразу, что
алгоритм не гарантирует получения допустимого целочисленного решения до
самой последней итерации и в этом смысле относится к категории
двойственных. Вследствие этого при преждевременном прекращении
вычислений нельзя получить допустимого решения. (Существуют алгоритмы,
базирующиеся на методе отсечения, которые относятся к разряду прямых в
том смысле, что на каждой итерации получаемое решение является
допустимым
и целочисленным, но эти алгоритмы в данной учебном пособии
не рассматриваются.)
Пример. Рассмотрим задачу:
максимизировать 21x
1
+ 11x
2
(6.4.20)
при ограничениях
7x
1
+ 4x
2
+ x
3
= 13, (6.4.21)
x
1
, x
2
, x
3
– неотрицательные целые, (6.4.22)
(Величину x
3
можно рассматривать как дополняющую переменную,
поскольку она не входит в целевую функцию.) В соответствии с принятой
схемой выразим целевую функцию линейным уравнением
x
0
– 21x
1
– 11x
2
=0, (6.4.23)
116
учитывая, что в этом примере на величину x
0
можно наложить условие
целочисленности. Получаем следующее решение задачи линейного
программирования:
x
0
+ x
2
+ 3x
3
=39 (строка 0),
x
1
+
4
/
7
x
2
+
1
/
7
x
3
=1
6
/
7
(строка 1). (6.4.24)
Поскольку согласно шагу 2 значение Xi является дробным, нужно добавить
ограничение (6.4.14), образованное из строки 1. Это ограничение выражается
следующим образом:
–
4
/
7
x
2
–
1
/
7
x
3
+ x
4
= –
6
/
7
(строка 2), (6.4.25)
где x
4
– целочисленная дополняющая переменная.
Переходя к шагу 3, получаем задачу линейного программирования (6.4.24),
дополненную (6.4.25). Новое оптимальное решение выражается следующими
уравнениями:
x
0
+2
3
/
4
x
3
+ 1
3
/
4
x
4
=37
1
/
2
(строка 0),
x
1
+ x
4
=1 (строка 1), (6.4.26)
x
2
+
1
/
4
x
3
– 1
3
/
4
x
4
=1
1
/
2
(строка 2).
Возвращаясь к шагу 2, получаем, что новое ограничение, образованное из
строки 2, имеет вид
–
1
/
4
x
3
–
1
/
4
x
4
+ x
5
= –
1
/
2
(строка 3) (6.4.27)
и что на шаге 3 оптимальное решение задачи линейного программирования
(6.4.26) – (6.4.27) описывается уравнениями:
x
0
+ x
1
+ 11x
5
= 33 (строка 0),
x
1
+
x
3
- x
5
= 1 (строка 1), (6.4.28)
2x
1
+
x
2
+ x
5
= 3 (строка 2),
x
1
+ x
4
=1 (строка 3).
При следующем возвращении к шагу 2 итерации заканчиваются
оптимальным целочисленным решением x
1
= 0, x
2
= 3 и x
3
= 1, что дает в
результате x
0
= 33. [Если бы решение (6.4.28) оказалось не целочисленным,
пришлось бы до выполнения следующего цикла оптимизации исключить
соотношение из строки 3, так как величина x
4
вновь вошла в базис.]
117
6.5. Метод ветвей и границ
Этот метод можно применять для решения как полностью, так и частично
целочисленных задач линейного программирования. Предположим для
определенности, что рассматриваемая модель имеет следующий вид:
максимизировать F =
∑
=
n
j
jj
xc
1
(6.5.1)
при ограничениях:
∑
=
n
j
j
j
i
xa
1
≤ b
i
(i=1,2,…,m), (6.5.2)
x
j
– целые, j = 1, 2, . . ., p (≤n), (6.5.3)
x
j
≥ 0 (j=1,2,…, n). (6.5.4)
Кроме того, допустим, что для каждой целочисленной переменной можно
задать верхнюю и нижнюю границы, в пределах которых безусловно
содержатся ее оптимальные значения
L
j
≤ x
j
≤ U
j
, j = 1, 2, . . ., р. (6.5.5)
Идея метода ветвей и границ основана на следующем элементарном
факте. Рассмотрим любую переменную x
j
и примем, что I есть некоторое целое
число, где L
j
≤ I ≤ U
j
– 1. Тогда оптимальное решение задачи (6.5.1) – (6.5.5)
будет удовлетворять либо линейному ограничению
x
j
≥ I +1, (6.5.6)
либо линейному ограничению
x
j
≤ I. (6.5.7)
Ниже дается формальное описание метода, а его вычислительные аспекты
обсуждаются в конце раздела. Метод ветвей и границ основан на решении
некоторого множества задач линейного программирования.
Алгоритм. На каждой итерации (обозначим ее t) имеется нижняя граница
(оценка), скажем
t
x
0
, оптимального значения целевой функции. Помимо
нижней границы имеется основной список задач линейного
программирования, подлежащих решению. Единственное отличие этих задач
118
друг от друга связано с изменением условий (6.5.5). На итерации 1 основной
список содержит всего одну задачу (6.5.1), (6.5.2), (6.5.4) и (6.5.5).
На произвольной итерации t выполняются следующие шаги.
Шаг 1. Прекратить вычисления, если основной список пуст. В противном
случае выбрать одну задачу линейного программирования из основного
списка.
Шаг 2. Решить выбранную задачу. Если она не
имеет допустимого
решения или если полученное в результате оптимальное значение целевой
функции меньше или равно
t
x
0
, то принять
1
0
+t
x =
t
x
0
и вернуться к шагу 1. В
противном случае перейти к шагу 3.
Шаг 3. Если полученное оптимальное решение задачи линейного
программирования удовлетворяет целочисленным ограничениям, то
зафиксировать его, принять
1
0
+t
x равным соответствующему оптимальному
значению целевой функции и вернуться к шагу 1. В противном случае перейти
к шагу 4.
Шаг 4. Выбрать любую переменную x
j
, j = 1, 2, . . ., р, не имеющую целого
значения в полученном оптимальном решении выбранной задачи линейного
программирования. Пусть b
j
соответствует этому значению, a [b
j
] определяет
наибольшее целое число, меньшее или равное b
j
. Добавить две задачи
линейного программирования в основной список. Эти две задачи идентичны
задаче, выбранной на шаге 1, за исключением того, что в одной из них нижняя
граница x
j
заменена на [b
j
] + l, а в другой верхняя граница x
j
заменена на [b
j
].
Принять
1
0
+t
x =
t
x
0
и вернуться к шагу 1.
При остановке алгоритма в случае, когда фиксируется допустимое
решение, дающее
t
x
0
, это решение оптимально, в противном случае
допустимого решения не существует. Как показывает приводимый ниже
пример, можно получить целочисленное решение, не дойдя до последней
итерации, однако при этом не известно, является ли оно действительно
оптимальным. По этой причине алгоритм можно назвать приближенно