Построение экономической модели с использованием симплекс-метода - (реферат)
Дата добавления: март 2006г.
Курсовая работа
Тема: Построение экономической модели с использованием симплекс-метода .
Работу выполнил
студент УТФ-4-2
Кулаков О. А.
Оглавление .
Введение
Моделирование как метод научного познания.
Введение в симплекс-метод
Словесное описание
Математическое описание
Ограничения
Переменные
Целевая функция
Симплекс-метод .
Представление пространства решений стандартной задачи линейного программирования
Вычислительные процедуры симплекс-метода
Анализ результатов .
Оптимальное решение
Статус ресурсов
Ценность ресурса
Максимальное изменение запаса ресурса
Максимальное изменение коэффициентов удельной
прибыли ( стоимости )
Моделирование как метод научного познания.
Моделирование в научных исследованиях стало применяться еще в глубокой древности и постепенно захватывало все новые области научных знаний : техническое конструирование , строительство и архитектуру , астрономию , физику , химию , биологию и , наконец , общественные науки . Большие успехи и признание практически во всех отраслях современной науки принес методу моделирования ХХ в . Однако методология моделирования долгое время развивалась независимо отдельными науками . Отсутствовала единая система понятий, единая терминология . Лишь постепенно стала осознаваться роль моделирования как универсального метода научного познания .
Термин "модель" широко используется в различных сферах человеческой деятельности и имеет множество смысловых значений . Рассмотрим только такие "модели", которые являются инструментами получения знаний . Модель - это такой материальный или мысленно представляемый объект, который в процессе исследования замещает объект-оригинал так, что его непосредственное изучение дает новые знания об объекте-оригинале .
Под моделирование понимается процесс построения , изучения и применения моделей . Оно тесно связано с такими категориями , как абстракция , аналогия , гипотеза и др . Процесс моделирования обязательно включает и построение абстракций , и умозаключения по аналогии, и конструирование научных гипотез. Главная особенность моделирования в том , что это метод опосредованного познания с помощью объектов-заместителей . Модель выступает как своеобразный инструмент познания , который исследователь ставит между собой и объектом и с помощью которого изучает интересующий его объект . Именно эта особенность метода моделирования определяет специфические формы использования абстракций , аналогий , гипотез , других категорий и методов познания .
Необходимость использования метода моделирования определяется тем, что многие объекты ( или проблемы , относящиеся к этим объектам ) непосредственно исследовать или вовсе невозможно, или же это исследование требует много времени и средств.
Моделирование - циклический процесс . Это означает , что за первым четырехэтапным циклом может последовать второй , третий и т. д. При этом знания об исследуемом объекте расширяются и точняются, а исходная модель постепенно совершенствуется . Недостатки , обнаруженные после первого цикла моделирования , бусловленные малым знанием объекта и ошибками в построении модели , можно исправить в последующих циклах . В методологии моделирования , таким образом , заложены большие возможности саморазвития .
Словесное описание
Фирма , производящая некоторую продукцию осуществляет её рекламу двумя способами через радиосеть и через телевидение . Стоимость рекламы на радио обходится фирме в 5 $ , а стоимость телерекламы - в 100$ за минуту . Фирма готова тратить на рекламу по 1000 $ в месяц . Так же известно , что фирма готова рекламировать свою продукцию по радио по крайней мере в 2 раза чаще , чем по телевидению .
Опыт предыдущих лет показал , что телереклама приносит в 25 раз больший сбыт продукции нежели радиореклама .
Задача заключается в правильном распределении финансовых средств фирмы .
Математическое описание .
X1 - время потраченное на радиорекламу .
X2 - время потраченное на телерекламу .
Z - искомая целевая функция , оражающая максимальный сбыт от 2-ух видов рекламы .
X1=>0 , X2=>0 , Z=>0 ;
Max Z = X1 + 25X2 ;
5X1 + 100X2 X1 -2X2 => 0
Использование графического способа удобно только при решении задач ЛП с двумя переменными . При большем числе переменных необходимо применение алгебраического аппарата . В данной главе рассматривается общий метод решения задач ЛП , называемый симплекс-методом .
Информация , которую можно получить с помощью симплекс-метода , не ограничивается лишь оптимальными значениями переменных . Симплекс-метод фактически позволяет дать экономическую интерепритацию полученного решения и провести анализ модели на чувствительность .
Процесс решения задачи линейного программирования носит итерационный характер : однотипные вычислительные процедуры в определенной последовательности повторяются до тех пор , пока не будет получено оптимальное решение . Процедуры , реализуемые в рамках симплекс-метода , требуют применения вычислительных машин - мощного средства решения задач линейного программирования . Симлекс-метод - это характерный пример итерационных вычислений , используемых при решении большинства оптимизационных задач . В данной главе рассматриваются итерационные процедуры такого рода , обеспечивающие решение задач с помощью моделей исследования операций .
В гл 2 было показано , что правая и левая части ограничений линейной модели могут быть связаны знаками . Кроме того , переменные , фигурирующие в задачах ЛП , могут быть неотрицательными или не иметь ограничения в знаке . Для построения общего метода решения задач ЛП соответствующие модели должны быть представлены в некоторой форме , которую назовем стандатрной формой линейных оптимизационных моделей . При стандартной форме линейной модели Все ограничения записываются в виде равенств с неотрицательной правой частью ; Значения всех переменных модели неотрицательны ;
Целевая функция подлежит максимизации или минимизации .
Покажем , каким образом любую линейную модель можно привести к стандартной .
Ограничения
Исходное ограничение , записанное в виде неравенства типа ) , можно представить в виде равенства , прибавляя остаточную переменную к левой части ограничения ( вычитая избыточную переменную из левой части ) . Например , в левую часть исходного ограничения
5X1 + 100X2
вводистя остаточная переменная S1 > 0 , в результате чего исходное неравенство обращается в равенство 5X1 + 100X2 + S1 = 1000 , S1 => 0
Если исходное ограничение определяет расход некоторого ресурса , переменную S1следует интерпретировать как остаток , или неиспользованную часть , данного ресурса .
Рассмотрим исходное ограничение другого типа :
X1 - 2X2 => 0
Так как левая часть этого ограничения не может быть меньше правой , для обращения исходного неравенства в равенство вычтем из его левой части избыточную переменную S2 > 0 . В результате получим
X1 - 2X2 - S2 = 0 , S2 => 0
Правую часть равенства всегда можно сделать неотрицательной , умножая оби части на -1 .
Например равенство X1 - 2X2 - S2 = 0 эквивалентно равенству - X1 + 2X2 + S2 = 0 Знак неравенства изменяется на противоположный при умножении обеих частей на -1 .
Например можно вместо 2 < 4 записать - 2 > - 4 , неравенство X1 - 2X2 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 ) . Решение , соответствующее этой точке , обычно называют начальным решением . От исходной точки осуществляется переход к некоторой смежной угловой точке . Выбор каждой последующей экстремальной точки при использовании симплекс-метода определяется следующими двумя правилами .
Каждая последующая угловая точка должна быть смежной с предыдущей . Этот переход осуществляется по границам ( ребрам ) пространства решений . Обратный переход к предшествующей экстремальной точке не может производиться . Таким образом , отыскание оптимального решения начинается с некоторой допустимой угловой точки , и все переходы осуществляются только к смежным точкам , причем перед новым переходом каждая из полученных точек проверяется на оптимальность .
Определим пространство решений и угловые точки агебраически . Требуемые соотнощшения устанавливаются из указанного в таблице соответствия геометрических и алгебраических определений .
Геометрическое определение
Алгебраическое определение ( симплекс метод )
Пространство решений
Ограничения модели стандартной формы
Угловые точки
Базисное решение задачи в стандартной форме
Представление пространства решений стандартной задачи линейного программирования .
Линейная модель , построенная для нашей задачи и приведенная к стандартной форме , имеет следующий вид :
Максимизировать
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 переменных равны нулю.
Однозначные решения такой системы уравнений, получаемые
путем приравнивания к нулю ( п — т ) переменных , называются базисными решениями . Если базисное решение удовлетворяет
требованию неотрицательности правых частей , оно называется допустимым базисным решением. Переменные , имеющие нулевое
значение , называются небазисными переменными , остальные — базисными переменными.
Из вышеизложенного следует , что при реализации симплекс
метода алгебраическое определение базисных решений соответст вует идентификации экстремальных точек , осуществляемой при геометрическом представлении пространства решений . Таким об разом , максимальное число итераций при использовании симплекс метода равно максимальному числу базисных решений задачи ЛП , представленной в стандартной форме . Это означает , что количество итерационных процедур симплекс-метода не превышает
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 ( Ограничение )
Как отмечалось ранее , в качестве начального пробного решения используется решение системы уравнений , в которой две переменные принимаются равными нулю . Это обеспечиваетединст
Страницы: 1, 2
