37449

РЕШЕНИЕ ЗАДАЧИ ПОИСКА ОПТИМАЛЬНОГО МАРШРУТА ГРУЗОПЕРЕВОЗОК. СЕТЕВЫЕ ЗАДАЧИ

Курсовая

Информатика, кибернетика и программирование

Mathematica — система компьютерной алгебры разработанная компанией Wolfram Research. Содержит множество функций как для аналитических преобразований, так и для численных расчётов. Кроме того, программа поддерживает работу с графикой и звуком, включая построение дву- и трёхмерных графиков функций, рисование произвольных геометрических фигур, импорт и экспорт изображений и звука.

Русский

2013-09-24

1.83 MB

52 чел.

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

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

Факультет прикладной математики и информатики

Кафедра компьютерных технологий и систем

Кафедра методов оптимального управления

Колодко Дмитрий Сергеевич

РЕШЕНИЕ ЗАДАЧИ ПОИСКА ОПТИМАЛЬНОГО МАРШРУТА ГРУЗОПЕРЕВОЗОК. СЕТЕВЫЕ ЗАДАЧИ

Курсовой проект

студента 3 курса 8 группы

«Допустить к защите»

Руководитель проекта

Костюков Иван Александрович

ассистент кафедры КТС

________________________

«___» _____________ 2011 г

Минск 2011

Белорусский  государственный  университет

Факультет  прикладной  математики и информатики

Кафедра компьютерных технологий и систем

Утверждаю

Заведующий кафедрой

_______________В.Б. Таранчук

“___”  _______________  2011 г.

ЗАДАНИЕ

ПО  ПОДГОТОВКЕ  КУРСОВОГО  ПРОЕКТА

Студенту 3 курса  Колодко Дмитрию Сергеевичу (группа 8)

  1.  Тема РЕШЕНИЕ ЗАДАЧИ ПОИСКА ОПТИМАЛЬНОГО МАРШРУТА ГРУЗОПЕРЕВОЗОК. СЕТЕВЫЕ ЗАДАЧИ (KIA-1-11)

2. Срок сдачи студентом законченной работы      ноября 2011 г.

