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

живой организм лекарственным препаратов и т.д. Формализация модели "черного

ящика" основывается на задании двух множеств входных и выходных переменных,

и никаких других отношений между множествами не фиксируется.

Вместе с тем следует отметить, что построение модели "черного ящика" не

является тривиальной задачей, так как ответ на вопрос о содержании множеств

не всегда однозначен.

Построение модели основывается на выборе из бесконечного множества связей

системы со средой их конечного множества, адекватно отражающего цели

исследования. Очевидно. Что такие модели не надо сводить к моносистеме

(т.е. системе с одним входом и выходом), а для обоснования необходимого и

достаточного количества параметров множеств X и Y широко использовать

методы математической статистики, привлекать опытных экспертов.

Следующим уровнем моделирования сложных систем являются модели состава

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

целостность и обособленность выступают как внешнее свойство. Вместе с тем

внутренняя структура системы также является многообразной, неоднородной и

состоит из множества неделимых функциональных элементов. Декомпозиция

внутренней структуры "черного ящика" на более мелкие составляющие

(подсистемы, отдельные элементы) позволяют строить модели состава систем

(рис. 1.8).

Рис. 1.8. Модель состава системы

Например, если в качестве системы рассматривать производственное

подразделение, то в качестве подсистемы выступают производственные участки,

а в качестве отдельных элементов - оборудование, сырье, рабочие; сис-тема

телевидения состоит из аппаратуры передачи, каналов связи, аппаратуры

приема.

Построение модели состава в силу многообразия природы и форм элементов

также не является простым делом. Это можно объяснить тремя факторами:

1.неоднозначностью понятия "элементарного элемента";

2.многоцелевым характером объекта, объективно требующим выделить под каждую

цель соответствующий ей состав;

3.условностью (субъективностью) процедуры деления целого на части (системы

на подсистемы, элементы).

Простота и доступность моделей "черного ящика" и состава позволяет решать с

их использованием множество практических задач. Вместе с тем для более

детального (глубокого) изучения систем необходимо устанавливать в модели

состав отношения (связи) между элементами. Описание системы через

совокупность необходимых и достаточных для достижения целей отношений между

элементами назовем моделью структуры системы.

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

отвлеченной, абстрактной моделью. На самом деле как рассматривать связи,

если не рассмотрены сами элементы.

ПРАКТИЧЕСКАЯ ЧАСТЬ

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

Фирма , производящая некоторую продукцию осуществляет её

рекламу двумя способами через радиосеть и через телевидение . Стоимость

рекламы на радио обходится фирме в 5 $ , а стоимость телерекламы - в 100$

за минуту .

Фирма готова тратить на рекламу по 1000 $ в месяц . Так же

известно , что фирма готова рекламировать свою продукцию по радио по

крайней мере в 2 раза чаще , чем по телевидению .

Опыт предыдущих лет показал , что телереклама приносит в 25

раз больший сбыт продукции нежели радиореклама .

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

средств фирмы .

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

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

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

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

рекламы .

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

Max Z = X1 + 25X2 ;

5X1 + 100X2 0

Использование графического способа удобно только при решении задач ЛП с

двумя переменными . При большем числе переменных необходимо применение

алгебраического аппарата . В данной главе рассматривается общий метод

решения задач ЛП , называемый симплекс-методом .

Информация , которую можно получить с помощью симплекс-метода ,

не ограничивается лишь оптимальными значениями переменных . Симплекс-метод

фактически позволяет дать экономическую интерепритацию полученного решения

и провести анализ модели на чувствительность .

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

итерационный характер : однотипные вычислительные процедуры в определенной

последовательности повторяются до тех пор , пока не будет получено

оптимальное решение . Процедуры , реализуемые в рамках симплекс-метода ,

требуют применения вычислительных машин - мощного средства решения задач

линейного программирования .

Симлекс-метод - это характерный пример итерационных вычислений ,

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

рассматриваются итерационные процедуры такого рода , обеспечивающие решение

задач с помощью моделей исследования операций .

В гл 2 было показано , что правая и левая части ограничений

линейной модели могут быть связаны знаками . Кроме того ,

переменные , фигурирующие в задачах ЛП , могут быть неотрицательными или не

иметь ограничения в знаке . Для построения общего метода решения задач ЛП

соответствующие модели должны быть представлены в некоторой форме , которую

назовем стандатрной формой линейных оптимизационных моделей . При

стандартной форме линейной модели

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

частью ;

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

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

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

Ограничения

1. Исходное ограничение , записанное в виде неравенства типа ) ,

