WWW.KNIGI.KONFLIB.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

 
<< HOME
Научная библиотека
CONTACTS

Pages:     || 2 | 3 | 4 | 5 |   ...   | 6 |

«КАФЕДРА АВТОМОБИЛЕЙ И АВТОМОБИЛЬНОГО ХОЗЯЙСТВА ПОТОКИ В СЕТЯХ Учебно-методический комплекс по дисциплине Потоки в сетях для студентов специальности 190601 Автомобили и ...»

-- [ Страница 1 ] --

СЫКТЫВКАРСКИЙ ЛЕСНОЙ ИНСТИТУТ

КАФЕДРА АВТОМОБИЛЕЙ И АВТОМОБИЛЬНОГО ХОЗЯЙСТВА

ПОТОКИ В СЕТЯХ

Учебно-методический комплекс

по дисциплине «Потоки в сетях»

для студентов специальности 190601

«Автомобили и автомобильное хозяйство»

всех форм обучения

СЫКТЫВКАР 2007

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

СЫКТЫВКАРСКИЙ ЛЕСНОЙ ИНСТИТУТ – ФИЛИАЛ

ГОУ ВПО «САНКТ-ПЕТЕРБУРГСКАЯ ГОСУДАРСТВЕННАЯ

ЛЕСОТЕХНИЧЕСКАЯ АКАДЕМИЯ ИМЕНИ С. М. КИРОВА»

КАФЕДРА АВТОМОБИЛЕЙ И АВТОМОБИЛЬНОГО ХОЗЯЙСТВА

ПОТОКИ В СЕТЯХ

Учебно-методический комплекс по дисциплине «Потоки в сетях»

для студентов специальности «Автомобили и автомобильное хозяйство»

всех форм обучения СЫКТЫВКАР УДК 629.3:519.852. ББК 65.9(2) П Рассмотрен и рекомендован к печати на заседании кафедры автомобилей и автомобильного хозяйства 10 октября 2006 г. (протокол № 2).

Утвержден к изданию советом лесотранспортного факультета Сыктывкарского лесного института 25 декабря 2006 г. (протокол № 4).

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

Е. Ю. Сундуков, старший преподаватель Рецензенты:

Л. И. Ильина, кандидат экономических наук, доцент (Сыктывкарский филиал Российского университета кооперации);

кафедра дорожного, промышленного и гражданского строительства (Сыктывкарский лесной институт) Потоки в сетях : учеб.-метод. комплекс по дисц. «Потоки в сетях» для студ. спец. П64 «Автомобили и автомобильное хозяйство» всех форм обуч. / Е. Ю. Сундуков ; СЛИ. – Сыктывкар, 2007. – 48 с.

УДК 629.3:519.852. ББК 65.9(2) Издание содержит рабочую программу по дисциплине «Потоки в сетях», а также рекомендации по самостоятельной работе студентов. Изложены алгоритмы оптимизации на графах и в сетях, методика построения сетевых моделей и расчета их с помощью MS Excel. Даны методические указания по выполнению контрольной и курсовой работ. Приведен пример выполнения курсовой работы. Дан библиографический список рекомендуемой литературы. Предназначено для студентов специальности 190601 «Автомобили и автомобильное хозяйство» всех форм обучения.

Сундуков Е. Ю., составление, Сыктывкарский лесной институт – филиал ГОУ ВПО «Санкт-Петербургская государственная лесотехническая академия имени С. М. Кирова»,

ОГЛАВЛЕНИЕ

ПРЕДИСЛОВИЕ

1. РУКОВОДСТВО ПО ИЗУЧЕНИЮ ДИСЦИПЛИНЫ

1.1. ЦЕЛЬ И ЗАДАЧИ ДИСЦИПЛИНЫ

1.2. СТРУКТУРА КУРСА

2. КОНСПЕКТ ЛЕКЦИЙ

2.1. ПРОГРАММА КУРСА

2.2. ОПОРНЫЙ КОНСПЕКТ ЛЕКЦИЙ

2.2.1. Общие вопросы

2.2.2. Задача о кратчайшем пути

2.2.3. Задача о максимальном потоке

2.2.4. Обобщенные задачи о потоке минимальной стоимости

3. НАИМЕНОВАНИЯ ПРАКТИЧЕСКИХ ЗАНЯТИЙ

4. САМОСТОЯТЕЛЬНАЯ РАБОТА И КОНТРОЛЬ УСПЕВАЕМОСТИ

4.1. МЕТОДИЧЕСКИЕ РЕКОМЕНДАЦИИ ПО САМОСТОЯТЕЛЬНОМУ ИЗУЧЕНИЮ

ТЕОРЕТИЧЕСКОГО МАТЕРИАЛА

5. МЕТОДИЧЕСКИЕ УКАЗАНИЯ ПО ВЫПОЛНЕНИЮ КОНТРОЛЬНОЙ РАБОТЫ.

6. МЕТОДИЧЕСКИЕ УКАЗАНИЯ ПО ВЫПОЛНЕНИЮ КУРСОВОЙ РАБОТЫ......... 7. КОНТРОЛЬ ЗНАНИЙ СТУДЕНТОВ ПО ДИСЦИПЛИНЕ

7.1. ВАРИАНТ ТЕСТА

7.2. ВОПРОСЫ К ЭКЗАМЕНУ

РЕКОМЕНДУЕМАЯ ЛИТЕРАТУРА

Приложение. ПРИМЕР ВЫПОЛНЕНИЯ КУРСОВОЙ РАБОТЫ

ПРЕДИСЛОВИЕ

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

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

Дисциплина «Потоки в сетях» предназначена для формирования у студентов специальности 190601 «Автомобили и автомобильное хозяйство» всех форм обучения навыков моделирования потоковых процессов и поиска оптимальных решений производственных задач.

1. РУКОВОДСТВО ПО ИЗУЧЕНИЮ ДИСЦИПЛИНЫ

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



В результате изучения «Потоки в сетях» студент должен знать:

• основные понятия, используемые в сетевом моделировании;

• способы сведения прикладных задач к потоковым задачам;

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

• способы представления, хранения и преобразования данных;

• основные алгоритмы потокового программирования;

• технологию решения потоковых задач на ЭВМ.

Дополнение к Государственному общеобразовательному стандарту высшего профессионального образования по дисциплине «Потоки в сетях»: определение сети; параметры узлов и дуг; моделирование потоковых процессов; оптимизационные алгоритмы; маршрутизация; транспортные потоки; поиск кратчайшего пути; определение максимального потока;

пропускная способность участка дороги; поток минимальной стоимости;

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

1.2. Структура курса Взаимосвязь между задачами потокового программирования программирования потокового программирования ботки и преобразования данных для потоковых задач минимальной стоимости для обобщенных потоковых задач минимальной стоимости нимальной стоимости Наименование темы Объем работы студента (ч) Форма контроля Взаимосвязь между задачами потокового программирования программирования потокового программирования ботки и преобразования данных для потоковых задач минимальной стоимости для обобщенных потоковых задач минимальной стоимости нимальной стоимости Наименование темы Объем работы студента (ч) Форма контроля Взаимосвязь между задачами потокового программирования программирования потокового программирования ботки и преобразования данных для потоковых задач минимальной стоимости для обобщенных потоковых задач минимальной стоимости нимальной стоимости ПЗ – практические занятия; СР – самостоятельная работа; ФО – фронтальный опрос текущего материала; к/р – контрольная работа; КР – курсовая работа.

2. КОНСПЕКТ ЛЕКЦИЙ 2.1. Программа курса Взаимосвязь между задачами потокового программирования Предварительное знакомство с предметом. Взаимосвязь между задачами потокового программирования. Специальные случаи стандартной линейной задачи о потоке минимальной стоимости. Сети с выигрышами [4, с.

7–15] (2 ч).

Тема 2. Примеры моделей потокового программирования Свободный узел и его параметры. Стандартная задача о потоке минимальной стоимости. Транспортная задача. Задача о назначениях. Задача о кратчайшем пути. Задача о максимальном потоке [4, с. 16–55] (2 ч).

Система обозначений в потоковых задачах. Алгебраическая модель сети. Стандартная задача о потоке минимальной стоимости как задача линейного программирования. Основные понятия из теории графов. Расширенные и предельные сети. Сети с нелинейными функциями стоимости дуг. Границы использования потоковых моделей [4, с. 63–91; 5; 9] (4 ч).

обработки и преобразования данных для потоковых задач Вычислительные затраты. Представление сети. Ввод и хранение информации о сети. Представление дерева. Алгоритмы изменения потока [4, с. 95– 127; 5; 7] (4 ч).

Поиск кратчайшего пути как задача о потоке минимальной стоимости.

Допустимые дуги с положительной стоимостью. Сеть без отрицательных циклов. Отрицательные циклы. Двойственный алгоритм поиска кратчайшего пути [4, с. 128–148; 2; 7] (4 ч).

Содержательная интерпретация двойственной задачи. Результаты теоретических исследований. Базисные и небазисные алгоритмы. Алгоритмы увеличения потока [4, с. 150–168; 2; 7] (4 ч).

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

Прямой базисный алгоритм. Двойственный алгоритм уменьшения неувязок в узлах [4, с. 169–206; 8] (4 ч).

Модель сети. Состояния с дефектом. Изменение потока и потенциала узлов. Пример использования метода [4, с. 208–231] (2 ч).

Модель сети с выигрышами. Потоки в обобщенных сетях. Потенциалы узлов [4, с. 233–271] (2 ч).

Тема 10. Обобщенные задачи о потоке минимальной стоимости Обобщенная задача о кратчайшем пути. Все дуговые стоимости положительны, а все выигрыши дуг меньше или равны единице. Дуги с отрицательной стоимостью и выигрышами больше единицы. Двойственный алгоритм решения задачи о кратчайшем пути. Алгоритмы решения обобщенной задачи о потоке минимальной стоимости [4, с. 274–325] (2 ч).

Тема 11. Выпуклая задача о потоке минимальной стоимости Выпуклые функции стоимости. Потоковые задачи в физических сетях.

Функция стоимости, зависящая от случайных переменных. Кусочнолинейная аппроксимация. Неявная кусочно-линейная аппроксимация [4, с.

329–351] (2 ч).

Области применения. Алгоритм полного перебора. Неполный перебор. Нижняя оценка Алгоритм неполного перебора [4, с. 354–376] (2 ч).

2.2. Опорный конспект лекций 2.2.1. Общие вопросы Исходные понятия сетевого моделирования связаны с ориентированными и неориентированными графами [5, 9].

Ориентированный граф G определяется как пара (V, Е), где V – конечное множество, а Е – бинарное отношение на V, т.е. подмножество множества V V. Ориентированный граф иногда для краткости называют орграфом. Множество V называют множеством вершин графа; его элемент называют вершиной графа. Множество Е называют множеством ребер графа; его элементы называют ребрами. На рис. 1 (а) показан ориентированный граф с множеством вершин {1, 2, 3, 4}. Вершины изображены кружками, а ребра – стрелками. Граф может содержать ребра-петли, соединяющие вершину саму с собой.

В неориентированном графе G = (V, E) множество ребер Е состоит из неупорядоченных пар вершин: парами являются множества {и, v}, где и, v V и и v. Неориентированное ребро обозначается как (u, v); при этом для неориентированного графа (u, v) и (v, u) обозначают одно и то же ребро. Неориентированный граф не может содержать ребер-петель, и каждое ребро состоит из двух различных вершин («соединяя» их). На рис. 1 (б) изображен неориентированный граф с множеством вершин {1, 2, 3, 4}.



Pages:     || 2 | 3 | 4 | 5 |   ...   | 6 |
 



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

«ОСНОВЫ АВТОМАТИЗИРОВАННОГО ПРОЕКТИРОВАНИЯ ТРАНСПОРТНЫХ СООРУЖЕНИЙ Учебно-методический комплекс по дисциплине для студентов направления специальности 270205 Автомобильные дороги и аэродромы всех форм обучения Самостоятельное учебное электронное издание СЫКТЫВКАР 2012 УДК 625.72 ББК 39.311 О-73 Рекомендован к изданию в электронном виде кафедрой дорожного, промышленного и гражданского строительства Сыктывкарского лесного института 12 июня 2012 г. Утвержден к изданию в электронном виде советом...»

«ХРОНИКА РАСШИРЕННОЕ СОВЕЩАНИЕ АКУСТИЧЕСКОЙ КОМИССИИ АКАДЕМИИ НАУК СССР С 2о февраля по 1 марта 1949 г. в Москве происходило расширенное совещание акустиков, созванное Акустической комиссией при Отделении физико-математических наук Академии Наук СССР. Цель совещания была осветить пути развития советской акустики как в прошлом; так и на будущее время. В совещании принимало участие 1Ь8 человек, представлявших Ьй научных институтов и различных организаций. Совещание с большим интересом и...»

«1. ОБЩИЕ ПОЛОЖЕНИЯ 1.1. Настоящая Инструкция регламентирует состав, порядок разработки, согласование и утверждение комплексной научно-исследовательской, изыскательской и проектно-сметной документации* для реставрации, консервации, воссоздания, ремонта и приспособления недвижимых памятников истории и культуры**, независимо от их принадлежности и форм собственности, являющихся элементами градостроительных образований, памятных мест, архитектурных ансамблей и комплексов, историко-культурных музеев...»

«А. ЛУКАС МАТЕРИАЛЫ И РЕМЕСЛЕННЫЕ ПРОИЗВОДСТВА ДРЕВНЕГО ЕГИПТА Перевод с английского Б. Н. Савченко Общая редакция и вступительная статья проф. В. И. Авдиева Издательство иностранной литературы Москва, 1958 [3] 1 АННОТАЦИЯ Книга А. Лукаса Материалы и ремесленные производства Древнего Египта представляет собою капитальный труд, рамки которого выходят далеко за пределы истории материальной культуры Древнего Египта. Это своего рода справочник по истории техники и естествознания, строительного дела...»

«Санитарные правила и нормы устройства, 2.4.3. содержания и организации учебно-воспитательного процесса и производственного обучения профессионально-технических и средних специальных учебных заведений. Санитарные правила и нормы СанПиН РБ № 14-121-99 СанПиН РБ 14-121-99 ПРЕДИСЛОВИЕ Разработаны Белорусским научно-исследовательским 1. санитарно-гигиеническим институтом (Крюкова А.А., Амвросьев П.А., Харевич Т.В.) с участием Главного управления гигиены, эпидемиологии и профилактики Минздрава...»

«Томск 2012 Отчет оформлен в соответствии с требованиями. Зав. кафедрой химии _ Саркисов Ю.С. (подпись) Ответственный по качеству общеобразовательного факультета _ Конева Н.А. (подпись) 1. Общая характеристика кафедры Кафедра Химия. Год образования 1952 год. Заведующий кафедрой – д.т.н., профессор, Саркисов Ю.С. 1.1. Состояние документации: - приказы и распоряжения Минобрнауки РФ, Рособразования, Рособрнадзора, ректора, проректоров академии, касающиеся научной и учебной деятельности академии и...»

«Молитвы о помощи Татьяна Лагутина 2 Книга Татьяна Лагутина. Молитвы о помощи скачана с jokibook.ru заходите, у нас всегда много свежих книг! 3 Книга Татьяна Лагутина. Молитвы о помощи скачана с jokibook.ru заходите, у нас всегда много свежих книг! Татьяна Владимировна Лагутина Молитвы о помощи 4 Книга Татьяна Лагутина. Молитвы о помощи скачана с jokibook.ru заходите, у нас всегда много свежих книг! Введение Святые покровители есть у каждого из нас. При рождении мы получаем ангела-хранителя, при...»

«РАБОЧАЯ ПРОГРАММА в строительной сфере ДИСЦИПЛИНЫ Социология наименование дисциплины Направление подготовки : 270800 Строительство Профиль подготовки : _ПГС_ Квалификация (степень) выпускника: Бакалавр (бакалавр, магистр, дипломированный специалист) Форма обучения: очная/заочная (очная, очно-заочная и др.) Автор программы кандидат исторических наук, доцент кафедры философии, социологии и истории Лихорадова И.Н. Программа обсуждена на заседании кафедры _ _ 2011 года Протокол № _ Зав. кафедрой _...»

«С.-Петербург 2012 2 Ноосферная общественная академия наук Петровская академия наук и искусств _ Европейская академия естественных наук Академия проблем качества (Санкт-Петербургское отделение) _ Смольный институт Российская академия образования Костромской государственный университет Им. Н.А.Некрасова Вологодский государственный педагогический университет Государственная полярная академия Институт качества высшего образования (при МИСиС – технологическом университете) Субетто Александр...»

«ПОЛИТОЛОГИЯ Учебно-методический комплекс по дисциплине для студентов всех форм обучения специальностей 190601 Автомобили и автомобильное хозяйство, 190603 Сервис транспортных и технологических машин и оборудования, 150405 Машины и оборудование лесного комплекса, 270102 Промышленное и гражданское строительство, 270205 Автомобильные дороги и аэродромы, 220301 Автоматизация технологических процессов и производств (по отраслям), 080502 Экономика и управление на предприятии (по отраслям), 080507...»






 
© 2013 www.knigi.konflib.ru - «Бесплатная электронная библиотека»

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