6.2. Методы решения задач целочисленного программирования
Методы решения задач целочис-1 Методы решения задач целочис-
ленного программирования можноленного профаммирования можно
классифицировать как методы отсе-классифицирован, как мегоды отсе-
-чений и комбинаторные методы,
чении и комбинаторные методы.»
Исходной задачей для демонстрации возможностей методов отсечений, используемых при решении линейных целочисленных задач, является задача с ослабленными ограничениями, которая возникает в результате исключения требования целочисленности переменных. По мере введения специальных дополнительных ограничений, учитывающих требование целочисленности, многогранник допустимых решений ослабленной задачи постепенно деформируется до тех пор, пока координаты оптимального решения не станут целочисленными. Название «методы отсечений» связано с тем обстоятельством, что вводимые дополнительные ограничения отсекают (исключают) некоторые области многогранника допустимых решений, в которых отсутствуют точки с целочисленными координатами.
В основе комбинаторных методов лежит идея перебора всех допустимых целочисленных решений. Разумеется, на первый план здесь вьщви-гается проблема разработки тестовых процедур, позволяющих непосредственно рассматривать лишь относительно небольшую часть указанных решений, а остальные допустимые решения учитывать некоторым косвенным образом. Наиболее известным комбинаторным методом является метод ветвей и границ, который также опирается на процедуру решения задачи с ослабленными ограничениями. При таком подходе из рассматриваемой задачи получаются две подзадачи путем специального «разбиения» пространства решений и отбрасывания областей, не содержащих допустимых целочисленных решений.
В случае, когда целочисленные переменные являются булевыми, применяют комбинированные методы. Булевы свойства переменных существенно упрощают поиск решения.
Методы, рассматриваемые в данной главе, предназначены для решения главным образом линейных целочисленных задач. Метод отсекающих плоскостей, разработанный Р. Гомори, включает дробный алгоритм (первый алгоритм Гомори), который используется при решении полностью целочисленных задач, а также алгоритм решения частично целочисленных задач (второй алгоритм Гомори). Алгоритм, реализующий метод ветвей и границ, был предложен А. Лэндом и А. Дойгом.
Для решения задач, содержащих только булевы переменные, обычно используется так называемый аддитивный алгоритм. Для решения нелинейных задач с булевыми переменными используется также обобщенный аддитивный алгоритм.
Основная идея метода отсекающих плоскостей состоит в том, что на каждом шаге рассматривается задача с ослабленными ограничениями (без требования целочисленности), для которой по специальному алгоритму строится некоторое дополнительное линейное ограничение (отсечение), отсекающее только некоторые нецелочисленные точки.
6.2.1. Метод отсекающих плоскостей. Рассмотрим задачу ЦЛП, записанную в стандартном виде (только ограничения равенства).
CjXj + ... + с„х„ шах (6.1)
%aijXj=\ /=l,...,w.
Xj >0,у = 1, XjZ,
где Z - множество целых чисел.
Основная идея метода отсечений состоит в том, что исходная задача ЦЛП первоначально рассматривается без требований целочисленности переменных. Если оптимальное решение такой задачи с ослабленными ограничениями тем не менее является целочисленным, то, как нетрудно показать, оно является оптимальным решением для исходной задачи. В противном случае по специальному алгоритму строится некоторое дополнительное линейное ограничение, обладающее следующими свойствами:
1)данное дополнительное ограничение отсекает полученное нецелочисленное оптимальное решение (т.е. оно не удовлетворяет данному дополнительному ограничению).
2)данное дополнительное ограничение не отсекает ни одного целочисленного решения (т.е. любое допустимое целочисленное решение предьщущей задачи удовлетворяет данному дополнительному ограничению). Дополнительное линейное ограничение, обладающее приведенными
свойствами, будем называть правильным отсечением.
Приведем алгоритм построения правильных отсечений, который предложен Гомори (метод Гомори). Пусть решение исходной задачи с ослабленными ограничениями (без требования целочисленности) симплекс-методом дало на последнем шаге, соответствующем оптимальному
решению, следующее выражение основных (базисных) переменных XI,...,х, через неосновные (свободные) переменные xi,...,x:
Xi=b[- d,mxXx - - - щХп(6.2)
~ Ьщ mm+lXm+lmww •
Как следует из теории симплекс-метода, оптимальным решением задачи в этом случае является вектор х* =(йр...,7,0,...,0). Если все компоненты этого вектора целочисленные, то, как было отмечено, это и есть оптимальное решение исходной задачи, иначе среди компонент вектора есть хотя бы одна нецелочисленная (с положительной дробной частью). Пусть это будет компонента b,{{bk]>0). Тогда рассмотрим следующее
линейное ограничение
{ bl }-{-...-{ }х„<0.(6.3)
Покажем, что линейное ограничение (6.3) удовлетворяет требованиям правильного отсечения.
1.Подставив компоненты вектора =(fej,...,fe,0,...,0) в неравенство
(6.3), получим ь<0, что противоречит выбору компоненты 6.
Таким образом, мы показали, что ограничение (6.3) отсекает нецелочисленное оптимальное решение исходной задачи.
2.Рассмотрим произвольное допустимое целочисленное решение X = (Xi,...,x„) задачи (6.1). Тогда компоненты вектора X удовлетворяют уравнениям (6.2). А, следовательно, выполнено следующее соотношение Xj=b[- a]+iX -... - ajx . Откуда bk=Xf-\-alx-\-.,.-\-ak„x„. Взяв дробную часть от обеих частей данного соотношения и учитывая, что дробная часть суммы не превосходит суммы дробных частей слагаемых, а дробная часть произведения неотрицательного целого и числа не превосходит произведения целого на дробную часть этого числа, получаем
{ X, } + { а, }х;„,+... + { }.-