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

но при этом меняем 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* —

дробное, из области решений исключаем полосу 3max

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

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ц.

Можно показать, что в задаче трех станков очередность выполнения

первых, вторых и третьих операций в оптимальном решении может быть

одинаковой (для четырех станков это свойство уже не выполняется). Поэтому

достаточно определить очередность запуска только на одном станке

(например, третьем).

Обозначим (k = (i1, i2 , ..., ik) — некоторую последовательность

очередности запуска длиной k (1 ( k ( п) и A ((k), В ((k), С ((k) — время

окончания обработки последовательности деталей (k на первом, втором и

третьем станках соответственно.

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

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

(

Покажем, как можно рекуррентно вычислять A ((k), В ((k), С ((k).

Пусть (k+1 = ((k ,ik+i), т. е. последовательность деталей (k+1 получена

из деталей (k с добавлением еще одной детали ik+1. Тогда

A ((k+1) = A ((k)+[pic],

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

С ((k+1) = max [В ((k+1); С ((k)] +[pic]

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

доминирования .

Если ( — некоторая начальная последовательность, а [pic] — под

последовательность образованная из ( перестановкой некоторых символов, то

вариант ( доминирует над [pic], когда выполняются следующие неравенства:

А (() ( А ([pic]), В (() ( В ([pic]), С (() ( С

([pic]),

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

Способ конструирования вариантов после-

довательностей ( и вычисления оценок ((() для каждого из них состоит в

следующем.

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

величины:

(C(() = С(() +[pic], (1)

(B(() = В (() +[pic] + min cj , (2)

(A(() = A (() +[pic] + [pic] (3)

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

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

((() = max {(A((), (B ((), (C (()}. (4)

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

формальной схемой.

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

последовательностями (( = 0).

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

где ((0) = max {(A(0), (B (0), бC (0)},

[pic]; [pic]; [pic].

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

Подмножество Gk определяется всеми последовательностями с началом

ik(k — 1, ...,n ).

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

соотношения (4), т. е.

(((k) = max {(A((k), (B ((k), (C ((k)}; k = 1, n.

Выбор варианта для продолжения. Из всех подпоследовательностей,

построенных на предыдущем шаге, выбирают наиболее перспективную

последовательность (k с наименьшей оценкой, т. е.

(((k(1))=min (((j(1)).

Ветвление. Выбрав наиболее перспективный вариант последовательности

(k(1), развивают его построением всех возможных подпоследовательностей

длиной 2 с началом (k(1) вида (k+1(2)= ((k(1), j), где j не входит в

(k.

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

(3).

k - ш а г. Допустим, что уже проведено k шагов, в результате чего

построены варианты (1(k), (2(k) ,…,(vk(k), а именно подпоследовательности

длиной k.

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

(((s(k))=min (((j(k)).

Множество Gs(k) разбиваем на (п — k) подмножеств, каждое из которых

образуется добавлением к последовательности (s(k) некоторого элемента

ik+1 такого, что ik+1[pic].

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

В результате строим дерево вариантов следующего вида: вершина О

отвечает ( = 0, вершины первого уровня G1(1), G2(1)..., Gn(1)

соответствуют последовательностям длиной 1, т. е. (1(1) = 1, (2(1) =

2,..., (n(1) = п и т. д. Каждая конечная вершина отвечает

последовательности максимальной длины п.

Признак оптимальности. Если (v(n) отвечает конечной вершине дерева,

причем оценка [pic] наименьшая из оценок всех вершин, то (v(n) — искомый

вариант, иначе переходим к продолжению варианта с наименьшей оценкой.

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

в табл. 1:

Таблица 1

|Длительность |Деталь |

|операций | |

| |1 |2 |3 |4 |5 |

|ai |2 |5 |1 |3 |3 |

|bi |3 |2 |1 |4 |5 |

|ci |4 |4 |2 |2 |2 |

Нулевой шаг. ( = 0.

(A(( = 0) = A(0) + [pic] + [pic] = 0 + 14 + 3 = 17;

(B(( = 0) = В(0) + [pic] + min cj = 0 + 15 + 2 = 17;

(C(( = 0) = С(0) + [pic]=14 .

Тогда

? (( = 0) = max {17, 17,14} = 17.

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

(1(1) = 1; (2(1) = 2; (3(1) = 3; (4(1) = 4; (5(1) = 5.

Находим

(A(1) = A1 + [pic] + [pic] = 14 + 3 = 17;

(B(1)(( = 0) = В1 + [pic] + [pic] = 5 + 12 + 2 = 19;

(C(1) = С1 + [pic]= 9 + 10 = 19 .

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

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

[pic]

Второй шаг. Среди множества подпоследовательностей длиной 1, (1(1) =

1, (2(1) = 2,..., (5(1) = 5 выбираем наиболее перспективную ( = 1, для

которой величина оценки-прогноза ? (() оказывается наименьшей. Далее

развиваем ее, конструируя возможные варианты длиной 2, т. е. (1.2),

(1.3), (1.4), (1.5).

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

— (4).

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

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

Каждой конечной вершине дерева вариантов будет отвечать полная

последовательность ( = i1,i2,,.in. Если для некоторой такой вершины

величина оценки ? (() не превосходит величины оценок для всех остальных

вершин, то эта оценка определяет искомый оптимальный вариант. В противном

случае разбиваем более перспективный вариант с наилучшей оценкой.

Конечная вершина определяет вариант (последовательность) [pic] = 3,

1, 5, 2, 4 с наилучшей оценкой ? = 20. Поэтому данный вариант является

оптимальным.

Непосредственной проверкой убеждаемся, что время обработки всей

последовательности деталей для этого варианта совпадает со значением

оценки-прогноза и является минимальным:

[pic]

Летература

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

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

Москва «В ысшая школа» 1993г.

3)Кузнецов Ю.Н., Кузубов В.И., Волощенко А.Б. «Математическое

программирование», Москва «В ысшая школа» 1980г.

-----------------------

††††††††††??

[pic]

Страницы: 1, 2



2012 © Все права защищены
При использовании материалов активная ссылка на источник обязательна.