Автоматизация технологического проектирования. Смирнов О.Л. - 33 стр.

UptoLike

ВУЗ: 

СПб ГУАП | Санкт-Петербург

Составители: 

Рубрика: 

33
несколько частичных решений, а также известна некоторая оценка оп-
тимального решения и зафиксировано допустимое решение, дающее
эту оценку, то для каждого частичного решения можно сделать провер-
ку на существование допустимого дополнения, для которого значение
целевой функции превышает текущую нижнюю оценку. Если такого
дополнения нет, то рассматриваемое частичное решение считается про-
зондированным. Для него нет необходимости дальнейшего ветвления
дерева решений. При этом из дальнейшего рассмотрения исключаются
2
n–s
возможных назначения свободных переменных. Если же такие до-
полнения есть, то при заданном частичном решении значения осталь-
ных переменных должны выбираться так, чтобы дополнение этого ре-
шения было оптимальным. Существует несколько способов определе-
ния бесперспективности дополнения частичного решения. Рассмотрим
один из простых для задачи с таким ограничением:
– x
1
+ 2x
2
– 6x
3
+ 4x
4
– x
5
≤ 0. (55)
Для частичного решения (x
1
, x
3
, x
4
) = (1, 0, 1) ни одно дополнение не
допустимо по условию (55). Пусть целевая функция для этого примера
описывается уравнением 2x
1
+ x
2
+ 5x
3
+ 3x
4
– x
5
, а текущая оценка
целевой функции x
0
t
= 7. Чтобы улучшить эту оценку, дополнение дол-
жно удовлетворять ограничению, полученному из выражения для целе-
вой функции и оценки x
0
t
= 7:
2x
1
+ x
2
+ 5x
3
+ 3x
4
– x
5
≥ 8 или – 2x
1
– x
2
– 5x
3
– 3x
4
+ x
5
≤ – 8. (56)
Последняя форма этого неравенства более удобна для проверки до-
полнений, так как в нем используется тот же знак неравенства, что и в
каждом ограничительном неравенстве. Итак, для частичного решения
(x
2
, x
3
, x
5
) = (1, 0, 1) ни одно дополнение не допустимо по условию (56).
Смысл рассмотренных примеров в следующем. Для заданного час-
тичного решения представим линейные ограничения в виде
По всем По всем
свободным частичным
переменным переменным
,0,1,2,,,
ij j i ij j
ax b ax i m
≤− =
∑∑
…
(57)
где каждой переменной x
j
в частичном решении поставлено в соответ-
ствие определенное значение, входящее под знак суммы в правой части
неравенства (57), а коэффициенты в ограничении при i = 0 равны a
0j
= – c
j
и b
0
= – x
0
t
– 1. Тогда, если для заданного частичного решения

Страницы