( 1 0 0 27/1105/22 2455/11 )
3) Новое X2-уравнение = ПредыдущееX2 - уравнение - ( -1/2 ) * Новое ведущее уравнение :
( 0 -1/2 1 01/20 )
- ( -1/2 ) * ( 0 1 01/55-50/551000/55 )
( 0 0 11/1101/2291/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 .