Построение экономической модели с использованием симплекс-метода
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 01/20 )
-
( -1/2
) * ( 0 1 01/55-50/551000/55 )
( 0 0 11/110 1/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 . Это решение соответствует данным
заключительной симплекс-таблицы .
Статус ресурсов
Будем относить ресурсы к дефицитным или
недифицитным в зависимости от того , полное или частичное их использо-
вание предусматривает оптимальное решение задачи . Сейчас цель
состоит в том , чтобы получить соответствующую информацию непос-
редственно из симплекс-таблицы для оптимального решения . Од-
нако сначала следует четко уяснить следующее . Говоря о ресурсах , фигурирующих в задаче ЛП , мы подразумеваем , что установлены
некоторые максимальные пределы их запасов , поэтому в соответст-
вующих исходных ограничениях должен использоваться знак <= .
Следовательно, ограничения со знаком => не могут рассматриваться
как ограничения на ресурсы. Скорее, ограничения такого типа отра-
жают то обстоятельство, что решение должно удовлетворять опре-
деленным требованиям, например обеспечению минимального спро-
са или минимальных отклонений от установленных структурных
характеристик производства (сбыта).
В модели, построенной для нашей задачи , фигурирует ограничение со знаком <= . Это требование можно рассматривать как ограничение на соответствующий
« ресурс » , так как увеличение спроса на продукцию эквивалентно расширению «
представительства » фирмы на рынке сбыта .
Из вышеизложенного следует ,
что статус ресурсов ( дефицитный
или недефицитный ) для любой модели ЛП можно установить не-
посредственно из результирующей симплекс-таблицы , обращая вни-
мание на значения остаточных переменных . Применительно к нашей задаче можно
привести следующую сводку результатов :
Главная