рефераты конспекты курсовые дипломные лекции шпоры

Реферат Курсовая Конспект

Построение экономической модели с использованием симплекс-метода

Построение экономической модели с использованием симплекс-метода - раздел Экономика, -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

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Построение экономической модели с использованием симплекс-метода

Что будем делать с полученным материалом:

Если этот материал оказался полезным для Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Еще рефераты, курсовые, дипломные работы на эту тему:

Предмет «Истории экономических учений», исторический процесс возникновения, развития и смены экономических идей. Периодизация истории экономических учений. Место учебной дисциплины в системе экономических наук».
Основные этапы развития экономических учений…3. Исторический процесс возникновения, развития и смены экономических идей…15 Заключение… …21 Список… Историю экономических учений интересует, под влиянием каких условий меняются… История экономических учений помогает понять общую направ¬ленность эволюции экономической науки, трансформацию ее…

Понятие информ., свойства информ., экономическая информ., свойства экономической информ., классификация экономической информ
Информ универсальный ресурс потребляемый всеми сферами экономики и представляющий собой совокупность сведений фактов знаний об окружающих ее... Информ должна рассматриваться в х аспектах... синтетический связан только со способом передачи информ...

Лекция 1. ПРЕДМЕТ ЭКОНОМИЧЕСКОЙ ТЕОРИИ. МЕТОДЫ ИССЛЕДОВАНИЯ ЭКОНОМИЧЕСКИХ ЯВЛЕНИЙ Предмет экономической теории как науки определился далеко не сразу
Предмет экономической теории как науки определился далеко не сразу он... Основные вопросы лекции...

Предмет и метод экономической теории Экономическая теория как часть системы экономических наук
Экономическая теория как часть системы экономических наук... Существует разветвленная система наук которые изучают различные аспекты хозяйственной экономической жизни общества...

Построение модели бизнес-процесса с использованием диаграмм потоков данных
Аэрокосмического приборостроения... РУКОВОДСТВО...

Построение модели бизнес-процесса с использованием сетей Петри
Аэрокосмического приборостроения... РУКОВОДСТВО...

ПОСТРОЕНИЕ ПРОЦЕССОВ И ПРОЦЕССНОЙ МОДЕЛИ СИСТЕМЫ МЕНЕДЖМЕНТА КАЧЕСТВА ПРЕДПРИЯТИЯ С ИСПОЛЬЗОВАНИЕМ MICROSOFT VISIO
ПОСТРОЕНИЕ ПРОЦЕССОВ И ПРОЦЕССНОЙ МОДЕЛИ СИСТЕМЫ МЕНЕДЖМЕНТА КАЧЕСТВА ПРЕДПРИЯТИЯ С ИСПОЛЬЗОВАНИЕМ MICROSOFT...

Экономика как сфера жизнедеятельности общества. Предмет и функции экономической теории. Экономические категории. Экономические законы
Целью функционирования экономики является удовлетворение экономических потребностей человека потребностей в товарах и услугах... Нужда толкает человека к тому чтобы приложить усилия для удовлетворения своих... Потребность нужда имеющая конкретные очертания которые определены особенностью личности человека эк развитием...

Использование сейсмических данных для построения модели резервуара
На сайте allrefs.net читайте: "Использование сейсмических данных для построения модели резервуара"

Прибыль – конечный финансово – экономический результат предприятия: формирование и использование
Необходимо более быстрое реагирование на изменение хозяйственной ситуации с целью поддержания устойчивого финансового состояния и постоянного… Предприятие самостоятельно планирует на основе договоров, заключенных с… Самостоятельно планируемым показателем в числе других стала прибыль.

0.028
Хотите получать на электронную почту самые свежие новости?
Education Insider Sample
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Реклама
Соответствующий теме материал
  • Похожее
  • По категориям
  • По работам