4°. В  случае необходимости составляют  дополнительные ограничения для  переменной, значение которой является  дробным, формулируют задачи, аналогичные  задачам (I) и (II), и находят их решение. Итерационный процесс продолжают до тех пор, пока не будет найдена вершина, соответствующая целочисленному плану задачи (1)-(3) и такая, что значение функции в этой вершине больше или равно значению функции в других возможных для ветвления вершинах.

 

  

  Проиллюстрируем метод ветвей и границ на примере.

  Решить задачу

  Z = Зх₁ + х₂ — max

при ограничениях:

                                 4x_l + Зх₂ < 18,

                                x₁ + 2x₂ £ 6,

                                0 £ x₁ £ 5,

                                0 £ x₂ £ 4,  

                  х₁, x₂ — целые числа.

  Решение. За нижнюю границу линейной функции примем, например, ее значение в точке (0,0), т.е. Z₀ = Z (0; 0) = 0.

I этап. Решая задачу симплексным методом, получим Z_max = 13 при Х₁^* = (4,5; 0; 0; 1,5; 0,5; 4); так как первая компонента х₁^* дробная, то из области решения исключается полоса, содержащая дробное оптимальное значение х₁^*, т.е. 4 < х₁ < 5. Поэтому задача 1 разбивается на две задачи 2 и 3:

 

  Задача 2

  Z=3x₁+x₂→max

  при ограничениях:

              4x_l + Зх₂ < 18

             x₁ + 2x₂ £ 6

             0 £ x₁ £ 4

             0 £ x₂ £ 4

             х₁, x₂ — целые числа.

  Задача 3

  Z=3x₁+x₂→max

   при ограничениях:

             4x_l + Зх₂ < 18

             x₁ + 2x₂ £ 6

             5 £ x₁ £ 5

             0 £ x₂ £ 4

             х₁, x₂ — целые числа. 
 

  Список задач: 2 и 3. Нижняя граница линейной функции не изменилась: Z₀= 0.

II этап. Решаем (по выбору) одну из задач списка, например задачу 3 симплексным методом.

Получим, что  условия задачи 3 противоречивы.

III этап.   Решаем задачу 2 симплексным методом. Получим Z_max = 14/3 при X₃^*= (4; 2/3; 0; 2/3; 0; 10/3). Хотя Z(X₃^*) = 14/3 > Z₀ = 0, по-прежнему сохраняется Z₀ = 0, ибо план нецелочисленный. Так как х₂^* — дробное число, из области решений исключаем полосу 0 < x₂ < 1 и задачу 2 разбиваем на две задачи 4 и 5. 

 

  

             Задача 4

  Z=3x₁+x₂→max

  при ограничениях:

              4x_l + Зх₂ < 18

             x₁ + 2x₂ £ 6

             0 £ x₁ £ 4

             0 £ x₂ £ 0

             х₁, x₂ — целые числа. 

             Задача 5

  Z=3x₁+x₂→max

   при ограничениях:

             4x_l + Зх₂ < 18

             x₁ + 2x₂ £ 6

             0 £ x₁ £ 4

             1 £ x₂ £ 4

             х₁, x₂ — целые числа. 
 

Список задач: 4 и 5. Значение Z₀ = 0.

IV этап. Решаем задачу 4 симплексным методом.

Получим Z_max = 12 при X₄^* = (4; 0; 2; 2; 0; 0). Задачу исключаем из списка, но при этом меняем Z₀; Z₀ = Z(X₄^*) = 12, ибо план Х₄^* целочисленный.

V этап. Решаем задачу 5 симплексным методом.

Получим Z_max = 12,25 при X₅^* = (3,75; 1; 0; 0,25; 0,25; 0; 3). Z ₀ не меняется, т.е. Z₀ = 12, ибо план X₅^* нецелочисленный. Так как х₁^* — дробное, из области решений исключаем полосу 3<x₁<4, и задача 5 разбивается на две задачи: 6 и 7. 

Замечание 1. Нетрудно видеть, что каждая последующая задача, составляемая в процессе применения метода ветвей и границ, отличается от предыдущей лишь одним неравенством — ограничением. Поэтому при решении каждой последующей задачи нет смысла решать ее симплексным методом с самого начала (с I шага). А целесообразнее начать решение с последнего шага (итерации) предыдущей задачи, из системы ограничений которой исключить "старые" (одно или два) уравнения — ограничения и ввести в эту систему "новые" уравнения — ограничения. 

  Задача 6

  Z=3x₁+x₂→max

  при ограничениях:

              4x_l + Зх₂ < 18

             x₁ + 2x₂ £ 6

             0 £ x₁ £ 3

             1 £ x₂ £ 4

             х₁, x₂ — целые числа. 
Задача 7

  Z=3x₁+x₂→max

   при ограничениях:

             4x_l + Зх₂ < 18

             x₁ + 2x₂ £ 6

             4 £ x₁ £ 4

             1 £ x₂ £ 4

             х₁, x₂ — целые числа

 

II.ПРАКТИЧЕСКАЯ ЧАСТЬ

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

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

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

Заданы п деталей 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) для каждого из них состоит в следующем.