Реферат Курсовая Конспект
Построение экономической модели с использованием симплекс-метода - раздел Экономика, -4-5. Моделирование Как Метод Научного Познания. Моделирован...
|
-4-5. Моделирование как метод научного познания. Моделирование в научных исследованиях стало применяться еще в глубокой древности и постепенно захватывало все новые области научных знаний техническое конструирование , строительство и архитектуру , астрономию , физику , химию , биологию и , наконец , общественные науки . Большие успехи и признание практически во всех отраслях современной науки принес методу моделирования ХХ в . Однако методология моделирования долгое время развивалась независимо отдельными науками . Отсутствовала единая система понятий, единая терминология . Лишь постепенно стала осознаваться роль моделирования как универсального метода научного познания . Термин модель широко используется в различных сферах человеческой деятельности и имеет множество смысловых значений . Рассмотрим только такие модели, которые являются инструментами получения знаний . Модель - это такой материальный или мысленно представляемый объект, который в процессе исследования замещает объект-оригинал так, что его непосредственное изучение дает новые знания об объекте-оригинале . Под моделирование понимается процесс построения , изучения и применения моделей . Оно тесно связано с такими категориями , как абстракция , аналогия , гипотеза и др . Процесс моделирования обязательно включает и построение абстракций , и умозаключения по аналогии, и конструирование научных гипотез.
Главная особенность моделирования в том , что это метод опосредованного познания с помощью объектов-заместителей . Модель выступает как своеобразный инструмент познания , который исследователь ставит между собой и объектом и с помощью которого изучает интересующий его объект . Именно эта особенность метода моделирования определяет специфические формы использования абстракций , аналогий , гипотез , других категорий и методов познания . Необходимость использования метода моделирования определяется тем, что многие объекты или проблемы , относящиеся к этим объектам непосредственно исследовать или вовсе невозможно, или же это исследование требует много времени и средств.
Моделирование - циклический процесс . Это означает , что за первым четырехэтапным циклом может последовать второй , третий и т.д. При этом знания об исследуемом объекте расширяются и точняются, а исходная модель постепенно совершенствуется . Недостатки , обнаруженные после первого цикла моделирования , бусловленные малым знанием объекта и ошибками в построении модели , можно исправить в последующих циклах . В методологии моделирования , таким образом , заложены большие возможности саморазвития . Словесное описание Фирма , производящая некоторую продукцию осуществляет е рекламу двумя способами через радиосеть и через телевидение . Стоимость рекламы на радио обходится фирме в 5 , а стоимость телерекламы - в 100 за минуту . Фирма готова тратить на рекламу по 1000 в месяц . Так же известно , что фирма готова рекламировать свою продукцию по радио по крайней мере в 2 раза чаще , чем по телевидению . Опыт предыдущих лет показал , что телереклама приносит в 25 раз больший сбыт продукции нежели радиореклама . Задача заключается в правильном распределении финансовых средств фирмы . Математическое описание . X1 - время потраченное на радиорекламу . X2 - время потраченное на телерекламу . Z - искомая целевая функция , оражающая максимальный сбыт от 2-ух видов рекламы . X1 0 , X2 0 , Z 0 Max Z X1 25X2 5X1 100X2 1000 X1 -2X2 0 Использование графического способа удобно только при решении задач ЛП с двумя переменными . При большем числе переменных необходимо применение алгебраического аппарата . В данной главе рассматривается общий метод решения задач ЛП , называемый симплекс-методом . Информация , которую можно получить с помощью симплекс-метода , не ограничивается лишь оптимальными значениями переменных . Симплекс-метод фактически позволяет дать экономическую интерепритацию полученного решения и провести анализ модели на чувствительность . Процесс решения задачи линейного программирования носит итерационный характер однотипные вычислительные процедуры в определенной последовательности повторяются до тех пор , пока не будет получено оптимальное решение . Процедуры , реализуемые в рамках симплекс-метода , требуют применения вычислительных машин - мощного средства решения задач линейного программирования . Симлекс-метод - это характерный пример итерационных вычислений , используемых при решении большинства оптимизационных задач . В данной главе рассматриваются итерационные процедуры такого рода , обеспечивающие решение задач с помощью моделей исследования операций . В гл 2 было показано , что правая и левая части ограничений линейной модели могут быть связаны знаками , и . Кроме того , переменные , фигурирующие в задачах ЛП , могут быть неотрицательными или не иметь ограничения в знаке . Для построения общего метода решения задач ЛП соответствующие модели должны быть представлены в некоторой форме , которую назовем стандатрной формой линейных оптимизационных моделей . При стандартной форме линейной модели 1. Все ограничения записываются в виде равенств с неотрицательной правой частью 2. Значения всех переменных модели неотрицательны 3. Целевая функция подлежит максимизации или минимизации . Покажем , каким образом любую линейную модель можно привести к стандартной . Ограничения 1. Исходное ограничение , записанное в виде неравенства типа , можно представить в виде равенства , прибавляя остаточную переменную к левой части ограничения вычитая избыточную переменную из левой части . Например , в левую часть исходного ограничения 5X1 100X2 1000 вводистя остаточная переменная S1 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 4 записать - 2 - 4 , неравенство X1 - 2X2 0 заменить на - X1 2X2 0 Переменные Любую переменную Yi , не имеющую ограничение в знаке , можно представить как разность двух неотрицательных переменных YiYi -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 , X2S2 , X1СS1 , S2X1 , X2 Анализируя таблицу , легко заметить две закономерности 1. Стандартная модель содержит два уравнения и четыренеизвестных , поэтому в каждой из экстремальных точек две 4 - 2 переменные должны иметь нулевые значения . 2. Смежные экстремальные точки отличаются только одной пе-ременной в каждой группе нулевых и ненулевых переменных , Первая закономерность свидетельствует о возможности опре-деления экстремальных точек алгебраическим способом путем при-равнивания нулю такого количества переменных , которое равноразности между количеством неизвестных и числом уравнений .В этом состоит сущность свойства однозначности экстремальныхточек . На рис. 1 каждой неэкстремальной точке соответствуетне более одной нулевой переменной . Так , любая точка внутреннейобласти пространства решений вообще не имеет ни одной нулевойпеременной, а любая неэкстремальная точка , лежащая на границе ,всегда имеет лишь одну нулевую переменную . Свойство однозначности экстремальных точек позволяет опре-делить их алгебраическим методом. Будем считать , что линейнаямодель стандартной формы содержит т уравнений и п т п не-известных правые части ограничений неотрицательные . Тогдавсе допустимые экстремальные точки определяются как все одно-значные неотрицательные решения системы m уравнений , в ко-торых п m переменных равны нулю. Однозначные решения такой системы уравнений, получаемыепутем приравнивания к нулю п т переменных , называютсябазисными решениями . Если базисное решение удовлетворяеттребованию неотрицательности правых частей , оно называетсядопустимым базисным решением.
Переменные , имеющие нулевоезначение , называются небазисными переменными , остальные базисными переменными.
Из вышеизложенного следует , что при реализации симплекс-метода алгебраическое определение базисных решений соответст-вует идентификации экстремальных точек , осуществляемой пригеометрическом представлении пространства решений . Таким об-разом , максимальное число итераций при использовании симплекс-метода равно максимальному числу базисных решений задачи ЛП ,представленной в стандартной форме . Это означает , что количествоитерационных процедур симплекс-метода не превышает Cпт n n - m m Вторая из ранее отмеченных закономерностей оказываетсявесьма полезной для построения вычислительных процедур симп-лекс-метода , при реализации которого осуществляется последова-тельный переход от одной экстремальной точки к другой, смежной с ней . Так как смежные экстремальные точки отличаются толькоодной переменной, можно определить каждую последующую смеж-ную экстремальную точку путем замены одной из текущих не-базисных нулевых переменных текущей базисной переменной.В нашем случае получено решение , соответствующее точке А , откуда следует осуществить переход в точку В . Для этого нужно увеличивать небазисную переменную X2 от исходного нулевого значения до значе-ния , соответствующего точке В см. рис. 1 . В точке B переменнаяS1 которая в точке А была базисной автоматически обращается внуль и , следовательно , становится небазисной переменной . Такимобразом , между множеством небазисных и множеством базисныхпеременных происходит взаимообмен переменными X2 и S1 . Этотпроцесс можно наглядно представить в виде следующей таблицы.
Экстремальная точкаНулевые переменныеНенулевые переменныеАS2 , X2 S1 , X1 ВS1 , X2S2 , 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 имеют нулевое значение . Поэтому , преобразовав уравнение целевой функции так , чтобы его правая часть стала равной нулю , можно убедиться в том , что правые части уравнений целевой функции и ограничений полностью характеризуют начальное решение . Это имеет место во всех случаях , когда начальный базис состоит из остаточных переменных.
Полученные результаты удобно представить в виде таблицы Базисные переменныеZX1X2S1S2РешениеZ1-1- 25000Z - уравнениеS105100101000S1 -уравнениеS20-12010S2 - уравнение Эта таблица интерпретируется следующим образом.
Столбец Базисные переменные содержит переменные пробного базиса S1 ,S2 , значения которых приведены в столбце Решение . Приэтом подразумевается , что небазисные переменные X1 и X2 не пред-ставленные в первом столбце равны нулю . Значение целевой функ-ции Z 10 250 01000 01 равно нулю , что и показано в последнем столбце таблицы . Определим , является ли полученное пробное решение наи-лучшим оптимальным . Анализируя Z - уравнение , нетрудно заме-тить , что обе небазисные переменные X1 и X2 , равные нулю , имеютотрицательные коэффициенты . Всегда выбирается переменная с большим абсолютным значением отрицательного коэффициента в Z - уравнении , так как практический опыт вычислений показывает , что в этом случае оптимум достигается быстрее . Это правило составляет основу используемого в вычислительнойсхеме симплекс-метода условия оптимальности , которое состоит втом , что , если в задаче максимизации все небазисные переменные вZ - уравнении имеют неотрицательные коэффициенты , полученное пробное решение является оптимальным . В противном случае в ка-честве новой базисной переменной следует выбрать ту , которая имеетнаибольший по абсолютной величине отрицательный коэффициент . Применяя условие оптимальности к исходной таблице , выберемв качестве переменной , включаемой в базис , переменную Х2 . Исклю-чаемая переменная должна быть выбрана из совокупности базисныхпеременных S1 , S2 . Процедура выбора исключаемой переменной предполагает проверку условия допустимости , требующего , чтобы в качестве исключаемой переменной выбиралась та из пере-менных текущего базиса , которая первой обращается в нуль при уве-личении включаемой переменной X2 вплоть до значения , соответствующего смежной экстремальной точке . Интересующее нас отношение фиксирующее искомую точку пе-ресечения и идентифицирующее исключаемую переменную можноопределить из симплекс-таблицы.
Для этого в столбце , соответствующем вводимой переменной X2 , вычеркиваются отрицательные и нулевые элементы ограничений . Затем вычисляются отношения постоянных , фигурирующих в правых частях этих ограничений , к оставшимся элементам столбца , соответствующего вводимой переменной X2 . Исключаемой переменной будет та переменная текущего базиса , для которой указанное выше отношение минимально.
Начальная симплекс-таблица для нашей задачи , получаемая после проверки условия допустимости т. е. после вычисления соответствующих отношений и определения исключаемой переменной , воспроизведена ниже . Для удобства описания вычислительных процедур , осуществляемых на следующей итерации , введем ряд необходимых определений . Столбец симплекс-таблицы , ассоциированный с вводимой переменной , будем называть ведущим столбцом . Строку , соответствующую исключаемой переменной , назовем ведущей строкой уравнением , а элемент таблицы , находящийся на пересечении ведущего столбца и ведущей строки , будем называть ведущим элементом . После того как определены включаемая и исключаемая пере-менные с использованием условий оптимальности и допустимости ,следующая итерация поиск нового базисного решения осуществля-ется методом исключения переменных , или методом Гаусса Жордана . Этот процесс изменения базиса включает вычислительные процедуры двух типов . Тип 1 формирование ведущего уравнения . Новая ведущая строка Предыдущая ведущая строка Ведущий элемент Тип 2 формирование всех остальных уравнений , включая Z - yравнение . Новое уравнение Предыдущее уравнение й Коэффициент щ к ведущего столбца к Новая ведущая строка . к предыдущего к л уравнения ы Выполнение процедуры типа 1 приводит к тому , что в новомведущем уравнении ведущий элемент становится равным единице .В результате осуществления процедуры типа 2 все остальные коэф-фициенты , фигурирующие в ведущем столбце , становятся равныминулю . Это эквивалентно получению базисного решения путем ис-ключения вводимой переменной из всех уравнений , кроме ведущего . Применяя к исходной таблице процедуру 1 , мы делим S2 - уравнение на ведущий элемент , равный 1 . Базисные переменныеZX1X2S1S2РешениеZS1S20-1210120 Чтобы составить новую симплекс-таблицу , выполним необходимые вычислительные процедуры типа 2 . 1. Новое Z - уравнение . старое Z - уравнение 1 -1 -25 0 0 0 - -25 0 -12 1 0 12 0 1 -1312 0 0 1212 0 2. Новое S1 - уравнение старое S1 - уравнение 0 5 100 1 0 1000 - 100 0 -12 1 0 12 0 0 55 0 1 -50 1000 Новая симплекс-таблица будет иметь вид Базисные переменныеZX1X2S1S2РешениеZ1-13120012120 Z - уравнениеS105501-501000S1 -уравнениеX20-1210120X2 - уравнение В новом решении X1 0 и S2 0 . Значение Z не изменяется . Заметим , что новая симплекс-таблица обладает такими же ха-рактеристиками , как и предыдущая только небазисные переменные X1 и S2 равны нулю , а значения базисных переменных , как и раньше ,представлены в столбце Решение . Это в точности соответствуетрезультатам , получаемым при использовании метода Гаусса Жор-дана . Из последней таблицы следует , что на очередной итерации в со-ответствии с условием оптимальности в качестве вводимой перемен-ной следует выбрать X1 , так как коэффициент при этой переменной в Z-ypaвнении равен -1312 . Исходя из условия допустимости , определяем , что исключаемой переменной будет S1 . Отношения , фигурирующие в правой части таблицы , показывают , что в новом базисном решении значение включаемой переменной X1 будет равно 100055 минимальному отношению . Это приводит к увеличению целевой функции на 100055 -1312 245511 . К получению симплекс-таблицы , соответствующей новой итерации , приводят следующие вычислительные операции метода Гаусса Жордана. 1 Новое ведущее S1 - уравнение Предыдущее S1 - уравнение 55 . Базисные переменныеZX1X2S1S2РешениеZS1010155- 5055100055X2 2 Новое Z - уравнение Предыдущее Z - уравнение - -1312 Новое ведущее уравнение 1 -1312 0 0 1212 0 - -1312 0 1 0 155 -5055 100055 1 0 0 27110 522 245511 3 Новое X2 - уравнение Предыдущее X2 - уравнение - -12 Новое ведущее уравнение 0 -12 1 0 12 0 12 0 1 0 155 -5055 100055 0 0 1 1110 122 9111 В результате указанных преобразований получим следующую симп-лекс-таблицу . Базисные переменныеZX1X2S1S2РешениеZ1002711052224 5511X1010155-5055100055X200111101229111В новом базисном решении X1100055 и X29111 . Значение Z увеличилось с 0 предыдущая симплекс-таблица до 245511 последняя симплекс-таблица . Этот результирующий прирост целевой функции обусловлен увеличением X1 от О до 100055 , так как из Z - строки предыдущей симплекс-таблицы следует , что возрастанию данной переменной на единицу соответствует увеличение целевой функции на -1312 . Последняя симплекс-таблица соответствует оптимальному реше-нию задачи, так как в Z - уравнении ни одна из небазисных переменных не фигурирует с отрицательным коэффициентом.
Получением этой pезультирующей таблицы и завершаются вычислительные процедуры симплекс-метода . В рассмотренном выше примере алгоритм симплекс-метода ис-пользован при решении задачи , в которой целевая функция подлежала максимизации . В случае минимизации целевой функции в этомалгоритме необходимо изменить только условие оптимальности в качестве новой базисной переменнойследует выбирать ту переменную , которая в Z - уравнении имеет наибольший положительный коэффициент . Условия допустимости в обоих случаях максимизации и минимизации одинаковы . Представляется целесообразным дать теперь окончательные формулировки обоим условиям , используемым в симплекс-методе . Условие оптимальности . Вводимой переменной в задаче максимизации минимизации является небазисная переменная , имеющая в Z -уравнении наибольший отрицательный положительный коэффициент , В случае равенства таких коэффициентов для нескольких небазисных переменных выбор делается произвольно , если все коэффициенты при небазисных переменных в Z - уравнении неотрицательны неположительны , полученное решение является оптимальным . Условие допустимости , в задачах максимизации и минимизации в качестве исключаемой переменной выбирается та базисная переменная , для которой отношение постоянной в правой части соответствующего ограничения к положительному коэффициенту ведущего столбца минимально.
В случае равенства этого отношения для нескольких базисных переменных выбор делается произвольно . Оптимальное решение С точки зрения практического использования результатов ре-шения задач ЛП классификация переменных , предусматривающаяих разделение на базисные и небазнсные , не имеет значения и прианализе данных , характеризующих оптимальное решение , можетне учитываться . Переменные , отсутствующие в столбце Базисныепеременные , обязательно имеют нулевое значение . Значения ос-тальных переменных приводятся в столбце Решение . При интер-претации результатов оптимизации в нашей задаче нас прежде всего интересует количество времени , которое закажет наша фирма на радио и телевидение , т. е. значения управляемых переменных X1 и X2 . Используя данные , содержащиеся в симплекс-таблице для оптимального решения , основные результаты можно представить в следующем виде Управляемые переменныеОптимальные значенияРешениеX1100055Время выделяемое фирмой на телерекламу X29111Время выделяемое фирмой на радиорекламуZ245511Прибыль получаемая от рекламы . Заметим, что Z X1 25X2 100055 25 9111 245511 . Это решение соответствует данным заключительной симплекс- таблицы . Статус ресурсов Будем относить ресурсы к дефицитным или недифицитным в зависимости от того , полное или частичное их использо-вание предусматривает оптимальное решение задачи . Сейчас цельсостоит в том , чтобы получить соответствующую информацию непос-редственно из симплекс-таблицы для оптимального решения . Од-нако сначала следует четко уяснить следующее . Говоря о ресурсах ,фигурирующих в задаче ЛП , мы подразумеваем , что установленынекоторые максимальные пределы их запасов , поэтому в соответст-вующих исходных ограничениях должен использоваться знак .Следовательно , ограничения со знаком не могут рассматриватьсякак ограничения на ресурсы . Скорее , ограничения такого типа отра-жают то обстоятельство , что решение должно удовлетворять опре-деленным требованиям , например обеспечению минимального спро-са или минимальных отклонений от установленных структурныххарактеристик производства сбыта . В модели , построенной для нашей задачи , фигурирует ограничение со знаком . Это требование можно рассматривать как ограничение на соответствующий ресурс , так как увеличение спроса на продукцию эквивалентно расширению представительства фирмы на рынке сбыта . Из вышеизложенного следует , что статус ресурсов дефицитныйили недефицитный для любой модели ЛП можно установить не-посредственно из результирующей симплекс-таблицы , обращая вни-мание на значения остаточных переменных . Применительно к нашей задаче можно привести следующую сводку результатов РесурсыОстаточная переменнаяСтатус ресурсаОграничение по бюджету S1ДефицитныйПревышение времени рекламы радио над теле S2Дефицитный Положительное значение остаточной переменной указывает нанеполное использование соответствующего ресурса , т . е . данныйресурс является недефицятным.
Если же остаточная переменная рав-на нулю , это свидетельствует о полном потреблении соответствующе- го ресурса.
Из таблицы видно , что наши ресурсы являются дефицитными . В случае недефицитности любое увиличение ресурсов сверх установленного максимального значения привело бы лишь к тому , что они стали бы еще более недефнинтными . Оптимальное решение задачи при этом осталось бы неизменным.
Ресурсы, увеличение запасов которых позволяет улучшить ре-шение увеличить прибыль , это остаточные переменные S1 и S2 , по-скольку из симплекс-таблицы для оптимального решения видно ,что они дефицитные . В связи с этим логично поставить следующийвопрос какому из дефицитных ресурсов следует отдать предпочте-ние при вложении дополнительных средств на увеличение их запа-сов , с тем чтобы получить от них максимальную отдачу Ответ наэтот вопрос будет дан в следующем подразделе этой главы , где рас-сматривается ценность различных ресурсов . Ценность ресурса Ценность ресурса характеризуется величиной улучшения опти-мального значения Z , приходящегося на единицу прироста объемаданного ресурса . Информация для оптимального решения задачи представлена в симплекс-таблице . Обратим внимание на значения коэффициентов Z - уравнения , стоящих при переменных начального базиса S1 и S2 . Выделим для удобства соответстзующую часть симплекс-таблицы Базисные переменныеZX1X2S1S2РешениеZ1002711052224 5511 Как следует из теории решения задач ЛП , ценность ресурсов всегда можно определить по значениям коэффициентов при переменных начального базиса , фигурирующих в Z - уравнении оптимальной симплекс-таблицы , таким образом Y1 27110 , а Y2 522 . Покажем , каким образом аналогичный результат можно получить непосредственно из симплекс-таблицы для оптимального решения . Рассмотрим Z - уравнение симплекс-таблицы для оптимального решения нашей задачи Z 245511 - 27110S1 522S2 . Положительное приращение переменной S1 относительно ее текущегонулевого значения приводит к пропорциональному уменьшению Z ,причем коэффициент пропорциональности равен 27110 . Но , как следует из первого ограничения модели 5X1 100X2 S1 1000 увеличение S1 эквивалентно снижению количества денег выделеных на рекламу далее мы будем использовать в тексте , как первый ресурс . Отсюда следует , что уменьшение количества денег выделеных на рекламу вызывает пропорциональное уменьшение целевой функции с тем же коэффициентом пропорциональности , равным 27110 . Так какмы оперируем с линейными функциями , полученный вывод можнообобщить , считая , что и увеличение количества денег выделеных на рекламу эквивалентное введению избыточной переменной S1 0 приводит к пропорциональному увеличению Z с тем же коэффициентом пропорциональности , равным 27110 . Аналогичные рассуждения справед-ливы для ограничения 2 . Несмотря на то что ценность различных ресурсов , определяемаязначениями переменных Yi , была представлена в стоимостном выражении , ее нельзя отождествлять с действительными це-нами , по которым возможна закупка соответствующих ресурсов .На самом деле речь идет о некоторой мере , имеющей экономическуюприроду н количественно характеризующей ценность ресурса только относительно полученного оптимального значения целевой функции .При изменении ограничении модели соответствующие экономическиеоценки будут меняться даже тогда , когда оптимизируемый процесспредполагает применение тех же ресурсов . Поэтому при характерис-тике ценности ресурсов экономисты предпочитают использоватьтакие терминыт , как теневая цена , скрытая цена , или более специ-фичный термин двойственная оценка . Заметим , что теневая цена ценность ресурса характеризует ин-тенсивность улучшения оптимального значения Z . Однако при этомне фиксируется интервал значений увеличения запасов ресурса ,при которых интенсивность улучшения целевой функции остаетсяпостоянной . Для большинства практических ситуаций логично пред-положить наличие верхнего предела увеличения запасов , при пре-вышении которого соответствующее ограничение становится избы-точным , что в свою очередь приводит к новому базисному решениюи соответствующим ему новым теневым ценам . Ниже определяетсянитервал значений запасов ресурса , при которых соответствую-щее ограничение не становится избыточным . Максимальное изменение запаса ресурса При решении вопроса о том , запас какого из ресурсов следуетувеличивать в первую очередь , обычно используются теневые ценыЧтобы определить интервал значений изменения запаса ресурса ,при которых теневая цена данного ресурса , фигурирующая в заклю-чительной симплекс-таблице , остается неизменной , необходимо выполнить ряд дополнительных вычислений . Рассмотрим сначала соответствующие вычислительные процедуры , а затем покажем , кактребуемая информация может быть получена из симплекс-таблицыдля оптимального решения . В нашей задаче запас первого ресурса изменился на D1 т. е. запас бюджета составит 1000 D1 . При положительной величине D1 запас данного ресурса увеличивается , при отрицательной уменьшается . Как правило , исследуется ситуация , когда объем ресурса увеличивается D1 0 , однако , чтобы получить результат в общем виде , рассмотрим оба случая . Как изменится симплекс-таблица при изменении величины за-паса ресурса на D1 Проще всего получить ответ на этот вопрос .если ввести D1 в правую часть первого ограничения начальной сим-плекс-таблицы и затем выполнить все алгебраические преобразова-ния , соответствующие последовательности итераций . Посколькуправые части ограничений никогда не используются в качествеведущих элементов , то очевидно , что на каждой итерации D1 будетоказывать влияние только на правые части ограничений . УравнениеЗначения элементов правой части на соответствующих итерациях начало вычислений 12 оптимум Z00245511110001000 D1100055 D12009111 Фактически вce изменения правых частей ограничений , обуслов-ленные введением D1 , можно определить непосредственно по данным ,содержащимся в симплекс-таблицах . Прежде всего заметим , чтона каждой итерации новая правая часть каждого ограничения пред-ставляет собой сумму двух величин 1 постоянной и 2 члена , ли-нейно зависящего от D1 . Постоянные соответствуют числам , которыефигурируют на соответствующих итерациях в правых частях ограничений симплекс-таблиц до введения D1 . Коэффициенты при D1 во вторых слагаемых равны коэффициентам при S1 на той же итерации . Так , например , на последнеи итерации оптимальное решение постоянные 245511 100055 9111 представляют собои числа , фигурирующие в правых частях ограничении оптимальной симплекс-таблицы до введения D1. Коэффициенты 27110 155 1110 равны коэффициентам при S1 в той же симплекс-таблице потому , что эта переменная связана только с первым ограничением . Другими словами , при анализе влияния изменений в правой части второго ограничения нужно пользоваться коэффициентами при переменной S2 . Какие выводы можно сделать из полученных результатовТак как введение D1 сказывается лишь на правой части симплекс-таблицы , изменение запаса ресурса может повлиять только надопустимость решения . Поэтому D1 не может принимать значений ,при которых какая-либо из базисных переменных становится отри-цательной . Из этого следует , что величина D1 должна быть огра-ничена таким интервалом значений , при которых выполняется ус-ловие неотрицательности правых частей ограничений в результи-рующей симплекс-таблице , т . е . X1 100055 155 D1 0 1 X2 9111 1110 D1 0 2 Для определения допустимого интервала изменения D1 рассмо-трим два случая . Случай 1 D1 0 Очевидно , что оба неравнества при этом условии всегда будут неотрицательными . Случай 2 D1 0 . Решаем неравенства 1 155 D1 - 100055 . Из этого следует , что D1 - 1000 2 1110 D1 - 9111 . Из этого следует , что D1 - 1000 Объединяя результаты , полученные для обоих случаев , можносделать вывод , что при - 1000 D1 решение рассматриваемой зада-чи всегда будет допустимым , любое значение D1 , выходящее запределы указанного интервала , приведет к недопустимости решения и новой совокупности базисных переменных . Теперь рассмотрим в каких пределах может изменяться запас ресурса 2 анализ проведем по аналогичной схеме Запас 2-ого ресурса изменился на D2 т . е . запас рекламного времени составит 0 D2 . Как изменилась симплекс-таблица при изменении величины запаса ресурса на D2 проиллюстрировано ниже . УравнениеЗначения элементов правой части на соответствующих итерациях начало вычислений 12 оптимум Z00245511110001000 100055 200 D29111 D2 Найдем интервал ограничивающий величину D2 X1 100055 - 5055 D2 1 X2 9111 122 D2 2 Для определения допустимого интервала изменения D1 рассмо-трим два случая . Случай 1 D2 0 Решаем неравенства 1 5055 D2 - 200 Объединяя 2 уравнения для Случая 2 мы получим интервал для D2 . D2 О - 200 0 Объединяя 2 случая мы получим интервал - 200 20 Максимальное изменение коэффициентов удельной прибыли стоимости Наряду с определением допустимых изменений запасов ресур-сов представляет интерес и установление интервала допустимыхизменений коэффициентов удельной прибыли или стоимости . Следует отметить , что уравнение целевой функции никогда не используется в качестве ведущего уравнения . Поэтому лю-бые изменения коэффициентов целевой функции окажут влияниетолько на Z-уравнение результирующей симплекс-таблицы . Этоозначает , что такие изменения могут сделать полученное решениенеоптимальным . Наша цель заключается в том , чтобы найти интер-валы значений изменений коэффициентов целевой функции рас-сматривая каждый из коэффициентов отдельно , при которых оп-тимальные значения переменных остаются неизменными . Чтобы показать, как выполняются соответствующие вычисле-ния , положим , что удельный объем сбыта , ассоциированной с переменной X1 изменяется от 1 до 1 d1 где d1 может быть как положительным , так и отрицательным числом . Целевая функция в этом случае принимает следующий вид Z 1 d1 X1 25X2 Если воспользоваться данными начальной симплекс-таблицы ивыполнить все вычисления , необходимые для получения заключн-тельной симплекс-таблицы , то последнее Z-уравнение будет выгля-деть следующим образом Базисные переменныеX1X2S1S2РешениеZ0027110155d152 2-5055d1245511100055d1 Коэффициенты при базисных переменных X1 , X2 и остаточных я равными нулю . Это уравнение отличается от Z-уравнения до введения d1 , только наличием членов , содержащих d1 . Коэффициенты при d1 равны кoэффициентам при соответствующих переменных в Z-уравнении симплекс-таблицы для полученного ранее оптимального решения Базисные переменныеX1X2S1S2РешениеX110155-5055100 055 Мы рассматриваем X1 - уравнение , так как коэффициент именно приэтон переменной в выражении для целевои функции изменилсяна d1 . Оптимальные значения переменных будут оставаться неизмен-ными при значениях d1 , удовлетворяющих условию неотрицатель-ности задача на отыскание максимума всех коэффициентов при не-базисных переменных в Z-уравнении . Таким образом , должны выполняться следующие неравенства 27110 155d1 0 522 - 5055d1 0 Из первого неравенства получаем , что d1 - 13,5 , а из второго следует что d1 14 . Эти результаты определяют пределы изменения коэффициента C1 в виде следующего соотношения - 13,5 d1 14 . Та-ким образом , при уменьшении коэффициента целевой функции припеременной X1 до значения , равного 1 - 13,5 - 12,5 или при его увеличении до 1 13,5 14,5 оптимальные значения переменных остаютсянеизменными . Однако оптимальное значение Z будет изменяться в соответствии с выражением 245511 100055d1 , где - 13,5 d1 14 X2 изменяется от 25 до 25 d2 где d2 может быть как положительным , так и отрицательным числом . Целевая функция в этом случае принимает следующий вид Z 25 d2 X2 X1 Все предыдущее обсуждение касалось исследования изменения коэффициента при переменной , которой поставлено в соответствие ограничение , фигурирующее в симплекс-таблице . Однако такое ограничение имеется лишь в том случае , когда данная переменная является базисной например X1 и X2 . Если переменная небазисная , то в столбце , содержащем базисные переменные , она не будет представлена . Любое изменение коэффициента целевой функции при небазисной переменной приводит лишь к тому , что в заключительной симплкс-таблице изменяется только этот коэффициент . Рассмотрим в качестве иллюстрации случай , когда коэффициент при переменной S1 первой остаточной переменной изменяется от 0 до d3 . Выполнение преобразований , необходимых для получения заключительной симплекс таблицы , приводит к следующему результирующему Z-уравнению Базисные переменныеX1X2S1S2РешениеZ0027110155d152 2245511.
– Конец работы –
Используемые теги: Построение, экономической, модели, использованием, симплекс-метода0.053
Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Построение экономической модели с использованием симплекс-метода
Если этот материал оказался полезным для Вас, Вы можете сохранить его на свою страничку в социальных сетях:
Твитнуть |
Новости и инфо для студентов