Реферат: Построение экономической модели c использованием симплекс-метода
Определим , является ли
полученное пробное решение наи-
лучшим ( оптимальным ) . Анализируя 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 )
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 ) .
| Базисные переменные | 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 )
В
результате указанных преобразований получим следующую симп-
лекс-таблицу .
| Базисные переменные | Z | X1 | X2 | S1 | S2 | Решение |
| Z | 1 | 0 | 0 |
27/110 |
5/22 |
2455/11 |
| X1 | 0 | 1 | 0 |
1/55 |
-50/55 |
1000/55 |
| X2 | 0 | 0 | 1 |
1/110 |
1/22 |
91/11 |
В новом базисном решении X1=1000/55 и X2=91/11 . Значение Z увеличилось с 0 ( предыдущая симплекс-таблица ) до 2455/11 ( последняя симплекс-таблица ) . Этот результирующий прирост целевой функции обусловлен увеличением X1 от О до 1000/55 , так как из Z - строки предыдущей симплекс-таблицы следует , что возрастанию данной переменной на единицу соответствует увеличение целевой функции на( -131/2 ) .
Последняя
симплекс-таблица соответствует оптимальному реше-
нию задачи, так как в Z - уравнении ни одна из небазисных переменных не фигурирует с
отрицательным коэффициентом. Получением этой pезультирующей таблицы и завершаются
вычислительные процедуры симплекс-метода .
В рассмотренном выше
примере алгоритм симплекс-метода ис-
пользован при решении задачи , в которой целевая функция подлежала максимизации
. В случае минимизации целевой функции в этом
алгоритме необходимо изменить только условие оптимальности :
в качестве новой базисной переменнойследует выбирать ту переменную , которая в Z - уравнении
имеет наибольший положительный коэффициент .
Условия допустимости в обоих случаях ( максимизации и минимизации ) одинаковы . Представляется целесообразным дать теперь окончательные формулировки обоим условиям , используемым в
симплекс-методе .
Условие оптимальности . Вводимой переменной в задаче максимизации ( минимизации ) является небазисная переменная , имеющая в Z -уравнении наибольший отрицательный ( положительный ) коэффициент , В случае равенства таких коэффициентов для нескольких небазисных переменных выбор делается произвольно , если все коэффициенты при небазисных переменных в Z - уравнении неотрицательны (неположительны) , полученное решение является оптимальным .
Условие допустимости , в задачах максимизации и минимизации в качестве исключаемой переменной выбирается та базисная переменная , для которой отношение постоянной в правой части соответствующего ограничения к ( положительному ) коэффициенту ведущего столбца минимально. В случае равенства этого отношения для нескольких базисных переменных выбор делается произвольно .
Оптимальное решение
С
точки зрения практического использования результатов ре-
шения задач ЛП классификация переменных , предусматривающая
их разделение на базисные и небазнсные , не имеет значения и при
анализе данных , характеризующих оптимальное решение , может
не учитываться . Переменные , отсутствующие в столбце « Базисные
переменные » , обязательно имеют нулевое значение . Значения ос-
тальных переменных приводятся в столбце « Решение » . При интер-
претации результатов оптимизации в нашей задаче нас прежде всего интересует
количество времени , которое закажет наша фирма на радио и телевидение , т. е. значения управляемых переменных X1 и X2 . Используя данные , содержащиеся в
симплекс-таблице для оптимального решения , основные результаты можно
представить в следующем виде :
| Управляемые переменные | Оптимальные значения | Решение |
|
X1 |
1000/55 |
Время выделяемое фирмой на телерекламу |
|
X2 |
91/11 |
Время выделяемое фирмой на радиорекламу |
| Z |
2455/11 |
Прибыль получаемая от рекламы . |
Заметим, что Z = X1 + 25X2 = 1000/55 + 25 * 91/11 = 2455/11 . Это решение соответствует данным заключительной симплекс-таблицы .
Статус ресурсов
Будем
относить ресурсы к дефицитным или недифицитным в зависимости от
того , полное или частичное их использо-
вание предусматривает оптимальное решение задачи . Сейчас цель
состоит в том , чтобы получить соответствующую информацию непос-
редственно из симплекс-таблицы для оптимального решения . Од-
нако сначала следует четко уяснить следующее . Говоря о ресурсах ,
фигурирующих в задаче ЛП , мы подразумеваем , что установлены
некоторые максимальные пределы их запасов , поэтому в соответст-
вующих исходных ограничениях должен использоваться знак <= .
Следовательно , ограничения со знаком => не могут рассматриваться
как ограничения на ресурсы . Скорее , ограничения такого типа отра-
жают то обстоятельство , что решение должно удовлетворять
опре-
деленным требованиям , например обеспечению минимального
спро-
са или минимальных отклонений от установленных структурных
характеристик производства ( сбыта ) .
