Базис и базисное решение

В задаче ЛП базисы и базисные решения играют ключевую роль в организации поиска оптимального решения, если оно существует. С их помощью генерируются очередные вершины области допустимых решений, и организуется переход из одной вершины в другую. Удачный выбор начального базиса и базисного решения может существенно ускорить процесс поиска.

Иллюстрируем возможность такого выбора на примере задачи с ограничениями в виде

f(x) = 2x1 + 3x2 + 5x3 → max.

4x1 + x2 + 5x3 = 10

2x1 + 3x2 + 2x3 = 12

x1 , x2 , x3 ≥ 0

 

Если представить ограничения этой задачи в виде Ax = b, то матрица А примет форму А = [a1, a2, a3], где a1 = (4, 2)T, a2 = (1, 3)T, a3 = (5, 2)T. x = (x1 , x2 , x3)T. Векторы a1, a2, a3, как легко в этом убедиться, являются линейно независимыми, поэтому любую двойку из них можно выбрать в качестве начального базиса. Примерами такого выбора являются, например, (2х2) – матрицы В1 = [a1, a2], B2 = [a2, a3], B3 = [a1, a3]. Эти матрицы действительно служат базисом для векторов матрицы А.

Путем разложения А = [B, N] матричное уравнение Ax = b представляется в виде

 

[B, N] ( хTB, xTN)T = b, (4.1)

или что эквивалентно,

 

B + NxN = b. (4.2)

Так как по определению матрица B имеет обратную матрицу, решение последнего уравнения относительно вектора хB, получим в виде

 

хB = B-1 b - B-1NxN. (4.3)

 

Принимая в этом выражении xN = 0, получим базисное решение в виде

 

хB = B-1 b. (4.4)

Если оно неотрицательно, т.е. хB ≥ 0, получим допустимое базисное решение. Этому решению соответствует вершина множества допустимых решений, которую можно определить в виде

х1 = . (4.5)

В этой точке значение целевой функции равно f(x1) = cTx1 = cBTxB.

Рассмотрим все три возможности.

 

а) В = В1 = [a1, a2]:

хB = (х х)Т = В1-1b = (0.6, 3.8)Т,

 

х1 = (0.6, 3.8, 0)Т;

 

б) В = В2 = [a2, a3]:

 

хB = (х х)Т = В2-1b = = (16/13,

38/13)Т, х2 = (0, 16/13, 38/13)Т;

 

в) В = В3 = [a1, a3]:

 

хB = (х х)Т = В3-1b = = (2, 1)Т,

х3 =( 2, 0, 1)Т.

 

Все три вершины являются допустимыми.

 

 

1.5. Табличный симплекс-метод (симплекс-алгоритм)

Cимплекс - метод основан на итеративном процессе перебора (или преобразования) вершин области допустимых решений и проверки в этих вершинах условия оптимальности. Вершины, как отмечалось выше, генерируются с помощью базисов. Табличный вариант алгоритма весьма удобен для машинного счета, так как связан с преобразованием таблиц – массивов данных, которые содержат сведения о текущем базисе, базисном решении, правиле остановки и, наконец, об оптимальном решении. В процессе преобразования таблиц, которое представляет собой реализацию процедуры полного исключения Гаусса, формируется также информация о двойственных переменных решаемой задачи.

Пусть задача представлена в канонической форме

 

, (5.1)

Ax = b

x ≥ 0.

 

где с и х – векторы размерности (п х1), т. е. сÎ Еп, хÎ Еп, А – матрица размерности (mхп), b – (пх1) – вектор.

Допустим, что матрица А допускает представление в виде А = [B, N], где B – (mхm) – матрица полного ранга. Для простоты предположим, что B - единичная матрица, т.е. B = I. Это может иметь место, например, если ограничения исходной задачи имеют вид Ax ≤ b. В случае неотрицательного вектора b, т. е. b ≥ 0, это предположение помогает найти первое базисное решение в виде

 

xB = B -!b = I -1b = b ≥ 0. (5.2)

Тогда первая вершина будет равна

 

х1 = (0Тп - m, bТ)Т, (5.3)

где через 0п–m обозначен нулевой вектор с п–m координатами. Для построения исходной таблицы обозначим через IB и IN, множества индексов векторов из B и N соответственно и вычислим так называемые симплекс -разности для векторов, принадлежащих N по формуле

 

(СР)j = cj . (5.4)

 

Симплекс – разности содержат в себе информацию об оптимальности текущего базисного решения, следовательно, и текущей вершины. Согласно этому правилу, если при решении задачи на максимум на каком-либо шаге (или итерации) симплексных преобразований имеет место

(СР)j £ 0, "j Î IN, (5.5)

тогда найденное базисное решение является оптимальным. В противном случае поиск решения продолжается.

Легко заметить, что для всех базисных векторов всегда имеет место условие

 

(СР)j = 0, "j Î IВ, (5.2)

 

т. е. векторы из В имеют нулевую симплекс – разность на всех этапах симплексных преобразований.

Пусть необходимо решить задачу

 

f(x) = 2x1 + 3x2max.

4x1 + 3x2 £ 12

x1 £ 2

x2 £ 3

x1, х2 ≥ 0

 

Удобно представить последующие действия в виде последовательности шагов алгоритма. Он состоит из предварительного и основного этапов.

Предварительный этап. Представить задачу в канонической форме

f(x) = 2x1 + 3x2 → max.

4x1 + 3x2 + x3 =12

x1 + x4 = 2

x2 + x5 = 3

xj ≥ 0, j = 1,…,5

 

Основной этап.

Шаг 1. Разложение матрицы А. Записать ограничения в виде матричного уравнения Ax = b, x ≥ 0, и представить матрицу А в виде

 

,

 

 

выделив в ней (mxm) – матрицу B полного ранга. Удобно в данном случае выбрать в качестве начального базиса единичную матрицу B = [a3, a4, a5] = I, следовательно, N = [a1, a2], IB {3, 4, 5}, IN = {1, 2}. Как видно, B = I – единичная матрица размерности (3х3). Если получение базиса В не представляется возможным, то задача не имеет решения.

Шаг 2. Нахождение базисного решения. Начальному базису В соответствует базисное решение в виде

 

хB =(х, х, х)Т = B-1b = Ib = (12, 2, 3)Т.

 

Соответствующая этому базисному решению вершина равна х1 = (0, 0, 12, 2, 3)Т. Последние три координаты х1 совпадают ссоответствующими координатами хB, а первые две координаты равны нулю. Значение целевой функции в этой точке равно

 

f(x1) = f(xB) = cBTxВ = 0,

т.к. сВ =(с3, с4, с5)Т = (0, 0, 0)Т.

Шаг 3.Вычисление симплекс - разностей и построение правила остановки. Вычислим симплекс - разности для небазисных векторов из N. Так как IN = {1, 2}, имеем

 

(СР)1 = c1 ,

 

(СР)2 = c2 .

 

Легко заметить, что из-за нулевого вектора сВ = (0, 0, 0)Т имеет место условие

 

(СР)3 = (СР)4 = (СР)5 = 0.

 

Так как симплекс - разности (СР)1 и (СР)2 положительны, поиск оптимального решения продолжается.

Шаг 4.Построение и преобразование исходной таблицы Т0.

Исходная симплекс – таблица, соответствующая решаемой задаче, приведена на рис. 2.2.

 

исходная таблица Т0

 

 
i0 = 5
J0 = 2

 

 

Рис. 2.2. Исходная симплекс – таблица.

 

 

Она содержит матрицу А, вектор b, базисное решение xB = b и так называемую индексную строку, в которой первый ее элемент – это текущее значение целевой функции f(x) = f(xB) = cBTxB, а остальные ее элементы – это= cBTxB, а остальные ее элементы – это так называемые индексы Dj = - (CP)j, j = 1, …, n, значение которых определяется как симплекс - разности с обратным знаком. Цифровая часть симплекс - таблицы называется ее главной частью: она и подвергается преобразованию от итерации к итерации.

Шаг 5. Проверка правила остановки

Если Dj ³ 0, j = 1, …, n, остановиться; найденное базисное решение является оптимальным, а значение целевой функции наибольшее. В данном случае обе величины Dj отрицательны. Это означает, что обе симплекс - разности (CP)j, j = 1, 2, положительные, следовательно, поиск продолжается.

Шаг 6. Выбор направляющего столбца и направляющей строки. Направляющий столбец с индексом j0 выбирается по наибольшему значению (CP)j > 0. В нашем случае это (CP)2 = 3, следовательно, j0 = 2. Направляющая строка с индексом i0 выбирается по правилу

 

.

 

Согласно этому правилу, среди всех отношений типа где xib – базисные переменные (их численные значения содержатся в столбце b), - положительные элементы направляющего столбца, выбирается наименьшее отношение с индексом i0. В нашем случае – это строка с индексом i0 = 5. Если в направляющем столбце положительных элементов нет, задача не имеет решения из-за неограниченности целевой функции.

Выбору направляющей строки и направляющего столбца с индексами i0 и j0 соответственно соответствует исключение из базисного решения переменной и включение вместо нее переменную , причем, новой переменной в базисе присваивается значение

 

l0 = .

 

В текущей таблице элемент называется ведущим элементом и отмечается кружком.