WWW.DISS.SELUK.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА
(Авторефераты, диссертации, методички, учебные программы, монографии)

 

Министерство образования Российской Федерации

Санкт-Петербургская государственная

лесотехническая академия им. С. М. Кирова

Сыктывкарский лесной институт (филиал)

Кафедра экологии и природопользования

АГРОЭКОЛОГИЯ

Методические указания и контрольные задания

для студентов заочной формы обучения

по специальности 600900 – Экономика и управление в АПК

Сыктывкар 2003 Рассмотрены и рекомендованы к изданию советом сельскохозяйственного факультета Сыктывкарского лесного института 29 мая 2003 г.

Составитель:

кандидат сельскохозяйственных наук, доцент Г. Г. Романов Отв. редактор:

кандидат биологических наук, доцент Г. Б. Лопатина Рецензент:

заведующий сектором аграрной экономики доктор экономических наук, профессор В. А. Иванов (Институт социально-экономических и энергетических проблем Севера Коми НЦ УрО РАН) В данных методических указаниях приведена рабочая программа дисциплины “Агроэкология”, соответствующая современным требованиям подготовки инженеров по специальности 600900 – Экономика и управление в АПК, даны рекомендации и указания к выполнению контрольных работ студентами заочной формы обучения. В приложениях приведены экологические законы, правила и принципы, а также термины и понятия, употребляемые в агроэкологии.

© Г. Г. Романов, составление, © Сыктывкарский лесной институт (филиал) Санкт-Петербургской государственной лесотехнической академии им. С. М. Кирова, Учебное издание

ГЕННАДИЙ ГРИГОРЬЕВИЧ РОМАНОВ

АГРОЭКОЛОГИЯ

Методические указания и контрольные задания для студентов заочной формы обучения по специальности 600900 – Экономика и управление в АПК Оригинал-макет подготовлен в редакционно-издательском отделе СЛИ по электронной версии рукописи, представленной составителем.

Редактор, верстка – В. Н. Столыпко Корректор – С. В. Сердитова Редакционно-издательский отдел СЛИ СПбГЛТА.

Подписано в печать 05.09.03. Бумага офсетная. Формат 60 х 90 1/16. Печать офсетная.

Гарнитура Таймс. Усл. печ. л. 1,5. Уч.-изд. л. 0,9. Тираж 120. Заказ №.

Сыктывкарский лесной институт (СЛИ) 167981, г. Сыктывкар, ул. Ленина, Отпечатано в типографии СЛИ 167981, г. Сыктывкар, ул. Ленина,

ВВЕДЕНИЕ

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

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

Т Е О Р Е Т И Ч Е С К А Я Ч АС Т Ь

Исходные определения для задачи о нахождении кратчайшего пути взяты из теории графов.

Граф G = (N, Х) состоит из конечного непустого множества вершин (узлов) N и заданного множества Х, содержащего в качестве элементов неупорядоченные пары различных вершин из N. Каждый элемент из Х называют ребром.

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

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

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

Граф называют ациклическим, если в нем нет циклов. Дерево – связный ациклический граф.

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

Элементы из М называют ориентированными ребрами, или дугами.

Ориентированная сеть D = [N, M] представляет собой ориентированный граф с заданным набором функций, каждая из которых любому ориентированному ребру (дуге) ставит в соответствие некоторый параметр.

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

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

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

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

Вершина графа, не имеющая ни одного прообраза, называется истоком; вершина, не имеющая ни одного образа, называется стоком.

Постановка задачи определения кратчайшего пути. Пусть сеть D = [N, M] – ориентированный граф, заданный на множестве узлов N, из которых s исток, t – сток, и множестве дуг М. Требуется найти (s–t) путь, имеющий наименьшую стоимость.

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

1. Присвоить потенциалу узла-источника значение s = 0. Потенциалам остальных узлов присвоить значение R, где R – очень большое число.

2. Начиная с узлов, связанных с узлом-источником одной дугой, производим пересчет потенциалов по формуле: j = i + hij, где i – потенциал начального узла дуги, j – потенциал конечного узла дуги, hij – стоимость передачи единицы потока по дуге ij. Если потенциал j получает значение меньшее полученного на предыдущем шаге (например, j R), присваиваем узлу потенциал, имеющий меньшее значение.

3. Проверяется, достигнут ли узел-сток (получает ли узел сток значение, т. е. j = t ). Если узел-сток не достигнут, узел с потенциалом i исключается из дальнейших расчетов, повторяется шаг 2 для узла, имеющего наименьшее значение потенциала j. Если узел-сток достигнут – переход к шагу 4.

4. Определяется последовательность узлов, образующих кратчайший путь.

Дерево кратчайших путей связывает узел-источник со всеми остальными узлами сети кратчайшими путями.

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

Таким образом, потоком в сети D = [N, M] называется неотрицательная вещественная функция, удовлетворяющая условиям:

1. ограниченности: поток по любой дуге сети не превосходит пропускной способности этой дуги;

2. сохранения: суммарный поток, заходящий в любую вершину сети (кроме истока и стока), равен суммарному потоку, выходящему из этой вершины.

Дуга сети называется насыщенной, если поток по этой дуге равен пропускной способности этой дуги.

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

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

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

Минимальный разрез можно отыскать при помощи максимального потока сети на основании теоремы Форда Фалкерсона: в любой транспортной сети величина любого максимального потока равна пропускной способности любого минимального разреза.

Для нахождения максимального потока в сети разработан алгоритм Форда Фалкерсона:

1. Перенумеровать все вершины сети произвольным образом, кроме истока и стока.

2. Задать некоторый начальный поток в сети (нулевой для первой итерации).

3. Вершинам сети присвоить целочисленные метки, а дугам знаки “+” и “” по следующим правилам:

а) вершине-истоку присвоить метку 0;

б) находим непомеченную вершину W, смежную помеченной вершине V. Если поток по соединяющей вершины V–W дуге меньше пропускной способности этой дуги, то происходит помечивание, иначе переходим к рассмотрению следующей вершины. Если вершина W является образом помеченной вершины V, то происходит прямое помечивание (дуга в прямом направлении допустима): вершина W получает метку, равную номеру вершины V, соединяющая вершины V–W дуга получает метку “+”, переход к рассмотрению следующей вершины. Если вершина W не имеет ни одного помеченного прообраза, поток по дуге в прямом направлении больше 0, то происходит обратное помечивание (дуга допустима в обратном направлении): вершина W получает метку, равную номеру вершины V (являющейся в данном случае её образом), соединяющая вершины W–V дуга получает метку “”, мы переходим к рассмотрению следующей вершины. Процесс помечивания продолжается до тех пор, пока все удовлетворяющие этим условиям вершины не получат метку.

4. Если в результате процедуры помечивания вершина-сток метки не получила, то текущий поток максимальный, задача решена. В противном случае, перейти к пункту 5.

5. Рассмотреть последовательность вершин L = (U0,..., v0), метка каждой из которых равна номеру следующей за ней вершины, и множество дуг М, соединяющих соседние вершины из L.

Построение нового потока по схеме:

Если дуга принадлежит множеству М (смотри выше) и имеет знак “+”, то новый поток по этой дуге = старый поток по этой дуге + К (см. далее).

Если дуга принадлежит множеству М и имеет знак “”, то новый поток по этой дуге = старый поток по этой дуге – К.

Если дуга не принадлежит множеству М, то поток по дуге оставляем без изменения.

Схема нахождения К.

К = min{К1;К2}, где для нахождения К1 рассматриваются все дуги, принадлежащие множеству М и имеющие знак “+”, и для каждой такой дуги вычисляется разность между пропускной способностью дуги и потоком по этой дуге. Затем из этих значений разностей выбирается минимальное значение и присваивается К1.

Для нахождения К2 рассматриваются все дуги, принадлежащие множеству М и имеющие знак “”. Затем из этих дуг выбирается дуга с минимальным потоком, и значение потока по этой дуге присваивается К2.

Таким образом, каждая итерация алгоритма предполагает выполнение шагов 2, 3, 4, 5. Выполнение алгоритма продолжается пока не найдем максимальный поток (минимальный разрез).

Постановка задачи поиска максимального потока: найти максимальный поток в транспортной сети (рис.1) с помощью алгоритма Форда Фалкерсона:

Результат выполнения алгоритма после шагов 2, 3, 4 первой итерации показан на рисунке 2. Поскольку дуги сети своей нумерации не получили пропускную способность дуг показываем как Сij, где i – номер узла, из которого выходит дуга, j – номер узла, в который дуга входит.

Рис. 2. Результат выполнения 1-й итерации до изменения потока Изменение потока на 5-м шаге первой итерации определяется следующим образом:

На дугах, образующих путь 1–2–3–6, задается поток f, равный 1. Дуга 1–2 становится насыщенной.

Осуществляется выполнение второй итерации. Заново осуществляется помечивание (рис. 3). Вершина 6 получает метку (М=3).

Рис. 3. Результат выполнения 2-й итерации до изменения потока Изменение потока в ходе выполнения второй итерации определяется:

На дугах, образующих путь 1–4–3–6, задается поток f, равный 1. Дуга 3–6 становится насыщенной.

На 3-й итерации алгоритма осуществляется помечивание (рис.4).

При этом из вершины 3 прямых допустимых дуг не выходит, однако дуга 2–3 является допустимой в обратном направлении. Вершина 6 получает метку (М=5).

Рис. 4. Результат выполнения 3-й итерации до изменения потока Изменение потока в ходе выполнения третьей итерации определяется:

3; 1 } = 1.

На дугах, образующих путь 1–4–3–2–5–6, задаем поток f, равный 1.

Дуга 5–6 становится насыщенной.

На 4-й итерации алгоритма осуществляется помечивание (рис. 5).

При этом из вершины 3 допустимые дуги не выходят. Вершина 6 не получает метку. Выполнение алгоритма заканчивается.

Максимальный поток в сети равен 3. Минимальный разрез образуют насыщенные дуги 3–6 и 5–6.

Алгоритм Форда Фалкерсона используется при решении многих практических задач. Одна из них задача об источниках и потребителях.

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

При выполнении работы должны выполняться требования по составлению и оформлению.

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

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

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

Характеристика основных вопросов начинается со второй страницы.

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

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

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

При оформлении отчета необходимо указать масштаб карты и год издания.

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

Выполнение работы состоит из следующих этапов:

1. Построение исходного графа;

2. Построение исходной сети;

3. Определение потенциалов узлов при помощи алгоритма Дийкстры;

4. Построение дерева кратчайших путей.

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

- железнодорожный вокзал;

- центральный рынок;

- гостиница «Центральная»;

- остановка «Давпон» (конечная);

- торговый центр «Орбита»;

- для студентов СЛИ учебные корпуса института: корпус № (ул. Ленина, 39) и учебный корпус на улице Южная, 11, также могут быть выбраны любые два пункта по желанию студента.

На маршруте предлагается выбрать примерно 15–18 узлов.

Исходный граф показывается на рисунке в графической части работы.

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

На дугах задается параметр стоимости передачи единицы потока.

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

Исходная сеть показывается на рисунке в графической части работы.

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

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

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

Дерево кратчайших путей показывается на рисунке в графической части работы.

В заключении отмечается, чему равно расстояние (в метрах или километрах) между заданными пунктами.

Пример оформления курсовой работы В качестве примера выполнения работы рассматривается определение кратчайшего пути на маршруте Железнодорожный вокзал – уч. корпус СЛИ (ул. Южная, 11).

Задание на курсовую работу: Определить кратчайший путь на маршруте Железнодорожный вокзал – уч. корпус СЛИ (ул. Южная, 11); построить сетевую модель для маршрута и дерево кратчайших путей.

Исходные данные: карта г. Сыктывкара, М 1:10000, 1996 г.

1. Построение исходного графа В качестве узлов (вершин) графа берутся следующие пункты:

– ул. Коммунистическая при пересечении с другими улицами образует узлы:

пересечение с Октябрьским проспектом узел 3;

– ул. Димитрова при пересечении с другими улицами образует узлы:

пересечение с ул. Старовского и Гаражной узел 7;

пересечение с Октябрьским проспектом узел 8;

– пересечение Окт. проспекта с ул. К. Маркса узел 9;

– пересечение ул. Первомайской с ул. Куратова узел 10;

– пересечение Окт. проспекта с ул. Куратова узел 11;

– пересечение Сысольского шоссе с ул. Гаражной узел 12;

13;

– пересечение ул. Первомайской, Южной, Сысольского шоссе Исходный граф показан на рисунке 1 (приложение1).

2. Построение исходной сети.

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

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

Исходная сеть показана на рисунке 2 (приложение 1).

3. Определение потенциалов узлов при помощи алгоритма Дийкстры Узлом-источником является узел 1, узлом-стоком – узел 15.

Шаг 1. Потенциал узла-источника берем равным 1 = 0, потенциалам остальных узлов присваиваем значение R, где R – бесконечно большое число.

Шаг 2 первая итерация. Перерасчет потенциалов узлов, соседних с узлом-источником:

Шаг 3 первая итерация. Узел 15 на втором шаге не достигнут, узел в дальнейших расчетах на рассматриваем, из узлов с пересчитанными потенциалами ( 2 и 6 ) наименьший потенциал имеет узел 6. Выполняем шаг 2 для 6-го узла.

Шаг 2 вторая итерация.

Шаг 3 вторая итерация. Узел 15 не достигнут, из узлов с пересчитанными потенциалами (2 и 7 ) наименьший потенциал имеет узел 2.

Выполняем шаг 2 для 2-го узла.

Шаг 2 третья итерация.

Из узла 2 выходят дуги в узлы 3 и 7:

Шаг 3 третья итерация. Узел 15 не достигнут, из узлов с пересчитанными потенциалами (3 и 7 ) наименьший потенциал имеет узел 7.

Выполняем шаг 2 для 7-го узла.

Выполнение шагов 2 и 3 продолжается пока не достигнут узел 15.

В примере узел 15 достигается на четырнадцатой итерации. Переходим к шагу 4.

Шаг 4. По значениям потенциалов узлов определяем кратчайший путь на маршруте.

Кратчайший путь из узла 1 в узел 15 определяем как последовательности узлов, дающих потенциал 290 для узла 15.

Это будет последовательность 15–14–10–5–4–3–2–1.

Сеть с рассчитанными потенциалами узлов показана на рис. 3 (приложение 1).

4. Построение дерева кратчайших путей В соответствии с потенциалами узлов, рассчитанными на этапе 3, строим дерево кратчайших путей. Дерево кратчайших путей включает в себя дуги, соединяющие узел-источник (узел 1) со всеми узлами сети кратчайшими путями.

Переводим значения потенциалов узлов в эквивалент в километрах в соответствии с масштабом карты. Длина кратчайшего пути на маршруте из узла 1 в узел 15 равна 2,9 км.

Дерево кратчайших путей показано на рис. 4 (приложение 1).

Заключение: кратчайший путь на маршруте ж/д вокзал – уч. корпус СЛИ (ул. Южная, 11) равен 2,9 км.

ПРИЛОЖЕНИЕ (графическая часть курсовой работы) G=(V, Г) Рис. 1. Исходный граф Рис. 2. Исходная сеть D = [N, M] Рис. 3. Сеть с рассчитанными потенциалами узлов Рис. 4. Дерево кратчайших путей Контрольная работа по темам «Определение кратчайшего пути» и «Определение максимального потока»

а) Найти кратчайший путь из s в5 t при помощи алгоритма Дийкстры.

б) Построить дерево кратчайших путей.

в) Построить расширенную сеть для исходной сети.

арианта а) Определить с13) (f13, максимальный поток в сети, найти минимальный разf35, с35) рез.

б) Составить список всех увеличивающих цепей при значениях потоков:

в) Построить предельную сеть для исходной сети.

арианта Библиографический список Использованная литература:

1. Йенсен, П. И. Потоковое программирование/ П. Йенсен, Д.

Барнес.– М.: Мир, 1984. – 2. Майника, Э. Алгоритмы оптимизации на сетях и графах/ Э.

Майника. – М.: Мир, 1981. – 323 с.

3. Форд, Л.Р. Потоки в сетях/ Л.Р. Форд, Д. Фалкерсон. – М.: Радио и связь, 1966. – 276 с.

Рекомендуемая литература:

1. ГОСТ 7.32-91. Отчет о научно-исследовательской работе.

Структура и правила оформления. – М.: Изд-во стандартов, 1991. – 18 с.

2. Большаков, Н.М. Учебно–методическое пособие по подготовке рефератов, контрольных и курсовых работ/ Н.М. Большаков, Ю.С. Новиков. – Сыктывкар: СЛИ, 2001. – 20 с.

3. Геронимус, Б.А. Экономико-математические методы в планировании на автомобильном транспорте / Б.А. Геронимус, Л.В. Цапфин. – М.: Транспорт, 1988. – 192 с.

4. Францифоров, Ю.В. От реферата к курсовой, от диплома к диссертации: практ. рук. по подгот., излож. и защите научн. работ/ Ю.В.

Францифоров, Е.П. Павлова. – М.: Книга-сервис, 2003. – 128 с.

Оглавление



Похожие работы:

«Министерство образования Российской Федерации Дальневосточный государственный технический университет им. В.В. Куйбышева НАСОСЫ И ТЯГОДУТЬЕВЫЕ МАШИНЫ ТЕПЛОВЫХ ЭЛЕКТРОСТАНЦИЙ Учебное пособие Владивосток 2002 BOOKS.PROEKTANT.ORG БИБЛИОТЕКА ЭЛЕКТРОННЫХ КОПИЙ КНИГ для проектировщиков УДК 621.184.85 и технических специалистов С47 Слесаренко В.В. Насосы и тягодутьевые машины тепловых электростанций: Учебное пособие. - Владивосток: Издательство ДВГТУ, 2002. - с. Учебное пособие предназначено для...»

«Министерство образования и науки Российской Федерации Тюменская государственная архитектурно-строительная академия Кафедра ПТ Методические указания к курсовому проекту: Промышленная котельная с паровыми котлами для студентов очного отделения специальности 140104 Промышленная теплоэнергетика Часть II: Тепловой расчет промышленного котла Тюмень-2004 Методические указания к курсовому проекту Промышленная котельная с паровыми котлами для студентов очного отделения специальности 140104 Промышленная...»

«CАНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ГЕОЛОГИЧЕСКИЙ ФАКУЛЬТЕТ И. М. Хайкович, С. В. Лебедев ГЕОФИЗИЧЕСКИЕ ПОЛЯ В ЭКОЛОГИЧЕСКОЙ ГЕОЛОГИИ Учебное пособие Под редакцией проф. В. В. Куриленко Санкт-Петербург 2013 УДК 504.05+504.5+550.3 ББК 26.2+20.1 Х-16 Р е ц е н з е н т: докт. геол.-минер. наук, проф. К. В. Титов (С.-Петерб. гос. ун-т) Печатается по постановлению Редакционно-издательского совета геологического факультета Санкт-Петербургского государственного университета И. М. Хайкович,...»








 
© 2013 www.diss.seluk.ru - «Бесплатная электронная библиотека - Авторефераты, Диссертации, Монографии, Методички, учебные программы»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.