 Построение экономической модели с использованием симплекс-метода |
|
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 .
| 
Знание — сила. Библиотека научных работ.
Наверх