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