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

	Оптимальное полетное расписание		Таблица 6.3
Порядок	Географическое	Географические координаты
(номер)	наименование	Широта	Долгота
Сщп	Санкт-Петербург	59057'	30О19'
1	Рига	56057'	24О06'
2	Балтийск	54*39'	19=55'
3	Вильнюс	54041'	25017
4	Минск	53054'	27034'
5	Пинск	52О07'	26О06'
6	Киев	50О27'	30=30'
7	Хойники	51054'	29058'
8	Новозыбков	52О30'	32=00'
9	Клиицы	52041'	32=17'
10	Яровшина	53038-	34=42'
11	Плавск	54=41'	37=18'
Финиш	Москва	56=39'	36031'

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

•при планировании вертолетных работ расстояние по поверхно­ сти Земли вычисляется с помощью функции geoway;

•для действий с привязкой к/юрожной сети расстояние опреде­ ляется с помощью матрицы достижимости

du	' dn	-	d\M
/) = d2l	d22	-	diM

dui dMl - dMM

где d,j - расстояние между пунктами Ai к Aj no дорожной сети, i,J = 1,2, ...,М.

Такая матрица D составляется с помощью полной математической индукции при решении задачи коммивояжера дня числа пунктов 2, 3, ..., М-1 при использовании карты региона. При этом расстояния отрезков дорожной сети определяются одним из двух способов:

•простейшего - с использованием обычных инструментов (цир­ куль, курвиметр, линейка);

•компьютерного - с помощью функции geoway.

231

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

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

Допустим, что необходимо построить маршрут из пункта Асарт (с аэродрома базирования) до другого пункта Лфиниш с посещением заданного множества населенных пунктов, причем путь должен про­ ходить через все пункты один раз и иметь минимальную длину. Толь­ ко точки Асщг и Лфишш в частном случае могут принадлежать одному и тому же населещюму пункту. Это самая общая постановка задачи.

При моделировании пространственных перемещений, связанных с поставкой товаров во многие пункты местности, используются уз­ лы queue и ргос (см. рис. 2.10). В аспекте имитации перемещений по маршруту необходимо установить такой порядок элементов в струк­ турном массиве space, чтобы этот порядок и был оптимальным маршрутньпй расписанием. Для определенности считаем, что пункты Асарт и /4финшп имеют специальные признаки.

Сначала необходимо пункт ^старт поставить на место 1, а.^финиш - на место Л/в массиве space.

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

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

232

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

Ам-1	7:||-<1>иниш
/ ' Зона действия ^ ^	*"
вертолета Б

Старт

Рис. 6.9. Схема оперативного решения задачи коммивояжера (задача о двух вертолетах)

233

Если вертолеты при построении маршрута находятся в пунктах Ai и Aj (в процессе составления расписания) и можно считать, что они имеют одинаковую среднюю скорость, то определим вероят­ ность того, что непосещенный пункт ^t принадлежит к зоне ответст­ венности вертолета А, находящегося в пункте А„ по формуле

р. = 1 _ _ ^ * _ , dik + dkj'

где d,ir lidk/- соответствующие расстояния между пунктами А,, А/, я Aj.

При составлении маршрута для действий с привязкой к дорож­ ной сети (автолй)били, речные суда, железнодорожный трайспорт) dikudkj- это элементы матрицы достижимости.

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

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

Рассмотрим алгоритм подробнее. Предположим, что имеется не­ упорядоченный список населенных пунктов, помещенный в массив space. Введем условные обозначения:

i,j,k -номера пунктов в неупорядоченном структурном массиве space;

At -название пункта;

Nt	- порядковый номер пункта / в массиве space после составле­
LI	ния маршрута;
	- расстояние от пункта iV/-l до пункта Л";;
G	- общая длина пути после составления расписания;
Gi	- длина пути вертолета А от пункта ^4ст«рт;
Gi	-дайна пути вертолета Б от пункта/^финиш (навстречу первому);
М	-число упорядочиваемых элементов в массиве space (количе­
	ство пунктов).

Перейдем к процедуре составления расписания. Присвоим на­ чальные значения пунктам старта и финиша:

А\ ~ Астарп Jy\ ~ ^етрт'г

234

Построение маршрута начнем от пункта старта (только для оп­ ределенности) и предположим, что уже выполнено ;с - 1 шагов этой процедуры (х = 1,2,..., М-2).

Допустим, что вертолет А находится в пункте /, а вертолет Б - в пункте j . При этом множество Г] всех упорядоченных пунктов, попавших в расписание после выполнения шага х, содержит 2 + х элементов, а множество Гг всех неупорядоченных пунктов содержит M-2-X элементов. Если Т - множество всех М пунктов, то справед­ лива операция объединения непересекающихся множеств Г = 7^1 и 7^2, где и - операция объединения (сложения). Причем 7*1 П Т'г = О, где П - операция пересечения (умножения).

Рассмотрим отдельно действия для каждого вертолета на шаге х. 1. Вертолет А. В множестве Г: выбирается пункт Ак, имеющий

минимальное значение вьфажения:

dik mm^dik + dkj^

TBS А, еТи AJBTU AirS Tj-

После определения такого пункта делаются следующие изме­ нения:

G = G + dn;

