Составители:
Рубрика:
34
По всем По всем
свободным частичным
переменным переменным
min( ,0)
ij i ij j
ab ax
>−
∑∑
для любого i = 0, 1, 2, …, m. (58)
то допустимого дополнения, которому соответствует значение целевой
функции, превосходящее нижнюю оценку x
0
t
, не существует.
Член в левой части неравенства (58) – сумма всех отрицательных
коэффициентов при свободных переменных. Если эта сумма больше
правой части неравенства, то даже полагая x
j
= 1, для каждой свободной
переменной с a
ij
< 0 невозможно выполнить i-е ограничение (57).
Другим важным моментом является то, что при заданном частичном
решении иногда удается определить, какое значение должна иметь сво-
бодная переменная при любом допустимом дополнении в случае, когда
значение целевой функции превосходит текущую нижнюю оценку. На-
пример, для частичного решения (x
1
, x
2
) = (1, 1) для задачи с ограниче-
нием
x
1
– x
2
+ 2x
3
– x
4
≤ 0 (59)
в любом дополнении должно выполняться условие x
3
= 0, при котором
оно допустимо по ограничению (59). Можно сформулировать общее
правило.
Если для частичного решения и свободной переменной x
k
По всем По всем
свободным частичным
переменным переменным
min( ,0)
ij ik i ij j
aab ax
+>−
∑∑
для любого i, (60)
то для a
ik
> 0 переменная x
k
= 0, а для a
ik
< 0 переменная x
k
= 1.
Перейдем к описанию алгоритма. На итерации t выполняются следу-
ющие шаги.
Шаг 1. Прекратить вычисления, если основной список частичных
решений пуст. Иначе выбрать частичное решение из основного списка
и вычеркнуть его из списка.
Шаг 2. Если можно найти свободные переменные, которые должны
иметь определенные значения при любом допустимом дополнении, когда
значение целевой функции превосходит текущую ее оценку x
0
t
, то рас-
ширить частичное решение включением значений найденных свобод-
Страницы
- « первая
- ‹ предыдущая
- …
- 32
- 33
- 34
- 35
- 36
- …
- следующая ›
- последняя »
