симплекс-алгоритм состоит из следующих шагов.
Шаг 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 - уравнении ) , так как практический опыт вычислений показывает, что в этом случае оптимум достигается быстрее.
Это правило составляет основу используемого в вычислительной
схеме симплекс-метода условия оптимальности, которое состоит в
том, что, если в задаче максимизации все небазисные переменные в
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 )
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-ypaвнении равен -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/551000/55 )