 |
 |
 |
 |
|
 |
 |
19
С вычислительной точки зрения критерий оптимальности в симплекс-методе реализуется через
нахождение специальных оценок для небазисных векторов-столбцов, относительно текущего базиса.
Для удобства дальнейшего изложения введем некоторые обозначения. Учитывая то, что симплекс-
метод представляет собой некоторый итеративный вычислительный процесс, то через
q будем
обозначать номер очередной (текущей) итерации. Соответственно, набор базисных столбцов,
получаемых на q-й итерации, будет обозначаться как ?
(q)
:
Для того чтобы было легче отличить номер итерации от номеров компонентов матриц и векторов, он
заключен в круглые скобки. Номера столбцов, входящих в базис, обозначим через N(?
(q)
), а именно
При этом Nr(?
(q)
) =jr — номер столбца, занимающего r-ю позицию в базисе. Тогда текущий базисный
план х имеет вид:
Обозначим через
?(
?
(q)
) матрицу, составленную из столбцов {а
j1
, а
j2
,..., а
jm
}, образующих базис, через
?(
?
(q)
) матрицу, образованную из соответствующих расширенных столбцов и дополненную слева
столбцом специального вида:
а через
?
-1
(?
(q)
) и
?
-1
(?
(q)
) — матрицы, обратные по отношению к ним. Также представляется удобным
ввести отдельные обозначения для элементов матрицы
?
-1
(?
(q)
):
?
i
(?
(q)
)
—
i-я строка матрицы
??
-1
(?
(q)
), (i ? 0: m );
?
ij
(?
(q)
)
— элемент матрицы
?
-1
(?
(q)
), находящийся в i-й строке j-го столбца (i ? 0: m, j? 0 : m).
Расширенный вектор ограничений b представляется в виде линейной комбинации расширенных
векторов условий с коэффициентами, равными базисным компонентам текущего базисного плана: