Xreferat.com » Рефераты по математике » Построение экономической модели с использованием симплекс-метода

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

В противном случае осуществляется переход к шагу 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.

1. Новое Z уравнение.

старое Z уравнение : ( 1 -1 -25 0 0 0 )

 ( ( -25 ) * ( 0 -1/2 1 0 1/2 0 )

   ( 1 -131/2 0 0 121/2 0 )

Новое S1 уравнение

старое S1 уравнение : ( 0 5 100 1 0 1000 )

  ( 100 ) * ( 0 -1/2 1 0 1/2 0 )

    ( 0 55 0 1 -50 1000 )

Новая симплекс-таблица будет иметь вид :

Базисные переменные Z X1 X2 S1 S2 Решение
Z 1 -131/2 0 0 121/2 0 Z – уравнение
S1 0 55 0 1 -50 1000 S1 –уравнение
X2 0 -1/2 1 0 1/2 0 X2 – уравнение

В новом решении X1 = 0 и S2 = 0. Значение Z не изменяется.

Заметим, что новая симплекс-таблица обладает такими же характеристиками, как и предыдущая : только небазисные переменные X1 и S2 равны нулю, а значения базисных переменных, как и раньше, представлены в столбце « Решение ». Это в точности соответствует результатам, получаемым при использовании метода Гаусса—Жордана.

Из последней таблицы следует, что на очередной итерации в соответствии с условием оптимальности в качестве вводимой переменной следует выбрать X1, так как коэффициент при этой переменной в

Z-ypaвнении равен -131/2. Исходя из условия допустимости, определяем, что исключаемой переменной будет S1. Отношения, фигурирующие в правой части таблицы, показывают, что в новом базисном решении значение включаемой переменной X1 будет равно 1000/55 ( = минимальному отношению ). Это приводит к увеличению целевой функции на ( 1000/55 ) * ( -131/2 ) = ( 2455/11 ).

К получению симплекс-таблицы, соответствующей новой итерации, приводят следующие вычислительные операции метода Гаусса—Жордана.

Новое ведущее S1 уравнение = Предыдущее S1 уравнение / ( 55 ).

Базисные переменные Z X1 X2 S1 S2 Решение
Z
S1 0 1 0 1/55 50/55 1000/55
X2

2) Новое Z уравнение = Предыдущее Z уравнение ( -131/2 ) * Новое /ведущее уравнение :

    ( 1 -131/2 0 0 121/2 0 )

 ( -131/2 ) * ( 0 1 0 1/55 -50/55 1000/55 )

    ( 1 0 0 27/110 5/22 2455/11 )

3) Новое X2 уравнение = Предыдущее X2 уравнение ( -1/2 ) * Новое ведущее уравнение :

    ( 0 -1/2 1 0 1/2 0 )

  ( 1/2 ) * ( 0 1 0 1/55 -50/55 1000/55 )

    ( 0 0 1 1/110 1/22 91/11 )

В результате указанных преобразований получим следующую симплекс-таблицу.

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: