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

Z=3x1+x2→max

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

4xl + Зх2 < 18

x1 + 2x2 £ 6

0 £ x1 £ 4

0 £ x2 £ 0

х1, x2 — целые числа.

Задача 5

Z=3x1+x2→max

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

4xl + Зх2 < 18

x1 + 2x2 £ 6

0 £ x1 £ 4

1 £ x2 £ 4

х1, x2 — целые числа.

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

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

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

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

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

Задача 6

Z=3x1+x2→max

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

4xl + Зх2 < 18

x1 + 2x2 £ 6

0 £ x1 £ 3

1 £ x2 £ 4

х1, x2 — целые числа.

Задача 7

Z=3x1+x2→max

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

4xl + Зх2 < 18

x1 + 2x2 £ 6

4 £ x1 £ 4

1 £ x2 £ 4

х1, x2 — целые числа.

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

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

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

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

Получим Zmax = 10,5 ,при   X6* = (3; 1,5; 1,5; 0; 0; 0,5; 2,5).

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

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

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

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

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

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

Заданы п деталей di (i = 1, 2, ..., n), последовательно обрабатываемых на трех станках R1, R2, R3,  причем технологические маршруты всех деталей одинаковы. Обозначим ai ,bi ,ci — длительность обработки деталей di на первом, втором и третьем станках соответственно.

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

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

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

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

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

     s

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

A (sk+1) = A (sk)+,                                   

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

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

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

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

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

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

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

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

dC(s) = С(s) +,                                                  (1)

dB(s) = В (s) + +  min cj ,                                 (2)

dA(s) = A (s) +  +                           (3)

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

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

                         D(s) = max {dA(s), dB (s), dC (s)}.   (4)

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

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

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

где                             D(0) = max {dA(0), dB (0), бC (0)},

;  ;  .

Первый шаг.Образование    множеств    G1(1) U  G1(2) U... …G1(n).

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

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

   D(sk) = max {dA(sk), dB (sk), dC (sk)};  k = 1, n.

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

D(sk(1))=min D(sj(1)).

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

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

k - ш а г. Допустим, что уже проведено k шагов, в результате чего построены варианты s1(k), s2(k) ,…,svk(k), а именно подпоследовательности длиной k.

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

D(ss(k))=min D(sj(k)).

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

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

В результате строим дерево вариантов следующего вида: вершина О отвечает s = 0, вершины первого уровня G1(1), G2(1)..., Gn(1) соответствуют последовательностям длиной 1, т. е. s1(1) = 1, s2(1) = 2,..., sn(1) = п и т. д. Каждая конечная вершина отвечает последовательности максимальной длины п.

Признак оптимальности. Если sv(n)  отвечает конечной вершине дерева, причем оценка  наименьшая из оценок всех вершин, то sv(n) — искомый вариант, иначе переходим к продолжению варианта с наименьшей оценкой.

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

Таблица 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.

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

dB(s = 0) = В(0) +  +  min cj = 0 + 15 + 2 = 17;

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

Тогда

∆ (s = 0) = max {17, 17,14} = 17.

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

s1(1)  = 1;  s2(1) = 2;   s3(1) = 3;   s4(1) = 4;   s5(1) = 5.

Находим

dA(1)  = A1  +   +   = 14 + 3 = 17;

dB(1)(s = 0) = В1 +  +   = 5 + 12 + 2 = 19;

dC(1) = С1 + = 9 + 10 = 19 .

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

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

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

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

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

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

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

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

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

Летература

1)Зайченко Ю. П., «Исследование операций», Киев «Высшая школа» 1975г.

2)Акулич И.Л., «Математическое программирование в примерах и задачах», Москва «В ысшая школа» 1993г.

3)Кузнецов Ю.Н., Кузубов В.И., Волощенко А.Б. «Математическое программирование», Москва «В ысшая школа» 1980г.