3. Исходные данные к работе  

  •  Теория, типы и методы решения сетевых задач.
  •  Практические примеры сетевых задач.
  •  Теория численных методов.
  •  Размещенные в электронной библиотеке методические материалы, примеры программных модулей по приемам интегрирования, дифференцирования, программирования алгоритмов расчета, графической визуализации функций в компьютерной технической системе (КТС) Mathematica.
  •  Технические требования к электронным версиям отчетных документов.

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

  •  Альсевич В.В., Крахотко В.В. Методы оптимизации: упражнения и задания. Учебное пособие – Мн.: БГУ, 2005. – 405 с
    •  Альсевич В.В., Габасов Р., Глушенков В.С. Оптимизация линейных экономических моделей: статические задачи — Мн.: БГУ, 2000. — 210 с.
    •   [Электрон. ресурс – е_Библиотека ИПМОАП]  Иллюстрированный самоучитель по Mathematica.  #самоучитель по Mathematica/ #Оглавление.htm
    •  [Электрон. ресурс – \\Serv314\subfaculty\ …]  Таранчук В.Б. Графический сервис вычислительного эксперимента. БГУ, факультет прикладной математики и информатики. 1_ZapuskUst-ki_v*.nb, 3_Grafika_v*.nb
    •  [Электронресурс  \\Serv314\subfaculty\ … GoldenSoftwareGrapher.rar]
    •  [Электронресурс  \\Serv314\subfaculty\ … #КурсовойПроект2011]  Таранчук В.Б. КурсовойПроект2011.pps.

4. Перечень вопросов подлежащих разработке или краткое содержание работы 

  •  Освоить функции ядра КТС Mathematica для решения сетевых задач.
  •  Запрограммировать в КТС Mathematica решение двух видов сетевых задач.
  •  Изучить функции работы с матрицами в КТС Mathematica.
  •  Освоить приемы графической визуализации функций в КТС Mathematica.
  •  Освоить приемы подготовки скриншотов и их включения в отчеты, презентации.

5. Перечень графического материала 

  •  Логотип БГУ для включения на слайды презентации.
  •  Графики решений
  •  Иллюстрации сравнительного анализа точного и приближенного решений.
  •  Скриншоты интерфейса для включения в презентацию.
  •  Фрагменты электронных ресурсов использованной литературы.

6. Дата выдачи задания  __ сентября 2011 г.

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

  •  сентябрь – ознакомление с предлагаемыми темами, выбор и согласование темы с руководителем, регистрация на кафедре ИПМОАП (к. 601);
  •  сентябрь – ознакомление с техническими требованиями к электронным отчетным документам (doc, ppt, pdf) и освоение правил, как их реализовать;
  •  сентябрь-октябрь – изучение постановки задачи, основных теоретических вопросов;
  •  сентябрь-октябрь – подготовка и сдача зачетного компьютерного теста (допуск или нет) по модулю “Инструментарий и правила подготовки отчетных doc, ppt, pdf”;
  •  сентябрь-октябрь – изучение основ программирования, правил и приемов символьных вычислений, графики в КТС Mathematica;
  •  октябрь-ноябрь – информационный поиск, работа с электронными ресурсами, программирование секций вычислений и визуализации;
  •  октябрь-ноябрь – подготовка и сдача зачетного компьютерного теста “Основные конструкции, функции, правила работы с КТС Mathematica”;
  •  ноябрь – практическая реализация задач проекта;
  •  ноябрь-декабрь – оформление результатов работы (отчета DOC, презентации PPT, NB), подготовка доклада и отладка презентации на защиту;
  •  17.11. – 12.12.: защита, зачет.

Руководитель ______________ / И. А. Костюков/ …. сентября 2011 г.

Задание принял к исполнению __________________ .… сентября 2011 г.

(подпись студента)


АННОТАЦИЯ

Колодко Д.С. Решение задачи поиска оптимального маршрута грузоперевозок. Сетевые задачи: Курсовой проект / Минск: БГУ, 2011. – 19 с.

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

АНАТАЦЫЯ

Калодка Д.С. Рашэнне задачы пошуку аптымальнага маршруту грузаперавозак. Cеткавыя задачы: Курсавы праект / Мінск: БДУ, 2011. – 19 с.

У рабоце разглядаюцца і рэалізуюцца з дапамогай КТС Mathematica метады рашэння задачы пошуку аптымальнага маршруту грузаперавозак у сеткавай форме.

ANNOTATION

Kolodko D.S. The solution of the problem of finding the optimal route of cargo transportation. Network problems: Course project / Minsk: BGU, 2011. – 19 p.

Methods for solving the problem of finding an optimal route transportation in the network form are being considered and implemented using the computer algebra system Mathematica.


РЕФЕРАТ

Курсовой проект, 19 с., 11 рис., 2 источника.

Ключевые слова: СЕТЕВАЯ ЗАДАЧА, СЕТЕВОЙ ПОТОК, МЕТОД ПОТЕНЦИАЛОВ.

Объект исследованиязадача поиска оптимального маршрута в сетевой форме.

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

Методы исследования – методы решения сетевой транспортной задачи.

Результатами являются освоение КТС Mathematica для решения сетевой транспортной задачи; полученные решения сетевой транспортной задачи.

Область примененияметоды оптимизации.


СОДЕРЖАНИЕ

[1] АННОТАЦИЯ

[2]
РЕФЕРАТ

[3]
СОДЕРЖАНИЕ

[4] ВВЕДЕНИЕ

[5] 2 РЕЗУЛЬТАТЫ ВЫЧИСЛЕНИЙ

[5.1] 2.1 Закрытая модель СТЗ

[5.2] 2.2 Открытая модель СТЗ

[6] 3 РЕАЛИЗАЦИЯ ВЫЧИСЛЕНИЙ

[7] ЗАКЛЮЧЕНИЕ

[8] СПИСОК ИСПОЛЬЗУЕМЫХ ИСТОЧНИКОВ


ВВЕДЕНИЕ

 Mathematica — система компьютерной алгебры разработанная компанией Wolfram Research. Содержит множество функций как для аналитических преобразований, так и для численных расчётов. Кроме того, программа поддерживает работу с графикой и звуком, включая построение дву- и трёхмерных графиков функций, рисование произвольных геометрических фигур, импорт и экспорт изображений и звука.

 На примере решения транспортной задачи показаны возможности КТС Mathematica. В процессе программирования используются стандартные функции и методы системы Mathematica.

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


1 КРАТКИЕ ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ

1.1 Постановка задачи. Основные определения

Рассмотрим следующую задачу. Пусть  — множество элементов, которые назовем узлами. Пусть некоторые пары узлов , упорядочены. Каждую такую пару будем обозначать через и называть дугой с началом  i и концом j (предпологается, что существуют только пути с односторонним движением). Множество всех дуг обозначим через U. Совокупность S={I,U} называется ориентированной сетью. Каждому узлу припишем число — интенсивность узла. Если , то узел называется источником, если  — стоком, если  — нейтральным узлом(транзитным).Каждой дуге (i,j) припишем два числа:  — дуговой поток и  — стоимость единичного дугового потока. Для каждого узла i обозначим через  множество узлов, в которые идут дуги из узла i, а через  — множество узлов, из которых идут дуги в узел i. Тогда условия баланса имеют вид

                                                         (1)

Совокупность  дуговых потоков называется потоком на сети S(или сетевым потоком), если она удовлетворяет ограничениям (1). Тогда стоимость сетевого потока равна .

Сетевая транспортная задача(СТЗ) имеет вид

                                                                        (2)

Сетевой поток  — решение задачи (2) называется оптимальным.Обозначим через X множество всех сетевых потоков. Из условий баланса (1) следует, что если  то

                                                                            (3)

Условие (3) называется условием общего баланса. Рассмотрим задачи, для которых выполняется условие общего баланса.

  1.  Основные сетевые понятия и утверждения

Дугу (i,j) без ориентации назовем ребром с граничными узлами i,j и обозначим через {i,j}.Узел назовем висячим, если он граничен для единственного ребра. Последовательность ребер называется цепью, соединяющей узлы . Цепь можно обозначить и следующим образом:. Если в цепи  нет одинаковых узлов, то цепь называется элементарной. Выберем направление движения вдоль цепи. Если при этом направлении дуги (i,j), соответствующей ребру {i,j} цепи, то дуга называется прямой, в противном случае — обратной. Сеть называется связной, если любые ее два узла можно соединить цепью. Цепь , в которой , т.е. последний узел совпадает с первым, называется циклом. В дальнейшем рассматриваются простые, элементарные цепи и связные сети.

Сеть S={I,U}, которой , называется деревом.

Лемма 2.1. Сеть без циклов содержит висячее ребро.

Лемма 2.2. Удаление висячего ребра вместе с висячим узлом или ребра из цикла не нарушает связности сети.

Лемма 2.3. Сеть является деревом тогда и только тогда, когда она не содержит циклов.

Лемма 2.4. Каждая пара узлов дерева связана единственной цепью.

Для сети S={I,U} сеть , где , называется частичной сетью. Если частичная сеть — дерево, то она называется деревом сети.

Лемма 2.5. Если к дереву сети  добавить дугу , то новая частичная сеть , где , содержит ровно один цикл.

  1.  Базисный сетевой поток

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

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

Не любое множество дуг  для которого  — дерево сети, можно положить в основу

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

Совокупность , для которой выполняется условие баланса (1), называется псевдопотоком. Если в псевдопотоке , то x — сетевой поток.

1.4 Критерий оптимальности базисного сетевого потока

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

                                                                      (4)

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

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

                                                                     (6)

Заметим, что формула приращений стоимости сетевого потока имеет вид

                                              (7)

 Отсюда ясен физический смысл оценок: оценка  — скорость изменения в точке x стоимости сетевого потока при увеличении небазисного сетевого потока .

1.5 Метод потенциалов для решения сетевой транспортной задачи. Итерация

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

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

приведенных выше лемм итерация методов потенциалов состоит из следующих шагов.

  1.  Решаем систему уравнений (4), и находим потенциалы узлов .
  2.  По потенциалам узлов подсчитываем оценки небазисных дуг (формулы (5)).
  3.  Проверяем условие оптимальности (6). Если они выполняются, решение заканчиваем:
  4.  Базисный поток x оптимальный. Если же существует дуга для которой

                                                                  (8)

переходим к следующему шагу.

  1.  Добавим дугу  для которой , к базисному множеству дуг . Согласно лемме 2.5, новая частичная сеть имеет ровно один цикл, причем дуга  входит в этот цикл. Выберем направление движения вдоль цикла по направлению дуги , т.е. .
  2.  Полагаем  где ,  — множества соответственно прямых  обратных дуг цикла. Определяем, где  — множество всех дуг цикла. Из определения  следует, что если все дуги цикла прямые, тогда  т.е. стоимость сетевого потока не ограничена снизу. В этом случае решение задачи завершаем. В противном случае переходим к следующему шагу.
  3.  Поток x заменим потоком  следующим образом: дуговые потоки обратных дуг цикла уменьшаем на величину , дуговые потоки прямых дуг цикла, в том числе дуги , увеличиваем на  . Все остальные дуговые потоки (как базисные, так и не базисные) не меняем. Заметим, что поскольку для небазисных дуговых потоков изменится лишь  на величину , то стоимость сетевого потока, согласно (7), уменьшится на величину , если сетевой базисный поток невырожденный, т.е.
  4.  Формируем новое базисное множество  где определяется из условия , и переходим к шагу 1.

Метод решения задачи по описанным выше правилам называется методом потенциалов.

1.6 Открытая и закрытая модели СТЗ

Модель сетевой транспортной задачи называется закрытой, если выполняется условие общего баланса (3), в противном случае — модель открытая. Последнюю можно интерпретировать как задачу, в которой совокупный спрос не равен совокупному предложению. Если , спрос превышает предложение, если a>0предложение превышает спрос. Открытая модель легко сводится к закрытой. Пусть a>0. Добавим вспомогательный узел m+1 с интенсивностью , т.е. этот узел является стоком. Соединим его с источниками дугами (i,m+1) и положим . Если a<0, то интенсивность (m+1)-го узла равна, т.е. этот узел является источником. Соединяем его дугами (m+1,i) со стоками и полагаем . Далее применяем к расширенной задаче метод потенциалов.


2 РЕЗУЛЬТАТЫ ВЫЧИСЛЕНИЙ

2.1 Закрытая модель СТЗ

            Рассмотрим следующую задачу 1:

Рисунок 1Условие задачи

           На рисунке 6 изображено графическое представление этой задачи.

Рисунок 2Графическое представление задачи 1

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

X

В результате выполнения программы получим решение (сетевой поток Х и ):

 1-ая итерация:

Рисунок 3Результаты первой итерации

2-ая итерация:

Рисунок 4Результаты второй итерации

Результат:

Рисунок 5Решение задачи 1

2.2 Открытая модель СТЗ

           Рассмотрим предыдущую задачу 1, в которой будем считать, что в пункте 4 требуется только 4 Ед. товара. Тогда модель становится открытой, поскольку спрос равен 12 Ед., а предложение 15 Ед. Построим расширенную задачу 2, как показано в пункте 1.6. Будем иметь следующее графическое представление данной задачи.

Рисунок 6Графическое представление задачи 2

Начальные данные программы будут следующими:

X

В результате выполнения программы получим решение (сетевой поток Х и ):

Рисунок 7Решение задачи 2


3 РЕАЛИЗАЦИЯ ВЫЧИСЛЕНИЙ

Рисунок 8Первый фрагмент кода

Рисунок 9Второй фрагмент кода

 Рисунок 10Третий фрагмент кода

Рисунок 11Четвертый фрагмент кода

с — матрица смежности графа, в которой имеется информация о стоимости дуговых единичных потоков; X— сетевой поток. Ub — базисное множество дуг; SizeMatrix — количество узлов;uвектор потенциалов; delta — оценка

ЗАКЛЮЧЕНИЕ

В данном курсовом проекте:

  •  Изучены методы решения сетевых транспортных задач.
  •  Запрограммирован в КТС Mathematica метод потенциалов для решения СТЗ.
  •  Изучены функции работы со списками в КТС Mathematica;
  •  Изучены функции ядра КТС Mathematica для решения задач ЛП.
  •  Освоены приемы подготовки скриншотов и включения их в отчеты, компьютерные презентации.


СПИСОК ИСПОЛЬЗУЕМЫХ ИСТОЧНИКОВ

  1.  Альсевич В.В. Методы оптимизации: упражнения и задания. Учебное пособие / В.В. Альсевич, В.В. Крахотко. – Мн.: БГУ, 2005. – 405 с.
  2.  Альсевич В.В. Оптимизация линейных экономических моделей: статические задачи / В.В. Альсевич, Р. Габасов, В.С. Глушенков — Мн.: БГУ, 2000. — 210 с.


 

А также другие работы, которые могут Вас заинтересовать

52253. НАВЧАННЯ АУДІЮВАННЮ З АНГЛІЙСЬКОЇ МОВИ 184.5 KB
  Труднощі сприйняття іноземної мови на слух – одна з основних проблем, з якою стикаються учні на початкових етапах навчання. Згодом ця проблема вирішується завдяки постійній практиці.
52255. Композиція музичного твору. Форми в музиці. Сонатна форма 65.5 KB
  Товаром на уроціаукціоні є знання учнів які пропонуються у вигляді лотів. Підготовкою запитань лотів може займатися як сам вчитель так і купці учні. Купці можуть готувати по дватри лоти завдання під керівництвом і контролем учителя. Скарбник після кожного лоту виконаного завдання визначає середній бал кожного акціонерного товариства й записує результати у зведену таблицю.
52256. Аукціон фізичних знань 140.5 KB
  Команда яка швидше записала букви в кінці зірки і прочитала слово отримує 5 балів. Інша команда якщо вона правильно впоралась з завданням отримує 4 бали. Команда прослухавши повідомлення і розглянувши портрет відгадує ім'я вченого. За кожен правильно вгаданий портрет команда отримує по 3 бали.
52257. Організація закупівлі товарів на аукціонах 249.5 KB
  Інструкційно – методична карта практичного заняття № 4 Тема: Організація підготовки і проведення аукціону. Навчальні цілі заняття: ознайомити студентів з планом проведення заняття ; І виявлення знань студентів по темі використовуючи різні форми і методи контролю; ІІ привити практичні навички оформлення акційних документів; ІІ навчити самостійно робити висновки вносити пропозиції щодо організації підготовки та проведення аукціону; ІІІ формувати особу спеціаліста з сучасним економічним мисленням здатну...
52259. Рельєф. Тектоніка. Геологічнабудова. Корисні копалини України 50.5 KB
  Корисні копалини України. Корисні копалини України. прищеплювати любов до України географії. Обладнання: Фізична карта України Тектонічна карта України магнітофон жетони гонг штатив молоточок таблиці атлас України 89 класи призи.
52260. Aus der Geschichte der Ukraine 50.5 KB
  Wie geht es euch Kinder Heute beginnen wir ein neues Them zu studieren. Es heißt Die Ukrine gestern und heute“. Dieses Them ht 10 Stunden. ber wie ds Them heutiger Stunde ist versteht ihr nch dieser ufgbe.