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