Оптимальное решение
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 )
В результате указанных преобразований получим следующую симп-
лекс-таблицу .
| Базисные переменные | 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 = 2455/11 - ( 27/110S1 + 5/22S2 ) .
Положительное приращение переменной S1 относительно ее текущего
нул евого значения приводит к пропорциональному уменьшению Z ,
причем коэфф ициент пропорциональности равен 27/110 . Но , как следует из первого ограничения модели :
5X1 + 100X2 + S1 = 1000
увелич ен ие S1 эквивалентно снижению количества денег выделеных на рекламу ( далее мы будем использовать в тексте , как первый ресурс ) . Отсюда следует , что уменьшение количества денег выделеных на рекламу вызывает пропорциональное уменьшение целевой функции с тем же коэфф ициентом пропорциональности , равным 27/110 . Так как
мы оперируем с линейными функциями , полученный вывод можно
обоб щить , считая , что и увеличение количества денег выделеных на рекламу ( эквивалентно е введ ению из быточной перем енной S 1 0 ) приводит к пропорц иональному увеличению Z с тем же коэффициентом пропорциональности , равным 27/110 . Аналогичные рассуждения спра вед-
ливы для ограничения 2 .
Несмотря на то что ценность различных ресурсов , о пределяем ая
знач ениями переменных Yi , была представлена в стоимостном выражении , ее нельзя отождествлять с дейст вительными це-
на ми , по которым возможна закупка соотв етствующ их ресурсов .
На самом д еле речь идет о некоторой мере , им еющей экономическую
природу н количественно характеризующей ценность ресурса только относительно полученного оптимального значения целевой функции .
При изменении ограничении модели соответствующие экономические
оценки будут меняться даже тогда , когда оптимизируемый процесс
предполагает применение тех же ресурсов . Поэтому при характерис-
тике ценности ресурсов экономисты предпочитают использовать
такие терминыт , как теневая цена , скрытая цена , или более специ-
фичный термин двойственная оценка .
Заметим , что теневая цена ( ценность ресурса ) характеризует ин-
тенсивность улучшения оптимального значения Z . Однако при этом
не фиксируется интервал значений увеличения запасов ресурса ,
при которых интенсивность улучшения целевой функции остается
постоянной . Для большинства практических ситуаций логично пред-
положить наличие верхнего предела увеличения запасов , при пре-
вышении которого соответствующее ограничение становится избы-
точным , что в свою очередь приводит к новому базисному решению
и соответствующим ему новым теневым ценам . Ниже определяется
нитервал значений запасов ресурса , при которых соответствую-
щее ограничение не становится избыточным .
Максимальное изменение запаса ресурса
При решении вопроса о том , запас какого из ресурсов следует
увеличивать в первую очередь , обычно используются теневые цены
Чтобы определить интервал значений изменения запаса ресурса ,
при которых теневая цена данного ресурса , ( фигурирующая в заклю-
чительной симплекс-таблице , остается неизменной , необходимо выполнить ряд дополнительных вычислений . Рассмотрим сначала
соответствующие вычислительные процедуры , а затем покажем , как
требуемая информация может быть получена из симплекс-таблицы
для оптимального решения .
В нашей задаче запас первого ресурса изменился на 1 т. е. запас бюджета составит 1000 + 1 . При положительной величине 1 запас данного ресурса увеличивается , при отрицательной уменьшается . Как правило , исследуется ситуация , когда объем ресурса увеличивается ( 1 0 ) , однако , чтобы получить результат в общем виде , рассмотрим оба случая .
Как изменится симплекс-таблица при изменении величины за-
паса ресурса на 1 ? Проще всего получить ответ на этот вопрос .
если ввести 1 в правую часть первого ограничения начальной сим-
плекс-таблицы и затем выполнить все алгебраические преобразова-
ния , соответствующие последовательности итераций . Поскольку
правые части ограничений никогда не используются в качестве
ведущих элементов , то очевидно , что на каждой итерации 1 будет
оказывать влияние только на правые части ограничений .
| Уравнение | Значения элементов правой части на соответствующих итерациях | ||
| ( начало вычислений ) | 1 | 2 ( оптимум ) | |
| Z | 0 | 0 | 2455/11 |
| 1 | 1000 | 1000 + 1 | 1000/55 + 1 |
| 2 | 0 | 0 | 91/11 |
ленные введением 1 , можно определить непосредственно по данным ,
содержащимся в симплекс-таблицах . Прежде всего заметим , что
на каждой итерации новая правая часть каждого ограничения пред-
ставляет собой сумму двух величин: 1) постоянной и 2) члена , ли-
нейно зависящего от 1 . Постоянные соответствуют числам , которые
фигурируют на соответствующих итерациях в правых частях ограничений симплекс-таблиц до введения 1 . Коэффициенты при 1 во вторых слагаемых равны коэффициентам при S1 на той же итерации . Так , например , на последнеи итерации ( оптимальное решение ) постоянные ( 2455/11 ; 1000/55 ; 91/11 ) представляют собои числа , фигурирующие в правых частях ограничении оптимальной симплекс-таблицы до введения 1. Коэффициенты ( 27/110 ; 1/55 ; 1/110 ) равны коэффициентам при S1 в той же симплекс-таблице потому , что эта переменная связана только с первым ограничением . Другими словами , при анализе влияния изменений в правой части второго ограничения нужно пользоваться коэффициентами при переменной S2 . Какие выводы можно сделать из полученных результатов?
Так как введение 1 сказывается лишь на правой части симплекс-
таблицы , изменение запаса ресурса может повлиять только на
допустимость решения . Поэтому 1 не может принимать значений ,
при которых какая-либо из ( базисных ) переменных становится отри-
цательной . Из этого следует , что величина 1 должна быть огра-
ничена таким интервалом значений , при которых выполняется ус-
ловие неотрицательности правых частей ограничений в результи-
рующей симплекс-таблице , т . е .
X1 = 1000/55 + ( 1/55 )1 = 0 ( 1 )
X2 = 91/11 + ( 1/110 )1 = 0 ( 2 )
Для определения допустимого интервала изменения 1 рассмо-
трим два случая .
Случай 1: 1 = 0 Очевидно , что оба неравнества при этом условии всегда будут неотрицательными .
Случай 2: 1 0 . Решаем неравенства : ( 1 )
( 1/55 )1 = - 1000/55 . Из этого следует , что 1 = - 1000
( 2 )
( 1/110 )1 = - 91/11 . Из этого следует , что 1 = - 1000 Объединяя результаты , полученные для обоих случаев , можно
сделать вывод , что при - 1000 = 1 = + решение рассматриваемой зада-
чи всегда будет допустимым , любое значение 1 , выходящее за
пределы указанного интервала , приведет к недопустимости решения и
новой совокупности базисных переменных . Теперь рассмотрим в каких пределах может изменяться запас ресурса 2 анализ проведем по аналогичной схеме :
Запас 2-ого ресурса изменился на 2 т . е . запас рекламного времени составит 0 + 2 . Как изменилась симплекс-таблица при изменении величины запаса ресурса на 2 проиллюстрировано ниже .
| Уравнение | Значения элементов правой части на соответствующих итерациях | ||
| ( начало вычислений ) | 1 | 2 ( оптимум ) | |
| Z | 0 | 0 | 2455/11 |
| 1 | 1000 | 1000 | 1000/55 |
| 2 | 0 | 0 + 2 | 91/11 + 2 |
трим два случая . Случай 1: 2 = 0 Решаем неравенства : ( 1 )
( 50/55 )2
( 2 )
Очевидно , что 2-ое уравнение неотрицательно на данном участке .
Объединяя 2 уравнения для Случая 1 мы получим интервал для 2 .
2 [ 0 ; 20 ]
Случай 2: 2 0 . Решаем неравенства : ( 1 )
( 50/55 )2 = - 1000/55 . Из этого следует , что 2
( 2 )
( 1/22 )2 = - 91/11 . Из этого следует , что 2 = - 200
Объединяя 2 уравнения для Случая 2 мы получим интервал для 2 .
2 [ - 200 ; 0 ]
Объединяя 2 случая мы получим интервал [ - 200 ; 20 ]
Максимальное изменение коэффициентов удельной прибыли ( стоимости )
Наряду с определением допустимых изменений запасов ресур-
сов представляет интерес и установление интервала допустимых
изменений коэффициентов удельной прибыли ( или стоимости ) .
Следует отметить , что уравнение целевой функции никогда не используется в качестве ведущего уравнения . Поэтому лю-
бые изменения коэффициентов целевой функции окажут влияние
только на Z-уравнение результирующей симплекс-таблицы . Это
означает , что такие изменения могут сделать полученное решение
неоптимальным . Наша цель заключается в том , чтобы найти интер-
валы значений изменений коэффициентов целевой функции ( рас-
сматривая каждый из коэффициентов отдельно ) , при которых оп-
тимальные знач ен ия переменных остаются неизм енными .
Чтобы по каз ать, как выполняются соответствующи е вычисле-
ния , положим , что удельный объем сбыта , ассоциированной с пер еменной
X1 изменяется от 1 до 1 + 1 где 1 может быть как положительным , так и отрицательным числом . Целевая функция в этом случае принимает следующий вид:
Z = ( 1 + 1 )X1 + 25X2
Если воспользоваться данными начальной симплекс-таблицы и
выполнить все вычисления , необходимые для ( получения заключн-
тельной симплекс-таблицы , то последнее Z-уравнение будет выгля-
деть следующим образом:
| Базисные переменные | X1 | X2 | S1 | S2 | Решение |
| Z | 0 | 0 | 27/110+1/551 | 5/22-50/551 | 2455/11+1000/551 |
| Базисные переменные | X1 | X2 | S1 | S2 | Решение |
| X1 | 1 | 0 | 1/55 | -50/55 | 1000/55 |
Мы рассматриваем X1 - уравнение , так как коэффициент именно при
этон переменной в выражении для целевои функции изменился
на 1 .
Оптимальные значения переменных будут оставаться неизмен-
ными при значениях 1 , удовлетворяющих условию неотрицатель-
ности ( задача на отыскание максимума ) всех коэффициентов при не-
базисных переменных в Z-уравнении . Таким образом , должны выполняться следующие неравенства :
27/110 + 1/551 = 0
5/22 - 50/551 = 0
Из первого неравенства получаем , что 1 = - 13,5 , а из второго следует что 1 = 1/4 . Эти результаты определяют пределы изменения коэффициента C1 в виде следующего соотношения : - 13,5 = 1 = 1/4 . Та-
ким образом , при уменьшении коэффициента целевой функции при
переменной X1 до значения , равного 1 + ( - 13,5 ) = - 12,5 или при его увеличении до 1 + 13,5 = 14,5 оптимальные значения переменных остаются
неизменными . Однако оптимальное значение Z будет изменяться ( в соответствии с выражением 2455/11 + 1000/551 , где - 13,5 = 1 = 1/4
X2 изменяется от 25 до 25 + 2 где 2 может быть как положительным , так и отрицательным числом . Целевая функция в этом случае принимает следующий вид:
Z = ( 25 + 2 )X2 + X1
Все предыдущее обсуждение касалось исследования изменения коэффициента при переменной , которой поставлено в соответствие ограничение , фигурирующее в симплекс-таблице . Однако такое ограничение имеется лишь в том случае , когда данная переменная является базисной ( например X1 и X2 ) . Если переменная небазисная , то в столбце , содержащем базисные переменные , она не будет представлена .
Любое изменение коэффициента целевой функции при небазисной переменной приводит лишь к тому , что в заключительной симплкс-таблице изменяется только этот коэффициент . Рассмотрим в качестве иллюстрации случай , когда коэффициент при переменной S1 ( первой остаточной переменной ) изменяется от 0 до 3 . Выполнение преобразований , необходимых для получения заключительной симплекс таблицы , приводит к следующему результирующему Z-уравнению :
| Базисные переменные | X1 | X2 | S1 | S2 | Решение |
| Z | 0 | 0 | 27/110+1/551 | 5/22 | 2455/11 |
