Методы покрытия гиперсети корневым деревом для оптимизации системы транспортных путей тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат наук Воронова, Анна Михайловна

• Воронова, Анна Михайловна
• кандидат наук
• 2013

Оглавление диссертации кандидат наук Воронова, Анна Михайловна

Содержание

Введение

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

1.1 Анализ существующих математических моделей и алгоритмов на графовых, гиперграфовых и гиперсетевых структурах

1.2 Заключение по главе

Глава 2. Постановка задачи

2.1 Описание задачи размещения транспортных объектов на лесосеке

2.2 Общие рекомендации по размещению погрузочных пунктов и сети волоков на лесосеке

2.3 Сбор данных об особенностях лесосеки и применение рассчитанных схем волоков при проведении подготовительных и основных работ на лесосеке

2.4 Заключение по главе

Глава 3. Математические модели в виде графовых, гиперграфовых и гиперсетевых структур для представления транспортной сети

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

3.2 Математическая модель транспортной сети на основе гиперграфа

3.3 Математическая модель транспортной сети на основе двухуровневой гиперсети

3.4 Заключение по главе

Глава 4 Математические методы покрытия графа, гиперграфа, гиперсети деревом минимальной стоимости, поиск корня покрывающего дерева

4.1 Алгоритм нахождения корня покрывающего дерева с учетом параметров заданного графа, гиперграфа, гиперсети

4.2 Алгоритм построения покрывающего дерева гиперграфа, гиперсети

4.2.1 Идея работы алгоритма и блок схема алгоритма построения покрывающего дерева гиперсети

4.2.2 Псевдокод алгоритма построения покрывающего дерева гиперсети

4.2.3 Пример работы алгоритма построения покрывающего дерева на гиперсети

4.3 Общий вид алгоритма построения покрывающего дерева

4.3.1 Анализ алгоритма и тестовые примеры

4.3.2 Временная сложность алгоритма. Ускорение алгоритма с помощью «двоичной кучи»

4.3.3 Условия существования решения

4.4 Заключение по главе

Глава 5. Программный комплекс для построения информационной системы по проектированию схемы транспортных путей на лесосеке

5.1 Назначение программного комплекса

5.2 Описание генератора входных значений и анализ алгоритма построения

корневого покрывающего дерева гиперсети

5.3 Заключение по главе

Заключение

Список литературы

Приложение А (обязательное) Экспериментальные данные и рассчитанные

покрывающие деревья

Приложение Б (обязательное) Результаты экспериментальных данных

Приложение В (обязательное) Свидетельства о регистрации программ

Введение диссертации (часть автореферата) на тему «Методы покрытия гиперсети корневым деревом для оптимизации системы транспортных путей»

Введение

Актуальность темы исследования

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

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

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

Степень разработанности

Гиперсети рассмотрены в работах В.К. Попкова, Г.Ы. Токтошова и др. [67 -75, 86]. Введены основные понятия теории гиперсетей, рассмотрены задачи оптимизации некоторых систем сетевой структуры, приведены формальные

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

Цель и задачи

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

Для достижения поставленной цели требуется решить следующие задачи:

1. Построить математическую модель транспортных путей при помощи покрывающего дерева двухуровневой гиперсети специального вида.

2. Разработать алгоритм построения покрывающего дерева двухуровневой гиперсети с поиском корня.

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

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

Теоретическая значимость работы

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

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

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

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

Кроме того разработанный программный комплекс может быть использован в учебном процессе для проведения практических работ при изучении студентами лесоинженерного факультета дисциплины «Технология лесосечных работ». Методология и методы исследования

В диссертационной работе используются методы математического моделирования, теории графов, гиперграфов, гиперсетей, дискретной математики, аналитической геометрии, методы разработки алгоритмов, объектно-ориентированное программирование. Программы написаны в среде разработке Microsoft .NET на языке С#.

Положения, выносимые на защиту

1. Предложен метод математического моделирования путей первичного транспорта леса при помощи покрывающего дерева двухуровневой гиперсети специального вида.

2. Разработан алгоритм построения покрывающего дерева двухуровневой гиперсети с поиском корня.

3. Разработана программа, реализующая предложенный алгоритм.

4. Даны рекомендации к применению предложенного подхода к построению схем путей первичного транспорта леса на лесосеке.

Степень достоверности

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

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

1. VII Всероссийская школа-семинар «Прикладные проблемы управления макросистемами» (Апатиты, 2008).

2. VIII международная научно-техническая конференция «Новые информационные технологии в целлюлозно-бумажной промышленности и энергетике» (Петрозаводск, 2008).

3. Международная научно-техническая конференция «Актуальные проблемы развития лесного комплекса» (Вологда, 2008).

4. 16 Международная конференция серии "Математика. Компьютер. Образование" (Пущино, 2009).

5. X Международная молодежная научная конференции "Севергеоэкотех-2009" (Ухта, 2009).

6. I республиканская научно-практическая конференция молодых ученых, аспирантов, докторантов «Повышение эффективности лесного комплекса Республики Карелия» (Петрозаводск, 2009).

7. IX международная научно-техническая конференция «Новые информационные технологии в целлюлозно-бумажной промышленности и энергетике» (Петрозаводск, 2010).

8. X международная научно-техническая конференция «Новые информационные технологии в целлюлозно-бумажной промышленности и энергетике» (Петрозаводск, 2012).

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

Программа «Планирование схемы волоков на лесосеке» зарегистрирована в Объединенном фонде электронных ресурсов «Наука и образование» (ОФЭРНиО) № 17756 от 27.12.2011 г.

Информационно-аналитическая система «Расчет схемы волоков на лесосеке с учетом минимизации отрицательного воздействия трелюющей техники на грунты» зарегистрирована в Реестре программ для ЭВМ Свидетельство № 2013614304 от 29.04.2013.

Информационно-аналитическая система «Составление схемы путей первичного транспорта леса на лесосеке с учетом минимизации расходов на топливо» зарегистрирована в Реестре программ для ЭВМ № 2013614105 от 23.04.2013.

Содержание работы

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

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

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

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

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

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

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

В заключении формулируются результаты диссертационного исследования.

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

1.1 Анализ существующих математических моделей и алгоритмов на графовых,

