Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

Получим 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_ц.

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

Обозначим _k = (i₁, i₂ , ..., i_k) — некоторую последовательность очередности запуска длиной k (1  k  п) и A (_k), В (_k), С (_k) — время окончания обработки последовательности деталей _k на первом, втором и третьем станках соответственно.

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

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



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

A (_k+1) = A (_k)+ ,

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

С (_k+1) = max [В (_k+1); С (_k)] +

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

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

А ()  А ( ), В ()  В ( ), С ()  С ( ),

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

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

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

_C() = С() + , (1)

_B() = В () + + min c_j , (2)

_A() = A () + + (3)

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

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

() = max {_A(), _B (), _C ()}. (4)

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

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

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

где (0) = max {_A(0), _B (0), б_C (0)},

; ; .

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

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

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

(_k) = max {_A(_k), _B (_k), _C (_k)}; k = 1, n.

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

(_k⁽¹⁾)=min (_j⁽¹⁾).

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

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

k - ш а г. Допустим, что уже проведено k шагов, в результате чего построены варианты ₁^(k), ₂^(k) ,…,_vk^(k), а именно подпоследовательности длиной k.

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

(_s^(k))=min (_j^(k)).

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

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

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

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

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

Таблица 1

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

_A( = 0) = A(0) + + = 0 + 14 + 3 = 17;

_B( = 0) = В(0) + + min c_j = 0 + 15 + 2 = 17;

_C( = 0) = С(0) + =14 .

Тогда

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

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

₁⁽¹⁾ = 1; ₂⁽¹⁾ = 2; ₃⁽¹⁾ = 3; ₄⁽¹⁾ = 4; ₅⁽¹⁾ = 5.

Находим

_A⁽¹⁾ = A₁ + + = 14 + 3 = 17;

_B⁽¹⁾( = 0) = В₁ + + = 5 + 12 + 2 = 19;

_C⁽¹⁾ = С₁ + = 9 + 10 = 19 .

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

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

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

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

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

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

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

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

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

Летература

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

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

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

9

Характеристики

Список файлов реферата