|  Построение экономической модели с использованием симплекс-метода |
Свойство однозначности экстремальных точек
позволяет опре-
делить их алгебраическим методом. Будем считать , что линейная
модель стандартной формы содержит т уравнений и п ( т <= п ) не-
известных ( правые части ограничений — неотрицательные ) . Тогда
все допустимые экстремальные точки определяются как все
одно-
значные неотрицательные решения системы m уравнений , в ко-
торых п — m переменных равны нулю.
Однозначные решения такой системы уравнений,
получаемые
путем приравнивания к
нулю ( п — т ) переменных , называются
базисными решениями . Если базисное решение
удовлетворяет
требованию неотрицательности правых частей , оно называется
допустимым базисным решением. Переменные ,
имеющие нулевое
значение , называются
небазисными переменными , остальные —
базисными переменными.
Из вышеизложенного
следует , что при реализации симплекс-
метода алгебраическое определение базисных решений соответст-
вует идентификации
экстремальных точек , осуществляемой при
геометрическом представлении пространства решений .
Таким об-
разом , максимальное число итераций при использовании симплекс-
метода равно максимальному числу базисных решений задачи ЛП ,
представленной в
стандартной форме . Это означает , что количество
итерационных процедур симплекс-метода не превышает
Cпт= n! / [ ( n - m )!m! ]
Вторая из ранее
отмеченных закономерностей
оказывается
весьма полезной для построения
вычислительных процедур симп-
лекс-метода , при реализации которого осуществляется
последова-
тельный переход от одной экстремальной точки к другой, смежной с
ней . Так как смежные экстремальные точки отличаются только
одной переменной,
можно определить каждую последующую ( смеж-
ную) экстремальную точку путем замены одной из текущих не-
базисных ( нулевых ) переменных текущей базисной
переменной.
В нашем случае получено решение , соответствующее точке А , откуда
следует осуществить переход в точку В . Для этого нужно увеличивать небазисную переменную X2 от исходного нулевого значения до значе-
ния , соответствующего точке В ( см. рис. 1
). В точке B
переменная
S1 ( которая в точке А была базисной ) автоматически
обращается в
нуль и , следовательно , становится небазисной переменной
. Таким
образом , между множеством небазисных и множеством базисных
переменных происходит взаимообмен переменными X2 и
S1 . Этот
процесс можно наглядно представить в виде следующей таблицы.
|
|
Экстремальная точка
|
Нулевые переменные
|
Ненулевые переменные
|
|
А
|
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 имеют
нулевое значение . Поэтому , преобразовав уравнение целевой функции так , чтобы
его правая часть стала равной нулю , можно убедиться в том , что правые части
уравнений целевой функции и ограничений полностью характеризуют начальное
решение . Это имеет место во всех случаях , когда
начальный базис состоит из остаточных переменных.
Полученные результаты удобно
представить в виде таблицы :
|
Знание — сила. Библиотека научных работ.
Наверх