Составители:
Рубрика:
37
– 6(x
2
= 1) – 3(x
3
= 1) – 6(x
4
= 1) ≤ – 13. (72)
Применяя условие (60) для i = 1, 2, получаем, что x
4
= 0 и x
2
= 0:
для i = 1 имеем
– 6(x
2
= 1) + 12(x
4
= 0) ≤ 8 – 6(x
3
= 1) = 2; (73)
для i = 2 имеем
+ 12(x
2
= 0)
– 6(x
4
= 1) ≤ 8 + 3(x
3
= 1). (74)
В результате проверки (58) для i = 0 получаем, что не существует
допустимого дополнения со значением ЦФ, превосходящим x
0
4
= 13.
Возвращаясь к шагу 1, прекращаем вычисления, так как все ЧР из дере-
ва ветвей исчерпаны. Оптимальное значение целевой функции равно 13.
18. Оптимизация запуска процессов обработки
с одинаковыми маршрутами динамическим программированием
по векторному критерию
Рассмотрим применение метода динамического программирования
на примере обработки пяти деталей a, b, c, d, e на пяти станках A, B, C,
D, E (табл. 3).
Как видно из таблицы, маршруты
обработки всех деталей одинаковы. Вре-
мя окончания процессов обработки всех
деталей T зависит от порядка запуска
их обработки T = T(σ
1
, σ
2
, σ
3
, σ
4
, σ
5
),
где σ
i
– номер детали, запускаемой в об-
работку. Необходимо определить такой
порядок обработки деталей (σ
1
opt
, σ
2
opt
,
σ
3
opt
, σ
4
opt
, σ
5
opt
), при котором T(σ
1
opt
,
σ
2
opt
, σ
3
opt
, σ
4
opt
, σ
5
opt
) = T
min
.
На первом этапе для всех пар дета-
лей производится сравнение времени их обработки для двух случаев
обработки сначала первой детали (σ
1
, σ
2
), а потом – второй (σ
2
, σ
1
). Из
каждой пары вариантов оставляется тот, для которого время заверше-
ния обработки обеих деталей на каждом станке меньше или равно соот-
ветствующему времени для другого варианта. В противном случае ос-
тавляются оба варианта для рассматриваемой пары деталей.
Таблица 3
Время выполнения операций
пяти деталей на пяти станках
ьлатеД
яиненлопывямерВ
екнатсаниицарепо
ABCDE
a25346
b43545
c54363
d43644
е36454
Страницы
- « первая
- ‹ предыдущая
- …
- 35
- 36
- 37
- 38
- 39
- …
- следующая ›
- последняя »