Lk = dfi,;

At« Г2;

Ak e Tu

x = x+l.

Если текущий путь вертолета А станет таким, что Gi > G2, то следующий шаг составления маршрута будет производиться для вертолета Б, так как считаем, что он долетел до пунктау своей зоны ответственности. В противном случае следующий шаг составления расписания опять делаем в отношении вертодета А.

2. Вертолет Б. В множестве Гг выбирается пункт А/,, имеющий минимальное значение вьфажения:

235

dkj mm^dik + dkjj

TaeA,^Tx,AjSTx,Ai£Ti.

После определения такого пункта делаются следующие изме­ нения:

Gi = Gi + dig-, G = G + d,,; Nt = Nj-l;

Lj = dig-.

At« T2,

At e Тй

j =A;

X =X+\.

Если текущий путь вертолета Б станет таким, что Ог "^ G\, то следующий шаг составления маршрута будет производиться для вертолета А, так как считаем, что он долетел до пункта / своей зоны ответственности. В противном случае следующий шаг составления расписания делаем в отношении вертолета Б.

Процедура составления маршрута делается всего за М-2 шагов, после чего множество Гг будет пустым, йТ\ = Т,

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

		Таблица 6.3
	Эффективность применения «алгоритма двух вертолетов»
п/п	Обследуемый	Выигрыш,
	регион	%
1	Гордеевский район	48
2	Клинцовский район	53
3	Красногорский район	54
4	Новозыбковский и Злынковский районы (вместе)	61

236

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

•пилоты эвристически применяют алгоритм «ближайшего непосещенного города»;

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

Реальный эффект в течение летней экспедиционной кампании 1989 г. составил 25 -35% экономии летного времени.

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

Выводы

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

идругих данных.

2.Геоинформационные системы имеют следующие свойства:

•в состав ГИС входят базы данных, причем полная технология обработки информации в ГИС значительно шире, чем просто работа

сбазой данных;

•ГИС рассчитана не просто на обработку данньк, а на проведе­ ние экспертных оценок во многих ситуациях;

•данные, которые обрабатывает и хранит ГИС, имеют не только пространственную, но и временную х^)актеристику, что важно в первую очередь для географических данных.

237

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

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

4.Взаимное расположение точек на поверхности Земли в сред­ них широтах, характерных для России, стран Европы и США, реко­ мендуется изображать на экране монитора в виде нормальной кони­ ческой проекции.

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

Вопросы для самопроверки

1.Какая проекция рекомендуется к использованию при компью­ терном изображении земной поверхности на территории России?

2.Как происходит отображение геоинформации в функциональном окне имитационной модели?

3.Какое средство в составе системы Pilgrim служит для определе­ ния расстояния меяаду точками Х и У по их географическим ко­ ординатам? Какие математические соотношения при этом ис­ пользуются?

4.Что такое карта? Какие основные свойства она имеет?

5.Что такое географические координаты?

6.Чем отличается план местности от к^ты?

7.Что такое картографическое изображение?

8.Из чего состоит легенда карты?

9.Из каких элементов состоит математическая основа карты?

10.Чем отличается карта от снимка, полученного с самолета или искусственного спутника Земли?

238

11.Для каких целей используются геоинформационные системы?

12.Каковы основные функции ГИС?

13.Что такое «электронный кадастр»?

14.Чем отличается геоид от эллипсоида вращения?

15.Когда необходимо учитывать, что Земля не является шаром?

16.Как определяется масштаб карты?

17.Какие картографические проекции используются в средних и приэкваториальных широтах?

18.Что означает аппроксимация (пространственная аппрокси­ мация)?

19.Как решается задача оценки взаимосвязи между явлениями на поверхности Земли?

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

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

22.Как формулируется задача коммивояжера в простейшей поста­ новке? С привязкой к сети речных, шоссейных и железных дорог? Для выполнения вертолетных работ?

23.В чем заключается преимущество алгоритма «двух вертолетов» при моделировании логистических задач по сравнению с алго­ ритмом «ближайшего непосещенного города» и другими алго­ ритмами?

Глава 7

ПЛАНИРОВАНИЕ ИМИТАЦИОННОГО КОМПЬЮТЕРНОГО ЭКСПЕРИМЕНТА

7.1 КИБЕРНЕТИЧЕСКИЙ ПОДХОД К ОРГАНИЗАЦИИ ЭКСПЕРИМЕНТАЛЬНЫХ

ИССЛЕДОВАНИЙ СЛОЖНЫХ ОБЪЕКТОВ И ПРОЦЕССОВ

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

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

Рассмотрим получение первого и второго момента произвольной величины, не являющейся параметром узла модели. Если неизвест­ ная величина х является интервалом времени (или пропорциональна интервалу), то ее можно связать:

1)с интервалом пребывания клапана key, дополнительно вве­ денного в модель, в запертом состоянии;

2)с временем жизни дополнительно сгенерированного транзакта

вузле creat, помещенного в запертый клапан key, который в нуж­ ный момент открывается и направляется в дополнительный терми­ натор term.

Впервом случае математическое ожидание длительности пре­ бывания клапана в запертом состоянии т определяется автоматиче­ ски в качестве параметра узла key. Дисперсия - это произведение

240