можно представить в виде равенства , прибавляя остаточную переменную к

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

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

5X1 + 100X2 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

Переменные

Любую переменную 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 каждой неэкстремальной точке соответствует

не более одной нулевой переменной . Так , любая точка внутренней

области пространства решений вообще не имеет ни одной нулевой

переменной, а любая неэкстремальная точка , лежащая на границе ,

всегда имеет лишь одну нулевую переменную .

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

делить их алгебраическим методом. Будем считать , что линейная

модель стандартной формы содержит т уравнений и п ( т не могут рассматриваться

как ограничения на ресурсы . Скорее , ограничения такого типа отра-

жают то обстоятельство , что решение должно удовлетворять опре-

деленным требованиям , например обеспечению минимального спро-

са или минимальных отклонений от установленных структурных

характеристик производства ( сбыта ) .

В модели , построенной для нашей задачи , фигурирует ограничение со

знаком

0 ) , однако , чтобы получить результат в общем виде , рассмотрим оба

случая .

Как изменится симплекс-таблица при изменении величины за-

паса ресурса на ?1 ? Проще всего получить ответ на этот вопрос .

если ввести ?1 в правую часть первого ограничения начальной сим-

плекс-таблицы и затем выполнить все алгебраические преобразова-

ния , соответствующие последовательности итераций . Поскольку

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

ведущих элементов , то очевидно , что на каждой итерации ?1 будет

оказывать влияние только на правые части ограничений .

|Уравнение |Значения элементов правой части на |

| |соответствующих итерациях |

| |) | |) |

|Z |0 |0 |2455/11 |

|1 |1000 |1000 + |1000/55 + |

| | |?1 |?1 |

|2 |0 |0 |91/11 |

Фактически вce изменения правых частей ограничений , обуслов-

ленные введением ?1 , можно определить непосредственно по данным ,

содержащимся в симплекс-таблицах . Прежде всего заметим , что

на каждой итерации новая правая часть каждого ограничения пред-

ставляет собой сумму двух величин: 1) постоянной и 2) члена , ли-

нейно зависящего от ?1 . Постоянные соответствуют числам , которые

фигурируют на соответствующих итерациях в правых частях ограничений

симплекс-таблиц до введения ?1 . Коэффициенты при ?1 во вторых слагаемых

равны коэффициентам при S1 на той же итерации . Так , например , на

последнеи итерации ( оптимальное решение ) постоянные ( 2455/11 ;

1000/55 ; 91/11 ) представляют собои числа , фигурирующие в правых частях

ограничении оптимальной симплекс-таблицы до введения ?1. Коэффициенты (

27/110 ; 1/55 ; 1/110 ) равны коэффициентам при S1 в той же симплекс-

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

Другими словами , при анализе влияния изменений в правой части второго

ограничения нужно пользоваться коэффициентами при переменной S2 .

Какие выводы можно сделать из полученных результатов?

Так как введение ?1 сказывается лишь на правой части симплекс-

таблицы , изменение запаса ресурса может повлиять только на

допустимость решения . Поэтому ?1 не может принимать значений ,

при которых какая-либо из ( базисных ) переменных становится отри-

цательной . Из этого следует , что величина ?1 должна быть огра-

ничена таким интервалом значений , при которых выполняется ус-

ловие неотрицательности правых частей ограничений в результи-

рующей симплекс-таблице , т . е .

X1 = 1000/55 + ( 1/55 )?1 ’> 0 ( 1 )

X2 = 91/11 + ( 1/110 )?1 => 0 ( 2 )

Для определения допустимого интервала изменения ?1 рассмо-

трим два случая .

Случай 1: ?1 ’> 0 Очевидно , что оба неравнества при этом условии всегда

будут неотрицательными .

Случай 2: ?1 < 0 .

( 1/55 )?1 => - 1000/55 . Из этого следует , что ?1 => - 1000

( 2 )

( 1/110 )?1 => - 91/11 . Из этого следует , что ?1 => - 1000

Объединяя результаты , полученные для обоих случаев , можно

сделать вывод , что при - 1000 0: ( 1 )

( 50/55 )?2 - 1000/55 . Из этого следует , что ?2 - 91/11 . Из этого следует , что ?2 ’> - 200

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

?2 ? [ - 200 ; 0 ]

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

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

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

Наряду с определением допустимых изменений запасов ресур-

сов представляет интерес и установление интервала допустимых

изменений коэффициентов удельной прибыли ( или стоимости ) .

Следует отметить , что уравнение целевой функции никогда не

используется в качестве ведущего уравнения . Поэтому лю-

бые изменения коэффициентов целевой функции окажут влияние

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

означает , что такие изменения могут сделать полученное решение

неоптимальным . Наша цель заключается в том , чтобы найти интер-

валы значений изменений коэффициентов целевой функции ( рас-

сматривая каждый из коэффициентов отдельно ) , при которых оп-

тимальные значения переменных остаются неизменными .

Чтобы показать, как выполняются соответствующие вычисле-

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

X1 изменяется от 1 до 1 + ?1 где ?1 может быть как положительным , так и

отрицательным числом . Целевая функция в этом случае принимает следующий

вид:

Z = ( 1 + ?1 )X1 + 25X2

Если воспользоваться данными начальной симплекс-таблицы и

выполнить все вычисления , необходимые для ( получения заключн-

тельной симплекс-таблицы , то последнее Z-уравнение будет выгля-

деть следующим образом:

|Базисные |X1 |X2 |S1 |S2 |Решение |

|Z |0 |0 |27/110+1/55|5/22-50/55|2455/11+1000/5|

| | | |?1 |?1 |5?1 |

Коэффициенты при базисных переменных X1 , X2 и остаточных я равными нулю .

Это уравнение отличается от Z-уравнения до введения ?1 , только наличием

членов , содержащих ?1 . Коэффициенты при ?1 равны Коэффициентам при

соответствующих переменных в Z-уравнении симплекс-таблицы для полученного

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

|Базисные |X1 |X2 |S1 |S2 |Решение |

|X1 |1 |0 |1/55 |-50/55 |1000/55 |

Мы рассматриваем X1 - уравнение , так как коэффициент именно при

этон переменной в выражении для целевои функции изменился

на ?1 .

Оптимальные значения переменных будут оставаться неизмен-

ными при значениях ?1 , удовлетворяющих условию неотрицатель-

ности ( задача на отыскание максимума ) всех коэффициентов при не-

базисных переменных в Z-уравнении . Таким образом , должны выполняться

следующие неравенства :

27/110 + 1/55?1 ’> 0

5/22 - 50/55?1 ’> 0

Из первого неравенства получаем , что ?1 => - 13,5 , а из второго следует

что ?1 <= 1/4 . Эти результаты определяют пределы изменения коэффициента C1

в виде следующего соотношения : - 13,5 <= ?1 <= 1/4 . Та-

ким образом , при уменьшении коэффициента целевой функции при

переменной X1 до значения , равного 1 + ( - 13,5 ) = - 12,5 или при его

увеличении до 1 + 13,5 = 14,5 оптимальные значения переменных остаются

неизменными . Однако оптимальное значение Z будет изменяться ( в

соответствии с выражением 2455/11 + 1000/55?1 , где - 13,5 <= ?1 <= 1/4

X2 изменяется от 25 до 25 + ?2 где ?2 может быть как положительным ,

так и отрицательным числом . Целевая функция в этом случае принимает

следующий вид:

Z = ( 25 + ?2 )X2 + X1

Все предыдущее обсуждение касалось исследования изменения

коэффициента при переменной , которой поставлено в соответствие ограничение

, фигурирующее в симплекс-таблице . Однако такое ограничение имеется лишь в

том случае , когда данная переменная является базисной ( например X1 и X2 )

. Если переменная небазисная , то в столбце , содержащем базисные

переменные , она не будет представлена .

Любое изменение коэффициента целевой функции при небазисной

переменной приводит лишь к тому , что в заключительной симплкс-таблице

изменяется только этот коэффициент . Рассмотрим в качестве иллюстрации

случай , когда коэффициент при переменной S1 ( первой остаточной переменной

) изменяется от 0 до ?3 . Выполнение преобразований , необходимых для

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

результирующему Z-уравнению :

|Базисные |X1 |X2 |S1 |S2 |Решение |

|Z |0 |0 |27/110+1/55|5/22|2455/11 |

| | | |?1 | | |

Заключение

В результате проведенного исследования, было получено подтверждение о

выгодности использования математико-экономического проектирования и методов

системного анализа для анализа и планирования экономических систем.

Список литературы :

В этом месте должна указываться литература использованная в курсовой

работе, но прогресс привел к тому, что вся информация черпалась на

страницах INTERNET, а следовательно

Список серверов:

www.citforum.ru

www.rambler.ru

www.msu.ru

www.ntcf.ru

www.yandex.ru

Страницы: 1, 2, 3

МЕНЮ

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