Новое Z - уравнение

1. Новое Z - уравнение .

старое Z - уравнение : ( 1 -1 -25 0 0 0 )

( - ( -25 ) * ( 0 -1/2 1 0 1/2 0 )

( 1 -13¹/₂ 0 0 12¹/₂ 0 )

2.   Новое S₁ - уравнение

старое S₁ - уравнение : ( 0 5 100 1 0 1000 )

 ( - 100 ) * ( 0 -¹/₂ 1 0 ¹/₂ 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 – уравнение

В новом решении X₁ = 0 и S₂ = 0 . Значение Z не изменяется .

Заметим , что новая симплекс-таблица обладает такими же ха-
рактеристиками , как и предыдущая : только небазисные переменные
 X₁ и S₂ равны нулю , а значения базисных переменных , как и раньше ,
представлены в столбце « Решение » . Это в точности соответствует
результатам , получаемым при использовании метода Гаусса—Жор-
дана .

Из последней таблицы следует , что на очередной итерации в со-
ответствии с условием оптимальности в качестве вводимой перемен-
ной следует выбрать X₁ , так как коэффициент при этой переменной в

Z-ypaвнении равен -13¹/₂ . Исходя из условия допустимости , определяем , что исключаемой переменной будет S₁ . Отношения , фигурирующие в правой части таблицы , показывают , что в новом базисном решении значение включаемой переменной X₁ будет равно ¹⁰⁰⁰/₅₅ ( = минимальному отношению ) . Это приводит к увеличению целевой функции на ( ¹⁰⁰⁰/₅₅ ) * ( -13^1/₂ ) = ( 245⁵/₁₁ ) .

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

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

Базисные переменные	Z	X1	X2	S1	S2	Решение
Z
S1	0	1	0	1/55	- 50/55	1000/55
X2

2) Новое Z - уравнение = Предыдущее Z - уравнение - ( -13¹/₂ ) * Новое /ведущее уравнение :

( 1 -13¹/₂ 0 0 12¹/₂ 0 )

- ( -13¹/₂ ) * ( 0 1 0 ¹/₅₅ -⁵⁰/₅₅¹⁰⁰⁰/₅₅  )

( 1 0 0 ²⁷/₁₁₀⁵/₂₂ 245⁵/₁₁ )

3) Новое X₂ - уравнение = Предыдущее X₂ - уравнение - ( -¹/₂ ) * Новое ведущее уравнение :

( 0 -¹/₂ 1  0  ¹/₂ 0 )

- ( - ¹/₂  ) *  ( 0 1  0 ¹/₅₅ -⁵⁰/₅₅¹⁰⁰⁰/₅₅ )

( 0 0  1  ¹/₁₁₀¹/₂₂  9¹/₁₁  )

В результате указанных преобразований получим следующую симп-
лекс-таблицу .

Базисные переменные	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

В новом базисном решении X₁=¹⁰⁰⁰/₅₅ и X₂=9¹/₁₁ . Значение Z увеличилось с 0 ( предыдущая симплекс-таблица ) до 245⁵/₁₁ ( последняя симплекс-таблица ) . Этот результирующий прирост целевой функции обусловлен увеличением X₁ от О до ¹⁰⁰⁰/₅₅ , так как из Z - строки предыдущей симплекс-таблицы следует , что возрастанию данной переменной на единицу соответствует увеличение целевой функции на( -13¹/₂ ) .

Последняя симплекс-таблица соответствует оптимальному реше-
нию задачи, так как в Z - уравнении ни одна из небазисных переменных не фигурирует с отрицательным коэффициентом. Получением этой pезультирующей таблицы и завершаются вычислительные процедуры симплекс-метода .

В рассмотренном выше примере алгоритм симплекс-метода ис-
пользован при решении задачи , в которой целевая функция подлежала максимизации . В случае минимизации целевой функции в этом
алгоритме необходимо изменить только условие оптимальности :
в качестве новой базисной переменнойследует выбирать ту переменную , которая в Z - уравнении имеет наибольший положительный коэффициент . Условия допустимости в обоих случаях ( максимизации и минимизации ) одинаковы . Представляется целесообразным дать теперь окончательные формулировки обоим условиям , используемым в симплекс-методе .

