Имитационное моделирование экономических процессов

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

Аппроксимация 1-го порядка (линейное уравнение) дает плос­ кость, отражающую только общий уклон поверхности, это очень грубое, слишком общее приближение. Поверхность 2-го порядка уже больше похожа на исходную модель, а аппроксимация 3-го по­ рядка (кубическое уравнение) дает достаточно хорошее приближе­ ние к исходной поверхности.

Тригонометрические функции позволяют описывать сложные, сильно расчлененные поверхности. Сферические функции приме­ няют, если при вычислениях нельзя пренебречь кривизной земной поверхности. Аппроксимация с помощью двойных рядов Фурье по­ зволяет вводить постепенное усложнение поверхности за счет до­ бавления двухмерных синусоид с разными фазами и амплитудами. Компьютерное моделирование обеспечивает выполнение подобных аппроксимаций для поверхнрстей любой сложности с помощью уравнений высокого порядка, содержащих порой несколько десят­ ков членов разложения.

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

Статистический анализ картографического изображения пресле­ дует главным образом три цели:

•изучение характеристик и функций распределения явления;

•определение формы и тесноты связей между явлениями;

•оценку степени влияния отдельных факторов на изучаемое яв­ ление и вьвделение ведущих факторов.

221

в основу всякого статистического исследования кладется выбор­ ка, т.е. некоторое подмножество однородных величин а„ снятых с карты по регулярной сетке точек (систематическая выборка), в слу­ чайно расположенных точках (случайная выборка), на ключевых участках (ключевая выборка) или по районам (районированная вы­ борка).

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

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

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

коэффициента парной корреляции г. Его числовые значения заклю­ чены в интервале [-1, 1]. Если г равно I или - 1 , то существует функциональная прямая или обратная связь. Когда г близок к нулю, связь между явлениями отсутствует, а при г ^ | 0,7 | связь считается существенной. Коэффициент коррелящш рассчитывают по формуле

	г-^	iiai-MaXbi-Mb)
		,
где О/иЬ,	- выборочные данные, полученные по картам А и В;

п- о&ьем выборки (число пар данных);

МаИМь - значения средних соответственно для а, и Ь,:

222

ип

п п

Ста и о* - значения среднеквадратичных соответственно для а, и 6,:

Ств=у Ма и a6 =

Оценку точности вычисления коэффициента корреляции г полу­ чают по формуле

W r = — 7 = - >

V«

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

50значений.

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

Значения г заключены в интервале [0°, 180°]. Если а = 0°, что свидетельствует о полном совпадении направлений скатов поверх­ ностей, то г = cos 0° = 1, т.е. между явлениями существует прямая связь. При а = 180° скаты поверхностей направлены в противопо­ ложные стороны, и г == cos 180°*= - 1 , следовательно, связь сильная, но отрицательная, а при а = 90° связь между явлениями отсутствует, поскольку г = cos 90° = 0.

На рис. 6.7 представлены две статистические поверхности и по­ казаны направления их наибольших скатов. Угол между ними ока­ зался равен 36°, тогда г = cos 36° = 0,81. Такие приближенные вы­ числения особенно удобны при сравнении изолинейных карт.

223

.2000

2000

Граница региона Изолиния дат начала цветения клевера Изотермы июня

Рис. 6.7. Приближенное определение коэффициента корреляции по карте региона

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

ранговый коэффициент корреляции у, который вьиисляют по фор­ муле

		у = 1 -	% ^"."^ь..
			п ~п
где р	п р	~ ранги значений, полученных соответственно по картам А и
"»•	^1	В, т.е. их порядковые номера в возрастающей последова­
		тельности (1,2,3 и т.д.);
		- о&ьем выборки.

224

По смыслу коэффициент у аналогичен коэффициенту парной корреляции г, он изменяется в интервале от -1 до +1. При этом не требуется больших объемов выборки, расчеты можно выполнять даже при и = 3. К тому же не нужны точные количественные значе­ ния а, и 6,, достаточно знать их ранги. Все это удобно для работы с картограммами, где используются интервальные шкалы, а объем выборки ограничен числом административных районов.

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

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

		п
		ак= l.lk,fk +ек,
		1=1
где oi,	-	исходные показатели;
fi	-ьыделенные главные факторы, дающие синтетическую оценку
		изучаемого явления;
/,	-	вес каждого фактора в синтетической оценке (факторная нагрузка);
eit	-	остаток, характеризующий неучтенные отклонения.

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

225

Энтропией £(А) некоторой системы А назьшается сумма произ­ ведений вероятностей со/ различных состояний этой системы на ло­ гарифмы вероятностей, взятая с обратным знаком:

п

Е{А) = £;(Ш1,Ш2,...,©„) = -Icojlogjco,-.

1=1

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

«О/),

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

6.5 РЕШЕНИЕ ЗАДАЧИ КОММИВОЯЖЕРА С ПРИВЯЗКОЙ К ГЕОГРАФИЧЕСКИМ КООРДИНАТАМ

