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

<span BetinaScript",«sans-serif»"> 

<span BetinaScript",«sans-serif»"> 

<span BetinaScript",«sans-serif»"> 

<span BetinaScript",«sans-serif»">Курсовая работа

<span BetinaScript",«sans-serif»">

<span BetinaScript",«sans-serif»">Тема

<span BetinaScript",«sans-serif»;mso-ansi-language:EN-US">:<span BetinaScript",«sans-serif»"> Построение экономическоймодели с использованием симплекс-метода .

<span BetinaScript",«sans-serif»"> 

<span BetinaScript",«sans-serif»"> 

<span BetinaScript",«sans-serif»"> 

<span BetinaScript",«sans-serif»"> 

<span BetinaScript",«sans-serif»"> 

<span BetinaScript",«sans-serif»"> 

<span BetinaScript",«sans-serif»"> 

<span BetinaScript",«sans-serif»"> 

<span BetinaScript",«sans-serif»"> 

<span BetinaScript",«sans-serif»">

<span BetinaScript",«sans-serif»">                                                     Работу выполнил

<span BetinaScript",«sans-serif»">                                                     студент УТФ-4-2 

<span BetinaScript",«sans-serif»">                                                     КулаковО. А.

 

 

 

 

 

Оглавление.

Введение

Моделирование как метод научного познания.

Введениев симплекс-метод

1.Словесное описание

2.Математическое описание

3.Ограничения

4.Переменные

5.Целевая функция

Симплекс-метод.

1.Представление пространства решений стандартнойзадачи линейного программирования

2.Вычислительные процедуры симплекс-метода

Анализрезультатов .

1.Оптимальное решение

2.Статус ресурсов

3.Ценность ресурса

4.Максимальное изменение запаса ресурса

5.Максимальное изменение коэффициентов удельной

прибыли (стоимости)

 

 

 

 

 

 

 

 

 

 

 

Моделирование  как метод научного познания.

     Моделирование в научных исследованиях  стало применятьсяеще в  глубокой  древности и постепенно захватывало все новыеобласти научных знаний:  техническое конструирование,  строительство и архитектуру, астрономию, физику, химию, биологию и,наконец, общественныенауки.  Большие успехи и признаниепрактически во всех отраслях современной науки принес методу моделирования ХХ в.  Однако методология моделирования долгое времяразвиваласьнезависимо отдельными науками.  Отсутствовала единая системапонятий, единая терминология. Лишь постепенно стала осознаваться роль  моделирования какуниверсального методанаучного познания.

     Термин «модель»  широко используется  в различных сферахчеловеческойдеятельности и имеет множество смысловых  значений.Рассмотрим  только такие«модели»,  которые являютсяинструментами получения знаний.

     Модель — это такой материальный или мысленнопредставляемый объект,  который в  процессе исследования  замещает  объект-оригинал так, что его непосредственноеизучение дает новыезнания об объекте-оригинале .

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

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

     Необходимость использования методамоделирования  определяется тем,  что многие объекты ( или проблемы , относящиеся к этим объектам ) непосредственно исследовать или вовсеневозможно, или же это исследование требует много времени и средств.

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

 

 

Словесноеописание

 

 

            Фирма, производящая некоторуюпродукцию осуществляет её рекламу двумя способами через радиосеть и черезтелевидение. Стоимость рекламы на радио обходится фирме в 5$ , а стоимость телерекламы — в 100$  за минуту.

            Фирма готова тратить на рекламу по1000 $ в месяц. Так же известно ,  чтофирма готова рекламировать свою продукцию по радио по крайней мере в 2 разачаще, чем по телевидению.

             Опыт предыдущих лет показал, чтотелереклама приносит в 25 раз больший сбыт продукции нежели радиореклама.

              Задача заключается в правильномраспределении финансовых средств фирмы.

Математическоеописание .

 

 

X1-время потраченное на радиорекламу .

X2 — время потраченное на телерекламу  .

Z — искомая целевая функция,оражающая максимальный сбыт от 2-ух видов рекламы .

X1=>0, X2=>0, Z=>0 ;

Max Z = X1+ 25X2 ;

5X1+100X2 <=1000 ;

X1-2X2=> 0

