Математические методы исследования операций в экономике (стр. 7 из 37)

δ_i(β^(q)) — i-я строка матрицы ∆ˉ^-1(β^(q)), (iÎ 0: m );

δ_ij(β^(q)) — элемент матрицы ∆^-1(β^(q)), находящийся в i-й строке j-го столбца (iÎ0: m, jÎ0 : m).

Расширенный вектор ограничений b представляется в виде линейной комбинации расширенных векторов условий с коэффициентами, равными базисным компонентам текущего базисного плана:

Если интерпретировать компоненты векторов а^j и b как координаты в ортогональном базисе, то их столбцы координат относительно произвольного базиса (β^(q)), дополненного единичным вектором (-1,0,..., 0), направленным противоположно оси аппликат примут вид:

а для расширенной матрицы задачи в целом можно записать

Нулевая строка данной матрицы a₀(β^(q)) содержит координаты расширенных векторов условий по оси аппликат. Согласно построению, элементы данной строки имеют следующие знаки:

- a_0,j (β^(q)) < 0 — для расширенных векторов условий, расположенных выше плоскости, натянутой на систему расширенных базисных векторов;

- a_0,j (β^(q))> 0 — для расширенных векторов условий, расположенных ниже плоскости, натянутой на систему расширенных базисных векторов;

- a_0,j (β^(q)) = 0 — для расширенных базисных векторов.

Подводя итог сказанному, сформулируем критерий оптимальности допустимого базисного плана в симплекс-методе:

-план является оптимальным, если для всехjÎ1:na_0,j (β^(q)) ≥ 0, и неоптимальным в противном

случае, т. е. если существует такое lÎl : n, что a_0l (β^(q)) < 0.

Значения a_0,j (β^(q))также называют оценками столбцов матрицы А относительно текущего базиса, или симплекс-разностями.

В случае неоптимальности текущего базиса в алгоритме симплекс-метода осуществляется переход к следующему базису. Это делается за счет вывода одного столбца из базиса и ввода другого. Для обеспечения улучшения значения целевой функции в базис должен быть введен вектор-столбец, имеющий отрицательную оценку. Если таких столбцов несколько, то для ввода рекомендуется выбирать столбец, имеющий максимальную по модулю оценку. Отметим, что данное правило носит относительный характер и не гарантирует наилучшего выбора вводимого столбца. Одновременно на этой стадии требуется принять решение о том, какой столбец следует вывести из базиса. Сделать это нужно таким образом, чтобы вновь формируемый базис оказался допустимым. Данное требование может быть легко проиллюстрировано для случая m = 2. Например, на рис. 1.3 векторы {а²,а³} образуют допустимый базис, а векторы {а³,a⁴} —недопустимый, т. к. разложение b по а³ и а⁴ содержит один отрицательный компонент плана, что противоречит условиям КЗЛП.

Можно доказать, что допустимость базиса, к которому осуществляется переход, обеспечивается следующим правилом вывода столбца из текущего базиса:

-для столбца l, претендующего на ввод в базис, и вектора ограничений b рассматриваются

отношения

и определяется такая строка r, что

Полученный индекс r определяет номер столбца вN(β^(q)), выводимого из базиса, а именно, N(β^(q)).

Таким образом, если базис на q-й итерации включал столбцы с номерами

то базис на итерацииq + 1 будет состоять из столбцов с номерами:

Отдельно следует обсудить тот случай, когда столбец a_l (β^(q)), претендующий на ввод в базис, не содержит положительных компонентовa_l (β^(q)) ≤ 0). Это означает, что целевая функция в задаче не ограничена на множестве допустимых значений, т. е. может достигать сколь угодно большого значения. Последнее, очевидно, означает завершение процесса вычислений ввиду отсутствия оптимального плана. Геометрически ситуация, когда a^l (β^(q)) ≤ 0, соответствует тому, что ось ординат оказывается внутри конуса, натянутого на систему расширенных столбцов а^j, а значит, прямая, проведенная через конец вектора bпараллельно оси аппликат, однажды «войдя» в этот конус, более никогда из него «не выходит».

Вообще говоря, после перехода от базиса β^(q) к базису β^(q+1) мы можем заново сформировать матрицы ∆ (β^(q+1)), Δ^-1(β^(q+1)) и, вычислив А(β^(q+1)) = Δ^-1(β^(q+1))A, делать выводы о его оптимальности. Однако, учитывая, что β^(q+1) отличается от β^(q) всего лишь одним столбцом, с точки зрения техники вычислений представляется рациональным непосредственно переходить от A(β^(q)) иb (β^(q)) к A(β^(q+1)) иb (β^(q+1)) . Дело в том, что у матриц типа A(β^(q)) столбцы, соответствующие базисным векторам, состоят из нулей, за исключением одного элемента, равного единице. Позиция этого ненулевого элемента определяется порядковым номером базисного столбца в N(β^(q)). Поэтому для получения матрицы A(β^(q+1)) достаточно с помощью линейных операций над строками матрицы A(β^(q)) привести ее столбец, соответствующий вводимому в базис вектору, к «базисному» виду.

Для это применяется преобразование Жордана—Гаусса(так называемый метод полного исключения). В данном случае оно состоит в том, что мы должны «заработать» единицу на месте элемента a_r,l(β^(q)) (он обычно называется ведущим)* и нули на месте остальных элементов столбца a^l(β^(q)). Первое достигается посредством деления r-й строки на ведущий элемент, второе — путем прибавления вновь полученной r-й строки, умноженной на подходящий коэффициент, к остальным строкам матрицы A(β^(q)).

* Напомним, что l — номер столбца, вводимого в базис, а r — номер строки в симплекс-таблице, определяющей номер столбца, выводимого из базиса.

Формально результат выполнения данного преобразования над элементами A(β^(q)) и b(β^(q)) может быть выражен в следующем виде

Следует особо отметить смысл элементов вектора b(β^(q)). Его нулевой компонент b₀(β^(q)) в соответствии с построением содержит значение целевой функции, достигаемое ею на текущем плане

а остальные элементы — ненулевые компоненты этого плана: