Симплекс-таблицы.

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

Рассмотрим следующую задачу линейного программирования:

задача линейного программирования(1)

Если в условии задачи есть ограничения со знаком ≥, то их можно привести к виду ∑ajibj, умножив обе части неравенства на -1. Введем m дополнительных переменных xn+j≥0(j =1,m) и преобразуем ограничения к виду равенств

 ограничения в виде равенств для задачи линейного программирования(2)

Предположим, что все исходные переменные задачи x1, x2,..., xn – небазисные. Тогда дополнительные переменные будут базисными, и частное решение системы ограничений имеет вид

x1 = x2 = ... = xn = 0, xn+ j = bj , j =1,m. (3)

Так как при этом значение функции цели F0 = 0 , можно представить F(x) следующим образом:

F(x)=∑cixi+F0=0 (4)

Начальная симплекс-таблица (симплекс-табл. 1) составляется на основании уравнений (2) и (4). Если перед дополнительными переменными xn+j стоит знак «+», как в (2), то все коэффициенты перед переменными xi и свободный член bj заносятся в симплекс-таблицу без изменения. Коэффициенты функции цели при ее максимизации заносятся в нижнюю строку симплекс-таблицы с противоположными знаками. Свободные члены в симплекс-таблице определяют решение задачи.

Алгоритм решения задачи следующий:

1-й шаг. Просматриваются элементы столбца свободных членов. Если все они положительные, то допустимое базисное решение найдено и следует перейти к шагу 5 алгоритма, соответствующему нахождению оптимального решения. Если в начальной симплекс-таблице есть отрицательные свободные члены, то решение не является допустимым и следует перейти к шагу 2.

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

Таблица 1.

базисные переменные Свободные члены в ограничениях Небазисные переменные
x1 x2 ... xl ... xn
xn+1 b1 a11 a12 ... a1l ... a1n
xn+2 b2 a21 a22 ... a2l ... a2n
. . . . . . . .
. . . . . . . .
. . . . . . . .
xn+r b2 ar1 ar2 ... arl ... arn
. . . . . . . .
. . . . . . . .
. . . . . . . .
xn+m bm am1 am2 ... aml ... amn
F(x)max F0 -c1 -c2 ... -c1 ... -cn

Для этого выбирают любой из отрицательных элементов столбца свободных членов (пусть это будет b2 < 0 ) и просматривают элементы строки, в которой он находится. В этой строке выбирают любой отрицательный элемент и соответствующий ему столбец определит переменную (например xl ), которую следует исключить из небазисных и ввести в базис на следующем шаге. Столбец, соответствующий переменной xl , называется ведущим, или разрешающим. Если в строке с отрицательным свободным членом нет отрицательных элементов, то система ограничений несовместна и задача не имеет решения.

Одновременно из БП исключается та переменная, которая первой изменит знак при увеличении выбранной НП xl . Это будет xn+r , индекс r которой определяется из условия

условие

т.е. та переменная, которой соответствует наименьшее отношение свободного члена к элементу выбранного ведущего столбца. Это отношение называется симплексным отношением. Следует рассматривать только положительные симплексные отношения.

Строка, соответствующая переменной xn+r , называется ведущей, или разрешающей. Элемент симплекс-таблицы arl , стоящий на пересечении ведущей строки и ведущего столбца, называется ведущим, или разрешающим элементом. Нахождением ведущего элемента заканчивается работа с каждой очередной симплекс-таблицей.

3-й шаг. Рассчитывается новая симплекс-таблица, элементы которой пересчитываются из элементов симплекс-таблицы предыдущего шага и помечаются штрихом, т.е. b'j , a'ji , c'i , F'0. Пересчет элементов производится по следующим формулам:

формулы для пересчета симплекс-таблицы

Сначала в новой симплекс-таблице заполнятся строка и столбец, которые в предыдущей симплекс-таблице были ведущими. Выражение (5) означает, что элемент a'rl на месте ведущего равен обратной величине элемента предыдущей симплекс-таблицы. Элементы строки ari делятся на ведущий элемент, а элементы столбца ajl также делятся на ведущий элемент, но берутся с противоположным знаком. Элементы b'r и c'l рассчитываются по тому же принципу.

Остальные формулы легко записать с помощью правила прямоугольника.

Прямоугольник строится по старой симплекс-таблице таким образом, что одну из его диагоналей образует пересчитываемый (aji ) и ведущий (arl ) элементы (рис. 1). Вторая диагональ определяется однозначно. Для нахождения нового элемента a'ji из элемента aji вычитается (на это указывает знак « – » у клетки) произведение элементов противоположной диагонали, деленное на ведущий элемент. Аналогично пересчитываются элементы b'j , ( j≠r) и c'i, (i≠l).

4-й шаг. Анализ новой симплекс-таблицы начинается с 1-го шага алгоритма. Действие продолжается, пока не будет найдено допустимое базисное решение, т.е. все элементы столбца свободных членов должны быть положительными.

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

правило прямоугольника

Рис. 1. Правило прямоугольника

 

Если среди коэффициентов F-строки имеются отрицательные (за исключением свободного члена), то нужно переходить к другому базисному решению. При максимизации функции цели в базис включается та из небазисных переменных (например xl ), столбцу которой соответствует максимальное абсолютное значение отрицательного коэффициента cl в нижней строке симплекс-таблицы. Это позволяет выбрать ту переменную, увеличение которой приводит к улучшению функции цели. Столбец, соответствующий переменной xl , называется ведущим. Одновременно из базиса исключается та переменная xn+r , индекс r которой определяется минимальным симплексным отношением:

минимальное симплексное отношение

Строка, соответствующая xn+r , называется ведущей, а элемент симплекс-таблицы arl , стоящий на пересечении ведущей строки и ведущего столбца, называется ведущим элементом.

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

Если в процессе оптимизации решения в ведущем столбце все элементы неположительные, то ведущую строку выбрать невозможно. В этом случае функция в области допустимых решений задачи не ограничена сверху и Fmax->&∞.

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

Пример 1. Решить задачу

max{F(x) = -2x1 + 5x2 | 2x1 + x2≤7; x1 + 4x2≥8; x2≤4; x1,2≥0}

симплексным методом и дать геометрическую интерпретацию процесса решения.

Графическая интерпретация решения задачи представлена на рис. 2. Максимальное значение функции цели достигается в вершине ОДЗП с координатами [0,4]. Решим задачу с помощью симплекс-таблиц. Умножим второе ограничение на (-1) и введём дополнительные переменные, чтобы неравенства привести к виду равенств, тогда

ограничения задачи для симплекс-метода

Исходные переменные x1 и x2 принимаем в качестве небазисных, а дополнительные x3 , x4 и x5 считаем базисными и составляем симплекс-таблицу(симплекс-табл. 2). Решение, соответствующее симплекс-табл. 2, не является допустимым; ведущий элемент обведен контуром и выбран в соответствии с шагом 2 приведенного ранее алгоритма. Следующая симплекс-табл. 3 определяет допустимое базисное решение, ему соответствует вершина ОДЗП [0,2] на рис. 2 Ведущий элемент обведен контуром и выбран в соответствии с 5-м шагом алгоритма решения задачи. Табл. 4 соответствует оптимальному решению задачи, следовательно:

x1 = x5 = 0; x2 = 4; x3 = 3; x4 = 8; Fmax = 20.

решение с помощью семплекс-таблиц

графическая интерпретация решения с помощью семплекс-таблиц

Рис. 2. Графическое решение задачи

ДОБАВИТЬ КОММЕНТАРИЙ