Использованиеграфического способа удобно только при решении задач ЛП с двумя переменными.При большем числе переменных необходимо применение алгебраического аппарата. Вданной главе рассматривается общий метод решения задач ЛП, называемыйсимплекс-методом .

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

           Процесс решения задачи линейногопрограммирования носит итерационный характер: однотипные вычислительныепроцедуры в определенной последовательности повторяются до тех пор, пока небудет полученооптимальное решение. Процедуры, реализуемые в рамках симплекс-метода, требуют применения вычислительных машин — мощного средства решения задачлинейного программирования .

           Симлекс-метод — это характерныйпример итерационных вычислений, используемых при решении большинстваоптимизационных задач. В данной главе рассматриваются итерационные процедурытакого рода, обеспечивающие решение задач с помощью моделей исследованияопераций . 

          В гл 2 было показано, что правая илевая части ограничений линейной модели могут быть связаны знаками <=, = и =>. Кроме того, переменные, фигурирующие взадачах ЛП, могут быть неотрицательными или не иметь ограничения в знаке. Дляпостроения общего метода решения задач ЛП соответствующие модели должны бытьпредставлены в некоторой форме, которую назовем стандатрной формой линейныхоптимизационных моделей. При стандартной форме линейной модели

1.<span Times New Roman"">   

Все ограничения записываютсяв виде равенств с неотрицательной правой частью ;

2.<span Times New Roman"">   

Значения всех переменныхмодели неотрицательны ;

3.<span Times New Roman"">   

Целевая функция подлежитмаксимизации или минимизации .

Покажем,каким образом любую линейную модель можно привести к стандартной .

           Ограничения  

 

1.<span Times New Roman"">   

Исходное ограничение, записанноев виде неравенства типа <= (=>) ,

можнопредставить в виде равенства, прибавляя остаточную переменную к левой частиограничения ( вычитая избыточную переменную из левой части ).

      Например, в левую часть исходногоограничения

5X1 +100X2 <= 1000

вводистяостаточная переменная S1>0 ,в результате чего исходное неравенство обращается в равенство

5X1 +100X2 + S1 = 1000, S1=>0

Если исходноеограничение определяет расход некоторого ресурса, переменную S1следует интерпретировать как остаток, или неиспользованную часть,данного ресурса .

      Рассмотрим исходное ограничение другоготипа :

X1 — 2X2 => 0

Так как леваячасть этого ограничения не может быть меньше правой, для обращения исходногонеравенства в равенство вычтем из его левой части избыточную переменную S2>0 . В результате получим

X1 — 2X2 — S2 = 0, S2=>0

2. <span Times New Roman""> 

Правую часть равенства всегда можно сделать неотрицательной, умножаяоби части на -1 .

Напримерравенство  X1 — 2X2 — S2= 0эквивалентно равенству — X1+ 2X2+ S2= 0

3. <span Times New Roman""> 

Знак неравенства изменяется на противоположный при умножении обеихчастей на -1 .

     Например можно вместо 2 <4записать — 2 >-4 , неравенство X1 — 2X2 <= 0 заменить на — 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 ). Решение, соответствующее этой точке, обычноназывают начальным решением. От исходной точки осуществляется переход кнекоторой смежной угловой точке.

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

1. <span Times New Roman""> 

Каждая последующая угловаяточка должна быть смежной с предыдущей. Этот переход осуществляется пограницам ( ребрам ) пространства решений.

2. <span Times New Roman""> 

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

Таким образом,отыскание  оптимального решенияначинается с некоторой допустимой угловой точки, и все переходы осуществляютсятолько к смежным точкам, причем перед новым переходом каждая из полученныхточек проверяется на оптимальность .

Определим пространстворешений и угловые точки агебраически. Требуемые соотнощшения устанавливаютсяиз указанного в таблице соответствия геометрических и алгебраическихопределений .

Геометрическое определение

Алгебраическое определение              ( симплекс метод )

Пространство решений

Ограничения модели стандартной формы

Угловые точки

Базисное решение задачи в стандартной форме

 

Представление пространстварешений стандартной задачи линейного программирования .

Линейная модель,построенная для нашей задачи и приведенная к стандартной форме, имеетследующий вид :

Максимизировать

                              Z= X1  +  25X2+  0S1+ 0S2

Приограничениях

            5X1 + 100X2 +    S1              = 1000

      — X1   +     2X2                   + S2 = 0

X1=>0, X2=>0, S1=>0, S2=>0

Каждую точку пространстварешений данной задачи, представленную на рис.1, можно определить с помощьюпеременных X1,X2,S1иS2, фигурирующими в моделистандартной формы. При S1= 0 и S2= 0 ограничения моделиэквивалентны равенствам, которые представляются соответствующими ребрамипространства решений. Увеличение переменных S1и S2будет соответствовать смещению допустимых точек с границ пространстварешений в его внутреннюю область. Переменные X1,X2,S1и S2,ассоциированные сэкстремальными точками А, В ,  и С можноупорядочить, исходя из того, какое значение ( нулевое или ненулевое ) имеет данная переменная в экстремальной точке .

Экстремальная точка

Нулевые переменные

Ненулевые переменные

А

S2, X2

S1, X1

В

S1, X2

S2, X1

С

S1, S2

X1, X2

 Анализируя таблицу, легко заметить две закономерности:

1.Стандартная модель содержит два уравненияи четыре
неизвестных, поэтому в каждой из экстремальных точек две ( = 4 -2 ) переменныедолжны иметь нулевые значения .

2.Смежные экстремальные точки отличаютсятолько одной пе-
ременной в каждой группе ( нулевых и ненулевых переменных ),

Первая закономерность свидетельствуето возможности опре-
деления экстремальных точек алгебраическим способомпутем при-
равнивания нулю такого количества переменных, которое равно
разности между количеством неизвестных и числом уравнений .
В этом состоит сущностьсвойства однозначностиэкстремальных
точек. На рис.1 каждой неэкстремальнойточке соответствует
не более одной нулевой переменной. Так, любая точкавнутренней
области пространства решений вообще не имеет ниодной нулевой
переменной, а любая неэкстремальная точка, лежащая на границе,
всегда имеет лишь одну нулевую переменную.

Свойство однозначности экстремальных точек позволяетопре-
делить их алгебраическим методом. Будем считать, что линейная
модель стандартной формы содержит т уравненийи п(т<= п)не-
известных (правые части ограничений—неотрицательные). Тогда
все допустимые экстремальные точки определяются как всеодно-
значные неотрицательные решения системыmуравнений, в ко-
торых п—m  переменных равнынулю.

Однозначные решения такой системы уравнений,получаемые
путем приравнивания кнулю (п— т)переменных, называются
базисными решениями. Если базисное решение удовлетворяет
требованию неотрицательности правых частей, ононазывается
допустимым базисным решением. Переменные, имеющие нулевое
значение, называются небазисными переменными, остальные—
базисными переменными.

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

Cпт= n!/ [ ( n — m )!m! ]      

Вторая из ранееотмеченных закономерностейоказывается
весьма полезной для построениявычислительных процедур симп-
лекс-метода, при реализациикоторого осуществляется последова-
тельный переход от одной экстремальной точки к другой, смежнойс ней. Так каксмежные экстремальныеточки отличаются только
одной переменной, можно определить каждую последующую ( смеж-
ную) экстремальную точку путем замены одной из текущих не-
базисных ( нулевых ) переменных текущей базиснойпеременной.
В нашем случае получено решение, соответствующее точке А, откуда следует осуществить переход в точку В. Для этого нужно увеличивать небазисную переменную X2от исходного нулевого значения до значе-
ния, соответствующего точке В (см. рис.1 ). В точкеBпеременная
S1( которая в точке А была базисной ) автоматическиобращается в
нуль и, следовательно, становится небазисной переменной. Таким
образом, между множеством небазисных и множеством базисных
переменных происходит взаимообмен переменными X2иS1.Этот
процесс можно наглядно представить в виде следующей таблицы.

Экстремальная точка

Нулевые переменные

Ненулевые переменные

А

S2, X2

S1, X1

В

S1, X2

S2, X1

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

Рассмотренный процессвзаимной замены переменных приводит
к необходимости введения двух новых терминов. Включаемой пе-
ременной называется небазисная в данный момент переменная ,
которая будет включена в множество базисных переменных на сле-
дующей итерации ( при переходе к смежной экстремальной точке ) .
Исключаемая переменная— это та базиснаяпеременная, которая
на следующей итерации подлежит исключению из множества ба-
зисных переменных .