гиперграфовых и гиперсетевых структурах

Для решения задач сетевой структуры используют представление объектов исследуемой задачи в виде графов, гиперграфов или гиперсетей. Это позволяет представить объекты реального мира в виде структур, удобных для моделирования, расчетов и поиска необходимых параметров сетей. Применение различных вычислений, производимых на графах, гиперграфах и гиперсетях, позволяет найти кратчайший объездной путь, спланировать оптимальный маршрут между любой парой или всеми пунктами и решить другие задачи. При этом такое представление отражает основные свойства реальных объектов. К задачам сетевой структуры относятся задачи проектирования дорожной сети, коммуникационных трасс, линий электропередач и многие другие [15, 30, 31, 36, 37, 77, 88, 89].

Классической задачей в сетевой постановке является транспортная задача, в которой осуществляется поиск оптимального плана перевозок однородного продукта из однородных пунктов наличия в однородные пункты потребления на однородных транспортных средствах. Для классической транспортной задачи выделяют два типа задач: критерий стоимости (достижение минимума затрат на перевозку) или расстояний и критерий времени (затрачивается минимум времени на перевозку) [47, 76].Задачу проектирования временных транспортных путей также можно рассматривать как транспортную задачу.

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

и

заданное количество населенных пунктов [47]. Минимальное покрывающее дерево — это ациклический связный подграф минимального веса данного связного неориентированного графа, в который входят все его вершины, где под весом дерева понимается сумма весов входящих в него рёбер. Задача о вершинном покрытии обобщается задачей о покрытии множества. Дано конечное множество и и семейство 5 его подмножеств. Покрытием называют семейство Сс5 наименьшей мощности, объединением которых является и [47, 49, 50, 60, 77]. Методами решения задачи о покрытии являются жадные приближенные алгоритмы, генетические алгоритмы и другие [1, 4, 6, 8].

Гиперграф представляет собой пару (V, Е), где V — непустое множество вершин гиперграфа, а Е — семейство непустых подмножеств множества V, называемых рёбрами гиперграфа [40, 48]. Теория графов и гиперграфов подробнее рассмотрена в [10, 40, 43, 48, 64, 87, 90].

Для моделирования многослойных сетевых задач используют иерахические гиперсети. В работах [67 - 75, 86] рассмотрена теория гиперсетей и применение этой теории для моделирования задач сложной сетевой структуры, таких как строительство инженерных сетей электросвязи, сети автомобильных дорог, нефтепроводных, газопроводных сетей и прочих. В статье [56, 67, 86] предложена гиперсетевая технология формализации задачи оптимизации инженерной сети на земной поверхности с неоднородной территорией и сведение ее к решению соответствующей задачи на иерархической гиперсети.

В работах [67, 68, 72, 73] в качестве математической модели инженерных сетей рассматривается гиперсеть, с помощью которой можно описать совокупность сетей, в том числе сети разной природы и назначения, а также карты рельефа и топографические карты местности. Введено определение основных понятий теории гиперсетей. Гиперсетью называется шестерка 5 = (х, V, Я, Р, IV), включающая в себя

X = (х1,х2,...,х„) — множество вершин;

V - (У1 > у2 > • • •' ) — множество ветвей;

Я = (г1,г2,...,гт) - множество ребер;

Р: V -> 2х — отображение, сопоставляющее каждому элементу у е V множество р(у) с X его вершин. Тем самым отображение Р определяет граф Р8 = (Х,У,Р);

^: Я 2УРЗ - отображение, сопоставляющее каждому элементу г е Я множество ветвей ^(г). Семейство подмножеств ветвей 2ГРЗ содержит такие подмножества, ветви которых составляют связную часть графа . Отображение ^ определяет гиперграф = (V, Я, F);

\/ге Я IV :г 2р(/7(г)) - отображение, сопоставляющее каждому элементу г е Я подмножество И/(г) с р(р(г)) его вершин, где P(F(r)) - множество вершин в Р5, инцидентных ветвям Отображение Ж определяет граф ИЪ = (х, Я,IV).

Гиперграф Р51 - первичная сеть, а гиперграф Ц'Б - вторичная сеть.

В работе [67] приведена постановка задачи минимального покрытия вершин ребрами гиперсети. Пусть задана взвешенная гиперсеть 5 = (X, V, Я, Р, IV), в которой Х = (х],х2,...,х„), Г = Я = (гх,г2,...,гт), у(г,) — вес ребра г,.

Требуется найти подмножество ребер Я' с Я такое, чтобы:

УхеХ, 1(х)аЯ', £у(г,)-ипш, []1(г) = Х,

/¡ей' гб/;'

где /(х) - множество всех ребер инцидентных (или слабо инцидентных) вершине х, а /(г) — множество вершин инцидентных (или слабо инцидентных) ребру г.

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

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

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

В работах [56, 67, 68, 72, 73, 86] рассматриваются вопросы учета неоднородности рельефа при строительстве инженерных сетей в горной местности. Предлагаются подходы к решению задач построения сетей связи и линий электропередач минимальной стоимости с учетом сильно пересеченной местности на основе применения иерархических гиперсетей. Пусть на ограниченном участке земной поверхности задано положение объектов, которые надо связать линейными сооружениями так, чтобы затраты на строительство инженерной сети были минимальны.

В [67] предлагается следующая схема учета неоднородности рельефа. В качестве модели участка представлена некоторая поверхность в трехмерном пространстве с некоторыми точками на ней. Обозначим ее через П, а множества точек на ней — X. Эта поверхность является образом земной поверхности, а каждая из точек х, е X — образом пункта земной поверхности, в котором

размещен какой-либо объект. Проекция поверхности П на плоскости хОу представляет собой область £>, в которой заданы точки, являющиеся образами точек поверхности П. С целью поиска оптимальных проектных решений методами теории графов и теории гиперсетей область £> разбивают регулярной сеткой т на л, образованной двумя семействами прямых: х = х}, у = \,...п,

параллельных оси Оу и у = у1 , / = 1,...т, параллельных оси Ох . С целью оценки стоимости строительства единицы длины коммуникации в области £) для каждой дуги сетки вводят функции следующего вида:

