|
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
Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15
При использовании материалов активная ссылка на источник обязательна.