Предыдущая страница реферата | 1  2  3  4  5  6 | Следующая страница реферата

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* — дробное, из области решений исключаем полосу 3max

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

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]), С (() ( С

Рекомендуем скачать другие рефераты по теме: реферат на тему русские, реферат охрана.





Предыдущая страница реферата | 1  2  3  4  5  6 | Следующая страница реферата