С{х] ,у, )= си • /(*., х,+к ^г), к, г = {-1; 0; 1},

где =(*,,>>,), / = \,...т, у = 1,...п — координаты точек пересечения сетки; /(*,>> ~ длина дуги из узла хи в узел х1+к]+г; в зависимости от

рассматриваемой ситуации / может интерпретироваться по-разному: / - время строительства по ветвям; / - надежность ветви; / - безопасность ветви и т.п. сц е Я+ и сц> 1 - коэффициент стоимостного удорожания, учитывающий

специфичность природных условий в каждой точке области И. Значение коэффициента сч должно выбираться в каждом конкретном случае в зависимости

от специфики природных условий и рельефа местности.

Формулируется задача в [67]: задача оптимизации линейного участка инженерных сетей заключается в поиске допустимого маршрута на плоскости хОу между заданными точками из множества X, который определяет минимальное значение приведенных затрат на этом участке.

В [67] рельеф моделируется на основе карты местности: рельеф местности в виде регулярной сетки с шагом ячеек / метров и минимальным перепадом высот к метров. Каждой клетке сеточной модели рельефа сопоставляют вершину графа ТО = (X, V) топоосновы. Каждой ветви сопоставляется вес, вычисляемый по одной из следующих формул:

a) Узлы соседних ячеек (хц, х1+кпг), где к,г = {-1; 0; 1}, расположены на одном

уровне /(*„, х1+ки+г)=1;

b) Вершины соседних клеток (ху, х1+к;+г) на разных уровнях

c) Вершины соседних клеток (ху, х!+к]+г) - на разных уровнях (диагональ с двумя ступенями) , х1+к^+г

)=л/2/2+4/г2 ;

(1) Вершины соседних клеток (ху, х,+4у+г) - на одном уровне (диагональ)

Ахи> *<+*,/+/•

е) Вершины соседних клеток х1+ки+г) - на разном уровне (диагональ с одной ступенью) /(ху, х1+к^+г

) = л/212+1г2 .

Таким образом, сеточное описание сложности рельефа определяет некоторое метрическое пространство W заданной размерностью. Далее определяется гиперсеть.

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

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

В работах Салминена Э. О., Гурова С. В., Большакова Б. М., Григорьева И. В. из Санкт-Петербургской государственной лесотехнической академии имени С. М. Кирова [33, 34, 35, 82] исследована задача определения схемы волоков на лесосеке. Для решения задачи территория лесосеки разбита на непересекающиеся квадратные участки (участки набора пачки древесины). Каждому участку поставлено в соответствие число - обобщенный коэффициент, характеризующий степень воздействия трелевочного трактора на почвогрунт участка по следующему правилу: чем больше коэффициент, тем слабее грунт, следовательно, тем сильнее отрицательное воздействие трелевочного трактора. Далее методом динамического программирования получена схема волоков с широким фронтом погрузки (или одним погрузочным пунктом с краю лесосеки).

Недостатками применения такого подхода являются ограничения на форму лесосеки, форму и размеры территории набора пачки древесины, привязка к конкретному погрузочному пункту. В работах [33, 34, 35, 82] рассмотрены лишь

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

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

В диссертации предложена математическая модель лесосеки в виде взвешенного ориентированного графа и алгоритм на основе метода Дейкстры для нахождения оптимального места размещения погрузочного пункта на лесосеке с учетом свойств грунта. Вершины графа соответствуют непересекающимся участкам набора пачки древесины, а дуги - возможным путям пролегания трелевочных волоков, соединяющим простейшие участки друг с другом. Веса дуг графа определяются, исходя из несущей способности грунта. В таком случае задача нахождения места размещения погрузочного пункта и схемы волоков на лесосеке с учетом особенностей грунта сводится к задаче поиска вершины в графе (выделенной вершины) методом Дейкстры, до которой сумма расстояний от всех остальных вершин в графе является минимальной [5, 55, 61]. Тогда кратчайшие пути в графе между всеми вершинами и выделенной вершиной укажут схему, согласно которой необходимо разместить трелевочные волока.

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

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

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

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

Список литературы диссертационного исследования кандидат наук Воронова, Анна Михайловна, 2013 год

Список литературы

1. Акулич, И. Л. Математическое программирование в примерах и задачах: Учебное пособие для студентов экономических специальностей вузов 2.изд., испр.и доп. / И. Л. Акулич // Москва: Высшая школа, 1993.

2. Анисимов, Г. М. Экологическая эффективность трелевочных тракторов / Г. М. Анисимов, И. В. Григорьев, А. И. Жукова // СПб.: Издательство СПб ГЛТА, 2006 г. 352 с.

3. Арманд, А. Н. Спутниковые СВЧ радиометры дециметрового диапазона / А. Н. Арманд, Ю. Г. Тищенко, В. С. Аблязов, А. А. Халдин // Современные проблемы дистанционного зондирования Земли из космоса: Физические основы, методы и технологии мониторинга окружающей среды, потенциально опасных явлений и объектов. Сборник научных статей. Выпуск 5. Том I. -Москва: ООО «Азбука-2000», 2008. - с. 214 - 218.

4. Асанов, М. О. Дискретная оптимизация: Учебное пособие / М. О. Асанов // Екатеринбург, 1998.

5. Ахо, А. В. Построение и анализ вычислительных алгоритмов / А. В. Ахо, Д. Э. Хопкрофт, Д. Д. Ульман // Москва: Мир, 1979.

6. Ахо, А. В. Структуры данных и алгоритмы / А. В. Ахо, Д. Э. Хопкрофт, Д. Д. Ульман // Москва: Вильяме. 2003.

7. Беллман, Р. Динамическое программирование / Р. Беллман // М.: Мир, 1960.

8. Беллман, Р. Прикладные задачи динамического программирования / Р. Беллман, С. Дрейфус // Москва: Мир, 1965.

9. Белоусов, А. И. Лекции по дискретной математике: Учебное пособие/ А. И. Белоусов, Б. В. Мартынов, А. Н. Щетинин; Под ред. А. И. Белоусова // Москва: Изд-во МГТУ им. Н. Э. Баумана, 1994.

Ю.Берж, К. Теория графов и её применение / К. Берж // Москва: Издательство иностранной литературы, 1962.

П.Берштейн, JI. С. Нечеткие графы и гиперграфы / Л. С. Берштейн, А. В. Боженюк. Москва: Научный мир, 2005.

12.Вагнер, Г. Основы исследования операций: В 3 т. / Г. Вагнер // Москва: Мир, 1972 - 1973.

13.Валяжонков, В. Д. Современные машины и технологические процессы лесосечных работ. Учебное пособие / В. Д. Валяжонков, И. В. Григорьев // СПб: Издательство ЛТА, 2009. 288 с.

Н.Вентцель, Е. С. Исследование операций / Е. С. Вентцель // Москва: Наука, 1980.

15.Верник, С. М. Линии связи: учеб. для вузов / С. М. Верник, И. И. Гроднев, Л. Н. Кочановский // Москва: Радио и связь, 1995. - 488 с.

16.Воронова, А. М. Гиперграфовая модель задачи размещения погрузочных пунктов и сети волоков на лесосеке с нечетким описанием свойств грунта / А. М. Воронова, Р. В. Воронов // Материалы IX международной научно-технической конференции «Новые информационные технологии в ИБП и энергетике». Петрозаводск: Изд-во 111 У, 2010. С. 30-34.

17.Воронова, А. М. Задача покрытия гиперсети взвешенным корневым деревом и ее приложение для оптимального проектирования схем волоков на лесосеках'/ А. М. Воронова, Р. В. Воронов, М. А. Пискунов // Информатика и системы управления. 2012. № 1 (31). С. 56-64. 9 с.

18.Воронова, А. М. Задача размещения волоков и погрузочных пунктов на лесосеке и вопросы применения оптимальных схем на практике / А. М. Воронова, Р. В. Воронов, М. А. Пискунов // Ученые записки Петрозаводского государственного университета. Серия: Естественные и технические науки. № 9 (103). Петрозаводск: Изд-во ПетрГУ, 2009. С. 58 - 62.

19.Воронова, А. М. Исследование и классификация действительных схем размещения волоков на лесосеке при сортиментной технологии заготовки леса / А. М. Воронова, М. А. Пискунов // Вестник Московского государственного университета леса: Лесной вестник. - 2011. - № 3. - С. 77 - 80.

20.Воронова, А. М. Математическая модель размещения волоков на лесосеке / А. М. Воронова // Материалы VIII международной научно-технической конференции «Новые информационные технологии в целлюлозно-бумажной промышленности и энергетике» (22 сентября - 26 сентября 2008 года.). -Петрозаводск: изд-во ПетрГУ, 2008. С. 39-41.

21.Воронова, А. М. Математическое моделирование схемы волоков на лесосеке с учетом особенностей грунта / А. М. Воронова // Математика. Компьютер. Образование. Тезисы XVI международной конференции. - Пущино, 19-24 января 2009. С. 85.

22.Воронова, А. М. Методы и модели построения схем волоков на лесосеке / А. М. Воронова, М. А. Пискунов // Опыт лесопользования в условиях Северо-запада РФ и Фенноскандии: Материалы международной научно-технической конференции, (20 - 22 сентября) - Петрозаводск: ПетрГУ, 2011. С. 28 - 29. ¿

23 .Воронова, А. М. Моделирование размещения погрузочных пунктов и схемы волоков на лесосеке в виде нечеткого гиперграфа / А. М. Воронова // Материалы X международной молодежной научной конференции «Севергеоэкотех-2009» (18-20 марта): в 4 ч.; ч. 4. - Ухта: УГТУ, 2009. С. 58-61.

24.Воронова, А. М. Моделирование схемы волоков при помощи покрытия гиперсети взвешенным корневым деревом / А. М. Воронова, Р. В. Воронов, М. А. Пискунов // Ученые записки Петрозаводского государственного университета. Сер. «Естественные и технические науки». 2012. № 2 (123). С. 114-117.

25.Воронова, А. М. Об одном подходе к моделированию размещения погрузочного пункта и схемы волоков на лесосеке / А. М. Воронова, М. А. Пискунов // Актуальные проблемы развития лесного комплекса: материалы международной научно-технической конференции. — Вологда: ВоГТУ, 2009. С. 14-16.

26.Воронова, А. М. Обоснование использования нечетких структур для моделирования размещения погрузочных пунктов и сети волоков на лесосеке / А. М. Воронова, Р. В. Воронов // Актуальные вопросы современной науки:

Сборник научных трудов (Выпуск 7) / Под общ. ред. С.С. Чернова. - В 2-х кн. - Кн. 1. - Новосибирск: ЦРНС, 2009. С. 86-93.

27.Воронова, А. М. Перспективы создания и использования систем автоматизированного проектирования схем волоков на лесосеке / А. М. Воронова, М. А. Пискунов // Актуальные проблемы лесного комплекса: Сборник научных трудов Брянской государственной инженерно-технологической академии. Вып. 29. Брянск -2011. С. 38 — 41.

28.Воронова, А. М. Применение гиперсети для моделирования и построения схемы волоков с учетом свойств грунта и рельефа на лесосеке / А. М. Воронова // Материалы X юбилейной международной научно-технической конференции «Новые информационные технологии в ЦБП и энергетике». Петрозаводск: Изд-во ПетГУ, 2012. С. 31-33.

29.Воронова, А. М. Распределение проходов по длине волока и расчёт рейсовых нагрузок трелёвочного трактора при движении по грунтам с низкой несущей способностью на примере хлыстовой технологии заготовки леса /

A. М. Воронова, Р. В. Воронов, М. А. Пискунов, В. Н. Васильев // Научный журнал Кубанского государственного аграрного университета. [Электронный ресурс]. - Краснодар: КубГАУ, 2012. - №77(03). - Шифр Информрегистра: 0421200012/0202.-Режим доступа: http://ej.kubagro.ru/2012/03/pdf/43.pdf. 11 с.

30.Галямов, В. А. О задаче оптимизации построения первичной сети связи /

B. А. Галямов // Проблемы оптимизации сложных систем: Материалы I Азиатской Международной школы семинара - г. Новосибирск, 19-26 июня 2005. - Новосибирск, 2005. - С. 66-78.

31.Гимади, 3. X. Дискретные экстремальные задачи принятия решений: Учебное пособие / 3. X. Гимади //Новосибирск, 1991.

32.Гольдштейн, А. Л. Исследование операции: многокритериальные задачи: Конспект лекций / А. Л. Гольдштейн // Пермь, 1995.

33.Григорьев, И. В. Пути совершенствования технологических процессов лесосечных работ на северо-западе Российской Федерации / И. В. Григорьев, А. И. Жукова // Актуальные проблемы развития лесного комплекса: материалы

международной научно-технической конференции. - Вологда: ВоГТУ, 2009. С. 19.

34.Григорьев, И. В. Снижение отрицательного воздействия на почву колесных трелевочных тракторов обоснованием режимов их движения и технологического оборудования: Научное издание / И. В. Григорьев // СПб.: СПбГЛТА, 2006.-236 с.

35.Григорьев, И. В. Средощадящие технологии разработки лесосек в условиях Северо-Западного региона Российской Федерации / И. В. Григорьев,

A. И. Жукова, О. И. Григорьева, А. А. Иванов // СПб.: ЛТА, 2008. 174 с.

36. Гэри, М., Джонсон Д. Вычислительные машины и трудно решаемые задачи / М. Гэри, Д. Джонсон // Москва: Мир, 1982.

37.Давидян Д. Б. Высокогорные линии электропередачи / Д. Б. Давидян // Ереван, 1979.-187 с. ^

38.Духовин, Ю. И. Оптимальное планирование в лесной, целлюлозно-бумажной и деревообрабатывающей промышленности / Ю. И. Духовин, Ю. Г. Павлов,

B. А. Марков // Москва: Лесная промышленность, 1984.

39.Евстигнеев, В. А. Применение теории графов в программировании / В. А. Евстигнеев // Москва: Наука, 1985.

40.Емеличев, В. А. Лекции по теории графов / В. А. Емиличев, О. И. Мельников, В. И. Сарванов, Р. И. Тышкевич // Москва: Наука, 1990.

41.Ершов, А. П. Введение в теоретическое программирование / А.П.Ершов // Москва: Наука, 1977.

42.Заде, Л. Понятие лингвистической переменной и ее применение к принятию

приближенных решений / Л. Заде // Москва: Мир, 1976. 43.Зыков, А. А. Основы теории графов / А. А. Зыков // Москва: Наука, 1987.

44.Карманов, В. Г. Математическое программирование / В. Г. Карманов // Москва: Физматлит, 2001.

45.Кнут, Д. Искусство программирования для ЭВМ, т. 1-3 / Д. Кнут // Москва: Мир 1977.

46.Коган, Д. И. Дискретные многокритериальные задачи распределительного типа: Учебное пособие/ Д. И. Коган // Н. Новгород, 1991.

47.Кормен, Т. Алгоритмы: построение и анализ / Т. Кормен, Ч. Лейзерсон, Р. Ривест // - Москва: МЦНМО; БИ-НОМ. Лаборатория знаний, 2004.

48.Кристофидес, Н. Теория графов. Алгоритмический подход / Н. Кристофидес // Москва: Мир, 1978.

49.Кузнецов, В. Ю. Два алгоритма решения задачи о минимальном покрытии прямоугольной области с запретными участками / В. Ю. Кузнецов // Актуальные проблемы в науке и технике : сб. ст. третьей всероссийской зимней шк.-сем. аспирантов и молодых ученых, 20-23 февраля 2008. 2008. Т.2. С.227-235.

50.Кузнецов, В. Ю. Задачи покрытия: модели, алгоритмы и приложения / В. Ю. Кузнецов, М. С. Егорова // Принятие решений в условиях неопределенности : сб. науч. тр. 2008. С. 138-143.

51 .Кук, В. Компьютерная математика / В. Кук, Г. Бейз // Москва: Наука, 1990.

52.Лавров, С. С. Автоматическая обработка данных, хранение информации в памяти ЭВМ / С. С. Лавров, Л. И. Гончарова // Москва: Наука, 1971.

53.Лебедева, Л. А. Модели целочисленного программирования: Учебное пособие / Л. А. Лебедева // Норильск, 1994.

54.Летова, Т. А. Задачи линейного и целочисленного программирования: Учебное пособие / Т. А. Летова // Москва: Изд-во МАИ, 1996.

55.Липский, В. Комбинаторика для программистов / В. Липский // Москва: Мир, 1988.

56.Лотарев, Д. Т. Преобразование задачи Штейнера на Евклидовой плоскости к задаче Штейнера на графе / Д. Т. Лотарев, А. П. Уздемир // Автоматика и телемеханика - 2005. - №10. - С. 80-92.

57.Махов, Г. А. Влияние эксплуатационных режимов работы гусеничного трелевочного трактора на его колееобразование / Г. А. Махов, Л. М. Эмайкин // Технология и комплексная механизация лесосечных работ: Труды. Химки: ЦНИИМЭ, 1976. С. 115-119.

58.Меламед, И. И. Бикритериальные задачи дискретного программирования с MINSUM-MAXSUM критериями / И. И. Меламед // Москва: ВЦ РАН, 2000.

59.Меламед, И. И. Некоторые задачи дискретного программирования с двумя и тремя критериями / И. И. Меламед // Москва: ВЦ РАН, 1998.

60.Моргунов, И. Б. Основы дискретной оптимизации некоторых задач упорядочения: На прим. учеб. процесса / И. Б. Моргунов // Москва, 1994.

61.Морз, Ф. М. Методы исследования операций / Ф. Морз, Д. Е. Кимбелл // Москва: Изд-во Наука, 1956.

62.Нефедов, В. Н. Дискретные задачи оптимизации: Учебное пособие /

B. Н. Нефедов // Москва: Изд-во МАИ, 1993.

63.Нуриев, Р. М. Дискретная математика Ч. 1. / Р. М. Нуриев // 1994. 64.Ope, О. Теория графов / О. Ope // Москва: Изд-во Мир, 1968. 368 с.

65.Орлов, А. И. Задачи оптимизации и нечеткие переменные / А. И. Орлов // Москва: Знание, 1980. 64 С.

66.Петрунин, С. В. Исследование операций Ч. 1: Методы оптимизации /

C. В. Петрунин // //Москва, 1994.

67.Попков, В. К. Гиперсетевая технология оптимизации инженерных сетей в горной или пересеченной местности / В. К. Попков, Г. Ы. Токтошов // Вестник Бурятского гос. ун-та. - 2010. - № 9. - С. 276-282.

68.Попков, В. К. Гиперсети и структурные модели сложных систем / В. К. Попков // Математические и имитационные модели сложных систем. СМ-6. -Новосибирск, 1981. - С. 26 - 48.

69.Попков, В. К. Математические модели живучести сетей связи / В. К. Попков // Новосибирск: ВЦ СО АН СССР, 1990. 233 с.

70.Попков, В. К. Математические модели и методы оптимизации городских транспортных систем / В. К. Попков // Материалы 2-й Всероссийской конференции «Проблемы оптимизации и экономические приложения». - Омск, -2009.-С. 80-81.

71.Попков, В. К. Математические модели связности / В. К. Попков // Новосибирск: ИВМиМГ СО РАН, 2006.

72.Попков, В. К. Методологические вопросы оптимизации инженерных сетей на неоднородной территории / В. К. Попков, Г. Ы. Токтошов // Известия Томского политехнического университета. 2010. Т. 317. № 5.

73.Попков, В. К. Методы оптимизации структур зоновых сетей связи /

B. К. Попков, С. Б. Кауль, М. И. Нечепуренко, Е. М. Букреев, А. И. Калеников // Новосибирск: ИВМиМГ СО РАН, 1984. - 180 с.

74.Попков, В. К. Применение теории гиперсетей в задачах оптимизации систем сетевой структуры / В. К. Попков // Проблемы оптимизации сложных систем: Материалы III Азиатской Международной школы семинара. - г. Бишкек, Кыргызская Республика, 1-12 июля 2007. - Новосибирск, 2007. - С. 87-92.

75.Попков, В. К. Трудно решаемые задачи теории гиперсетей / В. К. Попков // Российская конференция «Дискретная оптимизация и исследование операций»: Материалы конференции института математики. - Новосибирск, - 2007. -

C. 69-73.

76.Пярнпуу, А. А. Вопросы алгоритмизации в некоторых прикладных задачах / А. А. Пярнпуу, В. И. Хохлюк // Москва, 1994.

77.Рахимов, К. Р. Горные линии электропередачи: учебное пособие / К. Р. Рахимов, Ю. П. Беляков // Бишкек, 1999. - 284 с. *

78. Редькин, А. К. Технология и машины лесосечных работ: Учебник для ВУЗов / А. К. Редькин, В. И. Патякин, И. В. Григорьев, В. А. Иванов и др. // СПб.: ГПУ, 2012. -362

79.Романовский, И. В. Алгоритмы решения экстремальных задач / И. В. Романовский // Москва: Изд-во Наука, 1977.

80.Романовский, И. В. Дискретный анализ / И. В. Романовский // СПб: Невский диалект, 1999.

81.Романовский, И. В. Субоптимальные решения / И. В. Романовский // Петрозаводск: Изд-во ПетрГУ, 1998.

82.Салминен, Э. О. Размещение волоков на заболоченных лесосеках / Э. О. Салминен, С. В. Гуров, Б. М. Большаков // Лесная промышленность. -1988. — № 3. — С. 3.

83.Сачков, В. Н. Введение в комбинаторные методы дискретной математики / В. Н. Сачков // Москва: Наука, 1982.

84.Скрыпник, В. И. Испытания колесного трактора с пачковым захватом / В. И. Скрыпник, Ю. Е. Рыскин, Н. А. Петраков // Лесная промышленность. 1992. №8. С. 21-22.

85.Сухарев, А. Г. Курс методов оптимизации / А. Г. Сухарев, А. В. Тимохов,

B. В. Федоров // Москва: Изд-во Наука, 1986.

86.Токтошов, Г. Ы. Сеточная аппроксимация элементов рельефа местности / Г. Ы. Токтошов // Информатика и проблемы телекоммуникаций: Материалы Российской научно-технической конференции - Новосибирск, — 2009. — Т. 1. -

C. 23-24.

87.Уилсон, Р. Введение в теорию графов / Р. Уилсон // М.: Мир, 1977.

88.Федотов, Г. А. Инженерная геодезия / Г. А. Федотов // Москва: Высшая школа, 2009.-463 с.

89.Фрэнк, Г. Сети, связи и потоки / Г. Фрэнк, И. Фриш // Москва: Связь, 1978.

90.Харари, Ф. Теория графов / Ф. Харари // Москва: Мир, 1973.

91.Хахулин, Г. Ф. Постановки и методы решения задач дискретного программирования: Учебное пособие / Г. Ф. Хахулин // Москва: Изд-во МАИ, 1992.

92.Хачатуров, В. Р. Комбинаторные методы и алгоритмы решения задач дискретной оптимизации большой размерности / В. Р. Хачатуров, В. Е. Веселовский, А. В. Злотов // Москва: Наука, 2000.

93.Чернецкий, В. И. Математическое моделирование стохастических систем / В. И. Чернецкий // Петрозаводск, 1994.

94.Яблонский, С. В. Введение в дискретную математику / С. В. Яблонский // Москва: Наука, 1986.

95.Яхъяева, Г. Э. Нечеткие множества и нейронные сети: Учебное пособие / Г. Э. Яхъяева // М.: Интернет-Университет Информационных Технологий; БИНОМ. Лаборатория знаний, 2006. - 316 с.

112

Приложение А (обязательное)

Экспериментальные данные и рассчитанные покрывающие деревья

В таблице А. 1 приведены данные категорий грунта для экспериментов № 1 - 50 и рассчитанный схемы волоков, для которых черным квадратом обозначено место погрузочного пункта, линиями показаны волока на лесосеке. Толщина линий показывает категорию волока, образованного после завершения трелевочных работ (чем толще линия обозначения волока, тем глубже колея на этом волоке).

Приведем обозначения категорий грунта:

• 4 - твердый грунт (обозначен желтым цветом);

• 3 - твердопластичный грунт (обозначен оранжевым цветом);

• 2 - мягкопластичный грунт (обозначен розовым цветом);

• 1 - текучий грунт (обозначен красным цветом).

Таблица А.1 - Данные категорий грунта экспериментов № 1- 50 и рассчитанные

схемы волоков

№ Сгенерированные данные категорий __грунта_

Рассчитанная схема волокоз

3 1 1 2 3

1 1

2 3

1 1

3 3 1 1

4 1 3 4

4 3 2 3 3 2 20 4 3 3 3 4

3

4

3

4 3

2 3 1 4

40 3 4

1 1 3 4

3 2 2 3 2 4 1 1 1 2 4 1

3

4 1 3 3 3

1 1

1 3

1 1

3 2

4 4

4 3 4 1

30 з 1

2|~3] 3

1 1

1 1

3 3

3

4 3 1

1 1 1 4 1 4

1 1 3 4

3 4 40

4 1

1 1 4 3

1 1 1 3

3 4

3 2

4 1

1 1 3 1

2 4

2 2 1 3 3

4 1

2 2 4 2

1 1

2 1

2 3 1

3 4 2 3 4 4

30 4

1 1 1 2

11

13

1 1 4 2 2 3

2 4|_3 1 1 3 4 3 3 3 3 3 3 3

4 1 1

2 3 1

4 3

4 4

4 3

1 1 3 3

1 1 4 4

10

1 1 3 2

1 3 3 3 3 3 3d 3

2 4 4 4 2

1 1 1 3

1 1

2 3

4 4

4 4 4

3

4 4

3 1

4 3

1 1

2 3

3 4 1 1

12

_4

2 4

3 1

4 1 1

3

4

4 1

1 1 2 4 4 2 1 2

1 1 1 1

1 1 4 2

3 1 2 3

3 1 3|~3| 3 12 2

14

1 2 1 1

1 1 3 3

4 2 3

1 4 1

4 3 4

1 3 4

1 4 4

30 4

4 3 3

1 4 4

1 2 1

1 1 4

1 1

15 1 3 2 1 4 3 3 3 1 4 3 3 1 4 3 4 4 4 3 1

1 2 2 1 1 1 2 4 4 4 3 3 2 1 3 4 3 1 4 2

3 3 4 4 3 4 1 4 4 1 3 4 3 2 2 2 4 1 4 3

3 1 1 4 4 4 3 3 3 1 2 1 3 2 1 4 1 4 1 2

3 3 3 1 2 3 4 4 3 3 2 1 3 4 3 2 4 2 2 4

3 3 2 1 1 2 1 1 3 3 3 4 4 3 4 3 2 2 3 4

4 3 3 3 4 4 2 3 4 1 4 4 1 3 4 3 3 2 4 3

4 2 3 1 1 2 3 2 1 1 3 1 1 1 4 4 3 2 2 3

3 3 1 3 4 2 1 4 2 4 3 3 4 3 1 4 4 3 3 4

3 4 4 4 2 3 2 1 1 2 3 1 3 2 2 3 4 4 4 4

16 4 1 3 4 4 3 1 2 4 4 3 1 4 2 3 3 1 4 3 4

2 4 2 1 3 3 4 2 4 4 1 2 4 1 4 3 4 1 4 4

3 4 4 3 1 2 4 4 4 1 3 3 4 4 3 2 2 3 4 2

1 3 3 1 3 3 4 3 1 3 4 3 1 1 2 2 4 2 2 3

2 4 3 3 3 2 3 3 1 3 3 1 1 4 3 3 1 4 1 3

1 3 4 2 1 4 2 2 3 4 3 3 1 4 3 4 3 4 1 4

4 3 2 2 3 1 3 4 1 3 4 1 2 3 2 4 4 4 2 4

2 1 3 3 2 1 3 4 3 4 1 4 1 1 4 3 3 4 4 3

1 3 3 2 4 2 2 3 3 3 1 3 4 3 3 3 2 1 2 4

1 3 1 1 3 4 4 1 3 3 3 3 3 1 2 1 3 3 3 2

17 4 4 2 4 1 4 2 3 3 3 1 3 2 1 4 2 4 2 2 4

2 2 3 1 3 3 3 2 1 2 2 1 1 3 2 3 1 4 3 3

3 3 4 3 1 2 1 2 4 4 1 3 2 4 1 3 2 2 4 3

4 4 4 2 1 3 4 3 4 4 4 1 2 3 3 1 4 3 1 1

1 4 2 3 2 4 3 3 1 1 4 1 4 3 2 2 3 3 1 3

3 4 3 1 1 3 4 4 1 4 1 2 2 4 3 3 3 3 3 3

2 3 1 2 2 1 3 2 4 4 3 1 2 4 4 4 4 3 2 1

3 4 3 2 4 3 4 1 4 2 4 1 1 3 4 1 4 1 4 3

4 1 2 2 4 3 4 3 1 4 4 4 4 3 3 3 2 1 3 2

4 4 3 2 4 1 3 1 4 4 4 3 1 1 4 1 4 1 3 4

18 1 2 2 4 2 4 3 2 4 1 4 3 3 4 4 3 2 4 3 2

4 1 2 4 2 3 3 3 1 4 2 2 1 4 2 4 1 3 1 3

3 4 2 1 3 1 4 3 3 1 2 3 4 3 2 3 3 4 2 2

4 4 3 3 1 1 4 4 4 4 3 1 1 1 4 4 3 3 3 4

2 3 2 4 4 2 4 4 3 4 1 1 3 1 4 4 3 1 2 3

3 4 30 4 4 4 4 4 4 1 4 3 4 4 4 4 4 4 4

4 2 2 4 4 2 4 2 4 3 4 1 3 3 3 4 3 3 2 3

3 4 2 2 2 2 4 4 1 3 2 3 3 2 3 3 3 4 4 1

3 2 1 3 2 2 1 4 4 2 1 4 3 4 3 1 2 2 4 4

4 3 2 2 3 1 2 1 3 2 3 1 4 3 3 2 2 1 4 2

19 |_3| 2 2 4 2 4 3 4 4 1 4 2 4 4 1 2 3 4 2 4

3 4 2 1 3 4 2 1 2 4 1 1 4 2 1 1 3 1 2 4

4 2 2 4 2 1 1 4 1 2 4 1 3 3 4 4 2 2 4 4

4 4 4 2 1 4 1 1 2 4 4 3 4 4 3 4 1 4 2 4

3 4 2 4 2 3 3 2 2 2 4 4 4 3 3 4 3 3 4 3

3 4 3 2 3 3 1 4 2 4 2 3 2 2 3 3 3 1 3 2

2 3 4 1 2 3 3 2 2 3 4 4 1 2 3 4 1 4 1 2

2 2 3 1 4 4 4 4 2 4 1 3 4 3 2 2 3 4 2 1

4 3 3 1 1 1 4 3 4 1 4 2 3 1 3 4 3 3 1 1

4 4 2 3 1 2 1 3 3 1 2 1 3 4 1 3 2 4 3 1

20 4 4 3 3 1 2 3 2 2 4 2 3 1 3 2 3 4 2 1 3

3 2 1 3 3 4 4 4 4 4 2 1 2 2 2 2 4 3 4 4

4 4 2 2 4 1 4 3 1 1 4 1 3 2 4 4 3 1 2 4

3 4 1 4 4 1 2 1 1 2 2 2 2 4 3 3 2 « 2 4

4 3 1 2 2 2 4 1 1 2 1 2 4 3 1 4 2 3 4 1

2 4 4 3 1 4 3 4 1 3 4 4 4 1 4 3 1 3 3 4

3 4 2 1 2 4 1 1 4 3 4 4 1 4 2 3 1 1 3 2

2 3 3 4 1 4 4 2 3 3 4 4 4 4 3 3 2 3 4 1

1 3 4 2 3 4 3 4 3 3 2 2 2 3 3 2 2 4 1 3

2 3 4 4 3 4 3 3 4 3 3 4 1 4 4 4 2 2 2 4

2 3 2 3 4 3 4 3 3 3 2 4 2 3 2 2 3 1 3 4

2 2 1 2 2 2 4 3 2 4 3 3 2 4 1 1 2 1 4 2

1 3 2 1 3 4 1 4 4 4 3 2 1 4 2 2 4 2 1 3

3 3 3 3 2 3 1 3 3 2 2 2 3 1 2 4 4 3 3 2

2 4 3 3 1 3 3 2 4 2 4 4 3 4 1 3 3 3 3 1

3 1 1 1 1 3 2 4 4 1 1 3 1 1 2 3 4 2 3 2

3 3 3 2 1 2 4 2 2 1 3 3 3 3 2 3 4 1 4 1

2 4 1 1 2 3 2 2 2 2 3 1 1 2 3 1 3 1 2 2

4 2 3 3 4 3 2 2 4 3 4 4 1 3 1 4 1 1 3 2

3 4 2 3 2 3 2 4 2 2 3 2 2 4 2 1 2 2 2 3

3 1 4 4 1 3 2 2 2 3 2 3 3 2 3 1 1 1 1 1

1 2 4 1 3 2 2 3 2 4 1 2 4 4 4 3 4 2 2 2

1 2 2 3 2 3 1 1 2 2 1 3 1 4 2 4 3 4 3 2

4 4 4 2 3 3 2 2 3 2 3 1 2 4 4 1 2 4 2 1

3 2 2 2 2 3 4 3 3 1 4 3 3 2 4 4 2 1 2 4

2 3 3 1 2 4 1 3 4 2 4 4 1 3 2 1 4 3 1 2

4 2 2 2 4 3 1 1 2 3 3 2 2 2 1 2 3 3 3 1

2 3 2 2 1 3 2 3 2 2 1 4 2 2 2 1 2 3 3 3

1 4 4 3 3 2 4 1 1 3 3 1 3 4 3 4 4 1 3 2

1 1 4 2 2 3 2 4 2 4 2 1 1 1 4 1 3 4 1 1

3 1 2 4 3 2 3 3 2 3 1 2 2 2 1 2 3 4 4 1

4 4 2 3 4 1 2 1 4 2 1 2 2 2 4 2 1 2 1 3

2 1 1 3 2 1 2 4 4 1 4 3 4 2 2 4 4 3 3 1

2 2 3 1 2 4 1 3 1 3 1 1 3 2 2 2 3 3 2 3

4 2 1 2 2 3 4 4 2 2 4 1 3 1 3 2 1 2 3 3

4 1 2 4 2 3 3 2 3 3 2 2 2 2 3 3 3 4 2 4

1 1 4 1 3 1 2 2 2 3 4 1 2 1 4 2 2 4 3 3

4 2 4 2 2 4 4 1 4 2 1 2 3 2 3 3 4 4 2 1

3 4 4 2 2 1 3 2 2 2 2 2 2 2 4 3 1 4 2 2

2 2 1 4 2 2 2 2 2 4 2 2 3 3 2 4 2 2 3 3

33

2|_2 4 3

1 1

2 4

1 3

2 2 2 2 4 1 4 2 4 3

2 4 2 1

3 1

34

2[_2J 2

2 2 3 3 1 1 3 2

3 4 1 3 3 2 3 1 2

1 1

35

1 1 3 1

1 1

36

1 1 2 3

1 1 4 2

1 4

2 2 4 4 2

2

3

4 2 4 3

4 3 2 1 4 2 1 2

37

J

1 4 4 1 1 1 2

1 1 4 2

1 1 2 2

1 1 2 2

1 1

2 2

38

1 1 2 1

1 2 3 2 3 2

2 1 2

3

1 1 1 2 1 2 2 1

4 2

46

1 1

3 3 1

3 3 3 3 2 3 3 3 3

1 1

2 1

4 3 1 1

1 1

3 3

3 3_ 3 3 3

3

4 2 2 1 2 1 1

1 1

47

48

49

50

3

3

4

3

4

3 2

4 3 3

_3" 3 3 1 2

3

4 2 1

J_

2 1 3 2 1 3 1 1 3 _2_ 3 3 3 2 2

3 2

4 1 1 3 4

3|_3 1 4

1 1 3 3

1 1 3 1

3 2 3

1 4 4

2 1 1 1 1 1

3 3 3 3 2 2

2 3 3 3 3

_3^

2 3

2 3 1 1

3 3

1 1

3 3