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