Полученные результаты удобно представить в виде таблицы :
| Базисные переменные | 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 уравнении ), так как практический опыт вычислений показывает, что в этом случае оптимум достигается быстрее.
Это правило составляет основу используемого в вычислительной схеме симплекс-метода условия оптимальности, которое состоит в том, что, если в задаче максимизации все небазисные переменные в Z уравнении имеют неотрицательные коэффициенты, полученное пробное решение является оптимальным. В противном случае в качестве новой базисной переменной следует выбрать ту, которая имеет наибольший по абсолютной величине отрицательный коэффициент.
Применяя условие оптимальности к исходной таблице, выберем в качестве переменной, включаемой в базис, переменную Х2. Исключаемая переменная должна быть выбрана из совокупности базисных переменных S1, S2. Процедура выбора исключаемой переменной предполагает проверку условия допустимости, требующего, чтобы в качестве исключаемой переменной выбиралась та из переменных текущего базиса, которая первой обращается в нуль при увеличении включаемой переменной X2 вплоть до значения, соответствующего смежной экстремальной точке.
Интересующее нас отношение ( фиксирующее искомую точку пе-ресечения и идентифицирующее исключаемую переменную ) можно определить из симплекс-таблицы. Для этого в столбце, соответствующем вводимой переменной X2, вычеркиваются отрицательные и нулевые элементы ограничений. Затем вычисляются отношения постоянных, фигурирующих в правых частях этих ограничений, к оставшимся элементам столбца, соответствующего вводимой переменной X2. Исключаемой переменной будет та переменная текущего базиса, для которой указанное выше отношение минимально.
Начальная симплекс-таблица для нашей задачи, получаемая после проверки условия допустимости ( т. е. после вычисления соответствующих отношений и определения исключаемой переменной ), воспроизведена ниже. Для удобства описания вычислительных процедур, осуществляемых на следующей итерации, введем ряд необходимых определений. Столбец симплекс-таблицы, ассоциированный с вводимой переменной, будем называть ведущим столбцом. Строку, соответствующую исключаемой переменной, назовем ведущей строкой ( уравнением ), а элемент таблицы, находящийся на пересечении ведущего столбца и ведущей строки, будем называть ведущим элементом.
После того как определены включаемая и исключаемая переменные ( с использованием условий оптимальности и допустимости ), следующая итерация ( поиск нового базисного решения ) осуществляется методом исключения переменных, или методом Гаусса — Жордана. Этот процесс изменения базиса включает вычислительные процедуры двух типов.
Тип 1 ( формирование ведущего уравнения ).
Новая ведущая строка = Предыдущая ведущая строка / Ведущий элемент
Тип 2 ( формирование всех остальных уравнений, включая Z yравнение ).
Новое уравнение = Предыдущее уравнение —
Коэффициент
ведущего столбца Новая ведущая строка ).
предыдущего
уравнения
Выполнение процедуры типа 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 )
Новое 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-ypaвнении равен -131/2. Исходя из условия допустимости, определяем, что исключаемой переменной будет S1. Отношения, фигурирующие в правой части таблицы, показывают, что в новом базисном решении значение включаемой переменной X1 будет равно 1000/55 ( = минимальному отношению ). Это приводит к увеличению целевой функции на ( 1000/55 ) * ( -131/2 ) = ( 2455/11 ).
К получению симплекс-таблицы, соответствующей новой итерации, приводят следующие вычислительные операции метода Гаусса—Жордана.
Новое ведущее 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 уравнении ни одна из небазисных переменных не фигурирует с отрицательным коэффициентом. Получением этой pезультирующей таблицы и завершаются вычислительные процедуры симплекс-метода.
В рассмотренном выше примере алгоритм симплекс-метода использован при решении задачи, в которой целевая функция подлежала максимизации. В случае минимизации целевой функции в этом алгоритме необходимо изменить только условие оптимальности : в качестве новой базисной переменнойследует выбирать ту переменную, которая в Z уравнении имеет наибольший положительный коэффициент. Условия допустимости в обоих случаях ( максимизации и минимизации ) одинаковы. Представляется целесообразным дать теперь окончательные формулировки обоим условиям, используемым в симплекс-методе.
Условие оптимальности. Вводимой переменной в задаче максимизации ( минимизации ) является небазисная переменная, имеющая в Z -уравнении наибольший отрицательный ( положительный ) коэффициент, В случае равенства таких коэффициентов для нескольких небазисных переменных выбор делается произвольно, если все коэффициенты при небазисных переменных в Z уравнении неотрицательны (неположительны), полученное решение является оптимальным.
Условие допустимости, в задачах максимизации и минимизации в качестве исключаемой переменной выбирается та базисная переменная, для которой отношение постоянной в правой части соответствующего ограничения к ( положительному ) коэффициенту ведущего столбца минимально. В случае равенства этого отношения для нескольких базисных переменных выбор делается произвольно.
Оптимальное решение
С точки зрения практического использования результатов решения задач ЛП классификация переменных, предусматривающая их разделение на базисные и небазнсные, не имеет значения и при анализе данных, характеризующих оптимальное решение, может не учитываться. Переменные, отсутствующие в столбце « Базисные переменные », обязательно имеют нулевое значение. Значения остальных переменных приводятся в столбце « Решение ». При интерпретации результатов оптимизации в нашей задаче нас прежде всего интересует количество времени, которое закажет наша фирма на радио и телевидение, т. е. значения управляемых переменных X1 и X2. Используя данные, содержащиеся в симплекс-таблице для оптимального решения, основные результаты можно представить в следующем виде :