Условие оптимальности . Вводимой переменной в задаче максимизации ( минимизации ) является небазисная переменная , имеющая в Z -уравнении наибольший отрицательный ( положительный ) коэффициент , В случае равенства таких коэффициентов для нескольких небазисных переменных выбор делается произвольно , если все коэффициенты при небазисных переменных в Z - уравнении неотрицательны (неположительны) , полученное решение является оптимальным .

Условие допустимости , в задачах максимизации и минимизации в качестве исключаемой переменной выбирается та базисная переменная , для которой отношение постоянной в правой части соответствующего ограничения к ( положительному ) коэффициенту ведущего столбца минимально. В случае равенства этого отношения для нескольких базисных переменных выбор делается произвольно .

 
Оптимальное решение

С точки зрения практического использования результатов ре-
шения задач ЛП классификация переменных , предусматривающая
их разделение на базисные и небазнсные , не имеет значения и при
анализе данных , характеризующих оптимальное решение , может
не учитываться . Переменные , отсутствующие в столбце « Базисные
переменные » , обязательно имеют нулевое значение . Значения ос-
тальных переменных приводятся в столбце « Решение » . При интер-
претации результатов оптимизации в нашей задаче нас прежде всего интересует количество времени , которое закажет наша фирма на радио и телевидение , т. е. значения управляемых переменных X₁ и X₂ . Используя данные , содержащиеся в симплекс-таблице для оптимального решения , основные результаты можно представить в следующем виде :

Управляемые переменные	Оптимальные значения	Решение
X1	1000/55	Время выделяемое фирмой на телерекламу
X2	91/11	Время выделяемое фирмой на радиорекламу
Z	2455/11	Прибыль получаемая от рекламы .

Заметим, что Z = X₁ + 25X₂ = ¹⁰⁰⁰/₅₅ + 25 * 9¹/₁₁ = 245⁵/₁₁ . Это решение соответствует данным заключительной симплекс-таблицы .

Статус ресурсов

 

Будем относить ресурсы к дефицитным или недифицитным в зависимости от того , полное или частичное их использо-
вание предусматривает оптимальное решение задачи . Сейчас цель
состоит в том , чтобы получить соответствующую информацию непос-
редственно из симплекс-таблицы для оптимального решения . Од-
нако сначала следует четко уяснить следующее . Говоря о ресурсах ,
фигурирующих в задаче ЛП , мы подразумеваем , что установлены
некоторые максимальные пределы их запасов , поэтому в соответст-
вующих исходных ограничениях должен использоваться знак <= .
Следовательно , ограничения со знаком => не могут рассматриваться
как ограничения на ресурсы . Скорее , ограничения такого типа отра-
жают то обстоятельство , что решение должно удовлетворять опре-
деленным требованиям , например обеспечению минимального спро-
са или минимальных отклонений от установленных структурных
характеристик производства ( сбыта ) .

В модели , построенной для нашей задачи , фигурирует ограничение со знаком <= . Это требование можно рассматривать как ограничение на соответствующий « ресурс » , так как увеличение спроса на продукцию эквивалентно расширению « представительства » фирмы на рынке сбыта .

Из вышеизложенного следует , что статус ресурсов ( дефицитный
или недефицитный ) для любой модели ЛП можно установить не-
посредственно из результирующей симплекс-таблицы , обращая вни-
мание на значения остаточных переменных . Применительно к нашей задаче можно привести следующую сводку результатов

:

Ресурсы	Остаточная переменная	Статус ресурса
Ограничение по бюджету	S1	Дефицитный
Превышение времени рекламы радио над теле	S2	Дефицитный

Положительное значение остаточной переменной указывает на
неполное использование соответствующего ресурса , т . е . данный
ресурс является недефицятным. Если же остаточная переменная рав-
на нулю , это свидетельствует о полном потреблении соответствующе-
го ресурса. Из таблицы видно , что наши ресурсы являются дефицитными . В случае недефицитности любое увиличение ресурсов сверх установленного максимального значения привело бы лишь к тому , что они стали бы еще более недефнинтными . Оптимальное решение задачи при этом осталось бы неизменным.

Ресурсы, увеличение запасов которых позволяет улучшить ре-
шение ( увеличить прибыль ) , — это остаточные переменные S₁ и S₂ , по-
скольку из симплекс-таблицы для оптимального решения видно ,
что они дефицитные . В связи с этим логично поставить следующий
вопрос: какому из дефицитных ресурсов следует отдать предпочте-
ние при вложении дополнительных средств на увеличение их запа-
сов , с тем чтобы получить от них максимальную отдачу ? Ответ на
этот вопрос будет дан в следующем подразделе этой главы , где рас-
сматривается ценность различных ресурсов .

Ценность ресурса

 

Ценность ресурса характеризуется величиной улучшения опти-
мального значения Z , приходящегося на единицу прироста объема
данного ресурса .

Информация для оптимального решения задачи представлена в симплекс-таблице . Обратим внимание на значения коэффициентов Z - уравнения , стоящих при переменных начального базиса S₁ и S₂ . Выделим для удобства соответстзующую часть симплекс-таблицы :

Базисные переменные	Z	X1	X2	S1	S2	Решение
Z	1	0	0	27/110	5/22	2455/11

Как следует из теории решения задач ЛП , ценность ресурсов всегда можно определить по значениям коэффициентов при переменных начального базиса , фигурирующих в Z - уравнении оптимальной симплекс-таблицы , таким образом Y₁ = ²⁷/₁₁₀ , а Y₂ = ⁵/₂₂ .

Покажем , каким образом аналогичный результат можно получить непосредственно из симплекс-таблицы для оптимального решения . Рассмотрим Z - уравнение симплекс-таблицы для оптимального решения нашей задачи

Z = 245⁵/₁₁ - ( ²⁷/₁₁₀S₁ + ⁵/₂₂S₂ ) .

Положительное приращение переменной S₁ относительно ее текущего
нулевого значения приводит к пропорциональному уменьшению Z ,
причем коэффициент пропорциональности равен ²⁷/₁₁₀ . Но , как следует из первого ограничения модели :

5X1 + 100X2 + S₁ = 1000

увеличение S₁ эквивалентно снижению количества денег выделеных на рекламу ( далее мы будем использовать в тексте , как первый ресурс ) .

Отсюда следует , что уменьшение количества денег выделеных на рекламу вызывает пропорциональное уменьшение целевой функции с тем же коэффициентом пропорциональности,равным²⁷/₁₁₀.Так как
мы оперируем с линейными функциями , полученный вывод можно
обобщить , считая , что и увеличение количества денег выделеных на рекламу ( эквивалентное введению избыточной переменной S₁ < 0 ) приводит к пропорциональному увеличению Z с тем же коэффициентом пропорциональности , равным ²⁷/₁₁₀ . Аналогичные рассуждения справед-
ливы для ограничения 2 .

Несмотря на то что ценность различных ресурсов , определяемая
значениями переменных Y_i , была представлена в стоимостном выражении , ее нельзя отождествлять с действительными це-
нами , по которым возможна закупка соответствующих ресурсов .
На самом деле речь идет о некоторой мере , имеющей экономическую
природу н количественно характеризующей ценность ресурса только относительно полученного оптимального значения целевой функции .
При изменении ограничении модели соответствующие экономические
оценки будут меняться даже тогда , когда оптимизируемый процесс
предполагает применение тех же ресурсов . Поэтому при характерис-
тике ценности ресурсов экономисты предпочитают использовать
такие терминыт , как теневая цена , скрытая цена , или более специ-
фичный термин — двойственная оценка .

Заметим , что теневая цена ( ценность ресурса ) характеризует ин-
тенсивность улучшения оптимального значения Z . Однако при этом
не фиксируется интервал значений увеличения запасов ресурса ,
при которых интенсивность улучшения целевой функции остается
постоянной . Для большинства практических ситуаций логично пред-
положить наличие верхнего предела увеличения запасов , при пре-
вышении которого соответствующее ограничение становится избы-
точным , что в свою очередь приводит к новому базисному решению
и соответствующим ему новым теневым ценам . Ниже определяется
нитервал значений запасов ресурса , при которых соответствую-
щее ограничение не становится избыточным .

Максимальное изменение запаса ресурса

При решении вопроса о том , запас какого из ресурсов следует
увеличивать в первую очередь , обычно используются теневые цены
Чтобы определить интервал значений изменения запаса ресурса ,
при которых теневая цена данного ресурса , ( фигурирующая в заклю-
чительной симплекс-таблице , остается неизменной , необходимо выполнить ряд дополнительных вычислений . Рассмотрим сначала
 соответствующие вычислительные процедуры , а затем покажем , как
требуемая информация может быть получена из симплекс-таблицы
для оптимального решения .

В нашей задаче запас первого ресурса изменился на D₁ т. е. запас бюджета составит 1000 + D₁ . При положительной величине D₁ запас данного ресурса увеличивается , при отрицательной — уменьшается . Как правило , исследуется ситуация , когда объем ресурса увеличивается ( D₁ > 0 ) , однако , чтобы получить результат в общем виде , рассмотрим оба случая .

Как изменится симплекс-таблица при изменении величины за-
паса ресурса на D₁? Проще всего получить ответ на этот вопрос .
если ввести D₁в правую часть первого ограничения начальной сим-
плекс-таблицы и затем выполнить все алгебраические преобразова-
ния , соответствующие последовательности итераций . Поскольку
правые части ограничений никогда не используются в качестве
ведущих элементов , то очевидно , что на каждой итерации D₁будет
оказывать влияние только на правые части ограничений .

Уравнение	Значения элементов правой части на соответствующих итерациях
	( начало вычислений )	1	2 ( оптимум )
Z	0	0	2455/11
1	1000	1000 + D1	1000/55 + D1
2	0	0	91/11

Фактически вce изменения правых частей ограничений , обуслов-
ленные введением D₁, можно определить непосредственно по данным ,
содержащимся в симплекс-таблицах . Прежде всего заметим , что
на каждой итерации новая правая часть каждого ограничения пред-
ставляет собой сумму двух величин: 1) постоянной и 2) члена , ли-
нейно зависящего от D₁. Постоянные соответствуют числам , которые
фигурируют на соответствующих итерациях в правых частях ограничений симплекс-таблиц до введения D₁. Коэффициенты при D₁во вторых слагаемых равны коэффициентам при S₁ на той же итерации . Так , например , на последнеи итерации ( оптимальное решение ) постоянные ( 245⁵/₁₁ ; ¹⁰⁰⁰/₅₅ ; 9¹/₁₁ ) представляют собои числа , фигурирующие в правых частях ограничении оптимальной симплекс-таблицы до введения D₁. Коэффициенты ( ²⁷/₁₁₀ ; ¹/₅₅ ; ¹/₁₁₀ ) равны коэффициентам при S₁ в той же симплекс-таблице потому , что эта переменная связана только с первым ограничением . Другими словами , при анализе влияния изменений в правой части второго ограничения нужно пользоваться коэффициентами при переменной S₂ .

Какие выводы можно сделать из полученных результатов?
Так как введение D₁ сказывается лишь на правой части симплекс-
таблицы , изменение запаса ресурса может повлиять только на
допустимость решения . Поэтому D₁ не может принимать значений ,
при которых какая-либо из ( базисных ) переменных становится отри-
цательной . Из этого следует , что величина D₁ должна быть огра-
ничена таким интервалом значений , при которых выполняется ус-
ловие неотрицательности правых частей ограничений в результи-
рующей симплекс-таблице , т . е .

