05. Вычислительные процедуры симплекс-метода

симплекс-алгоритм состоит из следующих шагов.

Шаг 0. Используя линейную модель стандартной формы, определяют начальное допустимое базисное решение путем приравнивания к нулю П — т (небазисных) переменных.

Шаг 1. Из числа текущих небазисных (равных нулю) переменных выбирается включаемая в новый базис переменная, увеличение которой обеспечивает улучшение значения целевой функции. Если такой переменной нет, вычисления прекращаются, так как текущее базисное решение оптимально. В противном случае осуществляется переход к шагу 2.

Шаг 2. Из числа переменных текущего базиса выбирается исключаемая переменная, которая должна принять нулевое значение (стать небазисной) при введении в состав базисных новой переменной.

Шаг 3. Находится новое базисное решение, соответствующее новым составам небазисных и базисных переменных. Осуществляется переход к шагу 1.

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

Z - X1 - 25X2 +0S1 -0S2 = 0 (Целевая функция)

5X1 + 100X2 + S1 = 1000 (Ограничение)

-X1 + 2X2 + S2 = 0 (Ограничение)

Как отмечалось ранее, в качестве начального пробного решения используется решение системы уравнений, в которой две переменные принимаются равными нулю. Это обеспечивает Единственность и Допустимость получаемого решения. В рассматриваемом случае очевидно, что подстановка X1 = X2 = 0 сразу же приводит к следующему результату: S1 = 1000, S2 = 0 (т. е. решению, соответствующему точке А на рис. 1). Поэтому точку А можно использовать как начальное допустимое решение. Величина Z в этой точке равна нулю, так как и X1 и X2 имеют нулевое значение. Поэтому, преобразовав уравнение целевой функции так, чтобы его правая часть стала равной нулю, можно убедиться в том, что правые части уравнений целевой функции и ограничений полностью характеризуют начальное решение. Это имеет место во всех случаях, когда начальный базис состоит из Остаточных переменных.

Полученные результаты удобно представить в виде таблицы:

Базисные переменные	Z	X1	X2	S1	S2	Решение
Z	1	-1	- 25	0	0	0	Z - уравнение
S1	0	5	100	1	0	1000	S1 - уравнение
S2	0	-1	2	0	1	0	S2 - уравнение

Эта таблица интерпретируется следующим образом. Столбец “Базисные переменные” содержит переменные пробного базиса S1, S2, значения которых приведены в столбце “Решение”. При этом подразумевается, что небазисные переменные X1 и X2 (не представленные в первом столбце) равны нулю. Значение целевой функции

Z = 1*0 + 25*0 + 0*1000 + 0*1 равно нулю, что и показано в последнем столбце таблицы.

Определим, является ли полученное пробное решение наилучшим (оптимальным). Анализируя Z - уравнение, нетрудно заметить, что обе небазисные переменные X1 и X2, равные нулю, имеют Отрицательные коэффициенты. Всегда выбирается переменная с большим абсолютным значением отрицательного коэффициента, так как практический опыт вычислений показывает, что в этом случае оптимум достигается быстрее.

Это правило составляет основу используемого в вычислительной схеме симплекс-метода условия оптимальности, которое состоит в том, что, если в задаче максимизации Все небазисные переменные в Z - имеют Неотрицательные коэффициенты, полученное пробное решение является оптимальным. В противном случае в качестве новой базисной переменной следует выбрать ту, которая имеет наибольший по абсолютной величине отрицательный коэффициент. Применяя условие оптимальности к исходной таблице, выберем в качестве переменной, включаемой в базис, переменную Х2. Исключаемая переменная должна быть выбрана из совокупности базисных переменных S1 , S2 . Процедура выбора исключаемой переменной предполагает проверку Условия допустимости, требующего, чтобы в качестве исключаемой переменной выбиралась та из переменных текущего базиса, которая первой обращается в нуль при увеличении включаемой переменной X2 вплоть до значения, соответствующего смежной экстремальной точке.

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

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

После того как определены включаемая и исключаемая переменные (с использованием Условий оптимальности и Допустимости), Следующая итерация (поиск нового базисного решения) осуществляется методом исключения переменных, или методом Гаусса — Жордана. Этот процесс изменения базиса включает вычислительные процедуры двух типов.

