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

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

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

В канонической форме задача ЛП

разобьем вектор Х на два – Х _I и Х_II, таких что вектор Х_II соответствует начальному базису В, т.е. является начальным допустимым решением. Вектор С также разобьем на два вектора С _I и С_II в соответствии с векторами Х _I и Х_II. Тогда стандартную задачу ЛП можно записать следующим образом:

Для любой симплексной итерации будем обозначать через Х_В базисный вектор переменных, а через С_В – вектор коэффициентов целевой функции, соответствующих этому базису. Поскольку все небазисные переменные равны нулю, каноническая задача ЛП будет сведена к задаче с целевой функцией z=C _BX_B и ограничениями BX_B =b, где текущее решение удовлетворяет следующему уравнению:

Симплекс таблица получается из исходной задачи ЛП путем вычислений по следующей формуле:

Выполнив вычисления по этой формуле, получаем симплекс-таблицу:

Базис	ХI	XII	Решение
z	CBB-1A-CI	CBB-1-CII	CBB-1b
XB	B-1A	B-1	B-1b

В этой таблице предварительных вычислений требует только обратная матрица B ^-1, так как другие элементы таблицы C_B, C_I, C_II, A и b получаются из исходных данных задачи.

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

В симплекс-методе решение переходит от одного базиса В к следующему В_след путем замены в В базисного вектора (исключаемого) на небазисный (вводимый). Определение вводимых и исключаемых векторов основано на следующих условиях оптимальности и допустимости.

Условие оптимальности симплекс-метода

Из матричного представления симплекс-таблицы следует, что коэффициент при переменной x _j в z -строке равен

где P _j - j -й столбец матрицы (А,I), c _j – j -й элемент вектора С. Отметим, что разность  всегда равна нулю для базисных переменных x _j. Если обозначить через NB множество индексов небазисных переменных, тогда можно записать следующее уравнение для целевой функции

Из этого уравнения следует, увеличение значения небазисной переменной х_j приводит к возрастанию (убыванию) значения целевой функции z выше текущего значения C _BB ^-1b только в том случае, если разность строго отрицательна (положительна). В противном случае переменная х_j не может улучшить текущее решение и должна остаться небазисной с нулевым значением.

Условие допустимости симплекс-метода

Определение исключаемого из базиса вектора основано на проверке ограничения, представленного в виде равенства, соответствующего i -й базисной переменной. Это равенство имеет следующий вид:

Запись (V) _i означает i -й элемент вектор-столбца V.

Обозначим через P_k вводимый вектор, определенный из условия оптимальности, а через х _k – вводимую в базис переменную, принимающую положительное значение. Поскольку все остальные небазисные переменные сохраняют нулевые значения, равенство ограничения, соответствующего базисной переменной , можно записать следующим образом:

Это уравнение показывает, что при возрастание переменной х _k не приведет к отрицательному значению базисной переменной только в том случае, если будет выполняться неравенство

Таким образом, максимальное значение вводимой переменной х _k можно вычислить по следующей формуле:

Базисная переменная, на которой достигается этот минимум, становится исключаемой.

Пример 1.1 Проиллюстрируем матричное представление симплекс-метода.

Пусть B=(P₁, P ₄, P ₅, P ₆) является допустимым базисом.

a) Покажем, что решение B не является оптимальным.

b) Найдем вводимый в базис и исключаемый из него векторы и B_след.

На основании B=(P₁, P ₄, P ₅, P ₆) имеем X _B =(x ₁, s ₂, s ₃, s ₄) и С _B =(5, 0, 0, 0). Вычисляем обратную матрицу B^-1

Находим текущее базисное решение

откуда получаем z=C_BX_B =5*4+0*2+0*5+0*2=20.

Аналогично получим коэффициенты в ограничениях после первой итерации при х₁ и х₂

Для проверки оптимальности базиса B=(P₁, P ₄, P ₅, P ₆) вычислим разности для текущих небазисных переменных х₂ и s₁:

(z₂-c₂, z₃-c₃)=C_BB^-1[P₂, P₃]- (c₂, c₃)=

Легко видеть, что все коэффициенты совпадают с коэффициентами в задаче ЛП из примера 1.1 после первой итерации симплекс-метода.

 

Базис	z	x1	x2	s1	s2	s3	s4	Решение
z	1	0	-2/3	5/6	0	0	0	20
х 1	0	1	2/3	1/6	0	0	0	4
s2	0	0	4/3	-1/6	1	0	0	2
s3	0	0	5/3	1/6	0	1	0	5
s4	0	0	1	0	0	0	1	2

Поскольку в данной задаче следует максимизировать целевую функцию, разность z₂– c ₂ =-2/3 показывает, что базис X _B =(x ₁, s ₂, s ₃, s ₄) неоптимален и значение целевой функции можно увеличить, если ввести переменную x ₂.

Для того чтобы ввести в базис переменную х₂, из него нужно исключить одну из четырех базисных переменных. Для определения исключаемой переменной вычисляем X _B и B^-1P₂.

Значение вводимой переменной х₂ равно

Таким образом, в базисе X _B =(x ₁, s ₂, s ₃, s ₄) вектор P₄ будет заменен на P ₂, что приводит к новому базису

.

Соответствующее новое значение целевой функции равно z =20-(-2/3)*3/2=21.

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

Анализ чувствительности

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

В общем случае изменение коэффициентов исходной задачи может привести к одной из следующих ситуаций:

1 Текущее базисное решение остается неизменным.

2 Текущее решение становится недопустимым.

3 Текущее решение становится неоптимальным.

4 Текущее решение становится неоптимальным и недопустимым.

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

Для объяснения различных процедур анализа чувствительности используем пример 1.1 производства краски.

Исходная задача	Двойственная задача

Приведем также последнюю симплекс-таблицу этого примера.

Базис	z	x1	x2	s1	s2	s3	s4	Решение
z	1	0	0	3/4	1/2	0	0	21
х 1	0	1	0	1/4	-1/2	0	0	3
х 2	0	0	1	-1/8	3/4	0	0	3/2
s3	0	0	0	3/8	-5/4	1	0	5/2
s4	0	0	0	1/8	-3/4	0	1	1/2