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

БОЛЬШАЯ ЛЕНИНГРАДСКАЯ БИБЛИОТЕКА - РЕФЕРАТЫ - Построение экономической модели с использованием симплекс-метода

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

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

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

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

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

Кулаков О. А.

Оглавление .

Введение

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

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

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

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

Ограничения

Переменные

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

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

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

программирования

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

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

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

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

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

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

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

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

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

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

глубокой древности и постепенно захватывало все новые области научных

знаний : техническое конструирование , строительство и архитектуру ,

астрономию , физику , химию , биологию и , наконец , общественные науки .

Большие успехи и признание практически во всех отраслях современной науки

принес методу моделирования ХХ в . Однако методология моделирования долгое

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

система понятий, единая терминология . Лишь постепенно стала осознаваться

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

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

деятельности и имеет множество смысловых значений . Рассмотрим только

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

Модель - это такой материальный или мысленно представляемый объект,

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

непосредственное изучение дает новые знания об объекте-оригинале .

Под моделирование понимается процесс построения , изучения и

применения моделей . Оно тесно связано с такими категориями , как

абстракция , аналогия , гипотеза и др . Процесс моделирования обязательно

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

конструирование научных гипотез.

Главная особенность моделирования в том , что это метод

опосредованного познания с помощью объектов-заместителей . Модель

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

ставит между собой и объектом и с помощью которого изучает интересующий

его объект . Именно эта особенность метода моделирования определяет

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

категорий и методов познания .

Необходимость использования метода моделирования определяется тем,

что многие объекты ( или проблемы , относящиеся к этим объектам )

непосредственно исследовать или вовсе невозможно, или же это исследование

требует много времени и средств.

Моделирование - циклический процесс . Это означает , что за первым

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

знания об исследуемом объекте расширяются и точняются, а исходная модель

постепенно совершенствуется . Недостатки , обнаруженные после первого

цикла моделирования , бусловленные малым знанием объекта и ошибками в

построении модели , можно исправить в последующих циклах . В методологии

моделирования , таким образом , заложены большие возможности саморазвития .

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

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

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

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

за минуту .

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

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

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

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

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

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

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

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

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

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

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

рекламы .

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

Max Z = X1 + 25X2 ;

5X1 + 100X2 0

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

частью ;

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

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

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

.

Ограничения

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

знаком

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

случая .

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

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

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

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

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

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

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

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

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

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

| |( начало вычислений|1 |2 ( оптимум|

| |) | |) |

|Z |0 |0 |2455/11 |

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

| | |D1 |D1 |

|2 |0 |0 |91/11 |

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

X1 = 1000/55 + ( 1/55 )D1 => 0 ( 1 )

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

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

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

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

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

Случай 2: D1 < 0 . Решаем неравенства : ( 1 )

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

( 2 )

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

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

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

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

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

D2 О [ - 200 ; 0 ]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

вид:

Z = ( 1 + d1 )X1 + 25X2

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

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

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

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

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

|переменные | | | | | |

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

| | | |d1 |d1 |5d1 |

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

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

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

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

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

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

|переменные | | | | | |

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

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

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

на d1 .

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

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

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

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

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

27/110 + 1/55d1 => 0

5/22 - 50/55d1 => 0

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

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

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

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

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

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

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

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

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

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

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

Z = ( 25 + d2 )X2 + X1

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

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

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

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

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

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

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

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

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

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

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

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

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

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

|переменные | | | | | |

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

| | | |d1 | | |