ПОЗНАВАТЕЛЬНОЕ

Оси и плоскости тела человека - Тело человека состоит из определенных топографических частей и участков, в которых расположены органы, мышцы, сосуды, нервы и т.д.

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

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

Метод ветвей и границ для задачи

Предыдущая 1 2 3 4 5 678 9 10 11 12 13 14 15 16 Следующая

календарного планирования

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

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

Заданы п деталей 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).

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

Тогда:

A (s_k₊₁) = A (s_k)+ ,

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

С (s_k₊₁) = max [В (s_k₊₁); С (s_k)] +

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

Если s— некоторая начальная последовательность, а - подпоследовательность, образованная из s перестановкой некоторых символов, то вариант s доминирует над , когда выполняются следующие неравенства:

А (s) £ А ( ), В (s) £ В ( ), С (s) £ С ( )

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

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

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

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

d_A(s) = A (s) + + (3.3)

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

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

D(s) = max {d_A(s), d_B (s), d_C (s)}.(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.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₊₁⁽²⁾= (s_k⁽¹⁾, j), где j не входит в s_k.

Вычисление оценок производят в соответствии с соотношениями (3.1), (3.2), (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₊₁ такого, что i_k₊₁ .

Оценка определяется в соответствии с соотношениями (3.1) - (3.4).

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

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

Пример.

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

Таблица 3.1

Длительность операций	Деталь

a_i b_i c_i

Нулевой шаг.

s = 0.

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

d_B(s = 0) = В(0) + + min c_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.1) — (3.4).

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

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

Конечная вершина определяет вариант (последовательность) = 3, 1, 5, 2, 4 с наилучшей оценкой ∆ = 20. Поэтому данный вариант является оптимальным.

Непосредственной проверкой убеждаемся, что время обработки всей последовательности деталей для этого варианта совпадает со значением оценки-прогноза и является минимальным:

3.6. Тест по теме «Метод ветвей и границ»

Предыдущая 1 2 3 4 5 678 9 10 11 12 13 14 15 16 Следующая