но при этом меняем 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
4 ( x1 ( 4
Список задач: 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. Поэтому данный вариант является
оптимальным.
Непосредственной проверкой убеждаемся, что время обработки всей
последовательности деталей для этого варианта совпадает со значением
оценки-прогноза и является минимальным:
Летература
1)Зайченко Ю. П., «Исследование операций», Киев «Высшая школа» 1975г.
2)Акулич И.Л., «Математическое программирование в примерах и задачах»,
Москва «В ысшая школа» 1993г.
3)Кузнецов Ю.Н., Кузубов В.И., Волощенко А.Б. «Математическое
программирование», Москва «В ысшая школа» 1980г.
-----------------------
††††††††††??
Страницы: 1, 2