X₁ = ¹⁰⁰⁰/₅₅ + ( ¹/₅₅ )D₁ => 0 ( 1 )

X₂ = 9¹/₁₁ + ( ¹/₁₁₀ )D₁ => 0 ( 2 )

Для определения допустимого интервала изменения D₁рассмо-
трим два случая .

Случай 1: D₁ => 0 Очевидно , что оба неравнества при этом условии всегда будут неотрицательными .

 

 

Случай 2: D₁< 0 .

( ¹/₅₅ )D₁ => - ¹⁰⁰⁰/₅₅ . Из этого следует , что D₁ => - 1000

( 2 )

( ¹/₁₁₀ )D₁ => - 9¹/₁₁ . Из этого следует , что D₁ => - 1000

Объединяя результаты , полученные для обоих случаев , можно
сделать вывод , что при - 1000 <= D₁ <= + ¥ решение рассматриваемой зада-
чи всегда будет допустимым , любое значение D₁ , выходящее за
пределы указанного интервала , приведет к недопустимости решения и
новой совокупности базисных переменных .

Теперь рассмотрим в каких пределах может изменяться запас ресурса 2 анализ проведем по аналогичной схеме :

Запас 2-ого ресурса изменился на D₂ т . е . запас рекламного времени составит 0 + D₂ . Как изменилась симплекс-таблица при изменении величины запаса ресурса на D₂.

Уравнение	Значения элементов правой части на соответствующих итерациях
	( начало вычислений )	1	2 ( оптимум )
Z	0	0	2455/11
1	1000	1000	1000/55
2	0	0 + D2	91/11 + D2

Найдем интервал ограничивающий величину D₂

X₁ = ¹⁰⁰⁰/₅₅ - ( ⁵⁰/₅₅ )D₂ ( 1 )

X₂ = 9¹/₁₁ + ( ¹/₂₂ )D₂ ( 2 )

Для определения допустимого интервала изменения D₁рассмо-
трим два случая .

Случай 1: D₂ => 0: ( 1 )

( ⁵⁰/₅₅ )D₂ <= ¹⁰⁰⁰/₅₅ из этого неравенства следует , что D₂ <= 20

( 2 )

Очевидно , что 2-ое уравнение неотрицательно на данном участке .

Объединяя 2 уравнения для Случая 1 мы получим интервал для D₂.

D₂ Î [ 0 ; 20 ]

Случай 2: D₂< 0 . : ( 1 )

( ⁵⁰/₅₅ )D₂ => - ¹⁰⁰⁰/₅₅ . Из этого следует , что D₂ <= 20

 ( 2 )

( ¹/₂₂ )D₂ => - 9¹/₁₁ . Из этого следует , что D₂ => - 200

Объединяя 2 уравнения для Случая 2 мы получим интервал для D₂.

D₂ Î [ - 200 ; 0 ]

Объединяя 2 случая мы получим интервал [ - 200 ; 20 ]

Максимальное изменение коэффициентов удельной прибыли ( стоимости )

Наряду с определением допустимых изменений запасов ресур-
сов представляет интерес и установление интервала допустимых
изменений коэффициентов удельной прибыли ( или стоимости ) .
Следует отметить , что уравнение целевой функции никогда не используется в качестве ведущего уравнения . Поэтому лю-
бые изменения коэффициентов целевой функции окажут влияние
только на Z-уравнение результирующей симплекс-таблицы . Это
означает , что такие изменения могут сделать полученное решение
неоптимальным . Наша цель заключается в том , чтобы найти интер-
валы значений изменений коэффициентов целевой функции ( рас-
сматривая каждый из коэффициентов отдельно ) , при которых оп-
тимальные значения переменных остаются неизменными .

Чтобы показать, как выполняются соответствующие вычисле-
ния , положим , что удельный объем сбыта , ассоциированной с переменной

