База знаний студента. Реферат, курсовая, контрольная, диплом на заказ

 

 

 

Курсовая работа

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

 

 

 

 

 

 

 

 

 

                                                      Работу выполнил

                                                      студент УТФ-4-2 

                                                     Кулаков О. А.

 

 

 

 

 

Оглавление .

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 

 

 

 

 

 

 

 

 

 

 

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

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

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

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

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

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

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

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

 

 

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

 

 

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

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

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

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

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

 

 

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

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

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

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

Max Z = X1 + 25X2 ;

5X1 + 100X2 <=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 , не имеющую ограничение в знаке , можно представить как разность двух неотрицательных переменных :

Yi=Yi’-Yi’’, где Yi’,Yi’’=>0.

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

      Обычно находят решение задачи ЛП , в котором фигурируют переменные Yi’ и Yi’’ , а затем с помощью обратной подстановки определяют величину Yi . Важная особенность переменных Yi’ и Yi’’ состоит в том , что при любом допустимом решении только одна из этих переменных может принимать положительное значение , т.е. если Yi’>0 , то Yi’’=0, и наоборот . Это позволяет рассматривать Yi’ как остаточную переменную , а Yi’’ - как избыточную переменную , причем лишь одна из этих переменных может принимать положительное значение . Указанная закономерность широко используется в целевом программировании и фактически является предпосылкой для использования соответсвующих преобразований в задаче 2.30

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

 

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

      Максимизация некоторой функции эквивалентна минимизации той же функции , взятой с противоположным знаком , и наоборот . Например максимизация функции

Z = X1 + 25X2

эквивалентна минимизации функции

( -Z ) = -X1 - 25X2

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

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

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

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

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

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

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

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

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

Геометрическое определение	Алгебраическое определение              ( симплекс метод )
Пространство решений	Ограничения модели стандартной формы
Угловые точки	Базисное решение задачи в стандартной форме

 

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

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

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

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

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

            5X1 + 100X2 +    S1              = 1000

      - X1   +     2X2                   + S2 = 0

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

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

Экстремальная точка	Нулевые переменные	Ненулевые переменные
А	S2 , X2	S1 , X1
В	S1 , X2	S2 , X1
С	S1 , S2	X1 , X2

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

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

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

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

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

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

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

C^п_т= n! / [ ( n - m )!m! ]      

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

Экстремальная точка	Нулевые переменные	Ненулевые переменные
А	S2 , X2	S1 , X1
В	S1 , X2	S2 , X1

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Базисные переменные	Z	X1	X2	S1	S2	Решение
Z	1	-1	- 25	0	0	0	Z - уравнение
S1	0	5	100	1	0	1000	S1 -уравнение
S2	0	-1	2	0	1	0	S2 - уравнение

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

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

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

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

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

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

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

Тип 1 ( формирование ведущего уравнения ) .

Новая ведущая строка = Предыдущая ведущая строка / Ведущий элемент

Тип 2 ( формирование всех остальных уравнений , включая Z - yравнение ) .

Новое уравнение = Предыдущее уравнение —

é Коэффициент       ù

ê ведущего столбца  ê * ( Новая ведущая строка ) .   

ê предыдущего          ê

ë уравнения              û

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

Базисные переменные	Z	X1	X2	S1	S2	Решение
Z
S1
S2	0	-1/2	1	0	1/2	0

Чтобы составить новую симплекс-таблицу , выполним необходимые вычислительные процедуры типа 2 .

1. Новое Z - уравнение .

старое Z - уравнение : ( 1   -1      -25    0    0     0 )

                     ( - ( -25 ) *  ( 0   -1/2     1     0   1/2    0 )

                                        ( 1   -13¹/₂   0     0  12¹/₂  0 )

2.   Новое S₁ - уравнение

     старое S₁ - уравнение : ( 0    5   100   1     0    1000 )

                           ( - 100 ) *    ( 0   -¹/₂   1      0    ¹/₂       0   )

                                               ( 0   55    0     1   -50   1000 )       

        

    Новая симплекс-таблица будет иметь вид :

             

Базисные переменные	Z	X1	X2	S1	S2	Решение
Z	1	-131/2	0	0	121/2	0	Z - уравнение
S1	0	55	0	1	-50	1000	S1 -уравнение
X2	0	-1/2	1	0	1/2	0	X2 - уравнение

       

В новом решении X₁ = 0 и S₂ = 0 . Значение Z не изменяется .

Заметим , что новая симплекс-таблица обладает такими же ха-
рактеристиками , как и предыдущая : только небазисные переменные
 X₁ и S₂ равны нулю , а значения базисных переменных , как и раньше ,
представлены в столбце « Решение » . Это в точности соответствует
результатам , получаемым при использовании метода Гаусса—Жор-
дана .

Из последней таблицы следует , что на очередной итерации в со-
ответствии с условием оптимальности в качестве вводимой перемен-
ной следует выбрать X₁ , òак как коэффициент при этой переменной в

Z-ypaвнении равен -13¹/₂ . Исходя из условия допустимости , определяем , что исключаемой переменной будет S₁ . Отношения , фигурирующие в правой части таблицы , показывают , что в новом базисном решении значение включаемой переменной X₁ будет равно ¹⁰⁰⁰/₅₅ ( = минимальному отношению ) . Это приводит к увеличению целевой функции на ( ¹⁰⁰⁰/₅₅ ) *    (   -13^1/₂ ) = ( 245⁵/₁₁ ) .

К получению симплекс-таблицы , соответствующей новой итерации , приводят следующие вычислительные операции метода Гаусса—Жордана.

1)  Новое ведущее  S₁ - уравнение = Предыдущее S₁ - уравнение / ( 55 ) .

Базисные переменные	Z	X1	X2	S1	S2	Решение
Z
S1	0	1	0	1/55	- 50/55	1000/55
X2

2) Новое  Z - уравнение = Предыдущее  Z - уравнение - ( -13¹/₂ ) * Новое /ведущее уравнение :

                                         ( 1   -13¹/₂  0     0     12¹/₂       0     )

                    - ( -13¹/₂ ) *  (  0      1     0    ¹/₅₅   -⁵⁰/₅₅    ¹⁰⁰⁰/₅₅  )

                                         ( 1      0     0    ²⁷/₁₁₀   ⁵/₂₂   245⁵/₁₁ )

3) Новое X₂ - уравнение = Предыдущее  X₂ - уравнение - ( -¹/₂ ) * Новое ведущее уравнение :

                                               ( 0  -¹/₂   1     0       ¹/₂        0    )

                         - ( - ¹/₂  ) *     ( 0    1     0    ¹/₅₅  -⁵⁰/₅₅    ¹⁰⁰⁰/₅₅ )

                                         ( 0    0     1   ¹/₁₁₀    ¹/₂₂     9¹/₁₁  )

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

Базисные переменные	Z	X1	X2	S1	S2	Решение
Z	1	0	0	27/110	5/22	2455/11
X1	0	1	0	1/55	-50/55	1000/55
X2	0	0	1	1/110	1/22	91/11

В новом базисном решении X₁=¹⁰⁰⁰/₅₅ и X₂=9¹/₁₁ . Значение Z увеличилось с 0 ( предыдущая симплекс-таблица ) до 245⁵/₁₁  ( последняя симплекс-таблица ) . Этот результирующий прирост целевой функции  обусловлен увеличением X₁ от О до ¹⁰⁰⁰/₅₅ , так как из Z - строки предыдущей симплекс-таблицы следует , что возрастанию данной переменной на единицу соответствует увеличение целевой функции на( -13¹/₂ ) .

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

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

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

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

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

С точки зрения практического использования результатов ре-
шения задач ЛП классификация переменных , предусматривающая
их разделение на базисные и небазнсные , не имеет значения и при
анализе данных , характеризующих оптимальное решение , может
не учитываться . Переменные , отсутствующие в столбце « Базисные
переменные » , обязательно имеют нулевое значение . Значения ос-
тальных переменных приводятся в столбце « Решение » . При интер-
претации результатов оптимизации в нашей задаче нас прежде всего интересует количество времени , которое закажет наша фирма на радио и телевидение ,  т. е. значения управляемых переменных X₁ и X₂ . Используя данные , содержащиеся в симплекс-таблице для оптимального решения , основные результаты можно представить в следующем виде :

Управляемые переменные	Оптимальные значения	Решение
X1	1000/55	Время выделяемое фирмой на телерекламу
X2	91/11	Время выделяемое фирмой на радиорекламу
Z	2455/11	Прибыль получаемая от рекламы .

Заметим, что Z = X₁ + 25X₂ = ¹⁰⁰⁰/₅₅ + 25 * 9¹/₁₁ = 245⁵/₁₁ . Это решение соответствует данным заключительной симплекс-таблицы .

 

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

 

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

В модели , построенной для нашей задачи , фигурирует ограничение со знаком <= . Это требование можно рассматривать как ограничение на соответствующий « ресурс » , так как увеличение спроса на продукцию эквивалентно расширению « представительства » фирмы на рынке сбыта .

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

Ресурсы	Остаточная переменная	Статус ресурса
Ограничение по бюджету	S1	Дефицитный
Превышение времени рекламы радио над теле	S2	Дефицитный

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

Ресурсы, увеличение запасов которых позволяет улучшить ре-
шение ( увеличить прибыль ) , — это остаточные переменные S₁ и S₂ , по-
скольку из симплекс-таблицы для оптимального решения видно ,
что они дефицитные . В связи с этим логично поставить следующий
вопрос: какому из дефицитных ресурсов следует отдать предпочте-
ние при вложении дополнительных средств на увеличение их запа-
сов , с тем чтобы получить от них максимальную отдачу ? Ответ на
этот вопрос будет дан в следующем подразделе этой главы , где рас-
сматривается ценность различных ресурсов .

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

 

Ценность ресурса характеризуется величиной улучшения опти-
мального значения Z , приходящегося на единицу прироста объема
данного ресурса .

Информация для оптимального решения задачи представлена в симплекс-таблице . Обратим внимание на значения коэффициентов Z - уравнения , стоящих при переменных начального базиса S₁ и S₂ . Выделим для удобства соответстзующую часть симплекс-таблицы :

Базисные переменные	Z	X1	X2	S1	S2	Решение
Z	1	0	0	27/110	5/22	2455/11

Как следует из теории решения задач ЛП , ценность ресурсов всегда можно определить по значениям коэффициентов при переменных начального базиса , фигурирующих в Z - уравнении оптимальной симплекс-таблицы , таким образом Y₁ = ²⁷/₁₁₀ , а Y₂ = ⁵/₂₂ .

Покажем , каким образом аналогичный результат можно получить непосредственно из симплекс-таблицы для оптимального решения . Рассмотрим Z - уравнение симплекс-таблицы для оптимального решения нашей задачи

Z = 245⁵/₁₁ - ( ²⁷/₁₁₀S₁ +  ⁵/₂₂S₂ ) .

Положительное приращение переменной S₁ относительно ее текущего
нулевого значения приводит к пропорциональному уменьшению Z ,
причем коэффициент пропорциональности равен ²⁷/₁₁₀ . Но , как следует из первого ограничения модели :

5X1 + 100X2  + S₁ = 1000

увеличение S₁ эквивалентно снижению количества денег выделеных на рекламу ( далее мы будем использовать в тексте , как первый ресурс ) . Отсюда следует , что уменьшение количества денег выделеных на рекламу вызывает пропорциональное уменьшение целевой функции с тем же коэффициентом пропорциональности , равным ²⁷/₁₁₀ . Так как
мы оперируем с линейными функциями , полученный вывод можно
обобщить , считая , что и увеличение количества денег выделеных на рекламу ( эквивалентное введению избыточной переменной S₁ < 0 ) приводит к пропорциональному увеличению Z с тем же коэффициентом пропорциональности , равным ²⁷/₁₁₀ . Аналогичные рассуждения справед-
ливы для ограничения 2 .

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

Заметим , что теневая цена ( ценность ресурса ) характеризует ин-
тенсивность улучшения оптимального значения Z . Однако при этом
не фиксируется интервал значений увеличения запасов ресурса ,
при которых интенсивность улучшения целевой функции остается
постоянной . Для большинства практических ситуаций логично пред-
положить наличие верхнего предела увеличения запасов , при пре-
вышении которого соответствующее ограничение становится избы-
точным , что в свою очередь приводит к новому базисному решению
и соответствующим ему новым теневым ценам . Ниже определяется
нитервал значений запасов ресурса , при которых соответствую-
щее ограничение не становится избыточным .

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

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

В нашей задаче запас первого ресурса изменился на D₁ т. е. запас бюджета  составит 1000 + D₁ . При положительной величине D₁ запас данного ресурса увеличивается , при отрицательной — уменьшается . Как правило , исследуется ситуация , когда объем ресурса увеличивается            ( D₁ > 0 ) , однако , чтобы получить результат в общем виде , рассмотрим оба случая .

Как изменится симплекс-таблица при изменении величины за-
паса ресурса на D₁ ? Проще всего получить ответ на этот вопрос .
если ввести D₁ в правую часть первого ограничения начальной сим-
плекс-таблицы и затем выполнить все алгебраические преобразова-
ния , соответствующие последовательности итераций . Поскольку
правые части ограничений никогда не используются в качестве
ведущих элементов , то очевидно , что на каждой итерации D₁ будет
оказывать влияние только на правые части ограничений .

Уравнение	Значения элементов правой части на соответствующих итерациях
	( начало вычислений )	1	2 ( оптимум )
