|
Построение экономической модели с использованием симплекс-метода
Курсовая работа
Тема: Построение
экономической модели с
использованием симплекс-
метода .
Работу выполнил
студент УТФ-4-2
Кулаков О. А.
Оглавление .
Введение
Моделирование как метод научного познания.
Введение в симплекс-метод
1. Словесное описание
2. Математическое описание
3. Ограничения
4. Переменные
5. Целевая функция
Симплекс-метод .
1. Представление пространства решений стандартной задачи линейного
программирования
2. Вычислительные процедуры симплекс-метода
Анализ результатов .
1. Оптимальное решение
2. Статус ресурсов
3. Ценность ресурса
4. Максимальное изменение запаса ресурса
5. Максимальное изменение коэффициентов удельной
прибыли ( стоимости )
Моделирование как метод научного познания.
Моделирование в научных исследованиях стало применяться еще в
глубокой древности и постепенно захватывало все новые области
научных знаний : техническое конструирование , строительство и
архитектуру , астрономию , физику , химию , биологию и , наконец ,
общественные науки . Большие успехи и признание практически во всех
отраслях современной науки принес методу моделирования ХХ в . Однако
методология моделирования долгое время развивалась независимо
отдельными науками . Отсутствовала единая система понятий, единая
терминология . Лишь постепенно стала осознаваться роль моделирования
как универсального метода научного познания .
Термин "модель" широко используется в различных сферах
человеческой деятельности и имеет множество смысловых значений .
Рассмотрим только такие "модели", которые являются инструментами
получения знаний .
Модель - это такой материальный или мысленно представляемый
объект, который в процессе исследования замещает объект-оригинал
так, что его непосредственное изучение дает новые знания об объекте-
оригинале .
Под моделирование понимается процесс построения , изучения и
применения моделей . Оно тесно связано с такими категориями , как
абстракция , аналогия , гипотеза и др . Процесс моделирования
обязательно включает и построение абстракций , и умозаключения по
аналогии, и конструирование научных гипотез.
Главная особенность моделирования в том , что это метод
опосредованного познания с помощью объектов-заместителей . Модель
выступает как своеобразный инструмент познания , который
исследователь ставит между собой и объектом и с помощью которого
изучает интересующий его объект . Именно эта особенность метода
моделирования определяет специфические формы использования
абстракций , аналогий , гипотез , других категорий и методов познания .
Необходимость использования метода моделирования определяется
тем, что многие объекты ( или проблемы , относящиеся к этим объектам )
непосредственно исследовать или вовсе невозможно, или же это
исследование требует много времени и средств.
Моделирование - циклический процесс . Это означает , что за первым
четырехэтапным циклом может последовать второй , третий и т.д. При
этом знания об исследуемом объекте расширяются и точняются, а
исходная модель постепенно совершенствуется . Недостатки ,
обнаруженные после первого цикла моделирования , бусловленные
малым знанием объекта и ошибками в построении модели , можно
исправить в последующих циклах . В методологии моделирования ,
таким образом , заложены большие возможности саморазвития .
Словесное описание
Фирма , производящая некоторую продукцию осуществляет её
рекламу двумя способами через радиосеть и через телевидение . Стоимость
рекламы на радио обходится фирме в 5 $ , а стоимость телерекламы - в
100$ за минуту .
Фирма готова тратить на рекламу по 1000 $ в месяц . Так же
известно , что фирма готова рекламировать свою продукцию по радио по
крайней мере в 2 раза чаще , чем по телевидению .
Опыт предыдущих лет показал , что телереклама приносит в 25 раз
больший сбыт продукции нежели радиореклама .
Задача заключается в правильном распределении финансовых
средств фирмы .
Математическое описание .
X1 - время потраченное на радиорекламу .
X2 - время потраченное на телерекламу .
Z - искомая целевая функция , оражающая максимальный сбыт от 2-ух
видов рекламы .
X1=>0 , X2=>0 , Z=>0 ;
Max Z = X1 + 25X2 ;
5X1 + 100X2 0
Использование графического способа удобно только при решении задач ЛП
с двумя переменными . При большем числе переменных необходимо
применение алгебраического аппарата . В данной главе рассматривается
общий метод решения задач ЛП , называемый симплекс-методом .
Информация , которую можно получить с помощью симплекс-
метода , не ограничивается лишь оптимальными значениями переменных .
Симплекс-метод фактически позволяет дать экономическую
интерепритацию полученного решения и провести анализ модели на
чувствительность .
Процесс решения задачи линейного программирования носит
итерационный характер : однотипные вычислительные процедуры в
определенной последовательности повторяются до тех пор , пока не будет
получено оптимальное решение . Процедуры , реализуемые в рамках
симплекс-метода , требуют применения вычислительных машин - мощного
средства решения задач линейного программирования .
Симлекс-метод - это характерный пример итерационных
вычислений , используемых при решении большинства оптимизационных
задач . В данной главе рассматриваются итерационные процедуры такого
рода , обеспечивающие решение задач с помощью моделей исследования
операций .
В гл 2 было показано , что правая и левая части ограничений
линейной модели могут быть связаны знаками . Кроме того ,
переменные , фигурирующие в задачах ЛП , могут быть
неотрицательными или не иметь ограничения в знаке . Для построения
общего метода решения задач ЛП соответствующие модели должны быть
представлены в некоторой форме , которую назовем стандатрной формой
линейных оптимизационных моделей . При стандартной форме линейной
модели
1. Все ограничения записываются в виде равенств с неотрицательной
правой частью ;
2. Значения всех переменных модели неотрицательны ;
3. Целевая функция подлежит максимизации или минимизации .
Покажем , каким образом любую линейную модель можно привести к
стандартной .
Ограничения
1. Исходное ограничение , записанное в виде неравенства типа ) ,
можно представить в виде равенства , прибавляя остаточную переменную
к левой части ограничения ( вычитая избыточную переменную из левой
части ) .
Например , в левую часть исходного ограничения
5X1 + 100X2 0 , в результате чего исходное
неравенство обращается в равенство
5X1 + 100X2 + S1 = 1000 , S1 => 0
Если исходное ограничение определяет расход некоторого ресурса ,
переменную S1 следует интерпретировать как остаток , или
неиспользованную часть , данного ресурса .
Рассмотрим исходное ограничение другого типа :
X1 - 2X2 => 0
Так как левая часть этого ограничения не может быть меньше правой , для
обращения исходного неравенства в равенство вычтем из его левой части
избыточную переменную S2 > 0 . В результате получим
X1 - 2X2 - S2 = 0 , S2 => 0
2. Правую часть равенства всегда можно сделать неотрицательной ,
умножая оби части на -1 .
Например равенство X1 - 2X2 - S2 = 0 эквивалентно равенству - X1 + 2X2 +
S2 = 0
3. Знак неравенства изменяется на противоположный при умножении
обеих частей на -1 .
Например можно вместо 2 0
Переменные
Любую переменную Yi , не имеющую ограничение в знаке , можно
представить как разность двух неотрицательных переменных :
Yi=Yi'-Yi'', где Yi',Yi''=>0.
Такую подстановку следует использовать во всех ограничениях , которые
содержат исходную переменную Yi , а также в выражении для целевой
функции .
Обычно находят решение задачи ЛП , в котором фигурируют
переменные Yi' и Yi'' , а затем с помощью обратной подстановки
определяют величину Yi . Важная особенность переменных Yi' и Yi''
состоит в том , что при любом допустимом решении только одна из этих
переменных может принимать положительное значение , т.е. если Yi'>0 , то
Yi''=0, и наоборот . Это позволяет рассматривать Yi' как остаточную
переменную , а Yi'' - как избыточную переменную , причем лишь одна из
этих переменных может принимать положительное значение . Указанная
закономерность широко используется в целевом программировании и
фактически является предпосылкой для использования соответсвующих
преобразований в задаче 2.30
Целевая функция
Целевая функция линейной оптимизационной модели , представлена в
стандартной форме , может подлежать как максимизации , так и
минимизации . В некоторых случаях оказывается полезным изменить
исходную целевую функцию .
Максимизация некоторой функции эквивалентна минимизации той же
функции , взятой с противоположным знаком , и наоборот . Например
максимизация функции
Z = X1 + 25X2
эквивалентна минимизации функции
( -Z ) = -X1 - 25X2
Эквивалентность означает , что при одной и той же совокупности
ограничений оптимальные значения X1 , X2 , в обоих случаях будут
одинаковы . Отличие заключается только в том , что при одинаковых
числовых значениях целевых функций их знаки будут противоположны .
Симплекс-метод .
В вычислительной схеме симплекс-метода реализуется
упорядоченный процесс , при котором , начиная с некоторой исходной
допустимой угловой точки ( обычно начало координат ) , осуществляются
последовательные переходы от одной допустимой экстремальной точки к
другой до тех пор , пока не будет найдена точка , соответствующая
оптимальному решению .
Общую идею симплекс-метода можно проиллюстрировать на
примере модели , посроенной для нашей задачи . Пространство решений
этой задачи представим на рис. 1 . Исходной точкой алгоритма является
начало координат ( точка А на рис. 1 ) . Решение , соответствующее этой
точке , обычно называют начальным решением . От исходной точки
осуществляется переход к некоторой смежной угловой точке .
Выбор каждой последующей экстремальной точки при
использовании симплекс-метода определяется следующими двумя
правилами .
1. Каждая последующая угловая точка должна быть смежной с
предыдущей . Этот переход осуществляется по границам ( ребрам
) пространства решений .
2. Обратный переход к предшествующей экстремальной точке не
может производиться .
Таким образом , отыскание оптимального решения начинается с
некоторой допустимой угловой точки , и все переходы осуществляются
только к смежным точкам , причем перед новым переходом каждая из
полученных точек проверяется на оптимальность .
Определим пространство решений и угловые точки агебраически .
Требуемые соотнощшения устанавливаются из указанного в таблице
соответствия геометрических и алгебраических определений .
Геометрическое
определение
Алгебраическое определение
( симплекс метод )
Пространство решений
Ограничения модели
стандартной формы
Угловые точки
Базисное решение задачи в
стандартной форме
Представление пространства решений стандартной
задачи линейного программирования .
Линейная модель , построенная для нашей задачи и приведенная к
стандартной форме , имеет следующий вид :
Максимизировать
Z = X1 + 25X2 + 0S1 + 0S2
При ограничениях
5X1 + 100X2 + S1 = 1000
- X1 + 2X2 + S2 = 0
X1=>0 , X2=>0 , S1=>0 , S2=>0
Каждую точку пространства решений данной задачи ,
представленную на рис.1 , можно определить с помощью переменных X1 ,
X2 , S1 и S2 , фигурирующими в модели стандартной формы. При S1 = 0 и S2 = 0
ограничения модели эквивалентны равенствам , которые представляются
соответствующими ребрами пространства решений . Увеличение
переменных S1 и S2 будет соответствовать смещению допустимых точек с
границ пространства решений в его внутреннюю область. Переменные X1 ,
X2 , S1 и S2 , ассоциированные с экстремальными точками А , В , и С можно
упорядочить , исходя из того , какое значение ( нулевое или ненулевое )
имеет данная переменная в экстремальной точке .
Экстремальная
точка
Нулевые
переменные
Ненулевые
переменные
А
S2 , X2
S1 , X1
В
S1 , X2
S2 , X1
С
S1 , S2
X1 , X2
Анализируя таблицу , легко заметить две закономерности:
1. Стандартная модель содержит два уравнения и четыре
неизвестных , поэтому в каждой из экстремальных точек две ( = 4 - 2 )
переменные должны иметь нулевые значения .
2. Смежные экстремальные точки отличаются только одной пе-
ременной в каждой группе ( нулевых и ненулевых переменных ) ,
Первая закономерность свидетельствует о возможности опре-
деления экстремальных точек алгебраическим способом путем при-
равнивания нулю такого количества переменных , которое равно
разности между количеством неизвестных и числом уравнений .
В этом состоит сущность свойства однозначности экстремальных
точек . На рис. 1 каждой неэкстремальной точке соответствует
не более одной нулевой переменной . Так , любая точка внутренней
области пространства решений вообще не имеет ни одной нулевой
переменной, а любая неэкстремальная точка , лежащая на границе ,
всегда имеет лишь одну нулевую переменную .
Свойство однозначности экстремальных точек позволяет опре-
делить их алгебраическим методом. Будем считать , что линейная
модель стандартной формы содержит т уравнений и п ( т <= п ) не-
известных ( правые части ограничений — неотрицательные ) . Тогда
все допустимые экстремальные точки определяются как все одно-
значные неотрицательные решения системы m уравнений , в ко-
торых п — m переменных равны нулю.
Однозначные решения такой системы уравнений, получаемые
путем приравнивания к нулю ( п — т ) переменных , называются
базисными решениями . Если базисное решение удовлетворяет
требованию неотрицательности правых частей , оно называется
допустимым базисным решением. Переменные , имеющие нулевое
значение , называются небазисными переменными , остальные —
базисными переменными.
Из вышеизложенного следует , что при реализации симплекс-
метода алгебраическое определение базисных решений соответст-
вует идентификации экстремальных точек , осуществляемой при
геометрическом представлении пространства решений . Таким об-
разом , максимальное число итераций при использовании симплекс-
метода равно максимальному числу базисных решений задачи ЛП ,
представленной в стандартной форме . Это означает , что количество
итерационных процедур симплекс-метода не превышает
Cпт= n! / [ ( n - m )!m! ]
Вторая из ранее отмеченных закономерностей оказывается
весьма полезной для построения вычислительных процедур симп-
лекс-метода , при реализации которого осуществляется последова-
тельный переход от одной экстремальной точки к другой, смежной с ней .
Так как смежные экстремальные точки отличаются только
одной переменной, можно определить каждую последующую ( смеж-
ную) экстремальную точку путем замены одной из текущих не-
базисных ( нулевых ) переменных текущей базисной переменной.
В нашем случае получено решение , соответствующее точке А , откуда
следует осуществить переход в точку В . Для этого нужно увеличивать
небазисную переменную X2 от исходного нулевого значения до значе-
ния , соответствующего точке В ( см. рис. 1 ). В точке B переменная
S1 ( которая в точке А была базисной ) автоматически обращается в
нуль и , следовательно , становится небазисной переменной . Таким
образом , между множеством небазисных и множеством базисных
переменных происходит взаимообмен переменными X2 и S1 . Этот
процесс можно наглядно представить в виде следующей таблицы.
Экстремальная
точка
Нулевые
переменные
Ненулевые
переменные
А
S2 , X2
S1 , X1
В
S1 , X2
S2 , X1
Применяя аналогичную процедуру ко всем экстремальным точкам
рис. 1 , можно убедиться в том , что любую последующую экстре-
мальную точку всегда можно определить путем взаимной замены
по одной переменной в составе базисных и небазисных переменных
( предыдущей смежной точки ) . Этот фактор существенно упрощает
реализацию вычислительных процедур симплекс-метода.
Рассмотренный процесс взаимной замены переменных приводит
к необходимости введения двух новых терминов . Включаемой пе-
ременной называется небазисная в данный момент переменная ,
которая будет включена в множество базисных переменных на сле-
дующей итерации ( при переходе к смежной экстремальной точке ) .
Исключаемая переменная — это та базисная переменная , которая
на следующей итерации подлежит исключению из множества ба-
зисных переменных .
Вычислительные процедуры симплекс-метода .
Симплекс-алгоритм состоит из следующих шагов.
Шаг 0. Используя линейную модель стандартной формы , опреде-
ляют начальное допустимое базисное решение путем приравнива-
ния к нулю п — т ( небазисных ) переменных.
Шаг 1. Из числа текущих небазисных ( равных нулю ) перемен-
ных выбирается включаемая в новый базис переменная , увеличение
которой обеспечивает улучшение значения целевой функции. Если
такой переменной нет , вычисления прекращаются , так как текущее
базисное решение оптимально . В противном случае осуществляется
переход к шагу 2.
Шаг 2. Из числа переменных текущего базиса выбирается исклю-
чаемая переменная , которая должна принять нулевое значение ( стать
небазисной ) при введении в состав базисных новой переменной .
Шаг 3. Находится новое базисное решение , соответствующее
новым составам небазисных и базисных переменных . Осуществляется
переход к шагу 1.
Поясним процедуры симплекс-метода на примере решения нашей зада-
чи . Сначала необходимо представить целевую функцию и ограничения
модели в стандартной форме:
Z - X1 - 25X2 +0S1 -0S2 = 0 ( Целевая функция )
5X1 + 100X2 + S1 = 1000 ( Ограничение )
-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 )
2. Новое 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 , oак как коэффициент при этой переменной в
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 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 . Однако при этом
не фиксируется интервал значений увеличения запасов ресурса ,
при которых интенсивность улучшения целевой функции остается
постоянной . Для большинства практических ситуаций логично пред-
положить наличие верхнего предела увеличения запасов , при пре-
вышении которого соответствующее ограничение становится избы-
точным , что в свою очередь приводит к новому базисному решению
и соответствующим ему новым теневым ценам . Ниже определяется
нитервал значений запасов ресурса , при которых соответствую-
щее ограничение не становится избыточным .
Максимальное изменение запаса ресурса
При решении вопроса о том , запас какого из ресурсов следует
увеличивать в первую очередь , обычно используются теневые цены
Чтобы определить интервал значений изменения запаса ресурса ,
при которых теневая цена данного ресурса , ( фигурирующая в заклю-
чительной симплекс-таблице , остается неизменной , необходимо
выполнить ряд дополнительных вычислений . Рассмотрим сначала
соответствующие вычислительные процедуры , а затем покажем , как
требуемая информация может быть получена из симплекс-таблицы
для оптимального решения .
В нашей задаче запас первого ресурса изменился на ?? т. е. запас
бюджета составит 1000 + ?? . При положительной величине ?? запас
данного ресурса увеличивается , при отрицательной — уменьшается . Как
правило , исследуется ситуация , когда объем ресурса увеличивается
( ???> 0 ) , однако , чтобы получить результат в общем виде , рассмотрим
оба случая .
Как изменится симплекс-таблица при изменении величины за-
паса ресурса на????? Проще всего получить ответ на этот вопрос .
если ввести ???в правую часть первого ограничения начальной сим-
плекс-таблицы и затем выполнить все алгебраические преобразова-
ния , соответствующие последовательности итераций . Поскольку
правые части ограничений никогда не используются в качестве
ведущих элементов , то очевидно , что на каждой итерации ???будет
оказывать влияние только на правые части ограничений .
Уравнение
Значения элементов правой части на
соответствующих итерациях
( начало вычислений )
1
2 ( оптимум
)
Z
0
0
2455/11
1
1000
1000 + ??
1000/55 + ??
2
0
0
91/11
Фактически вce изменения правых частей ограничений , обуслов-
ленные введением ???, можно определить непосредственно по данным ,
содержащимся в симплекс-таблицах . Прежде всего заметим , что
на каждой итерации новая правая часть каждого ограничения пред-
ставляет собой сумму двух величин: 1) постоянной и 2) члена , ли-
нейно зависящего от ???. Постоянные соответствуют числам , которые
фигурируют на соответствующих итерациях в правых частях ограничений
симплекс-таблиц до введения ???. Коэффициенты при ???во вторых
слагаемых равны коэффициентам при S1 на той же итерации . Так ,
например , на последнеи итерации ( оптимальное решение ) постоянные
( 2455/11 ; 1000/55 ; 91/11 ) представляют собои числа , фигурирующие в правых
частях ограничении оптимальной симплекс-таблицы до
введения?????Коэффициенты ( 27/110 ; 1/55 ; 1/110 ) равны коэффициентам при
S1 в той же симплекс-таблице потому , что эта переменная связана только с
первым ограничением . Другими словами , при анализе влияния изменений
в правой части второго ограничения нужно пользоваться коэффициентами
при переменной S2 .
Какие выводы можно сделать из полученных результатов?
Так как введение ?? сказывается лишь на правой части симплекс-
таблицы , изменение запаса ресурса может повлиять только на
допустимость решения . Поэтому ?? не может принимать значений ,
при которых какая-либо из ( базисных ) переменных становится отри-
цательной . Из этого следует , что величина ?? должна быть огра-
ничена таким интервалом значений , при которых выполняется ус-
ловие неотрицательности правых частей ограничений в результи-
рующей симплекс-таблице , т . е .
X1 = 1000/55 + ( 1/55 )????> 0 ( 1 )
X2 = 91/11 + ( 1/110 )???=> 0 ( 2 )
Для определения допустимого интервала изменения ???рассмо-
трим два случая .
Случай 1: ????> 0 Очевидно , что оба неравнества при этом условии
всегда будут неотрицательными .
Случай 2: ??? - 1000
( 2 )
( 1/110 )???=> - 91/11 . Из этого следует , что ???=> - 1000
Объединяя результаты , полученные для обоих случаев , можно
сделать вывод , что при - 1000 <= ???<= + ??решение рассматриваемой зада-
чи всегда будет допустимым , любое значение ???, выходящее за
пределы указанного интервала , приведет к недопустимости решения и
новой совокупности базисных переменных .
Теперь рассмотрим в каких пределах может изменяться запас
ресурса 2 анализ проведем по аналогичной схеме :
Запас 2-ого ресурса изменился на ???т . е . запас рекламного времени
составит 0 + ?????Как изменилась симплекс-таблица при изменении
величины запаса ресурса на????i?ieee?no?e?iaaii ie?a .
Уравнение
Значения элементов правой части на
соответствующих итерациях
( начало вычислений )
1
2 ( оптимум
)
Z
0
0
2455/11
1
1000
1000
1000/55
2
0
0 + ??
91/11 + ??
Найдем интервал ограничивающий величину ??
X1 = 1000/55 - ( 50/55 )?? ?????
X2 = 91/11 + ( 1/22 )?? ?????
Для определения допустимого интервала изменения ???рассмо-
трим два случая .
Случай 1: ????> 0 Рaoaai ia?aaainoaa : ( 1 )
( 50/55 )??????1000/55 из этого неравенства следует , что ????????
????????
Очевидно , что 2-ое уравнение неотрицательно на данном участке .
Объединяя 2 уравнения для Случая 1 мы получим интервал для ?????
?????[ 0 ; 20 ]
Случай 2: ???< 0 . Рaoaai ia?aaainoaa : ( 1 )
( 50/55 )????????1000/55 . Из этого следует , что ????? 20
( 2 )
( 1/22 )????????91/11 . Из этого следует , что ???????????
Объединяя 2 уравнения для Случая 2 мы получим интервал для ?????
?????[ - 200 ; 0 ]
Объединяя 2 случая мы получим интервал [ - 200 ; 20 ]
Максимальное изменение коэффициентов удельной
прибыли ( стоимости )
Наряду с определением допустимых изменений запасов ресур-
сов представляет интерес и установление интервала допустимых
изменений коэффициентов удельной прибыли ( или стоимости ) .
Следует отметить , что уравнение целевой функции никогда не
используется в качестве ведущего уравнения . Поэтому лю-
бые изменения коэффициентов целевой функции окажут влияние
только на Z-уравнение результирующей симплекс-таблицы . Это
означает , что такие изменения могут сделать полученное решение
неоптимальным . Наша цель заключается в том , чтобы найти интер-
валы значений изменений коэффициентов целевой функции ( рас-
сматривая каждый из коэффициентов отдельно ) , при которых оп-
тимальные значения переменных остаются неизменными .
Чтобы показать, как выполняются соответствующие вычисле-
ния , положим , что удельный объем сбыта , ассоциированной с переменной
X1 изменяется от 1 до 1 + ???где ?? может быть как положительным , так и
отрицательным числом . Целевая функция в этом случае принимает
следующий вид:
Z = ( 1 + ????X1 + 25X2
Если воспользоваться данными начальной симплекс-таблицы и
выполнить все вычисления , необходимые для ( получения заключн-
тельной симплекс-таблицы , то последнее Z-уравнение будет выгля-
деть следующим образом:
Базисные
переменные
X1
X2
S1
S2
Решение
Z
0
0
27/110+1/55??
5/22-50/55??
2455/11+1000/55??
Коэффициенты при базисных переменных X1 , X2 и остаточных я равными
нулю . Это уравнение отличается от Z-уравнения до введения??? , только
наличием членов , содержащих ???. Коэффициенты при ?? равны
кoэффициентам при соответствующих переменных в Z-уравнении
симплекс-таблицы для полученного ранее оптимального решения
Базисные
переменные
X1
X2
S1
S2
Решение
X1
1
0
1/55
-50/55
1000/55
Мы рассматриваем X1 - уравнение , так как коэффициент именно при
этон переменной в выражении для целевои функции изменился
на??? .
Оптимальные значения переменных будут оставаться неизмен-
ными при значениях ???, удовлетворяющих условию неотрицатель-
ности ( задача на отыскание максимума ) всех коэффициентов при не-
базисных переменных в Z-уравнении . Таким образом , должны
выполняться следующие неравенства :
27/110 + 1/55???????
5/22 - 50/55???????
Из первого неравенства получаем , что ?? => - 13,5 , а из второго следует что
?? <= 1/4 . Эти результаты определяют пределы изменения коэффициента C1
в виде следующего соотношения : - 13,5 <= ?? <= 1/4 . Та-
ким образом , при уменьшении коэффициента целевой функции при
переменной X1 до значения , равного 1 + ( - 13,5 ) = - 12,5 или при его
увеличении до 1 + 13,5 = 14,5 оптимальные значения переменных остаются
неизменными . Однако оптимальное значение Z будет изменяться ( в
соответствии с выражением 2455/11 + 1000/55???, где - 13,5 <= ?? <= 1/4
X2 изменяется от 25 до 25 + ???где ?? может быть как положительным
, так и отрицательным числом . Целевая функция в этом случае принимает
следующий вид:
Z = ( 25 + ????X2 + X1
Все предыдущее обсуждение касалось исследования изменения
коэффициента при переменной , которой поставлено в соответствие
ограничение , фигурирующее в симплекс-таблице . Однако такое
ограничение имеется лишь в том случае , когда данная переменная
является базисной ( например X1 и X2 ) . Если переменная небазисная , то в
столбце , содержащем базисные переменные , она не будет представлена .
Любое изменение коэффициента целевой функции при небазисной
переменной приводит лишь к тому , что в заключительной симплкс-
таблице изменяется только этот коэффициент . Рассмотрим в качестве
иллюстрации случай , когда коэффициент при переменной S1 ( первой
остаточной переменной ) изменяется от 0 до ?????Выполнение
преобразований , необходимых для получения заключительной симплекс
таблицы , приводит к следующему результирующему Z-уравнению :
Базисные
переменные
X1
X2
S1
S2
Решение
Z
0
0
27/110+1/55??
5/2
2
2455/11
23
| |
