Матричное описание симплекс-метода

Рассмотрим каноническую ЗЛП в матричной форме:
max cx
Ах = b, х ≥ 0.

Рассмотрим сначала случай, когда строки матрицы A линейно независимые. Пусть B — некоторая база матрицы A, а B — соответствующая базисная подматрица и пусть
A = (B,N)

Матричное описание симплекс-метода

c = (cB, cN)
где через xB, cB обозначены векторы, составленные из базисных компонент векторов x и c соответственно, а через xN, cN обозначены векторы, составленные из небазисных компонент векторов x и c соответственно. Тогда ЗЛП  примет вид:

max(cBxB + cNxN)

BxB + NxN = b, xB 0,  xN0.

Шаг исключения Гаусса на каждой итерации симплекс-метода заключается в умножении слева текущей симплексной таблицы на матрицу

где r ≠0, s≠0. Следовательно, серия шагов исключения Гаусса эквивалентна домножению симплексной таблицы на произведение

M = Et· Et-1 · …· E1
Матрица M имеет следующее блочное строение:


Пусть на некоторой итерации симплекс-метода получена симплекс-таблица
соответствующая базе B. Тогда uB - cB = 0 и FB = E, откуда u = cBB-1. Итак, симплекс-таблица, соответствующая базе B, имеет вид:
Строка u = с B В-1 называется вектором цен, соответствующим базе B. Компоненты вектора u называются ценами, или симплекс-множителями.

Справедливы следующие равенства, выражающие элементы симплексной таблицы через коэффициенты ограничений и вектор цен:
q00 = cx = ub, b* = B-1b, c*= c —u A, а* = B-1as.

Интерпретируя коэффициенты симплекс-таблицы, получим следующую эквивалентную формулировку задачи:

max (cBB-1 b + (cN –cBB-1N)xN)

xB = B -1 b – B -1 NxN
xB ≥ 0 , xN ≥ 0

Формула с* = c - uA показывает, что для того, чтобы вычислить текущие относительные оценки (нулевую строку симплекс-таблицы) необходимо из строки c вычесть все строки матрицы A, домноженные на соответствующие цены u.

Решение х системы Ax = b базисное, если хN = 0 и, следовательно, xB = В-1b. Базисное решение х допустимо, если х ≥ 0 и, так как х N = 0, то достаточно потребовать х B 0. Значение целевой функции cx на базисном решении х есть сх = ub. Базисное решение оптимально, если c * = c — uA ≥ 0, или с N= cN — uN ≥ 0.

см. также Решение модифицированным симплекс-методом

загрузка...