Z	0	0	2455/11
1	1000	1000 + D1	1000/55 + D1
2	0	0	91/11

Фактически вce изменения правых частей ограничений , обуслов-
ленные введением D₁ , можно определить непосредственно по данным ,
содержащимся в симплекс-таблицах . Прежде всего заметим , что
на каждой итерации новая правая часть каждого ограничения пред-
ставляет собой сумму двух величин: 1) постоянной и 2) члена , ли-
нейно зависящего от D₁ . Постоянные соответствуют числам , которые
фигурируют на соответствующих итерациях в правых частях ограничений симплекс-таблиц до введения D₁ . Коэффициенты при D₁ во вторых слагаемых равны коэффициентам при S₁ на той же итерации . Так , например , на последнеи итерации ( оптимальное решение ) постоянные       ( 245⁵/₁₁ ; ¹⁰⁰⁰/₅₅ ; 9¹/₁₁ ) представляют собои числа , фигурирующие в правых частях ограничении оптимальной симплекс-таблицы до введения D₁. Коэффициенты ( ²⁷/₁₁₀ ; ¹/₅₅ ; ¹/₁₁₀ ) равны коэффициентам при S₁  в той же симплекс-таблице потому , что эта переменная связана только с первым ограничением . Другими словами , при анализе влияния изменений в правой части второго ограничения нужно пользоваться коэффициентами при переменной S₂ .

       Какие выводы можно сделать из полученных результатов?
Так как введение D₁ сказывается лишь на правой части симплекс-
таблицы , изменение запаса ресурса может повлиять только на
допустимость решения . Поэтому D₁ не может принимать значений ,
при которых какая-либо из ( базисных ) переменных становится отри-
цательной . Из этого следует , что величина D₁ должна быть огра-
ничена таким интервалом значений , при которых выполняется ус-
ловие неотрицательности правых частей ограничений в результи-
рующей симплекс-таблице , т . е .

X₁ = ¹⁰⁰⁰/₅₅  + ( ¹/₅₅ )D₁ => 0                                ( 1 )

X₂ = 9¹/₁₁ + ( ¹/₁₁₀ )D₁ => 0                                  ( 2 )

Для определения допустимого интервала изменения D₁ рассмо-
трим два случая .

Случай 1: D₁ => 0 Очевидно , что оба неравнества при этом условии всегда будут неотрицательными .

Случай 2: D₁ < 0 . Рåøàåì íåðàâåíñòâà :  ( 1 )

( ¹/₅₅ )D₁ => - ¹⁰⁰⁰/₅₅ . Из этого следует , что D₁ => - 1000

                                                                          ( 2 )        

( ¹/₁₁₀ )D₁ => - 9¹/₁₁ . Из этого следует , что D₁ => - 1000

Объединяя результаты , полученные для обоих случаев , можно
сделать вывод , что при - 1000 <= D₁ <= + ¥ решение рассматриваемой зада-
чи всегда будет допустимым , любое значение D₁ , выходящее за
пределы указанного интервала , приведет к недопустимости решения и
новой совокупности базисных переменных .

            Теперь рассмотрим в каких пределах может изменяться запас ресурса 2 анализ проведем по аналогичной схеме :

Запас 2-ого ресурса изменился на D₂ т . е . запас рекламного времени составит 0 + D₂ . Как изменилась симплекс-таблица при изменении величины запаса ресурса на D₂ ïðîèëëþñòðèðîâàíî íèæå .

Уравнение	Значения элементов правой части на соответствующих итерациях
	( начало вычислений )	1	2 ( оптимум )
Z	0	0	2455/11
1	1000	1000	1000/55
2	0	0 + D2	91/11 + D2

    

Найдем интервал ограничивающий величину D₂

X₁ = ¹⁰⁰⁰/₅₅ - ( ⁵⁰/₅₅ )D₂                            ( 1 )

X₂ = 9¹/₁₁ + ( ¹/₂₂ )D₂                     ( 2 )

            Для определения допустимого интервала изменения D₁ рассмо-
трим два случая .

       Случай 1: D₂ => 0 Рåøàåì íåðàâåíñòâà :  ( 1  )

( ⁵⁰/₅₅ )D₂ <= ¹⁰⁰⁰/₅₅ из этого неравенства следует , что D₂ <= 20

                                                                 ( 2 )

Очевидно , что 2-ое уравнение неотрицательно на данном участке .

Объединяя 2 уравнения для Случая 1 мы получим интервал для D₂ .

D₂ Î [ 0 ; 20 ]

Случай 2: D₂ < 0 . Рåøàåì íåðàâåíñòâà :  ( 1 )