Вычислительные процедурысимплекс-метода .

 симплекс-алгоритмсостоит из следующих шагов.

Шаг0.Используя линейную модель стандартной формы, опреде-
ляют начальное допустимое базисное решение путем приравнива-
ния к нулю п — т ( небазисных ) переменных.

Шаг1.Из числа текущих небазисных ( равных нулю ) перемен-
ных выбирается включаемая в новый базис переменная, увеличение
которой обеспечивает улучшение значения целевой функции. Если
такой переменной нет, вычисления прекращаются, так как текущее
базисное решение оптимально. В противном случае осуществляется
переход к шагу2.

Шаг2.Из числа переменных текущего базиса выбирается исклю-
чаемая переменная, которая должна принять нулевое значение ( стать
небазисной ) при введении в состав базисных новой переменной .

Шаг3.Находится новое базисное решение, соответствующее
новым составам небазисных и базисных переменных. Осуществляется переход к шагу1.

Поясним процедурысимплекс-метода на примере решения нашей зада-
чи .Сначала необходимо представить целевую функцию и ограничения модели встандартной форме:

                        Z -    X1    -    25X2+0S1 -0S2=   0 ( Целеваяфункция )

          5X1  +  100X2+  S1           =1000 ( Ограничение )

           -X1    +     2X2          + S2= 0( Ограничение )   

Как отмечалось ранее, в качестве начального пробного решения
используется решение системы уравнений, в которой две переменные принимаютсяравными нулю. Это обеспечивает единст-
венность и допустимостьполучаемого решения. В рассматриваемом
случае очевидно, что подстановкаX1= X2= 0сразу же приводит к следующему результату:S1= 1000, S2= 0(т. е. решению, соответствующему точке А на рис.1 ). Поэтому точку А можно использовать какначальное допустимое решение. Величина Zв этой точке равна нулю,так как иX1и X2 имеют нулевоезначение. Поэтому, преобразовав уравнение целевой функции так, чтобы егоправая часть стала равной нулю, можно убедиться в том, что правые частиуравнений целевой функции и ограничений полностью характеризуют начальноерешение. Это имеет место во всехслучаях, когда начальныйбазис состоит из остаточныхпеременных.            

Полученные результаты удобнопредставить в виде таблицы :

Базисные переменные

Z

X1

X2

S1

S2

Решение

Z

1

-1

— 25

Z — уравнение

S1

5

100

1

1000

S1-уравнение

S2

-1

2

1

S2 — уравнение

Эта таблица интерпретируетсяследующим образом. Столбец
«Базисные переменные» содержит переменные пробного базисаS1,
S2 , значения которых приведены встолбце «Решение». При
этом подразумевается, что небазисные переменные X1иX2(не пред-
ставленные в первом столбце) равны нулю. Значение целевой функ-
цииZ =1*0 + 25*0 + 0*1000 + 0*1  равно нулю, что и показано в последнем столбце таблицы.

 Определим,является ли полученное пробное решение наи-
лучшим ( оптимальным ). Анализируя Z -уравнение, нетруднозаме-
тить, что обе небазисные переменные X1иX2 ,равные нулю, имеют
отрицательные коэффициенты. Всегдавыбирается переменная с большим абсолютным значением отрицательногокоэффициента ( вZ — уравнении) , таккак практический опыт вычислений показывает, что в этом случае оптимумдостигается быстрее.

Это правило составляет основу используемого ввычислительной
схеме симплекс-метода условия оптимальности, которое состоит в
том, что, если в задаче максимизации всенебазисные переменные в
Z — уравненииимеют неотрицательные коэффициенты, полученноепробноерешение является оптимальным. В противном случае в ка-
честве новой базисной переменной следует выбрать ту, котораяимеет
наибольший по абсолютной величине отрицательный коэффициент.

Применяя условие оптимальности к исходной таблице, выберем
в качестве переменной, включаемой в базис, переменную Х2 . Исклю-
чаемая переменная должна быть выбрана из совокупности базисных
переменныхS1, S2. Процедура выбора исключаемой переменной предполагает проверку условия допустимости,требующего,чтобы в качест

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