X₁ изменяется от 1 до 1 + d₁ где d₁ может быть как положительным , так и отрицательным числом . Целевая функция в этом случае принимает следующий вид:

Z = ( 1 + d₁ )X₁ + 25X₂

Если воспользоваться данными начальной симплекс-таблицы и
выполнить все вычисления , необходимые для ( получения заключн-
тельной симплекс-таблицы , то последнее Z-уравнение будет выгля-
деть следующим образом:

Базисные переменные	X1	X2	S1	S2	Решение
Z	0	0	27/110+1/55d1	5/22-50/55d1	2455/11+1000/55d1

Коэффициенты при базисных переменных X₁ , X₂ и остаточных я равными нулю . Это уравнение отличается от Z-уравнения до введения d₁ , только наличием членов , содержащих d₁. Коэффициенты при d₁ равны Коэффициентам при соответствующих переменных в Z-уравнении симплекс-таблицы для полученного ранее оптимального решения

Базисные переменные	X1	X2	S1	S2	Решение
X1	1	0	1/55	-50/55	1000/55

Мы рассматриваем X₁ - уравнение , так как коэффициент именно при
этон переменной в выражении для целевои функции изменился
на d₁ .

Оптимальные значения переменных будут оставаться неизмен-
ными при значениях d₁ , удовлетворяющих условию неотрицатель-
ности ( задача на отыскание максимума ) всех коэффициентов при не-
базисных переменных в Z-уравнении . Таким образом , должны выполняться следующие неравенства :

²⁷/₁₁₀+ ¹/₅₅d₁ => 0

⁵/₂₂ - ⁵⁰/₅₅d₁ => 0

Из первого неравенства получаем , что d₁ => - 13,5 , а из второго следует что d₁ <= ¹/₄ . Эти результаты определяют пределы изменения коэффициента C₁ в виде следующего соотношения : - 13,5 <= d₁ <= ¹/₄ . Та-
ким образом , при уменьшении коэффициента целевой функции при
переменной X₁ до значения , равного 1 + ( - 13,5 ) = - 12,5  или при его увеличении до 1 + 13,5 = 14,5 оптимальные значения переменных остаются
неизменными . Однако оптимальное значение Z будет изменяться ( в соответствии с выражением 245⁵/₁₁ + ¹⁰⁰⁰/₅₅d₁ , где - 13,5 <= d₁ <= ¹/₄

X₂ изменяется от 25 до 25 + d₂ где d₂ может быть как положительным , так и отрицательным числом . Целевая функция в этом случае принимает следующий вид:

Z = ( 25 + d₂ )X₂ + X₁

Все предыдущее обсуждение касалось исследования изменения коэффициента при переменной , которой поставлено в соответствие ограничение , фигурирующее в симплекс-таблице . Однако такое ограничение имеется лишь в том случае , когда данная переменная является базисной ( например X₁ и X₂ ) . Если переменная небазисная , то в столбце , содержащем базисные переменные , она не будет представлена .

Любое изменение коэффициента целевой функции при небазисной переменной приводит лишь к тому , что в заключительной симплкс-таблице изменяется только этот коэффициент . Рассмотрим в качестве иллюстрации случай , когда коэффициент при переменной S₁ ( первой остаточной переменной ) изменяется от 0 до d₃. Выполнение преобразований , необходимых для получения заключительной симплекс таблицы , приводит к следующему результирующему Z-уравнению :

Базисные переменные	X1	X2	S1	S2	Решение
Z	0	0	27/110+1/55d1	5/22	2455/11

Заключение

В результате проведенного исследования, было получено подтверждение о выгодности использования математико-экономического проектирования и методов системного анализа для анализа и планирования экономических систем.

Список литературы :

В этом месте должна указываться литература использованная в курсовой работе, но прогресс привел к тому, что вся информация черпалась на страницах INTERNET, а следовательно

Список серверов:

www.citforum.ru

www.rambler.ru

www.msu.ru

www.ntcf.ru

www.yandex.ru