Тип 1 (формирование ведущего уравнения).

Новая ведущая строка = Предыдущая ведущая строка / Ведущий элемент

Тип 2 (формирование всех остальных уравнений, включая Z - уравнение).

Новое уравнение = Предыдущее уравнение —

┌ ┐

│Коэффициент │

│ведущего столбца │*(Новая ведущая строка).

│предыдущего │

│уравнения │

└ ┘

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

Базисные переменные	Z	X1	X2	S1	S2	Решение
Z
S1
S2	0	-1/2	1	0	1/2	0

Чтобы составить новую симплекс-таблицу, выполним необходимые вычислительные процедуры типа 2 .

1. Новое Z - уравнение.

Старое Z - уравнение: (1 -1 -25 0 0 0)

(- (-25) * (0 -1/2 1 0 1/2 0)

(1 -131/2 0 0 121/2 0)

2. Новое S1 - уравнение

старое S1 - уравнение: (0 5 100 1 0 1000)

( - 100) * (0 -1/2 1 0 1/2 0)

( 0 55 0 1 -50 1000)

Новая симплекс-таблица будет иметь вид:

Базисные переменные	Z	X1	X2	S1	S2	Решение
Z	1	-131/2	0	0	121/2	0	Z - уравнение
S1	0	55	0	1	-50	1000	S1 - уравнение
X2	0	-1/2	1	0	1/2	0	X2 - уравнение

В новом решении X1 = 0 и S2 = 0 . Значение Z не изменяется.

Заметим, что новая симплекс-таблица обладает такими же характеристиками, как и предыдущая: только небазисные переменные X1 и S2 равны нулю, а значения базисных переменных, как и раньше, представлены в столбце “ Решение ”. Это в точности соответствует результатам, получаемым при использовании метода Гаусса—Жордана.

Из последней таблицы следует, что на очередной итерации в соответствии с условием оптимальности в качестве вводимой переменной следует выбрать X1 ,так как коэффициент при этой переменной в Z - уравнений равен -131/2 . Исходя из условия, определяем, что исключаемой переменной будет S1. Отношения, фигурирующие в правой части таблицы, показывают, что в новом базисном решении значение включаемой переменной X1 будет равно 1000/55 ( = минимальному отношению). Это приводит к увеличению целевой функции на ( 1000/55 ) * ( -131/2 ) = ( 2455/11 ) .

К получению симплекс-таблицы, соответствующей новой итерации, приводят следующие вычислительные операции метода Гаусса—Жордана.

1) Новое ведущее S1 - уравнение = Предыдущее S1 - уравнение / (55) .

Базисные переменные	Z	X1	X2	S1	S2	Решение
Z
S1	0	1	0	1/55	- 50/55	1000/55
X2

2) Новое Z - новое = Предыдущее Z - уравнение - (-131/2) * Новое /ведущее уравнение:

( 1 -131/2 0 0 121/2 0)

- ( -131/2) * (0 1 0 1/55 -50/55 1000/55)

( 1 0 0 27/110 5/22 2455/11)

3) Новое X2 - уравнение = Предыдущее X2 - уравнение - (-1/2) * Новое ведущее уравнение:

( 0 -1/2 1 0 1/2 0)

- ( - 1/2) * (0 1 0 1/55 -50/55 1000/55)

( 0 0 1 1/110 1/22 91/11)

В результате указанных преобразований получим следующую симплекс-таблицу.

Базисные переменные	Z	X1	X2	S1	S2	Решение
Z	1	0	0	27/110	5/22	2455/11
X1	0	1	0	1/55	-50/55	1000/55
X2	0	0	1	1/110	1/22	91/11

В новом базисном решении X1=1000/55 и X2=91/11 . Значение Z увеличилось с 0 (предыдущая симплекс-таблица) до 2455/11 (последняя симплекс-таблица). Этот результирующий прирост целевой функции обусловлен увеличением X1 от О до 1000/55 , так как из Z - строки предыдущей симплекс-таблицы следует, что возрастанию данной переменной на единицу соответствует увеличение целевой функции на( -131/2 ) .

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

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

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

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

< Предыдущая		Следующая >