Эта таблица интерпретируется следующим образом. Столбец « Базисные переменные » содержит переменные пробного базиса 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.
|
Главная