Быстрый поиск

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

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

2. Новое 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 ) .

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

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