Метод математического моделирования

ВЕДЕНИЕ

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

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

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

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

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

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

       Процесс моделирования включает три элемента: 1) субъект (исследователь), 2) объект исследования, 3) модель, опосредствующую отношения  познающего субъекта и познаваемого объекта.

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

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

       На  втором этапе процесса моделирования  модель выступает как самостоятельный  объект исследования. Одной из форм такого исследования является проведение "модельных" экспериментов, при  которых сознательно изменяются условия функционирования модели и  систематизируются данные о ее "поведении". Конечным результатом этого этапа  является множество знаний о модели R.

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

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

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

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

Глава I

1.   Особенности применения  метода математического  моделирования в  экономике.

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

       Большинство объектов, изучаемых экономической  наукой, может быть охарактеризовано кибернетическим понятием сложная  система.

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

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

       Сложность экономики иногда рассматривалась  как обоснование невозможности  ее моделирования, изучения средствами математики. Но такая точка зрения в принципе неверна. Моделировать можно  объект любой природы и любой  сложности. И как раз сложные  объекты представляют наибольший интерес  для моделирования; именно здесь  моделирование может дать результаты, которые нельзя получить другими  способами исследования.

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

 Глава II 

2.1. Транспортная задача 

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

     Кроме того, к задачам транспортного  типа сводятся многие другие  задачи линейного программирования  – задачи назначениях,  сетевые, календарного планирования.

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

     Транспортная задача линейного программирования формулируется следующим образом. Необходимо минимизировать транспортные расходы 
 
 
 
при ограничениях 
 
, 
 
где c_ij - стоимость перевозки единицы продукции из пункта i в пункт j; x_ij - планируемая величина перевозок из пункта i в пункт j (план перевозок X - матрица размерности m ×n); b_j - потребности в продукте в пункте j; a_i - запасы в пункте i. 
 
Предполагается, что модель закрытого типа, то есть  . 
 
Если модель открытого типа  , то ее всегда можно привести к закрытому типу введением фиктивного пункта производства или фиктивного пункта потребления: 
 
Если  , то  , тогда  , причем  . 
 
Если  , то  ,   и  . 
 
Транспортная задача представляет собой задачу линейного программирования и, естественно, ее можно решить с использованием метода последовательного улучшения плана или метода последовательного уточнения оценок. В этом случае основная трудность бывает связана с числом переменных задачи (m´n) и числом ограничений (m+n). Поэтому специальные алгоритмы оказываются более эффективными. К таким алгоритмам относятся метод потенциалов и венгерский метод.  

  2.2. Составление опорного плана.

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

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

      Условия  транспортной  задачи  заданы транспортной  таблицей.

      Таблица № 1

      Будем  заполнять  таблицу  перевозками  постепенно  начиная  с левой верхней ячейки ("северо-западного угла" таблицы). Будем рассуждать  при этом  следующим образом. Пункт В₁   подал заявку    на  18 единиц груза. Удовлетворим эту заявку за счёт запаса 48, имеющегося  в пункте  А₁ , и запишем перевозку 18 в клетке (1,1). После этого заявка  пункта  В₁ удовлетворена, а в пункте  А₁  осталось  ещё 30  единиц  груза. Удовлетворим  за  счёт  них заявку  пункта  В₂ (27  единиц), запишем 27  в клетке (1,2); оставшиеся  3  единицы пункта  А₁  назначим  пункту  В₃. В составе заявки  пункта  В₃  остались  неудовлетворёнными  39  единиц.  Из  них 30  покроем за  счёт  пункта А₂, чем его запас будет исчерпан, и   ещё 9  возьмём из  пункта  А₃. Из  оставшихся  18  единиц  пункта  А₃ 12  выделим пункту В₄;  оставшиеся  6  единиц  назначим  пункту  В₅,  что вместе  со  всеми 20  единицами пункта  А₄  покроет его заявку.  На  этом  распределение запасов закончено;  каждый  пункт назначения   получил груз,  согласно  своей заявки. Это выражается  в том, что сумма перевозок в каждой  строке  равна   соответствующему   запасу, а в столбце - заявке. Таким образом, нами  сразу же  составлен план  перевозок,  удовлетворяющий  балансовым  условиям. Полученное  решение  является  опорным  решением  транспортной  задачи:    

            Таблица № 2 

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

      Другой  способ - способ минимальной стоимости  по строке - основан на том, что мы распределяем продукцию от пункта A_i не в любой из пунктов B_j, а в тот, к которому стоимость перевозки минимальна. Если в этом пункте заявка полностью удовлетворена, то мы убираем его из расчетов и находим минимальную стоимость перевозки из оставшихся пунктов B_j. Во всем остальном этот метод схож с методом северо-западного угла. В результате, опорный план, составленный способом минимальной стоимости по строке выглядит, так как показано  в таблице № 3.

      При этом методе может получиться, что  стоимости перевозок C_ij и C_ik от пункта A_i к пунктам B_j и B_k равны. В этом случае, с экономической точки зрения, выгоднее распределить продукцию в тот пункт, в котором заявка больше. Так, например, в строке 2:  C₂₁ = C₂₄, но заявка b₁ больше заявки b₄, поэтому 4 единицы продукции мы распределим в клетку (2,1).

