Дискретная математика & математическая логика

4.2. МЕТОД ВЕТВЕЙ И ГРАНИЦ

Метод ветвей и границ – общий алгоритмический метод для нахождения оптимальных решений различных задач оптимизации, особенно дискретной и комбинаторной оптимизации. По существу, метод является комбинаторным (алгоритм перебора) с отсевом подмножеств множества допустимых решений, не содержащих оптимальных решений. Метод был впервые предложен Ленд и Дойг в 1960 году для решения задач целочисленного линейного программирования. Для метода ветвей и границ необходимы две процедуры: ветвление и нахождение оценок (границ).

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

Процедура нахождения оценок заключается в поиске верх-

них и нижних границ для оптимального значения на подобласти допустимых решений.

В основе метода ветвей и границ лежит следующая идея (для задачи минимизации): если нижняя граница для подобласти A дерева поиска больше, чем верхняя граница какой-либо ранее просмотренной подобласти B, то A может быть исключена из дальнейшего рассмотрения (правило отсева). Обычно минимальную из полученных верхних оценок записывают в глобальную переменную m; любой узел дерева поиска, нижняя граница которого больше значения m, может быть исключен из дальнейшего рассмотрения.

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

Рассмотрим частный случай метода ветвей и границ.

Метод половинного разбиения при поиске отказов в ком-

пьютерных системах. Иногда возможно проверять компоненты не по одному, а группой. Проверим наличие тока через последова-

122

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

n = 2m + r ,

где r – « остаток» до соответствующей степени числа 2,

n − r = 2m.

Например, при n = 5 m = 2 , r =1 .

Построим дерево проверок для n = 5 (рис. 4.3):

Рис. 4.3. Дерево проверок для n = 5

Минимальное количество проверок Nmin = 2 = m. Максимальноеколичествопроверок Nmax = 3 = m +1 (for _ r ≠ 0). При m проверках распознается n − 2r технических состояний

(при n = 5 – три состояния).

123

Причем необязательно разбивать множество на одинаковое число компонентов. Достаточно, чтобы количество компонент в «длинном» участкеnд соответствоваловыражению

2m−1 < nд ≤ 2m ,

а в «коротком» участке

nк ≥ 2m−1 .

Естественно, что

nд + nк = n.

124

Полученные результаты могут использоваться для иллюстрации метода оптимизации, называемого методом ветвей и границ. Функция предпочтения – это, например, показания прибора, определяющего наличие тока, или диагностической аппаратуры, формирующей сообщение «есть отказ – нет отказа».

Задача о рюкзаке [8]

Перед туристическим походом в рюкзак вместимостью не более А единиц веса из набора I = {1, 2, 3, …, n} предметов, каждый весом аi и ценностью сi необходимо положить такие предметы, которые максимизируют суммарную ценность груза и по весу вмещаются в рюкзак. «Рюкзак» может толковаться как полезный груз, выводимая на орбиту ракета, как кузов грузовой машины и пр.

Пусть допустимый вес рюкзака V = 15. Количество предметов n = 5. Вес предметов 3, 2, 4, 5, 6. Ценность предметов соответствен-

но 6, 5, 6, 12, 10.

Определим ценность единиц грузов: 6/3, 5/2, 6/4, 12/5, 10/6. Получим следующие показатели ценности: 2; 2,5; 1,5; 2,4; 1,67. Упорядочим ценности по убыванию: 2,5; 2,4; 2; 1,67; 1,5. Составим таблицу исходных данных к задаче о ранце:

125

В данной задаче можно относительно быстро подобрать оптимальный вариант № 30 без сложных процедур ветвления.

4.3. ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ

Линейное программирование – математическая дисциплина, посвященная теории и методам решения задач об экстремумах линейных функций на множествах n-мерного векторного пространства, задаваемых системами линейных уравнений и неравенств.

Линейное программирование является частным случаем выпуклого программирования, которое в свою очередь является частным случаем математического программирования. Одновременно оно – основа нескольких методов решения задач целочисленного и нелинейного программирования.

Пусть система ограничений (уравнений) имеет вид

Здесь три уравнения и пять неизвестных. Выразим переменные х3, х4, х5 через х1, х2:

Учитывая, что х3, х4, х5, получим геометрическую интерпретацию задачи оптимизации – рис. 4.4.

126

Эти точки называются вершинами симплекса, в частности:

–0- симплекс – точка,

–1- симплекс – отрезок,

–2- симплекс – треугольник,

–3- симплекс – тетраэдр.

Выпуклая оболочка любых m + 1 из n + 1 вершин n-симплек- са сама является симплексом и называется m-гранью симплекса. 0-грани – это вершины, 1-грани – это рёбра, n–1- грани называют просто гранями. Стандартный симплекс представлен на рис. 4.6.

Рис. 4.6. Стандартный 2-симплекс – зелёный треугольник

Симплекс-метод – алгоритм решения оптимизационной задачи линейного программирования путём перебора вершин выпуклого многогранника в многомерном пространстве. Метод был разработан американским математиком Джорджем Данцигом (George Dantzig,

рис. 4.7) в 1947 году.

128

Ввиду того, что n – m = 2, в качестве свободных можно взять,

например, х1, х2.

Приравняв их нулю, находим базисное решение

Это решение допустимо, поскольку переменные неотрицательны. Проверку того, не достигнут ли максимум, можно выполнить путём поиска нового допустимого базисного решения, при котором целевая функция будет больше.

Для перехода к новому допустимому базисному решению одну из свободных переменных х1, х2 следует сделать базисной. В нашем примере переменная х1 входит в выражение целевой функции со знаком +. Значит, максимум целевой функции не достигнут, и переменную х1 следует сделать базисной. Возьмём систему уравнений

При х2 = 0 увеличение х1 не приводит к уменьшению х3, но уменьшаетх4, х5, такчто прих1 = 2 получим

x1 = 2,

x2 = 0,

x3 = 6,

x4 = 0,x5 = 3,

q' = x1 − x2 = 2.

130