Поясним процедуры симплекс-метода на примере решения нашей зада-чи . Сначала необходимо представить целевую функцию и ограничения модели в стандартной форме:
Z - X 1 - 25X 2 +0S1 -0S2 = 0 ( Целевая функция )
5X 1 + 100X 2 + S 1 = 1000 ( Ограничение )
-X 1 + 2X 2 + S 2 = 0 ( Ограничение )
Как отмечалось ранее , в качестве начального пробного решенияиспользуется решение системы уравнений , в которой две переменные принимаются равными нулю . Это обеспечивает единст-венность и допустимость получаемого решения . В рассматриваемомслучае очевидно, что подстановка X 1 = X 2 = 0 сразу же приводит к следующему результату: S 1 = 1000 , S 2 = 0 ( т. е. решению , соответствующему точке А на рис. 1 ) . Поэтому точку А можно использовать как начальное допустимое решение . Величина Z в этой точке равна нулю , так как и X 1 и X 2 имеют нулевое значение . Поэтому , преобразовав уравнение целевой функции так , чтобы его правая часть стала равной нулю , можно убедиться в том , что правые части уравнений целевой функции и ограничений полностью характеризуют начальное решение . Это имеет место во всех случаях , когда начальный базис состоит из остаточных переменных.
Полученные результаты удобно представить в виде таблицы :
|
Базисные переменные
|
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 - уравнение |
Эта таблица интерпретируется следующим образом. Столбец« Базисные переменные » содержит переменные пробного базиса S 1 ,S2 , значения которых приведены в столбце « Решение » . Приэтом подразумевается , что небазисные переменные X 1 и X 2 ( не пред-ставленные в первом столбце ) равны нулю . Значение целевой функ-ции Z = 1*0 + 25*0 + 0*1000 + 0*1 равно нулю , что и показано в последнем столбце таблицы .
Определим , является ли полученное пробное решение наи-лучшим ( оптимальным ) . Анализируя Z - уравнение , нетрудно заме-тить , что обе небазисные переменные X 1 и X 2 , равные нулю , имеют отрицательные коэффициенты . Всегда выбирается переменная с большим абсолютным значением отрицательного коэффициента ( в Z - уравнении ) , так как практический опыт вычислений показывает , что в этом случае оптимум достигается быстрее .
Это правило составляет основу используемого в вычислительнойсхеме симплекс-метода условия оптимальности , которое состоит втом , что , если в задаче максимизации все небазисные переменные вZ - уравнении имеют неотрицательные коэффициенты , полученное пробное решение является оптимальным . В противном случае в ка-честве новой базисной переменной следует выбрать ту , которая имеетнаибольший по абсолютной величине отрицательный коэффициент .
Применяя условие оптимальности к исходной таблице , выберемв качестве переменной , включаемой в базис , переменную Х 2 . Исклю-чаемая переменная должна быть выбрана из совокупности базисныхпеременных S 1 , S 2 . Процедура выбора исключаемой переменной предполагает проверку условия допустимости , требующего , чтобы в качестве исключаемой переменной выбиралась та из пере-менных текущего базиса , которая первой обращается в нуль при уве-личении включаемой переменной X 2 вплоть до значения , соответствующего смежной экстремальной точке .
Интересующее нас отношение ( фиксирующее искомую точку пе-ресечения и идентифицирующее исключаемую переменную ) можноопределить из симплекс-таблицы. Для этого в столбце , соответствующем вводимой переменной X 2 , вычеркиваются отрицательные и нулевые элементы ограничений . Затем вычисляются отношения постоянных , фигурирующих в правых частях этих ограничений , к оставшимся элементам столбца , соответствующего вводимой переменной X 2 . Исключаемой переменной будет та переменная текущего базиса , для которой указанное выше отношение минимально.
Начальная симплекс-таблица для нашей задачи , получаемая после проверки условия допустимости ( т. е. после вычисления соответствующих отношений и определения исключаемой переменной ) , воспроизведена ниже . Для удобства описания вычислительных процедур , осуществляемых на следующей итерации , введем ряд необходимых определений . Столбец симплекс-таблицы , ассоциированный с вводимой переменной , будем называть ведущим столбцом . Строку , соответствующую исключаемой переменной , назовем ведущей строкой ( уравнением ) , а элемент таблицы , находящийся на пересечении ведущего столбца и ведущей строки , будем называть ведущим элементом .
После того как определены включаемая и исключаемая пере-После того как определены включаемая и исключаемая пере-менные ( с использованием условий оптимальности и допустимости ) , следующая итерация ( поиск нового базисного решения ) осуществля-ется методом исключения переменных , или методом Гаусса — Жордана . Этот процесс изменения базиса включает вычислительные процедуры двух типов .
Тип 1 ( формирование ведущего уравнения ) .
Новая ведущая строка = Предыдущая ведущая строка / Ведущий элемент
Тип 2 ( формирование всех остальных уравнений , включая Z - yравнение ) .
Новое уравнение = Предыдущее уравнение —
й Коэффициент щ
к ведущего столбца к * ( Новая ведущая строка ) .
к предыдущего к
л уравнения ы
Выполнение процедуры типа 1 приводит к тому , что в новомведущем уравнении ведущий элемент становится равным единице .В результате осуществления процедуры типа 2 все остальные коэф-фициенты , фигурирующие в ведущем столбце , становятся равныминулю . Это эквивалентно получению базисного решения путем ис-ключения вводимой переменной из всех уравнений , кроме ведущего .Применяя к исходной таблице процедуру 1 , мы делим S 2 - уравнение на ведущий элемент , равный 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 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 . Это решение соответствует данным заключительной симплекс-таблицы .
Статус ресурсов
Будем относить ресурсы к дефицитным или недифицитным в зависимости от того , полное или частичное их использо-вание предусматривает оптимальное решение задачи . Сейчас цельсостоит в том , чтобы получить соответствующую информацию непос-редственно из симплекс-таблицы для оптимального решения . Од-нако сначала следует четко уяснить следующее . Говоря о ресурсах , фигурирующих в задаче ЛП , мы подразумеваем , что установленынекоторые максимальные пределы их запасов , поэтому в соответст-вующих исходных ограничениях должен использоваться знак <= .Следовательно , ограничения со знаком => не могут рассматриватьсякак ограничения на ресурсы . Скорее , ограничения такого типа отра-жают то обстоятельство , что решение должно удовлетворять опре-деленным требованиям , например обеспечению минимального спро-са или минимальных отклонений от установленных структурныххарактеристик производства ( сбыта ) .
В модели , построенной для нашей задачи , фигурирует ограничение со знаком <= . Это требование можно рассматривать как ограничение на соответствующий « ресурс » , так как увеличение спроса на продукцию эквивалентно расширению « представительства » фирмы на рынке сбыта .
Из вышеизложенного следует , что статус ресурсов ( дефицитныйили недефицитный ) для любой модели ЛП можно установить не-посредственно из результирующей симплекс-таблицы , обращая вни-мание на значения остаточных переменных . Применительно к нашей задаче можно привести следующую сводку результатов :
|
Ресурсы
|
Остаточная переменная |
Статус ресурса |
Ограничение по бюджету |
S1 |
Дефицитный |
Превышение времени рекламы радио над теле
|
S2 |
Дефицитный |
