Реферат: Построение экономической модели c использованием симплекс-метода

Cпт= n! / [ ( n - m )!m! ]     

Вторая из ранее отмеченных закономерностей оказывается
весьма полезной для построения вычислительных процедур симп-
лекс-метода , при реализации которого осуществляется последова-
тельный переход от одной экстремальной точки к другой, смежной с ней . Так как смежные экстремальные точки отличаются только
одной переменной, можно определить каждую последующую ( смеж-
ную) экстремальную точку путем замены одной из текущих не-
базисных ( нулевых ) переменных текущей базисной переменной.
В нашем случае получено решение , соответствующее точке А , откуда следует осуществить переход в точку В . Для этого нужно увеличивать небазисную переменную X2 от исходного нулевого значения до значе-
ния , соответствующего точке В ( см. рис. 1 ). В точке B переменная
S1 ( которая в точке А была базисной ) автоматически обращается в
нуль и , следовательно , становится небазисной переменной . Таким
образом , между множеством небазисных и множеством базисных
переменных происходит взаимообмен переменными X2 и S1 . Этот
процесс можно наглядно представить в виде следующей таблицы.

Применяя аналогичную процедуру ко всем экстремальным точкам
рис. 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  имеют нулевое значение . Поэтому , преобразовав уравнение целевой функции так , чтобы его правая часть стала равной нулю , можно убедиться в том , что правые части уравнений целевой функции и ограничений полностью характеризуют начальное решение . Это имеет место во всех случаях , когда начальный базис состоит из остаточных переменных.            

Полученные результаты удобно представить в виде таблицы :

Эта таблица интерпретируется следующим образом. Столбец
« Базисные переменные » содержит переменные пробного базиса S1 ,
S2 ,  значения которых приведены в столбце « Решение » . При
этом подразумевается , что небазисные переменные X1 и X2 ( не пред-
ставленные в первом столбце ) равны нулю . Значение целевой функ-
ции Z = 1*0 + 25*0 + 0*1000 + 0*1  равно нулю , что и показано в последнем столбце таблицы .

 Определим , является ли полученное пробное решение наи-
лучшим ( оптимальным ) . Анализируя Z - уравнение , нетрудно заме-
тить , что обе небазисные переменные X1 и X2 , равные нулю , имеют
отрицательные коэффициенты . Всегда выбирается переменная с большим абсолютным значением отрицательного коэффициента ( в Z - уравнении ) , так как практический опыт вычислений показывает , что в этом случае оптимум достигается быстрее .

Это правило составляет основу используемого в вычислительной
схеме симплекс-метода условия оптимальности , которое состоит в
том , что , если в задаче максимизации все небазисные переменные в
Z - Уравнение имеют неотрицательные коэффициенты , полученное пробное решение является оптимальным . В противном случае в ка-
честве новой базисной переменной следует выбрать ту , которая имеет
наибольший по абсолютной величине отрицательный коэффициент .

Применяя условие оптимальности к исходной таблице , выберем
в качестве переменной , включаемой в базис , переменную Х2 . Исклю-
чаемая переменная должна быть выбрана из совокупности базисных
переменных S1 , S2 . Процедура выбора исключаемой переменной предполагает проверку условия допустимости , требующего , чтобы в качестве исключаемой переменной выбиралась та из пере-
менных текущего базиса , которая первой обращается в нуль при уве-
личении включаемой переменной X2 вплоть до значения , соответствующего смежной экстремальной точке .

Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10