4.6. ПРИБЛИЖЕННЫЕ МЕТОДЫ ДИСКРЕТНОЙ ОПТИМИЗАЦИИ
Общая характеристика
Исключительно важную роль в решении задач дискретного программирования играют приближенные методы. Можно указать такие обстоятельства, которые обусловили резкое увеличение интереса к разработке приближенных методов дискретного программирования в последние годы.
Во-первых, из-за комбинаторного характера большинства задач дискретного программирования, точные методы не дают возможности получить строго оптимального решения для практических задач довольно большой размерности.
Во-вторых, часто на практике для задач исследования операций применяются приближенные модели, где исходные данные определены неточно и приближенно. Это обесценивает поиск оптимальных решений, и потому часто ограничиваются приближенными решениями, удовлетворительными с точки зрения практики. На их поиск расходуется значительно меньше машинного времени и других ресурсов ЭВМ, что особенно важно, если соответствующие задачи должны решаться в реальном времени (например, в условиях функционирования АСУ).
Метод вектора спада
Метод вектора спада относится к группе приближенных методов локальной оптимизации. Его предложил И. В. Сергиенко еще в середине 60-х годов, а затем он вместе с группой сотрудников развил этот метод применительно к решению различных классов задач дискретной оптимизации, в том числе задач полностью и частично целочисленного программирования, задач с булевыми переменными, оптимизационных комбинаторных задач [43].
Различные модификации метода успешно применялись для решения таких классов задач исследования операций, как размещения приборов, организации вычислительного процесса, синтеза структуры сети типа дерева, классификации объектов, задач теории расписаний и других.
Прежде чем изложить общую схему метода, введем ряд необходимых понятий.
Пусть М - метрическое пространство с некоторой метрикой r (x, y), определяемой для двух произвольных точек x и y из M. Если r - некоторое положительное число, а x - фиксированная точка метрического пространства, то множество всех точек y Î М, для которых r (x, y) < r, называется открытой окрестностью с центром в точке x и радиусом r (или открытым шаром). Множество всех точек y Î М, для которых r (x, y) £ r, называется замкнутым шаром радиуса r (r >0) с центром в точке x Î М (замкнутой окрестности). Обозначим его ОМ (x, r).
Пусть М - дискретное множество, а f (x) - произвольная функция, определенная на М.
Определение 4.1. Точку x Î М будем называть точкой локального минимума функции f (x) относительно окрестности радиуса r, если для всех y Î ОМ (x, r) выполняется неравенство
f (x) £ f (y) и ОМ (x, r) \ x ¹ Æ .
Задача дискретного программирования состоит в определении локального минимума функции f (x), заданной на M ,относительно окрестности радиуса r.
Определение 4.2. Векторную функцию 
,определенную на M, название вектором спада функции f относительно окрестности радиуса r, если выполняются следующие условия:
1) значения функции 
в каждой точке xÎМ являются l-мерным вектором с компонентами Δ1, Δ2 , .,Δl - действительными числами;
2) точка xÎМ является точкой локального минимума функции f (x) тогда и только тогда, когда Δi ³ 0 для всех 
;
3) если xÎМ не является точкой локального минимума функции f (x) в окрестности ОМ (x, r), то с помощью вектора спада можно определить точку x¢Î ОМ (x, r) такую, что f (x¢) < f (x).
В соответствии с этим определением вектор 
позволяет для каждой точки xÎМ в окрестности ОМ (x, r) найти направление уменьшения (спада) значений функции f в окрестности ОМ (x, r) . Идея использования вектора спада для поиска такого направления и лежит в основе данного метода.
Описание алгоритма вектора спада
П е р в ы й ш а г. Случайно или исходя из учета специфики решаемой задачи выбираем некоторое начальное приближение 
Î M и задаем величину радиуса r > 0.
В т о р о й ш а г. Задаем некоторую последовательность радиусов {r1, r2, ., rm}, которая удовлетворяет соотношение
0 < r1 < r2 < . < rm = r; m ³ l.
Т р е т и й ш а г. Полагаем n = 0.
Ч е т в е р т ы й ш а г. На каждой (n + 1)-и итерации алгоритма выполняем следующие действия (процедуры).
4.1. Полагаем k = 1.
4.2. Рассматриваем окрестность ОМ (x*, rk).
4.3. По значениям компонент вектора спада 
определяем, является ли f (
) локальным минимумом функции f (x) относительно 
. Если да, то при k < m, заменив k на k +1, переходим к п.4.2, а при k = m - к шагу 5. В противном случае переходим к п.4.4.
4.4. По значениям компонент вектора спада 
находим в окрестности точку 
, для которой f ( ) < f( ).
Заменяем n на n+1 и переходим к п.4.1.
П я т ы й ш а г. Заканчиваем работу алгоритма в связи с тем, что является искомой точкой локального минимума f (x) относительно окрестности радиуса r.
Пункт 4.4 этого алгоритма можно изменить слебующим образом.
В окрестости среди точек x с меньшим значением целевой функции, чем f(
), выбрать одну, которая доставляет минимум функции f (x). Обозначив эту точку и заменив n на n+1, перейдем к четвертому шагу алгоритма (п.4.1).
Установим достаточные условия сходимости алгоритма метода вектора спада [43].
Теорема 4.8. Если функция f (x), определенная на дискретном множестве M, удовлетворяет следующим условиям:
1) f (x) ограничена снизу на M, то есть f (x) ³ c , где c = const для всех точек xÎM;
2) ½f * (x¢) - f (x²)½ ³ d, где d - const для любых точек x¢, x² таких, что f (x¢) ¹ f (x²),
то при любом выборе начального приближения x0 Î M, величины радиуса r > 0 и последовательности {r1, r2, ., rm} вычислительный процесс алгоритма вектора спада сходится за конечное число шагов, не превышающее величины
. (4.6.1)
Д о к а з а т е л ь с т в о. Оно почти очевидно. Для получаемой в результате применения алгоритма последовательности точек {x0, x1, .,
} справедливые неравенства f(x0) > f(x1) > . >f() > f(), из которых следует, что f(x0) - c ³ Hd, где H - число шагов алгоритма. Таким образом,
H £ 
В случае, когда функция f(x) задана на некотором конечном множестве, выполняются оба условия теоремы. Следовательно, вычислительный процесс по методу вектора спада будет конечным. Если же решается общая задача дискретной оптимизации, целевая функция которой не удовлетворяет условия теоремы 4.8, то можно применять описанный выше алгоритм, введя в него некоторый дополнительный признак окончания вычислительного процесса, например, достижения некоторого заведомо заданного числа шагов алгоритма.
Кроме того, получая на каждом шаге алгоритма соответствующее значение целевой функции, можно оценивать его с точки зрения некоторых практических требований.
Описание общей схемы метода необходимо дополнить рассмотрением следующего возможного случая: пусть локальное решение 
не удовлетворяет некоторому заданному дополнительному критерию (например, критерию, устанавливающему максимально допустимое отклонение локального минимума от глобального). Для такого случая можно предложить несколько вариантов поиска других приближенных решений.
Во-первых, выбрав точку как новое начальное приближение и увеличив заданную первоначально заданную величину радиуса r, следует продолжить вычислительный процесс до получения других приближенных решений задачи, которые, очевидно, будут ближе к глобальному по значению целевой функции, чем . Однако при этом процесс вычислений может существенно усложниться.
Во-вторых, исходя из точки 
и увеличив значения радиуса r, можно осуществить лишь первый шаг алгоритма для получения точки x′, удовлетворяющей неравенству f(x′) < f( ), потом вернуться к первоначальной величине радиуса и продолжить вычислительный процесс.
В-третьих, не изменяя величины r, можно продолжить процесс вычислений исходя из некоторого другого начального приближения 
Î М и получить в результате другое локальное решение x′, в общем случае отличное от .
Применение метода вектора спада
для задач линейного целочисленного программирования
Рассмотрим особенности реализации общей схемы метода вектора спада при решении задач ЛЦП. Пусть имеем задачу ЛЦП, заданную в виде:
максимизировать f(x) = 
(4.6.2)
при ограничениях
£ bi, i = 
(4.6.3)
xj ³ 0, j = 
(4.6.4)
xj - целое число, j = 
(4.6.5)
Дискретным множеством решений M в этом случае будет множество 
всех упорядоченных наборов из n целых чисел, расстояние между двумя произвольными элементами x = [x1, x2, . . . , xn] и y = [y1, y2, . . . , yn] которого определим по формуле
r (x, y) = 
| xj - yj |. (4.6.6)
В метрическому просторі расстояние между любыми двумя его точками равно целому числу, а любая окрестность ОZ (x, r) состоит из точки x и всех точек множества , расположенных от x на расстоянии, равном 1, 2, ., |r|. Пусть G - множество допустимых решений данной задачи, то есть G Ì , что определяется ограничениями (4.6.3) - (4.6.6).
В соответствии с определением вектора спада функции (4.6.2) относительно окрестности радиуса r рассмотрим определенную на векторную функцию вида
= {D (x, x1), D (x, x2), ., D (x,
)},
D (x, 
) = f () - f (x) = 
cj ( xj(k) - xj), k = 1, 2, ., l; (4...6.7)
где
{ } = {
}, k = 
, Î 
Заметим, что если окрестность 
содержит некоторую точку y = {y1, y2, ., yn} вместе с противоположной относительно т. x точкой y¢= { y¢1, y¢2, ., y'n}, то значение компоненты D (x, y) вектора спада DZ(x) будет содержать информацию о поведении целевой функции в обеих точках y и y¢, так как D (x, y¢ ) = - D (x, y).
Это означает, що компоненти D (x, y¢) можно не рассматривать. Кроме того, из компонент вектора DZ(x) следует выбрать лишь те, которые соответствуют точкам 
Î
(x, r).
Если некоторой точке z Î (x,r) соответствует отрицательная компонента DZ (x, r) вектора спада 
, то имеет место неравенство f(z) < f(x).
Для решения задачи ЛЦП (4.6.2) - (4.6.5) методом вектора спада в п.4.2 алгоритма, описанного выше, рассматривается окрестность 
. Координату xj произвольной точки x этой окрестности можно выразить через соответствующую координату ее центра 
с помощью формулы
(4.6.8)
где I Í {s, ., n}j , pj Î {+ s, - s, ., + rk, - rk} для всех 
При выполнении п.4.3 и 4.4 алгоритма компоненты вектора спада вычисляем по формуле
D ( , x) = 
,
причем для искомой точки 
Î 
должно выполняться неравенство D ( , ) < 0.
Достаточные условия сходимости метода вектора спада при решении задачи ЛЦП устанавливаются в следующей теореме [43].
Теорема 4.9. Если все компоненти cj , функции (4.6.2) неотрицательны, то последовательность { }, построенная по алгоритму вектора спада, при любом выборе начального приближения 
Î G и радиуса r > 0,конечна и завершается точкой локального минимума функции f (x) относительно окрестности радиуса r. При этом число шагов алгоритма не превышает величины b f ( ), где b - наименьшее общее кратное чисел bj, взятых из следующего выражения для cj:
cj = 
, j = 1, ., n, (4...6.9)
где 
,
- целые числа, ¹ 0.
Эта теорема является следствием теоремы 4.8. Действительно, если выполнены условия теоремы 4.9, то для всех точек x Î G справедливо f(x) ³ 0 и, кроме того, для любых двух точек x¢ и x² Î G , таких, что f(x¢)¹ f(x²), справедливо неравенство
|f(x¢) - f(x²)| ³ 
.
Очевидно, что выполняются оба условия теоремы 4.8.
Для исследования алгоритма вектора спада при решении задач вида (4.6.2) - (4.6.5) средней и большой размерности был проведен следующий вычислительный эксперимент [43].
Коэффициенты в условиях задач формировались с помощью датчика псевдослучайных чисел. Независимо друг от друга выбиралась каждая из (mn + n + m) величин 
,
,
, где и - целые числа, равномерно распределенные на отрезке
[-10; +10], - целые числа, равномерно распределенные на отрезке [0,9 ´ n; 2,6 ´ n].
При проведении эксперимента использовались определенные правила перебора точек в окрестностях; во всех примерах в качестве начального приближения выбирался нулевой n-мерный вектор, радиус окрестностей выбирался равным 1. Результаты машинных экспериментов приведены в табл.4.21, где обозначено: m ´ n - размеры матрицы коэффициентов ограничений; n - количество решенных задач; 
и 
- минимальная и максимальная абсолютная величина разности между полученным локальным минимумом функции f (x) и значением этой функции в точке x0 среди n задач данного размера; 
и 
- минимальное и максимальное время решения одной задачи; 
, 
- минимальное и максимальное число итераций.
Таблица 4.21
|
m ´ n |
n |
|f (xh) - f(x0)| min |
|f (xh) - f(x0)| max |
Nmin |
Nmax |
tmin |
tmax |
|
10´10 |
10 |
34 |
481 |
13 |
83 |
0,64 |
3,27 |
|
20´10 |
10 |
1 |
38 |
2 |
8 |
0,18 |
0,48 |
|
50´10 |
10 |
1 |
10 |
2 |
3 |
0,18 |
0,43 |
|
50´50 |
10 |
89 |
221 |
26 |
44 |
11,4 |
37,7 |
|
50´100 |
3 |
514 |
631 |
92 |
125 |
208 |
266 |
|
100´50 |
3 |
51 |
230 |
21 |
48 |
13,2 |
74 |
|
100´100 |
4 |
178 |
690 |
37 |
136 |
101 |
344 |
|
100´200 |
2 |
526 |
899 |
137 |
150 |
802 |
855 |
Применение метода вектора спада
в задаче булева программирования
Рассмотрим задачу ЛЦП с булевыми переменными вида:
минимизировать (4.6.10)
при ограничениях
, (4.6.11)
xj Î {0, 1}, 
. (4.6.12)
Дискретным множеством M в данном случае является подмножество 
всех точек метрического пространства , удовлетворяющих условию (4.6.12). Это пространство той же метрики (4.6.6), которая было задана в всем пространстве .
При реализации общей схемы метода вектора спада для решения задачи вида (4.9.10) - (4.9.12) в п.4.2 алгоритма, предложенного в предыдущем разделе, рассматриваем окрестность 
. Координаты произвольной точки x = (x1, x2, ., xn) этой окрестности можно выразить через координаты точки следующим образом:
(4.6.13)
При выполнении п.4.3 и п.4.4 алгоритма компонентs вектора спада 
вычисляем в этом случае по формуле
,
где I0 - множество тех значений индекса j Î I, для которых
= 0, I0 Í I.
Справедлива следующая теорема о сходимости алгоритма вектора спада применительно к задаче булева программирования [43].
Теорема 4.10. При любом выборе начального приближения Î G (G - множество точек, удовлетворяющих ограничениям (4.6.11) и (4.6.12)), радиуса r > 0 последовательность приближений { }, определяемая по алгоритму, сходится к локальному решению задачи (4.6.10) - (4.6.12) за конечное число шагов, не превышающее величины
b (f ( ) - c), (4.6.14)
где b определяется так же, как и в теореме 4.9, а
(4.6.15)
где I - множество тех значений индекса j Î{1, 2, . . . , n}, для которых cj< 0.
Доказательство теоремы аналогично доказательству теоремы 4.8. Это связано с тем, что множество конечно и, следовательно, функция f (x), определенная на множестве G Î , удовлетворяет условиям теоремы 4.8. Действительно, очевидно, что для всех точек xÎG, f (x) ³ c, где c - величина, определяемая формулой (4.6.15), и для всех x¢, x² Î G таких, что f (x¢) ¹ f (x²), имеет место неравенство
½ f (x¢) - f (x²)½³ .
Пример 4.8. Для иллюстрации применения метода вектора спада рассмотрим следующую задачу ЛЦП, которая раньше была решена методом Гомори и ветвей и границ (см. примеры 4.2, 4.3):
максимизировать (
+
) (1)
при ограничениях
(2)
, , - целые числа. (3)
Выберем в качестве начального решения x(0) = (0, 0). Зададим некоторую последовательность радиусов r = 2, 3, 4. Полагаем n = 0.
Первая итерация. 1. Полагаем r1 = 2.
2. Рассмотрим окрестность 
. В нее попадают вектора 
= [0; 1]; 
= [1; 0]; 
= [1; 1]; 
= [2; 0]; 
= [0; 2].
Вектор недопустим по ограничениям (2).
3. Вычислим компоненты вектора спада 
где
.
Получим 
= {1, 1, 2, 2}.
4. Полагаем в качестве вектора x(1) = = [1; 1], для которого f (x(1)) = 2.
Вторая итерация. 1. Рассмотрим окрестность точки x(1): 
(x(1), r = 2). В нее попадают векторы: = [0; 1]; = [1; 0]; = [2; 1]; = [1; 2]; 
= [1; 3]; 
= [3; 1]; 
= [2; 2]. Вектор недопустим по ограничениям (2), а точки , уже рассматривались раньше (на предыдущей итерации), для них значение целевой функции меньше, чем для текущей точки x(1), а потому их можно опустить.
2. Вычислим компоненты вектора спада
(x(1)) = {D(x(1), ); D(x(1), ); D(x(1), ); D(x(1), )} = {1, 1, 2, 2}.
3. Выберем в качестве новой текущей точки = [2, 2] с наибольшей компонентой D = 2. Полагаем x(2) = = [2, 2].
Третья итерация. 1. Рассмотрим окрестность x(2): (x(2), r = 2). В нее попадают вектора = [2; 3]; = [3; 2]; = [4; 2]; = [2; 4]; = [1; 3]; = [3; 1]; = [0; 2]. Среди них допустимыми оказываются , , , . Вычислим компоненты вектора спада:
(x(2)) = {D (x(2), ); D (x(2), ); D (x(2), ) D (x(2), )} = {1, 1, 0, -2}.
В качестве нового приближения можно выбрать как , так и с одинаковыми компонентами D (x(2),
) = 1, i=1,2.
Выберем для определенности и положим x(3) = = [3; 2].
Четвертая итерация. 1. Рассмотрим окрестность x(3):
(x(3), r = 2) = { = [4; 2]; = [3; 3]; = [2; 3]; = [3; 4]; = [5; 2]; = [2; 2]; = [1; 2]; = [3; 1]; 
= [2; 1]}.
Вектора , , , являются недопустимыми по ограничениям (2).
2. Для остальных точек вычислим компоненти вектора спада:
(x(3)) = {0, -1, -2, -1, -2}.
Поскольку все компоненти вектора не положительны, увеличим радиус окрестности (r = 3) и переходим к первому шагу.
Снова рассмотрим окрестность точки x(3) и определим все прнадлежащие ей точки при r = 3 ,которые не входят в окрестность при r = 2.
В нее попадают такие точки: 
= [6; 2]; 
= [2; 4]; 
= [1; 4]; 
= [3; 5]. Среди них точки , , -недопустимы, а для : D (x(3), ) = -1 < 0. Поэтому увеличим радиус окрестности до r = 4. Легко проверить, что и при r = 4 все компоненты вектора спада остаются неположительными. Следовально, точка x(3) = [3; 2] является точкой локального максимума. Увеличивая r, можно убедиться в том, что она является и точкой глобального максимума. Одновременно находится и вторая точка максимума = [2; 3], поскольку D (x(3), ) = 0.
Пример 4.9. Рассмотрим задачу булева программирования:
максимизировать (
) = z
при ограничениях
£ 8, i = 1;
£ 8, i = 2; (2)
Î {0, 1}, j = 
.
Первая итерация. 1. В качестве начального приближения выбираем 
= [0, 0, 0, 0, 0] и пусть радиус сходимости r = 2. Рассмотрим окрестность 
( , r = 2).
2. Находим последовательно все вектора , , .,
, приналежащие окрестности ( , r = 2), то есть такие. что
Ими оказываются векторы
= {1, 0, 0, 0, 0};= {0, 1, 0, 0, 0};= {0, 0, 1, 0, 0};= {0, 0, 0, 1, 0};
= {0, 0, 0, 0, 1};
= {1, 1, 0, 0, 0};
= {1, 0, 1, 0, 0};= {1, 0, 0, 1, 0};
= {1, 0, 0, 0, 1};= {0, 1, 1, 0, 0};
= {0, 1, 0, 1, 0};= {0, 1, 0, 0, 1};
= {0, 0, 1, 1, 0};
= {0, 0, 1, 0, 1};
= {0, 0, 0, 1, 1}.
Среди этого множества векторов допустимыми по ограничениям (2) оказываются вектора , , , , ,
.
3. Вычисляем компоненти вектора спада
{3, 3, 13, 6, 9, 12}.
Поскольку все компоненты D( , ) > 0, то в качестве новой точки можно выбрать любую из них. Выберем , для которой D( , ) = max {D( , )} = 13. При этом значение целевой функции равно f ( ) = 13. Полагаем x(1) = .
Вторая итерация. 1. Находим окрестность (x(1), r = 2). В нее входят все вектора, определяемые соотношением (4.6.13). С учетом условий (2) допустимыми оказываются следующие: , , , которые представлены выше.
2. Вычисляем компоненти вектора спада
.
Поскольку все D(x(1), ) < 0, то переходим снова к шагу 1, увеличив радиус до r = 3. Нетрудно убедиться, что и при r = 3 все компоненти вектора спада отрицательны. Следовательно, точка x(1) = {0, 0, 0, 0, 1} - это точка локального максимума. Последовательно увеличивая радиус окрестности до r = 4, 5, ., можно проверить, что это - глобальный максимум (сравните с решением данной задачи методом Балаша, см. пример 4.5).
