5.4. Вырожденность. Метод возмущений

В случае, когда угловая точка х множества R₀ вырождена, число ее положительных компонент будет меньшим m. Тогда может оказаться, что λ₀ = 0 (см. (5.7)) и, следовательно, при переходе в симплексном методе от вырожденной угловой точки х к Следующей угловой точке значение целевой функции может не убывать (см. (5.10)). Кроме того, как мы видели, вырожденность может повлечь за собой неоднозначность выбора вектора, исключаемого из базиса, при переходе от угловой точки х к вырожденной угловой точке x_k=x_k(λ₀).

Эти обстоятельства теоретически могут привести к явлению зацикливания, когда через некоторое число итераций процедура симплексного метода приводит к прежней угловой точке. Для преодоления явления зацикливания существует правило выбора вектора, исключаемого из Зазиса, основанное на так называемом методе возмущений.

Предположим, угловой точке х множества R₀ соответствует такая линейно-независимая система m векторов а₁, a₂ ,..., а_m, что x_B=B^-1b≥0 (в отличие от не вырожденного случая, когда х_в > 0), где В = [а₁, а₂, ...., а_m].

Рассмотрим "возмущенный" вектор

где ε - достаточно малое положительное число (ε > 0), а ε^j означает j-ю степень числа ε. Обозначив, как и прежде, z_ij, = (В^-1а_j)_i, получаем

Так как

то

(5.16)

Рассмотрим наряду с задачей (5.1):

- так называемую ε-задачу:

(5.17)

и покажем, что для всех достаточно малых ε >> 0 эта задача не вырождена.

Пусть а₁, а₂,... , а_m-произвольная линейно-независимая система векторов матрицы А. Так как функции x_i(ε) (i = 1,...,m) представляют собой многочлены относительно ε, не равные тождественно нулю (см. (5.16)), то каждый из них имеет не более n корней и, следовательно, не более n положительных корней.

Пусть η есть наименьший положительный корень среди всех положительных корней m многочленов x_i(ε) (i = 1,...,m) (если положительных корней нет ни у одного из этих многочленов, то полагаем η = ∞). Величина η определяется выбранной системой линейно-независимых векторов a₁, а₂,... , а_m, и поскольку число линейно-независимых систем векторов матрицы А конечно, то конечно и число соответствующих наименьших положительных корней η.

Пусть ε₀ > 0-наименьшее из всех чисел η (то есть наименьший положительный корень всех многочленов x_i(ε), построенных по всевозможным линейно-независимым системам векторов матрицы А). Ясно, что при ε<ε₀ ни один из многочленов вида (5.16) не обращается в нуль (ε > 0), а следовательно, всякая угловая точка ε-задачи содержит m положительных компонент, то есть не вырождена.

Можно доказать, что для малых ε угловым точкам x ∈ R₀ и х(ε) ∈ R_n (ε) соответствует один и тот же базис^*, поэтому для однозначного выбора индекса s ∈ I_k, на котором достигается минимум отношения

(см. (5.7))

при симплексной процедуре решения задачи (5.1), целесообразно обратиться к ε-задаче. То есть в качестве номера s вектора a_s, исключаемого из базиса, следует выбрать тот номер (единственный ввиду не вырожденности ε-задачи), для которого достигается минимум отношения

На практике нет нужды переходить к ε-задаче. Из предыдущей формулы ясно, что выбор номера s можно осуществить следующим путем.

Обозначим через I_k0(s_k) совокупность индексов s_k∈I_k, для которых достигается минимум отношения

^* (Строгое обоснование этого утверждения можно найти в [14]. )

Если I_k0(s_k) состоит более чем из одного элемента, то вычисляют

Если I_k1(s_l) состоит из одного элемента, то s_l и есть искомый номер. Если I_kl(s_l) содержит два и более элементов, то вычисляют

и т. д. Ясно, что такой процесс конечен и приводит к однозначному выбору искомого номера.

Опыт применения симплексного метода показал, что для исключения возможности зацикливания достаточно выбрать любой регулярный способ однозначного выбора номера s, например, в качестве s можно выбрать первый (в порядке установленной нумерации) номер, для которого достигается минимум отношения (5.7). При этом естественно, что номер k также должен выбираться (если он не единствен) регулярным способом, например, среди всех k таких, что Δ_k > 0 и (B^-1a_k)_i > 0 можно выбирать тот, для которого величина Δ_k наименьшая.