Таблица № 3

      Способ  минимальной стоимости по столбцу  аналогичен предыдущему способу. Их отличие состоит в том, что  во втором способе мы распределяем продукцию от пунктов B_i к пунктам A_j по минимальной стоимости C_ji.

      Опорный план, составленный способами минимальных  стоимостей, обычно более близок к  оптимальному решению. Так в нашем  примере общие затраты на транспортировку  по плану, составленному первым способом F₀ = 1039, а по второму F₀ = 723.

      Клетки  таблицы, в  которых  стоят  ненулевые  перевозки,  являются  базисными. Их  число должно  равняться   m + n - 1.  Необходимо отметить  также, что встречаются такие ситуации, когда количество  базисных    клеток  меньше  чем m + n - 1. В этом   случае распределительная задача    называется  вырожденной.  И следует в одной из  свободных клеток поставить количество  перевозок равное нулю. Так, например, в таблице № 3:

      m + n - 1 = 4 + 5 - 1 = 8,

      а базисных клеток 7, поэтому нужно  в одну из клеток строки 3 или столбца 2 поставить значение “0”. Например в клетку (3,5).

      Составляя план по способам минимальных стоимостей в отличии от плана по способу северо-западного угла мы учитываем стоимости перевозок C_ij, но все же не можем утверждать, что составленный нами план является оптимальным.  

Глава III 

3.1 Решение  транспортной  задачи  с использованием модифицированного распределительного метода 

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

Модифицированный  распределительный метод. Этот первый точный метод решения транспортной задачи предложен в 1949 году Кантаровичем А. В. И Гавуриным М. К. по существу он является детализацией метода последовательного улучшения плана применительно к транспортной задаче. Однако в начале он был изложен вне связи с общими методами линейного программирования. Несколько позднее аналогичный алгоритм был разработан Данциом, который исходил из общей идеи линейного программирования. В американской литературе принято называть модифицированным распределительным методом. Метод потенциалов позволяет определить  отправляясь от некоторого опорного плана перевозок построить решение транспортной задачи за конечное число шагов (итераций).       

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

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

      Стоимость  перевозки  единицы  груза  из A_i  в  B_j равна C _ij ; таблица стоимостей  задана. Требуется найти план  перевозок x_ij, который удовлетворял  бы   балансовым  условиям  и  при  этом  стоимость  всех  перевозок  бала  минимальна.

      Идея  метода  потенциалов  для  решения  транспортной задачи  сводиться  к  следующему. Представим  себе что  каждый  из пунктов  отправления  A_i  вносит  за  перевозку  единицы  груза (всё  равно  куда)  какую-то  сумму  a_i ;  в свою  очередь каждый  из  пунктов назначения  B_j  также  вносит  за  перевозку  груза  (куда  угодно)  сумму  b_j . Эти платежи передаются некоторому третьему лицу (“перевозчику“). Обозначим a_i  + b_j  =  č_ij ( i=1..m ;j=1..n)  и будем называть  величину č_ij  “псевдостоимостью” перевозки единицы груза из A_i в B_j. Заметим, что платежи   a_i   и  b_j  не  обязательно должны  быть  положительными; не  исключено, что “перевозчик”  сам платит  тому  или другому пункту  какую-то  премию  за  перевозку. Также надо  отметить, что суммарная псевдостоимость  любого допустимого плана перевозок при заданных  платежах  (a_i   и  b_j  )  одна  и та  же  и от  плана к плану не  меняется.

      До  сих пор  мы никак не связывали  платежи (a_i  и b_j) и псевдостоимости č_ij  с истинными стоимостями перевозок C _ij. Теперь мы  установим между ними связь. Предположим, что план x_ij невырожденный (число базисных клеток в таблице перевозок ровно m + n -1). Для всех  этих  клеток  x_ij  >0. Определим платежи (a_i и b_j) так, чтобы во всех базисных клетках псевдостоимости были ровны стоимостям:

      č_ij = a_i  + b_j  = с_ij ,  при   x_ij  >0.

      Что касается свободных  клеток  (где  x_ij = 0), то  в них соотношение между псевдостоимостями  и стоимостями может быть, какое угодно.

      Оказывается соотношение между псевдостоимостями и стоимостями в свободных клетках показывает, является ли план оптимальным или же  он  может быть  улучшен. Существует  специальная теорема:  Если  для всех  базисных  клеток   плана x_ij  > 0,

      a_i  + b_j  = č_ij= с_ij ,

      а  для  всех  свободных  клеток x_ij =0,

      a_i  + b_j  = č_ij≤ с_ij ,

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

            č_ij= с_ij (для всех  базисных  клеток ) (1)

            č_ij≤ с_ij ( для всех  свободных клеток ) (2) 

называется  потенциальным  планом, а соответствующие   ему платежи (a_i  и b_j ) — потенциалами  пунктов A_i и B_j ( i=1,...,m ; j=1,...,n ). Пользуясь этой  терминологией вышеупомянутую  теорему можно сформулировать  так:

Всякий  потенциальный  план  является  оптимальным. 

      Итак, для  решения  транспортной  задачи  нам  нужно  одно - построить  потенциальный   план. Оказывается  его  можно  построить  методом  последовательных  приближений, задаваясь  сначала  какой-то  произвольной  системой  платежей, удовлетворяющей  условию (1). При  этом  в  каждой  базисной  клетке  получиться  сумма  платежей, равная  стоимости  перевозок  в  данной  клетке;  затем, улучшая  план  следует одновременно  менять  систему платежей. Так, что они приближаются  к потенциалам. При улучшении плана нам помогает  следующее свойство  платежей  и псевдостоимостей: какова  бы ни  была  система платежей  (a_i  и b_j )  удовлетворяющая условию (1), для каждой  свободной клетки  цена  цикла пересчёта равна разности  между стоимостью и псевдостоимостью в данной клетке : g_i,j= с_i,j - č_i,j.