 |
 |
 |
 |
|
 |
 |
23
получаемому на
q-й итерации. Столбец N(?
(q)
) содержит номера базисных столбцов (в той
последовательности, в которой они входят в базис), столбец b(?
(q)
) —компоненты вектора ограничений
относительно текущего базиса ?
(q)
,
A(?
(q)
) — компоненты матрицы задачи относительно текущего
базиса ?
(q)
. Наконец, в строке а
0
(?
(q)
) находятся текущие оценки столбцов, а ячейка b
0
(?
(q)
) содержит
значение целевой функции, достигаемое для текущего плана.
Безусловно, следует добавить, что табличная модификация симплекс-метода имеет важное
практическое значение не
столько как удобная форма организации ручного счета, сколько как основа
для реализации данного алгоритма в рамках программного обеспечения ЭВМ.
1.4.3. Пример решения ЗЛП симплекс-методом. Рассмотрим на конкретном примере процесс
решения КЗЛП табличным симплекс-методом. Пусть дана каноническая задача ЛП:
Как видно, столбцы матрицы с номерами {5, 2, 3} являются линейно независимыми. И можно
получить разложение по данным столбцам вектора ограничений с положительными коэффициентами.
Последнее означает, что столбцы {5, 2, 3} образуют допустимый базис, с которого можно начать
решение задачи. Из столбцов, входящих в базис, с учетом нулевых элементов формируется матрица
?(?
(1)
) и обратная по отношению к ней ?
-1
(?
(1)
):
Используя их, по формуле (1.26) получаем
-84
0
0
-88
0
1/3
0
0
1/3
1
=
2
1
0
3
0
;
-2/3
0
1
-4/3
0
Используя полученные значения A(?
(1)
) и b(?
(1)
), заполняем симплекс-таблицу T
(1)
, соответствующую
первой итерации (q=1).