Существует классическая задача исследования операций, кото­ рая в различных модификациях решается для оптимизации процес­ сов в логистике, при сплошном обследовании населенных пунктов в каком-либо регионе в связи с экономическими, экологическими или медицинскими проблемами, а также в зонах чрезвьлчайных ситуа­ ций. Она получила название «задачи коммивояжера». .Рассмотрим три постановки этой задачи.

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

226

•каждый пункт необходимо посетить только один раз;

•длина маршрута должна быть минимальной.

Данная постановка предполагает два взаимосвязанных, но прак­ тически невьшолнимых предположения:

•коммивояжер (или транспортное средство) врегда может пере­ двигаться в данном регионе по прямой линии;

•вся поверхность региона - это идеально гладкая и твердая плоскость, пригодная для движения транспортных средств.

При такой постановке задачи можно использовать следующие методы составления маршрута: линейное программирование, метод «ветвей и границ», динамическое программирование и алгоритм «ближайшего непосещенного города». Первые три метода при большом числе населенных пунктов требуют применения ЭВМ большой мощности и создания довольно сложньц расчетных про­ грамм, а четвертый метод дает решения, которые на 20-50% хуже оптимального (в зависимости от густоты и неравномерности рас­ стояний между пунктами).

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

Постановка задачи коммивояжера с привязкой к дорожной се­ ти. В регионе с развитой сетью дорог имеется:

•множество М населенных пунктов;

•множество Л'^ перекрестков (развилок) вне населенных пунк­

тов;

•множество К участков дорог.

Участком дороги назовем дорогу от пункта А до пункта Б, при­ чем пункт - это населенный пуЬкт или перекресток.

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

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

|?*ден весь набор решений, среди которых есть и оптимальное.

227

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

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

•каждый пункт необходимо посетить только один раз;

•длина маршрута должна быть минимальной;

•при определении отрезков маршрута учитьшается, что поверх­ ность Земли - эллипсоид;

•на маршруте могут работать один или два вертолета (если два - то они движутся навстречу друг другу).

Задача в данной постановке может решаться теми же методами. Существует «алгоритм двух вертолетов», который подходит для

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

Прежде чем перейти к описанию этого алгоритма, введем два определения и сформулируем одну теорему (без доказательства). Рассмотрим рис. 6.8. Предположим, что нужно составить полетное расписание для самолета, который вылетает из Санкт-Петербурга в Москву, причем он должен пролететь по кратчайшему маршруту над одиннадцатью промежуточными населенными пунктами. Пред­ варительное расписание было составлено вручную и выдано эки­ пажу самолета (табл. 6.2). Траектория маршрута показана на ри­ сунке.

Определение 1. Под корректировкой понимается тако? исправле­ ние маршрута следования, которое приводит к его сокращению без исключения каких-либо населенных пунктов из маршрутного распи­ сания. Корректировка вьшолняется на основании графической тра­ ектории движения, изображенной на карте, и опыта руководителя движения.

228

I o^

', ,Ба/1Тнис

Рис. 6.8. Пример составления оптимального маршрута коммивояжера с двумя корректируемыми участками:

1 - неоптимального участка; 2 - петли

На рис. 6.8 пунктирным контуром 1 выделен неоптимальный участок, где установлен следующий порядок движения (полета):

Рига->Вильнюс-^Балтийск->Минск.

Корректировка, проведенная экипажем, заключается в измене­ нии порядка посещения (пролета). Оптимальным будет (это заметно на рисунке):

Рига-» Балтийск-^Вильнюс-* Минск.

229

			Таблица 6.2
	Полетное расписание (исходный вариант)
Порядок	Географическое	Географические координаты
(номер)	наименование	Широта	Долгота
Ст^гг	Санкт-Петербург	ЗЭ'ЗТ	30° 19'
1	Рига	56°57'	24О06'
2	Вильнюс	54°41'	25°17'
3	Балтийск	54°39'	19055'
4	Минск	53<'54'	27=34'
5	Хойники	51''54'	29°58'
6	Киев	50°27'	30=30'
7	Пинск	52°07'	26=06'
8	Новозыбков	52030'	32=00'
9	Клинцы	52''4Г	32=17'
10	Яровщина	53°38'	34=42'
И	Плавск	54041'	37=18'
Финиш	Москва	56039'	36=31'

Определение 2. Петлей называется траектория движения по маршруту, имеюшая замкнутый контур из ломаных линий, причем один угол такого контура находится вне перекрестка или населенно­ го пункта.

На рис. 6.8 пунктирным контуром 2 выделен участок, имеющий характерную петлю. Точка А (угол Пинск-А-Хойники на пересече­ нии траекторий Минск->Хойники и Пинск->Новозыбков) действи­ тельно находится 3^ пределами населенных пунктов, через которые проходит м^шрут.

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

Исходя из этой теоремы участок маршрута внутри контура 2 не­ оптимален. На нем установлен порядок:

Минск->Хойншси->Киев-»Пинск->^Новозыбков.

После корректировки порядок изменится, а длина траектории уменьшится:

Минск->Пинск->Киев->Хойники->Новозыбков.

В результате двух вьшолненных корректировок из исходного (псевдооптимального) полетного расписания получено расписание полета по оптимальному маршруту (табл. 6.3).

230