После того как определены включаемая и исключаемая пере-менные ( с использованиемусловий оптимальностиидопустимости ) ,следующая итерация ( поиск нового базисного решения ) осуществля-ется методом исключения переменных , или методом Гаусса — Жордана . Этот процесс изменения базиса включает вычислительные процедуры двух типов .
Тип 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. Это решение соответствует данным заключительной симплекс-таблицы .
Статус ресурсов
Будем относить ресурсык дефицитнымилинедифицитнымв зависимости от того , полное или частичное их использо-вание предусматривает оптимальное решение задачи . Сейчас цельсостоит в том , чтобы получить соответствующую информацию непос-редственно из симплекс-таблицы для оптимального решения . Од-нако сначала следует четко уяснить следующее . Говоря оресурсах ,фигурирующих в задаче ЛП , мы подразумеваем , что установленынекоторыемаксимальныепределы их запасов , поэтому в соответст-вующих исходных ограничениях должен использоваться знак <= .Следовательно , ограничения со знаком => не могут рассматриватьсякак ограничения на ресурсы . Скорее , ограничения такого типа отра-жают то обстоятельство , что решение должно удовлетворять опре-деленным требованиям , например обеспечению минимального спро-са или минимальных отклонений от установленных структурныххарактеристик производства ( сбыта ) .
В модели , построенной для нашей задачи , фигурирует ограничение со знаком <= . Это требование можно рассматривать как ограничение на соответствующий « ресурс » , так как увеличение спроса на продукцию эквивалентно расширению « представительства » фирмы на рынке сбыта .
Из вышеизложенного следует , что статус ресурсов ( дефицитныйили недефицитный ) для любой модели ЛП можно установить не-посредственно из результирующей симплекс-таблицы , обращая вни-мание на значения остаточных переменных . Применительно к нашей задаче можно привести следующую сводку результатов
:
|
Ресурсы
|
Остаточная переменная |
Статус ресурса |
Ограничение по бюджету |
S1 |
Дефицитный |
Превышение времени рекламы радио над теле
|
S2 |
Дефицитный |
Положительное значение остаточной переменной указывает нанеполное использование соответствующего ресурса , т . е . данныйресурс является недефицятным. Если же остаточная переменная рав-на нулю , это свидетельствует о полном потреблении соответствующе-го ресурса. Из таблицы видно , что наши ресурсы являются дефицитными . В случае недефицитности любое увиличение ресурсов сверх установленного максимального значения привело бы лишь к тому , что они стали бы еще более недефнинтными . Оптимальное решение задачи при этом осталось бы неизменным.
Ресурсы, увеличение запасов которых позволяет улучшить ре-шение ( увеличить прибыль ) , — это остаточные переменные S1и S2, по-скольку из симплекс-таблицы для оптимального решения видно ,что они дефицитные . В связи с этим логично поставить следующийвопрос: какому из дефицитных ресурсов следует отдать предпочте-ние при вложении дополнительных средств на увеличение их запа-сов , с тем чтобы получить от них максимальную отдачу ? Ответ наэтот вопрос будет дан в следующем подразделе этой главы , где рас-сматривается ценность различных ресурсов .
Ценность ресурса
Ценность ресурсахарактеризуется величиной улучшения опти-мального значения Z,приходящегося на единицу прироста объемаданного ресурса .
Информация для оптимального решения задачи представлена в симплекс-таблице . Обратим внимание на значениякоэффициентовZ - уравнения , стоящих при переменныхначальногобазисаS1и S2.Выделим для удобствасоответстзующую часть симплекс-таблицы :
|
Базисные переменные
|
Z |
X1 |
X2 |
S1 |
S2 |
Решение |
Z |
1 |
0 |
0 |
27/110 |
5/22 |
2455/11 |
Как следуетиз теории решения задачЛП , ценность ресурсов всегда можно определить по значениям коэффициентовпри переменныхначального базиса ,фигурирующих вZ - уравнении оптимальной симплекс-таблицы , таким образом Y1=27/110, а Y2=5/22.
Покажем , каким образом аналогичный результат можно получить непосредственно из симплекс-таблицы для оптимального решения . РассмотримZ - уравнение симплекс-таблицы для оптимального решения нашей задачи
Z = 2455/11- (27/110S1+5/22S2) .
Положительное приращение переменной S1относительно ее текущегонулевого значения приводит к пропорциональному уменьшению Z,причем коэффициент пропорциональности равен27/110. Но , как следует из первого ограничения модели :
5X1 + 100X2 + S1= 1000
увеличение S1эквивалентноснижениюколичества денег выделеных на рекламу ( далее мы будем использовать в тексте , как первый ресурс ) .
Отсюда следует , что уменьшение количества денег выделеных на рекламу вызывает пропорциональное уменьшение целевой функции с тем же коэффициентом пропорциональности,равным27/110.Так какмы оперируем слинейнымифункциями , полученный вывод можнообобщить , считая , что иувеличениеколичества денег выделеных на рекламу ( эквивалентноевведениюизбыточнойпеременной S1< 0 ) приводит к пропорциональномуувеличениюZ с тем же коэффициентом пропорциональности , равным27/110. Аналогичные рассуждения справед-ливы для ограничения 2 .
Несмотря на то что ценность различных ресурсов , определяемаязначениями переменных Yi,была представлена в стоимостном выражении , ее нельзя отождествлять с действительными це-нами , по которым возможна закупка соответствующих ресурсов .На самом деле речь идет о некоторой мере , имеющей экономическуюприродун количественно характеризующей ценность ресурса только относительно полученного оптимального значения целевой функции .При изменении ограничении модели соответствующие экономическиеоценки будут меняться даже тогда , когда оптимизируемый процесспредполагает применение тех же ресурсов . Поэтому при характерис-тике ценности ресурсов экономисты предпочитают использоватьтакие терминыт , как теневая цена , скрытая цена , или более специ-фичный термин — двойственная оценка .
Заметим , что теневая цена ( ценность ресурса ) характеризует ин-тенсивность улучшения оптимального значения Z . Однако при этомне фиксируется интервал значений увеличения запасов ресурса ,при которых интенсивность улучшения целевой функции остаетсяпостоянной . Для большинства практических ситуаций логично пред-положить наличие верхнего предела увеличения запасов , при пре-вышении которого соответствующее ограничение становится избы-точным , что в свою очередь приводит к новому базисному решениюи соответствующим ему новым теневым ценам . Ниже определяетсянитервал значений запасов ресурса , при которых соответствую-щее ограничение не становится избыточным .
Максимальное изменение запаса ресурса
При решении вопроса о том , запас какого из ресурсов следуетувеличивать в первую очередь , обычно используютсятеневые ценыЧтобы определить интервал значений изменения запаса ресурса ,при которых теневая цена данного ресурса , ( фигурирующая в заклю-чительной симплекс-таблице , остается неизменной , необходимо выполнить ряд дополнительных вычислений . Рассмотрим сначаласоответствующие вычислительные процедуры , а затем покажем , кактребуемая информация может быть получена из симплекс-таблицыдля оптимального решения .
В нашей задаче запас первого ресурса изменился наD1т. е. запас бюджета составит 1000 +D1. При положительной величинеD1запас данного ресурса увеличивается , при отрицательной — уменьшается . Как правило , исследуется ситуация , когда объем ресурса увеличивается (D1> 0 ) , однако , чтобы получить результат в общем виде , рассмотрим оба случая .
Как изменится симплекс-таблица при изменении величины за-паса ресурса наD1? Проще всего получить ответ на этот вопрос .если ввестиD1в правую часть первого ограничения начальной сим-плекс-таблицы и затем выполнить все алгебраические преобразова-ния , соответствующие последовательности итераций . Посколькуправые части ограничений никогда не используются в качествеведущих элементов ,то очевидно , что на каждой итерацииD1будетоказывать влияние только на правые части ограничений .
|
Уравнение
|
Значения элементов правой части на соответствующих итерациях |
|
( начало вычислений )
|
1 |
2 ( оптимум ) |
Z |
0 |
0 |
2455/11 |
1 |
1000 |
1000 +D1 |
1000/55+D1 |
2 |
0 |
0 |
91/11 |
