Рефераты | Рефераты по математике | Построение экономической модели с использованием симплекс-метода |
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 Рекомендуем скачать другие рефераты по теме: мировая война реферат, конспект урока 3. Предыдущая страница реферата | 1 2 3 4 5 6 7 8 9 10 11 | Следующая страница реферата Поделитесь этой записью или добавьте в закладкиКатегории: |