( ⁵⁰/₅₅ )D₂ => - ¹⁰⁰⁰/₅₅ . Из этого следует , что D₂ <= 20

                                                                                 ( 2 ) 

( ¹/₂₂ )D₂ => - 9¹/₁₁ . Из этого следует , что D₂ => - 200

Объединяя 2 уравнения для Случая 2 мы получим интервал для D₂ .

      D₂ Î [ - 200 ; 0 ]

      Объединяя 2 случая мы получим интервал [ - 200 ; 20 ]

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

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

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

Чтобы показать, как выполняются соответствующие вычисле-
ния , положим , что удельный объем сбыта , ассоциированной с переменной

X₁ изменяется от 1 до 1 + d₁ где d₁ может быть как положительным , так и отрицательным числом . Целевая функция в этом случае принимает следующий вид:

Z = ( 1 + d₁ )X₁ + 25X₂

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

Базисные переменные	X1	X2	S1	S2	Решение
Z	0	0	27/110+1/55d1	5/22-50/55d1	2455/11+1000/55d1

Коэффициенты при базисных переменных X₁ , X₂ и остаточных я равными нулю . Это уравнение отличается от Z-уравнения до введения d₁ , только наличием членов , содержащих d₁ . Коэффициенты при d₁ равны кoэффициентам при соответствующих переменных в Z-уравнении симплекс-таблицы для полученного ранее оптимального решения

Базисные переменные	X1	X2	S1	S2	Решение
X1	1	0	1/55	-50/55	1000/55

Мы рассматриваем X₁ - уравнение , так как коэффициент именно при
этон переменной в выражении для целевои функции изменился
на d₁ .

Оптимальные значения переменных будут оставаться неизмен-
ными при значениях d₁ , удовлетворяющих условию неотрицатель-
ности ( задача на отыскание максимума ) всех коэффициентов при не-
базисных переменных в Z-уравнении . Таким образом , должны выполняться следующие неравенства :

²⁷/₁₁₀ + ¹/₅₅d₁ => 0

⁵/₂₂ - ⁵⁰/₅₅d₁ => 0

Из первого неравенства получаем , что d₁ => - 13,5 , а из второго следует что d₁ <= ¹/₄ . Эти результаты определяют пределы изменения коэффициента C₁ в виде следующего соотношения : - 13,5 <= d₁ <= ¹/₄ . Та-
ким образом , при уменьшении коэффициента целевой функции при
переменной X₁ до значения , равного 1 + ( - 13,5 ) = - 12,5   или при его увеличении до 1 + 13,5 = 14,5 оптимальные значения переменных остаются
неизменными . Однако оптимальное значение Z будет изменяться ( в соответствии с выражением 245⁵/₁₁ + ¹⁰⁰⁰/₅₅d₁ , где - 13,5 <= d₁ <= ¹/₄

            X₂  изменяется от 25 до 25 + d₂ где d₂ может быть как положительным , так и отрицательным числом . Целевая функция в этом случае принимает следующий вид:

Z = ( 25 + d₂ )X₂ + X₁

            Все предыдущее обсуждение касалось исследования изменения коэффициента при переменной , которой поставлено в соответствие ограничение , фигурирующее в симплекс-таблице . Однако такое ограничение имеется лишь в том случае , когда данная переменная является базисной ( например X₁ и X₂ ) . Если переменная небазисная , то в столбце , содержащем базисные переменные , она не будет представлена .

            Любое изменение коэффициента целевой функции при небазисной переменной приводит лишь к тому , что в заключительной симплкс-таблице изменяется только этот коэффициент . Рассмотрим в качестве иллюстрации случай , когда коэффициент при переменной S₁ ( первой остаточной переменной ) изменяется от 0 до d₃ . Выполнение преобразований , необходимых для получения заключительной симплекс таблицы , приводит к следующему результирующему Z-уравнению :

Базисные переменные	X1	X2	S1	S2	Решение
Z	0	0	27/110+1/55d1	5/22	2455/11

Курсовая работа Тема: Построение экономической модели с использованием симплекс-метода .                                                       Работу выполнил                                                       студент

 

• 14:21 05 Июля 2016
  Российско-китайский медуниверситет откроет магистерскую программу по TCM
• 01:21 05 Июля 2016
  На форуме МГУ Россия и Китай обсудят научно-образовательное сотрудничество
• 11:00 04 Июля 2016
  Реморенко: "ЕГЭ-туризм" в России сходит на нет
• 10:52 04 Июля 2016
  Летняя российско-австрийская школа откроется в Москве
• 15:31 01 Июля 2016
  В СПбГУ могут воссоздать географический факультет

Заказать уникальную работу