Анализ метода ветвей и границ в задачах линейного программирования

D(s_k⁽¹⁾)=min D(s_j⁽¹⁾).   (3.1.13)

Ветвление. Выбрав наиболее перспективный вариант последовательности s_k⁽¹⁾, развивают его построением всех возможных подпоследовательностей длиной 2 с началом  s_k⁽¹⁾ вида   s_k+1⁽²⁾= (s_k⁽¹⁾, j), где j не входит в s_k.

Вычисление  оценок производят в соответствии с  соотношениями (3.1.6), (3.1.7), (3.1.8).

3)k-й  шаг. Допустим, что уже проведено k шагов, в результате чего построены варианты s₁^(k), s₂^(k) ,…,s_k^(k), а именно подпоследовательности длиной k.

Выбираем самый  перспективный вариант s_S^(k) такой, что

D(s_s^(k))=min D(s_j^(k)).

Множество G_s^(k) разбиваем на (n — k) подмножеств, каждое из которых образуется добавлением к последовательности s_s^(k) некоторого элемента i_k+1 такого, что i_k+1 .

Оценка  определяется в соответствии с соотношениями (3.1.6) — (3.1.9).

В результате строим дерево вариантов следующего вида: вершина О отвечает s = 0, вершины первого уровня G₁⁽¹⁾, G₂⁽¹⁾..., G_n⁽¹⁾ соответствуют последовательностям длиной 1, т. е. s₁⁽¹⁾ = 1, s₂⁽¹⁾ = 2,..., s_n⁽¹⁾ = п и т. д. Каждая конечная вершина отвечает последовательности максимальной длины n.

Признак оптимальности. Если s_v⁽ⁿ⁾  отвечает конечной вершине дерева, причем оценка наименьшая из оценок всех вершин, то s_v⁽ⁿ⁾ — искомый вариант.

 

3.2 Задача коммивояжера

3.2.1 Формулировка задачи

Задача коммивояжёра является одной  из самых известных задач комбинаторной  оптимизации. Задача заключается в  отыскании самого выгодного маршрута, проходящего через указанные города хотя бы по одному разу с последующим возвратом в исходный город. В условиях задачи указываются критерий выгодности маршрута (кратчайший, самый дешёвый, совокупный критерий и т. п.) и соответствующие матрицы расстояний, стоимости и т. п. Как правило, указывается, что маршрут должен проходить через каждый город только один раз.

В этом случае, очевидно, что задача коммивояжера – это задача отыскания  кратчайшего гамильтонова цикла  в полном графе.

Можно предложить следующую простую  схему решения задачи коммивояжера: сгенерировать все n! возможных перестановок вершин полного графа, подсчитать для каждой перестановки длину маршрута и выбрать кратчайший. Однако, n! с ростом n растет быстрее, чем любой полином от n, и даже быстрее, чем . Таким образом, решение задачи коммивояжера методом полного перебора оказывается практически неосуществимым, даже при достаточно небольших n.

Решить задачу коммивояжера также  можно с помощью алгоритма Крускала и «деревянного» алгоритма. Эти методы ускоряют разработку алгоритма по сравнению с методом полного перебора, однако не всегда  дают оптимальное решение.

Существует метод решения задачи коммивояжера, который дает оптимальное  решение. Этот метод называется методом ветвей и границ.

3.2.2 Метод ветвей и границ

Решение задачи коммивояжера методом  ветвей и границ по-другому называют алгоритмом Литтла. 

Если считать города вершинами  графа, а коммуникации (i,j) – его дугами, то требование нахождения минимального пути, проходящего один и только один раз через каждый город, и возвращения обратно, можно рассматривать как нахождение на графе гамильтонова контура минимальной длины.

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

Опишем алгоритм Литтла для нахождения минимального гамильтонова контура  для графа с n вершинами. Граф представляют в виде матрицы его дуг. Если между вершинами X_i и X_j нет дуги, то ставится символ «∞».

Алгоритм Литтла для решения  задачи коммивояжера можно сформулировать в виде следующих правил:

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

. (3.2.1)

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

,  (3.2.2)

каждая строка и столбец, которой содержит хотя бы один нуль. Такая матрица называется приведенной по строкам и столбцам.

3. Суммируем элементы  и , получим константу приведения

  ,   (3.2.3)

которая будет нижней границей множества всех допустимых гамильтоновых контуров, то есть

.   (3.2.4)

