Построение экономической модели с использованием симплекс-метода
S2,
X2
S1,
X1
В
S1 , X2
S2 , X1
Применяя аналогичную процедуру ко всем
экстремальным точкам
рис. 1 , можно убедиться в том, что любую
последующую экстре-
мальную точку всегда можно определить путем взаимной замены
по одной переменной в составе базисных и небазисных переменных
( предыдущей смежной точки ) . Этот фактор существенно упрощает
реализацию вычислительных процедур симплекс-метода.
Рассмотренный процесс
взаимной замены переменных приводит
к необходимости введения двух новых терминов.
Включаемой пе-
ременной называется небазисная в данный момент переменная ,
которая будет включена в множество базисных переменных на сле-
дующей итерации ( при переходе к смежной экстремальной точке ) .
Исключаемая переменная — это та базисная переменная , которая
на следующей итерации подлежит исключению из множества ба-
зисных переменных .
Вычислительные
процедуры симплекс-метода .
симплекс-алгоритм состоит из следующих шагов.
Шаг 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 .
Главная