Z=3x₁ +x₂ →max

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

4x_l + Зх₂ < 18

x₁ + 2x₂ £ 6

4 £x₁ £ 4

1 £x₂ £ 4

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

Список задач: 6 и 7. Значение Z₀ = 12.

VI этап. Решаем одну из задач списка, например задачу 7, симплексным методом.

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

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

Получим Z_{m ax} = 10,5 ,при X₆ ^* = (3; 1,5; 1,5; 0; 0; 0,5; 2,5).

Так какZ(X₆ ^* ) = 10,5 < Z₀ = 12, то задача исключается из списка.

Итак, список задач исчерпан и оптимальным целочисленным решением исходной задачи будет X^* = Х₄ ^* = (4; 0; 2; 2; 0; 0), а оптимум линейной функции Z_max = 12

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

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) £ С ( ),