4. Находим степени нулей для  приведенной по строкам и столбцам  матрицы. Для этого мысленно  нули в матице заменяем на  знак «∞» и находим сумму минимальных элементов строки и столбца, соответствующих этому нулю. Записываем ее в правом верхнем углу клетки:

.  (3.2.5)

5. Выбираем дугу  , для которой степень нулевого элемента достигает максимального значения

.   (3.2.6)

6. Разбиваем множество всех гамильтоновых  контуров  на два подмножества и . Подмножество гамильтоновых контуров содержит дугу , - ее не содержит. Для получения матрицы контуров , включающих дугу , вычеркиваем в матрице строку и столбец . Чтобы не допустить образования негамильтонова контура, заменим симметричный элемент на знак «∞».

7. Приводим матрицу гамильтоновых  контуров  . Пусть - константа ее приведения. Тогда нижняя граница множества определится так:

.   (3.2.7)

8. Находим множество гамильтоновых  контуров  , не включающих дугу . Исключение дуги достигается заменой элемента в матрице на ∞.

9. Делаем приведение матрицы  гамильтоновых контуров  . Пусть - константа ее приведения. Нижняя граница множества определится так:

.   (3.2.8)

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

Процесс разбиения множеств на подмножества сопровождается построением дерева ветвлений.

11. Если в результате ветвлений  получаем матрицу , то определяем полученный ветвлением гамильтонов контур и его длину.

12. Сравниваем длину гамильтонова  контура с нижними границами  оборванных ветвей. Если длина  контура не превышает их нижних  границ, то задача решена. В противном случае развиваем ветви подмножеств с нижней границей, меньшей полученного контура, до тех пор, пока не получим маршрут с меньшей длиной или не убедимся, что такого не существует.

 

 

3.3 Применение метода ветвей и границ для задач календарного планирования

Рассмотрим применение разновидности  метода ветвей и границ — метода «последовательного конструирования и анализа вариантов» для решения задачи календарного планирования трех станков.

Заданы п деталей d_i (i = 1, 2, ..., n), последовательно обрабатываемых на трех станках R₁, R₂, R₃,  причем технологические маршруты всех деталей одинаковы. Обозначим a_i ,b_i ,c_i — длительность обработки деталей d_i на первом, втором и третьем станках соответственно.

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

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

Обозначим s_k = (i₁, i₂ , ..., i_k) — некоторую последовательность очередности запуска длиной k (1 £ k £ п) и A (s_k), В (s_k), С (s_k) — время окончания обработки последовательности деталей s_k на первом, втором и третьем станках соответственно.

Необходимо найти такую последовательность s_опт, что

С(s_опт) = min С (s).

     s

Покажем, как можно рекуррентно  вычислять A (s_k), В (s_k), С (s_k). Пусть s_k+1 = (s_k ,i_k+i), т. е. последовательность деталей s_k+1 получена из деталей s_k с добавлением еще одной детали i_k+1. Тогда

A (s_k+1) = A (s_k)+ , 

В (s_k+1) = max [A (s_k+1);  В (s_k)] + ,   

С (s_k+1) = max [В (s_k+1); С (s_k)] +  

Для задачи трех станков можно использовать следующее правило доминирования .

Если  s — некоторая  начальная  последовательность,   а — под последовательность образованная из s перестановкой некоторых символов, то вариант s доминирует над , когда выполняются следующие неравенства:   А (s) £ А ( ),     В (s) £ В ( ),    С (s) £ С ( ), причем хотя бы одно из них выполняется как строгое неравенство.

Способ конструирования вариантов  последовательностей s и вычисления оценок D(s) для каждого из них состоит в следующем.

Пусть имеется начальная подпоследовательность s. Тогда вычисляются величины:

d_C(s) = С(s) + , (3.3.1)

d_B(s) = В (s) + +  min c_j , (3.3.2)

d_A(s) = A (s) +   +  (3.3.3)

где J (s) — множество символов,  образующих последовательность s.

За оценку критерия С (s) для варианта s можно принять величину

                         D(s) = max {d_A(s), d_B (s), d_C (s)}.    (3.3.4)

Тогда ход решения задачи трех станков можно представить  следующей формальной схемой.

Нулевой шаг. Задание множества G⁽⁰⁾, образуется всеми возможными последовательностями (s = 0).

Вычисление оценки для множества G₀:

где   D(0) = max {d_A(0), d_B (0), б_C (0)},

;  ;  .

Первый шаг. Образование    множеств    G₁⁽¹⁾ U G₁⁽²⁾ U... …G₁⁽ⁿ⁾.

Подмножество G_k определяется всеми последовательностями с началом i_k(k — 1, ...,n ).

