 |
 |
 |
 |
|
 |
 |
20
Если интерпретировать компоненты векторов а
j
и b как координаты в ортогональном базисе, то их
столбцы координат относительно произвольного базиса (?
(q)
), дополненного единичным вектором (-
1,0,..., 0), направленным противоположно оси аппликат примут вид:
а для расширенной матрицы задачи в целом можно записать
Нулевая строка данной матрицы a
0
(?
(q)
) содержит координаты расширенных векторов условий по оси
аппликат. Согласно построению, элементы данной строки имеют следующие знаки:
a
0,j
(?
(q)
) < 0 — для расширенных векторов условий, расположенных выше плоскости, натянутой
на систему расширенных базисных векторов;
a
0,j
(?
(q)
)
> 0 — для расширенных векторов условий, расположенных ниже плоскости, натянутой
на систему расширенных базисных векторов;
a
0,j
(?
(q)
) = 0 — для расширенных базисных векторов.
Подводя итог сказанному, сформулируем критерий оптимальности допустимого базисного плана
в симплекс-методе:
план является оптимальным, если для всех j
1: n a
0,j
(?
(q)
)
? 0,
и неоптимальным в противном
случае, т. е. если существует такое l
l : n, что a
0l
(?
(q)
) < 0.
Значения a
0,j
(?
(q)
)
также называют оценками столбцов матрицы А относительно текущего базиса,
или симплекс-разностями.
В случае неоптимальности текущего базиса в алгоритме симплекс-метода осуществляется переход к
следующему базису. Это делается за счет вывода одного столбца из базиса и ввода другого. Для
обеспечения улучшения значения целевой функции в базис должен быть введен вектор-столбец,
имеющий отрицательную оценку. Если таких столбцов несколько, то для ввода рекомендуется
выбирать столбец, имеющий максимальную по модулю оценку. Отметим, что данное правило носит
относительный характер и не гарантирует наилучшего выбора вводимого столбца. Одновременно на
этой стадии требуется принять решение о том, какой столбец следует вывести из базиса. Сделать это
нужно таким образом, чтобы вновь формируемый базис оказался допустимым. Данное требование
может быть легко проиллюстрировано для случая m = 2. Например, на рис. 1.3 векторы {а²,а³} образуют
допустимый базис, а векторы {а³,a
4
} —недопустимый, т. к. разложение b по а³ и а
4
содержит один
отрицательный компонент плана, что противоречит условиям КЗЛП.
Можно доказать, что допустимость базиса, к которому осуществляется переход, обеспечивается
следующим правилом вывода столбца из текущего базиса:
для столбца l, претендующего на ввод в базис, и вектора ограничений b рассматриваются
отношения
и определяется такая строка r, что
Полученный индекс r определяет номер столбца в N(?
(q)
), выводимого из базиса, а именно, N(?
(q)
).
Таким образом, если базис на q-й итерации включал столбцы с номерами
то базис на итерации q + 1 будет состоять из столбцов с номерами: