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

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.

Задача 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₂ — целые числа.

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

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

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

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

Получим Z_max = 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) £ С (

),

причем хотя бы одно из них выполняется как строгое неравенство.

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

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

d_C(s) = С(s) +

, (1)

d_B(s) = В (s) +

+ minc_j, (2)

d_A(s) = A (s) +

+ (3)

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

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

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

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

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

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

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

; ; .

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

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

Вычисление оценок. Оценку для последовательности s_kопределяют из соотношения (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.

Вычисление оценок производят в соответствии с соотношениями (1), (2), (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

.

Оценка

определяется в соответствии с соотношениями (1) — (4).

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

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

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