Вычисление оценок. Оценку для последовательности s_k определяют из соотношения (3.3.4), т. е.

   D(s_k) = max {d_A(s_k), d_B (s_k), d_C (s_k)};  k = 1, n.

Выбор варианта для продолжения. Из всех подпоследовательностей, построенных на предыдущем шаге, выбирают наиболее перспективную последовательность s_k с наименьшей оценкой, т. е.

D(s_k⁽¹⁾)=min D(s_j⁽¹⁾).

Ветвление. Выбрав наиболее перспективный вариант последовательности s_k⁽¹⁾, развивают его построением всех возможных подпоследовательностей длиной 2 с началом  s_k⁽¹⁾ вида   s_k+1⁽²⁾= (s_k⁽¹⁾, j), где j не входит в s_k.

Вычисление оценок производят в  соответствии с соотношениями (3.3.1), (3.3.2), (3.3.3).

k - ш а г. Допустим, что уже проведено k шагов, в результате чего построены варианты s₁^(k), s₂^(k) ,…,s_vk^(k), а именно подпоследовательности длиной k.

Выбираем самый перспективный  вариант s_S^(k) такой, что D(s_s^(k))=min D(s_j^(k)).

Множество G_s^(k) разбиваем на (п — k) подмножеств, каждое из которых образуется добавлением к последовательности s_s^(k) некоторого элемента i_k+1 такого, что i_k+1 .

Оценка  определяется в соответствии с соотношениями (3.3.1) — (3.3.4).

В результате строим дерево вариантов  следующего вида: вершина О отвечает s = 0, вершины первого уровня G₁⁽¹⁾, G₂⁽¹⁾..., G_n⁽¹⁾ соответствуют последовательностям длиной 1, т. е. s₁⁽¹⁾ = 1, s₂⁽¹⁾ = 2,..., s_n⁽¹⁾ = п и т. д. Каждая конечная вершина отвечает последовательности максимальной длины п.

Признак оптимальности. Если s_v⁽ⁿ⁾  отвечает конечной вершине дерева, причем оценка наименьшая из оценок всех вершин, то s_v⁽ⁿ⁾ — искомый вариант, иначе переходим к продолжению варианта с наименьшей оценкой.

 

Пример. Рассмотрим задачу трех станков, условия которой приведены в табл. 3.3.1:

Таблица 3.3.1

Длительность операций	Деталь
	1	2	3	4	5
ai bi ci	2 3 4	5 2 4	1 1 2	3 4 2	3 5 2

Нулевой шаг. s = 0.

d_A(s =0)=A(0)+ + =0+14+3=17;

d_B(s=0)=В(0)+ +minc_j =0+15+2=17;

d_C(s = 0) = С(0) + =14 .

Тогда ∆ (s = 0) = max {17, 17,14} = 17.

Первый шаг. Конструируем все возможные последовательности длиной 1

s₁⁽¹⁾  = 1;  s₂⁽¹⁾ = 2;   s₃⁽¹⁾ = 3;   s₄⁽¹⁾ = 4;   s₅⁽¹⁾ = 5.

Находим d_A⁽¹⁾ = A₁ + + = 14 + 3 = 17;

d_B⁽¹⁾(s =0)=В₁+ + =5+12+2=19;

d_C⁽¹⁾ = С₁ + = 9 + 10 = 19 .

Откуда ∆ (1) = max {17, 19, 19} = 19.

Аналогично определяем ∆ (2), ∆ (3), ∆  (4), ∆ (5).

Второй шаг. Среди множества подпоследовательностей длиной 1, s₁⁽¹⁾ = 1, s₂⁽¹⁾ = 2,..., s₅⁽¹⁾  = 5  выбираем наиболее перспективную s = 1, для которой величина оценки-прогноза ∆ (s) оказывается наименьшей. Далее развиваем ее, конструируя возможные варианты длиной 2, т. е. (1.2), (1.3), (1.4), (1.5).

Для каждого из этих вариантов вновь  определяем оценки по формулам (3.3.1) — (3.3.4).

Процесс вычислений продолжаем аналогично.

Процесс построения дерева вариантов  приведен на схеме.

Каждой конечной вершине дерева вариантов будет отвечать полная последовательность s = i₁,i_2,,.i_n. Если для некоторой такой вершины величина оценки ∆ (s) не превосходит величины оценок для всех остальных вершин, то эта оценка определяет искомый оптимальный вариант. В противном случае разбиваем более перспективный вариант с наилучшей оценкой.