Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

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

ФГБОУ ВО «САМАРСКИЙ ГОСУДАРСТВЕННЫЙ АРХИТЕКТУРНО-СТРОИТЕЛЬНЫЙ УНИВЕРСИТЕТ»

Кафедра информационных и развивающих образовательных систем и технологий

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

к выпускной квалификационной работе бакалавра на тему: Автоматизированная система поиска оптимального маршрута на транспортной сети

Студента ГИП-112 Терентьева Данилы Андреевича

Самара 2016 г.

Реферат

Выпускная квалификационная работа.

Программный комплекс, проекты, алгоритм, транспортный путь, оптимальный маршрут.

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

Комплекс спроектирован по методологии UML и реализован на языке

программирования C++ c использованием фреймворка Qt 5.4.

В ходе дипломного проектирования разработана автоматизированная система (АС) поиска оптимального маршрута на транспортной сети (ТС). Решение принимается на основе сравнения расчетов, полученных двумя различными способами: алгоритму Дейкстры и жадному алгоритму. Тема работы входит в перечень приоритетных направлений в Самарской области, а именно: Новые транспортные технологии, Информационные технологии и электроника. Разработаны коды названных методов на языке С++. В ходе разработки АС применялась методология UML.

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

Функциональными возможностями комплекса являются: создание транспортной сети нужного размера и типа, вывод оптимального маршрута.

Содержание

• Введение
• 1. Предпроектный анализ
• 1.1 Описание и анализ проектирования транспортных систем и транспортных сетей
• 1.1.1 Особенности транспортных систем
• 1.1.2 Транспортныесети
• 1.1.3 Оптимизация
• 1.2 Обзор аналогов и прототипа
• 2. Проектирование
• 2.1 Диаграмма вариантов использования
• 2.2 Сценарий наиболее сложного варианта использования
• 2.3 Диаграмма сущностных классов
• 2.4 Диаграмма граничных классов
• 2.5 Диаграмма классов управления
• 2.6 Диаграмма состояний
• 2.7 Схема наиболее сложного алгоритма
• 3. Реализация
• 3.1 Архитектура и платформа реализации
• 3.1.1 Особенности
• 3.1.2 Работа с проектами
• 3.1.3 Редактирование кода
• 3.1.4 Отладка кода
• 3.1.5 Архитектура
• 3.2 Расчет необходимого объема внешней памяти
• 3.3 Расчет необходимого объема оперативной памяти
• 3.4 Расчет времени реакции системы
• 3.5 Основные интерфейсы
• 3.6 Диаграмма компонентов
• 3.7 Диаграмма развертывания
• 3.8 Программа и методика испытаний
• 3.9 Контрольный пример
• 3.10 Руководство пользователя
• 4. Внедрение и анализ эффективности
• 4.1 Описание объекта внедрения
• 4.2 Описание хода предполагаемого внедрения
• 5. Организационная деятельность
• 5.1 Перечень публикаций
• 5.2 Перечень выполненных курсовых работ и проектов
• 5.3 Портфолио
• Заключение
• Список используемых источников
• Приложения
• Введение
• Одной из основных целей автомобильного транспорта в городской сети дорог является нахождение оптимального пути из точки А в точку Б. Под «оптимальностью пути» понимается не минимальное расстояние, а минимальная затрата времени на прохождение пути. Городская сеть дорог может быть представлена в виде графа с нижеперечисленными параметрами:
• - граф является ориентированным графом;
• - в графе нет ребер с отрицательным весом;
• - в графе большое количество вершин;
• - граф находится в одном компоненте связности;
• - каждое ребро графа имеет различную длину.
• Ценность любого алгоритма состоит в его эффективности, времени работы программы и в легкости написания этого алгоритма. Исходя из этого, алгоритм нахождения оптимального пути должен обладать определенными свойствами. Это возможность работы с полным графом, небольшая сложность алгоритма, а также возможность сохранения всего пути в формате вершин и ребер в массиве или другой структуры данных[1].
• Одной из важнейших задач современной логистики является выбор схемы маршрутов при доставке грузов. В принципе речь идет о задачах оптимизации, однако критерий оптимизации может быть самым разным.
• Классификация маршрутов по типам во многом связана с критерием оптимизации маршрутов, а если точнее, то имеется ряд факторов, которые существенны при характеристике маршрута. Причем эти характеристики могут относиться не только непосредственно к самому маршруту, но и к способу и особенностям передвижения транспортного средства по этому маршруту.

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

1. Предпроектный анализ

1.1 Описание и анализ проектирования транспортных систем и транспортных сетей

1. Объект -А Споиска оптимального маршрута на ТС.

2. Предмет - Определенный граф, с вершинами, ребрами и их весом.

3. Цель - поиск оптимального маршрута для перемещения по ТС.

1.1.1 Особенности транспортных систем

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

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

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

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

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

Рисунок 1 - Обобщенная схема предметной области ЛС

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

* технологическая - обеспечивает выполнение основных функций транспортной системы;

* обеспечивающая - выполняет функции, сопровождающие транспортные процессы;

* восстанавливающая - выполняет функции по поддержанию элементов системы в работоспособном состоянии.

Рисунок 2 - Функциональная структура транспортной системы

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

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

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

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

1.1.2 Транспортные сети

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

Рисунок 3 - Классификация транспортных сетей по использованию их видами транспорта

По кратчайшим направлениям между пунктами перемещения гут перемещаться лишь немногие виды транспорта. Причем реальные пути их перемещения практически всегда отклоняются от прямолинейных вследствие необходимости обхода запретных районов, суверенных территорий, природных особенностей и т.п. Например, для воздушного транспорта в целях разумного ограничения пролета над иностранной территорией, облета воздушного пространства городов, повышения безопасности прокладываются воздушные коридоры, которые используются для прокладки различных маршрутов. Естественные пути для перемещения являются наиболее древ- ними транспортными сетями. Главным образом это реки и пригодные для перемещения внедорожных транспортных средств участки земной поверхности. Основное количество грузов и пассажиров перемещается по дорогам. Дороги по особенностям перемещения делятся на рельсовые и безрельсовые. Из рельсовых дорог несколько особняком стоят монорельсовые дороги не только потому, что они используют один рельс, но и по причине особенностей привода используемых на них транспортных средств, расположения их над или под рельсом и т.п. Среди безрельсовых дорог можно выделить транспортные сети с направляющим устройством (механическим или бесконтактным), которые полу- чают в последнее время все большее распространение не только в пре- делах производственных помещений, но и для городского транспорта.

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

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

1.1.3 Оптимизация

Термином оптимизация - процесс или последовательность операций, позволяющая получить уточненное решение. Хотя конечной целью оптимизации является отыскивание наилучшего, или оптимального решения. Хотя конечной целью оптимизации является отыскание наилучшего или оптимального решения [3].

Проблема оптимизации имеет два основных аспекта:

1. Нужно поставить задачу формализовав понятие наилучший или оптимальный.

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

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

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

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

- в первом случае при убывании целевой функции, качество возрастает - минимизация функции качества;

- во втором случае возрастание функции приводит к уменьшению качества - минимизация.

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

Оптимизация бывает безусловной и условной.

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

Безусловная оптимизация первого порядка - метод скорейшего спуска, метод сопряженных градиентов, метод переменной метрики.

Безусловная оптимизация второго порядка - методы Ньютона.

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

Ручная разработка порождает следующие проблемы:

1. неадекватную спецификацию требований

2. неспособность обнаружить ошибки в проектных решениях;

3. низкое качество документации, снижающее эксплуатационные характеристики;

4. затяжной цикл и неудовлетворительные результаты тестирования.

CASE - Computer Aided Software System engineering (компьютерная помощь в создании программного обеспечения).

Появлению CASE-технологий и CASE-средств предшествовали исследования в области методологии программ.

Этому способствовали следующие факторы.

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

2. Широкое внедрение и постоянный рост производительности компьютеров.

3. Внедрение сетевой технологии.

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

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

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

- выделить управляемые и неуправляемые параметры системы и среды, оказывающие существенное влияние на критерий эффективности;

- определить ограничения на значения параметров.

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

1.2 Обзор аналогов и прототипа

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

В связи с этим методы, используемые в АС были проверены по отдельности со своими аналогами.

Алгоритм Дейкстры был сравнен с найденной в интернете версией и было определено, что представленный в данной работе код является более полным и простым в обращении [4].

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

Ниже на рисунках 4, 5 представлены скриншоты работы найденных аналогов

Рисунок 4 - Работа аналога, алгоритм Дейкстры



Рисунок 5 - Работа аналога, жадный алгоритм

транспортный код алгоритм дейкстра

2. Проектирование

2.1 Диаграмма вариантов использования

Диаграмма вариантов использования описывает функциональное назначение системы [6]. Она является исходным концептуальным представлением системы и строится с целью:

- определить общие границы и контекст моделируемой предметной области;

- сформировать общие требования к функциональному поведению и - интерфейсу системы;

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

В диаграмму вариантов использования входят актанты (actors), варианты использования (usecase) и ассоциации (association).

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

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

Рисунок 6 - Диаграмма вариантов использования

2.2 Сценарий наиболее сложного варианта использования

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

Ниже приведён сценарий для варианта использования «Ввод начальных данных».

Вариант использования: Решение задачи оптимизации по выбору маршрута.

Краткое описание. Оптимизирует выбор кратчайшего маршрута на транспортной сети.

Актант. Пользователь.

Предусловия. Выполнен вариант использования «Авторизация пользователя» с правами Пользователя. На экране - главное окно приложения с пунктами меню «Оптимизация по выбору маршрута», «Справка», «Выход».

Основной поток событий

1. Пользователь выбирает пункт меню «Оптимизация по выбору маршрута».

А1: Выход.

А2: Справка.

2. Система выводит окно с кнопками «Ввести новые начальные данные» и «Загрузить ранее использованные начальные данные».

3. Пользователь нажимает кнопку «Ввести новые начальные данные».

А3: Загрузить ранее использованные начальные данные.

4. Система выводит окно "Ввод начальных данных" с полем ввода "Количество вершин" и кнопками "Далее", "Закрыть".

5. Пользователь вводит количество вершин и нажимает кнопку "Далее".

А4: Закрытие окна ввода.

6. Система закрывает окно «Ввод начальных данных» и открывает окно «Заполнение матриц», в которое выводятся таблицы для задания весовых коэффициентов маршрутов по стоимости и по расстоянию, в которых строкам и столбцам соответствуют номера пунктов маршрута. Размерность таблиц определяется количеством вершин. В окне так же имеются три поля: "Начальная точка", "Конечная точка", “Выбор метода”. К полю “Выбор метода” подключен выпадающий список выбора метода решения задачи. На форме имеются кнопки «ОК», «Сохранить введенные начальные данные» и «Закрыть».

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

А5: Закрытие окна «Заполнение матриц».

А6:Сохранение введенных начальных данных.

8. Система закрывает окно «Заполнение матриц» и выводит на экран форму «Отчет об оптимальном маршруте» с заголовком: «Отчёт об оптимальном маршруте…(дата/время отчета)». Содержание отчета выводится в виде таблиц: «Оптимальный маршрут по стоимости» и «Оптимальный маршрут по расстоянию» с колонками «Номер пункта маршрута», «Весовые коэффициенты». В колонке «Номера пунктов маршрута» перечислены все пункты маршрута от начального до конечного, включая промежуточные, по которым проходит маршрут. В колонке «Весовые коэффициенты» напротив пунктов перечислены веса рёбер до этого пункта от предыдущего. Ниже таблиц указаны итоговые результаты, в виде значения одного критерия. На форме расположена кнопка «Закрыть» .

9. Пользователь просматривает отчет и нажимает кнопку «Закрыть».

10. Система закрывает форму «Отчет об оптимальном маршруте». На экране - главная форма приложения с пунктами меню, настроенными на права Пользователя. Вариант использования завершается успешно.

Альтернативы

А 1: Выход.

А 1.1. Пользователь выбирает пункт меню "Выход".

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

А 2 : Справка.

А 2.1 Пользователь выбирает пункт меню "Справка".

А 2.2. Система открывает форму справки, показывающая основную информацию о системе с кнопкой "ОК".

А 2.3. Пользователь просматривает справку и нажимает кнопку "ОК".

А 2.4. Система закрывает форму справки и выводит на экран главное окно приложения с пунктами меню настроенными на права Пользователя. Вариант использования завершается.

А 3: Загрузить ранее использованные начальные данные

А 3.1: Пользователь нажимает кнопку «Загрузить ранее использованные начальные данные».

А 3.2: Система открывает окно с выбором файлов, в которых хранятся ранее использованные начальные данные.

А 3.3:Пользователь выбирает нужный ему файл и нажимает кнопку «ОК».

А 3.4:Система открывает окно «Заполнение матриц» с уже заполненными формами.

А 3.5:Дальнейшие действия аналогичны действиям, начиная с п. 7.

А 4: Закрытие окна ввода

А 4.1. Пользователь нажимает кнопку "Закрыть" .

А 4.2. Система закрывает форму "Ввод условий запроса" и выводит на экран главное окно приложения с пунктами меню настроенными на права Пользователь. Вариант использования завершается.

А 5 : Закрытие окна «Заполнение матриц»

А 5.1. Пользователь нажимает кнопку "Закрыть" .

А 5.2. Система закрывает окно "Заполнение матриц" и выводит на экран главное окно приложения с пунктами меню настроенными на права Пользователь. Вариант использования завершается.

А 6:Сохранение введенных начальных данных

А 6.1: Пользователь нажимает кнопку «Сохранить введенные начальные данные».

А 6.2: Система открывает окно с выбором файла для сохранения.

А 6.3: Пользователь выбирает файл и нажимает кнопку «ОК»

А 6.4: Система сохраняет введенные начальные данные в выбранном файле.

А 6.5: Дальше работа система продолжает работу, начиная с п.8.

Постусловия. При успешном завершении на экране - главная форма приложения с меню, настроенном на права Пользователя.

Неясные вопросы. Уточнить права пользователей и настройки.

2.3 Диаграмма сущностных классов

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

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

На рисунке 7 представлена диаграмма сущностных классов.

Рисунок 7 - Диаграмма сущностных классов

2.4 Диаграмма граничных классов

Объекты граничных классов реализуют интерфейсы системы с внешней средой и различными пользователями (не следует их путать с внутренними интерфейсами взаимодействия классов, упоминавшихся ранее) [6].

На рисунке 8 представлена диаграмма граничных классов.

Рисунок 8 - Диаграмма граничных классов

2.5 Диаграмма классов управления

На рисунке 9 представлена диаграмма класса управления, объекты этих классов являются активными, берущими на себя управление и организацию вычислительных процессов; чаще всего это стандартные компоненты операционных систем и систем управления базами данных (СУБД), таймеры, координаторы и т.п. [6].

Рисунок 9 - Диаграмма классов управления

2.6 Диаграмма состояний

Диаграмма состояний показывает: пространство состояний данного класса; события, которые влекут переход из одного состояния в другое; действия, которые происходят при изменении состояния. Отдельная диаграмма состояний представляет определенный ракурс динамической модели отдельного класса и целой системы. Строится диаграмма состояний только для классов, поведение которых существенно. Так же можно представить диаграмму состояний для управляемого события поведения системы в целом. Эта диаграмма используется в ходе анализа, чтобы показать динамику поведения системы, а в ходе проектирования - для выражения поведения отдельных классов или их взаимодействия [6].

Рисунок 10 - Диаграмма состояний

Схема наиболее сложного алгоритма

На рисунках 11-17 представлена схема алгоритма Дейкстры. Данный алгоритм находит кратчайшие пути от начальной вершины графа до конечной, заданных с клавиатуры. Алгоритм работает только для графов без рёбер отрицательного веса. Алгоритм широко применяется в программировании и технологиях маршрутизации.



Рисунок 11 - Блок-схема алгоритма(ввод данных: количество вершин, начальная и конечная вершины)

Рисунок 12 - Блок-схема алгоритма (ввод данных: расстановка ребер графа и их веса)



Рисунок 13 - Блок-схема алгоритма(проверка корректности ввода)

Рисунок 14 - Блок-схема алгоритма (расстановка меток из вершины начала прохода)



Рисунок 15 - Блок-схема алгоритма(продолжение расстановок меток графа)



Рисунок 16 - Блок-схема алгоритма

Рисунок 17 - Блок-схема алгоритма(вывод конечного результата)

3. Реализация

3.1 Архитектура и платформа реализации

Для создания данного программного комплекса использовалась платформа QtCreator 5.4 и язык программирования C++. Qt Creator -- кросс платформенная свободная IDE для разработки на С, С++ и QML. Разработана Trolltech (Digia) для работы с фреймворком Qt. Включает в себя графический интерфейс отладчика и визуальные средства разработки интерфейса как с использованием QtWidgets, так и QML[7].

3.1.1 Особенности

Основная задача Qt Creator -- упростить разработку приложения с помощью фреймворка Qt на разных платформах. Поэтому среди возможностей, присущих любой среде разработки, есть и специфичные, такие как отладка приложений на QML и отображение в отладчике данных из контейнеров Qt, встроенный дизайнер интерфейсов как на QML, так и на QtWidgets.

3.1.2 Работа с проектами

Qt Creator поддерживает системы сборкиqmake, cmake, autotools, с версии 2.7 qbs. Для проектов, созданных под другими системами, может использоваться в качестве редактора исходных кодов. Есть возможность редактирования этапов сборки проекта.

Также IDE нативно поддерживает системы контроля версии, такие как Subversion, Mercurial, Git, CVS, Bazaar, Perforce. Начиная с версии 2.5, в поле комментария к правке поддерживается автодополнение.

3.1.3 Редактирование кода

В Qt Сreator реализовано автодополнение, в том числе ключевых слов, введённых в стандарте C++11 (начиная с версии 2.5), подсветка кода (её определение аналогично таковому в Kate, что позволяет создавать свои виды подсветок или использовать уже готовые). Также, начиная с версии 2.4, есть возможность задания стиля выравнивания, отступов и постановки скобок.

Реализован ряд возможностей при работе с сигнатурами методов, а именно:

· автогенерация пустого тела метода после его обновления;

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

· возможность автоматически поменять порядок следования аргументов.

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

3.1.4 Отладка кода

Среда разработки имеет графический интерфейс для следующих отладчиков: GDB, CDB и QML/ JavaScript. В качестве отдельной опции реализовано отображение содержимого контейнеров, таких как QString, std::map и прочих. Поддерживаются следующие режимы отладки:

· простой для отладки локально запущенных приложений, таких как GUI приложения на Qt;

· терминал для отладки локально запущенных процессов, которым требуется консоль, обычно это приложения без GUI;

· подключённый для отладки локальных процессов, запущенных вне Qt Creator;

· удалённый для отладки запущенных на другой машине процессов (используя gdbserver);

· ядро для отладки завершившихся аварийно процессов на Unix;

· Post-mortemдля отладки завершившихся аварийно процессов на Windows;

· TRK для отладки процессов, запущенных на устройстве Symbian.

Точки остановки можно задать различными способами, а именно:

· останавливаться на заданной строчке заданного файла;

· останавливаться при вызове функции с определенным именем;

· останавливаться при обращении к данным по заданному адресу;

· останавливаться при поимке исключения;

· останавливаться при запуске или создании нового процесса;

· останавливаться при выполении системного вызова;

· останавливаться при изменении в данных с адресами, заданными выражением.

3.1.5 Архитектура

Функция main -- вызов загрузчика плагинов, которые и реализуют всю функциональность. Поэтому все компоненты QtCreator так или иначе связаны с плагинами.

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

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

Utils-- библиотека утилит, которые могут вызывать плагины.

QmlJS-- библиотека для поддержки QML и JavaScript.

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

Язык C++ представляет собой набор команд, которые говорят компьютеру, что необходимо сделать. Этот набор команд, обычно называется исходный код или просто код. Командами являются или «функции» или «ключевые слова». Ключевые слова(зарезервированные слова С/С++) являются основными строительными блоками языка. Функции являются сложными строительными блоками, так как записаны они в терминах более простых функций -- вы это увидите в нашей самой первой программе, которая показана ниже. Такая структура функций напоминает содержание книги. Содержание может показывать главы книги, каждая глава в книге может иметь своё собственное содержание, состоящее из пунктов, каждый пункт может иметь свои подпункты. Хотя C++ предоставляет много общих функций и зарезервированных слов, которые вы можете использовать, все-таки возникает потребность в написании своих собственных функций.

В данном проекте вместо СУБД используется файловая система ОС.

3.2 Расчет необходимого объема внешней памяти

Расчет объема требуемой внешней памяти происходит по следующей формуле (1)

V_ВП=V_ОС+V_ФС+V_Данных+V_{Программы,} (1)

где V_ВП - общий объем внешней памяти, Гбайт;

V_ОС - объем внешней памяти, занимаемый операционной системой, Мб;

V_ФС - объем внешней памяти, занимаемый файловой системой, Мб_;

V_Данных - объем внешней памяти, занимаемый данными, необходимыми для работы системы, Мб;

V_{Программы} - объем внешней памяти, занимаемый программными модулями, Мб.

Расчет необходимого объема внешней памяти

V_ОС - объем внешней памяти, по паспорту для операционной системы Windows 7 64-бит- 20 гб;

V_{ФС =} 0,01 гб

V_Данных = 0,07 гб

V_{программы} - объем внешней памяти, необходимой для хранения текстов и библиотек приложений -0,03 гб

V_ВП = V_ОС (20.0) +V_ФС(0,01)+ V_данных (0,07) + V_{программы} (0.03)= 20,11 Гб

3.3 Расчет необходимого объема оперативной памяти

Для расчета ОЗУ воспользуемся формулой (2)

V_ОП=V_ОС+V_ФС+V_данных+V_{программы}, (2)

где V_ОП- общий объем оперативной памяти, Мбайт;

V_ОС - объем оперативной памяти, требуемый для установки операционной системы, Мбайт;

V_ФС - объем оперативной памяти, требуемый для установки файловой системы, Мбайт;

V_данных - объем оперативной памяти, требуемый для хранения записей файловой системы и результатов выполнения функций, Мбайт;

V_{программы} - объем оперативной памяти, необходимой для хранения текстов и библиотек приложений, Мбайт.

Расчет необходимого объема оперативной памяти

Vос- по паспорту для операционной системы Windows 7 64 бит- 2048 мб;

V_ФС - 0,8 мб:

V данных - 0,5 мб ;

V программы -30 мб.

Суммарный объем ОЗУ, необходимый для функционирования системы:

V_ОП = V_ОС (2048) + V_ФС (0,8) + V_данных (0,5) + V_{программы} (30)= 2079,3 Мб

3.4 Расчет времени реакции системы

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

Общее время реакции системы на выполнение запроса рассчитывается по формуле (3).

, (3)

t_eeoda - время на ввод входных данных запроса;

k_ee - коэффициент ошибок при вводе, для расчетов можно принять равным 1.5;

L_симe - количество символов, вводимых в качестве исходных данных запроса. Т.к. количество вводимых символов изначально не известно, то для расчетов можно взять примерную величину = 50

t_симe - время ввода одного символа, при ручном вводе с клавиатуры в некоторую экранную форму можно принять в среднем равным 1.5 с;

t_{считывания} - время, затрачиваемое на считывание физических блоков при работе с накопителем;

N_бл - количество считываемых физических блоков, зависит от количества обрабатываемых таблиц (файлов) и объема таблиц (файлов);

t_поз=0,006 сек - время позиционирования головок дискового накопителя;

t_сч.бл =0,001 сек - время считывания физического блока в дисковом накопителе;

t_{вычисления} - время, затрачиваемое процессором на обработку информации с учетом выполнения циклов;

N_опер = 100 - количество операций высокого уровня, необходимых для формирования результата;

K₁ - среднее количество тактов машинных команд на одну операцию, для большинства случаев можно принять К₁ = 60;

f = 1600*10⁶ - тактовая частота процессора, Гц;

V_maбл = 1024 байт - средний объем таблицы, байт;

N_maбл = 1 - количество таблиц, обрабатываемых в запросе;

У_блока= 512 байт - объем физического блока носителя, байт;

t_вывода - время на вывод результата на устройство вывода или

отображения, для принтера оценивается отдельно. Для дисплея можно принять 0.5 с. (зависит от видеокарты и дисплея).

Полученное время реакции системы без времени ввода с клавиатуры соответствует нормам времени для диалогового режима (до 30 с).

На основании проведенных расчетов определена конфигурация КТС в стандартном составе.

Процессор с тактовой частотой 2,0Ггц

Необходимая оперативная память 2Гб

Необходимая внешняя память не менее 20Гб

3.5 Основные интерфейсы

После запуска программы появляется окно «Авторизация пользователя» (рисунок 18).

Рисунок 18 - Авторизация пользователя

После правильного ввода логина и пароля появится главное окно работы программы. Пользователю необходимо ввести количество пунктов и нажать клавишу «ОК» (рисунок 19).



Рисунок 19 - Главное окно программы

После нажатия кнопки «ОК» появляется пустая матрица стоимостей. Пользователь заполняет поля «Начальная точка» и «Конечная точка» (рисунок 20). Далее пользователь заполняет матрицу стоимостей вручную или может загрузить ранее использованную матрицу стоимостей.

Рисунок 20 - Ввод начальной и конечной точек

Чтобы загрузить ранее использованную матрицу стоимостей необходимо нажать кнопку «Загрузить», после чего появится окно с выбором нужного файла. Пользователь выбирает нужный ему файл и нажимает кнопку «Открыть» (рисунок 21).



Рисунок 21 - Загрузка ранее использованной матрицы стоимостей

После того как все начальные данные были загружены пользователь может нажать кнопку «Дейкстра» или «жадный» для расчета конечного результата по соответствующим алгоритмам (рисунок 22).

Рисунок 22 - Заполненная матрица стоимостей

После нажатия кнопки «Дейкстра» или «жадный» появляется окно с конечным результатом (рисунок 23), (рисунок 24).



Рисунок 23 - Результат работы алгоритма Дейкстры

Рисунок 24 - Результат работы жадного алгоритма

3.6 Диаграмма компонентов

Диаграмма компонентов, Component diagram -- статическая структурная диаграмма, показывает разбиение программной системы на структурные компоненты и связи (зависимости) между компонентами. В качестве физических компонентов могут выступать файлы, библиотеки, модули, исполняемые файлы, пакеты и т. п. [9].

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

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

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

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

Рисунок 25 - Диаграмма компонентов

3.7 Диаграмма развертывания

Диаграмма развёртывания, Deployment diagram в UML моделирует физическое развертывание артефактов на узлах. Например, чтобы описать веб-сайт диаграмма развертывания должна показывать, какие аппаратные компоненты («узлы») существуют (например, веб-сервер, сервер базы данных, сервер приложения), какие программные компоненты («артефакты») работают на каждом узле (например, веб-приложение, база данных), и как различные части этого комплекса соединяются друг с другом (например, JDBC, REST, RMI) [9].

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

Существует два типа узлов:

1. Узел устройства

2. Узел среды выполнения

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

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



Рисунок 26 - Диаграмма развертывания

3.8 Программа и методика испытаний

1. ОБЪЕКТ ИСПЫТАНИЙ.

1.1. Наименование испытуемой программы.

Наименование - «Модуль решения задачи оптимизации функции».

1.2. Область применения испытуемой программы.

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

1.3. Обозначение испытуемой программы.

Наименование темы разработки - «Автоматизированная система поиска оптимального маршрута на транспортной сети».

2. ЦЕЛЬ ИСПЫТАНИЙ.

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

3. ТРЕБОВАНИЯ К ПРОГРАММЕ.

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

4. ТРЕБОВАНИЯ К ПРОГРАММНОЙ ДОКУМЕНТАЦИИ.

4.1. Состав программной документации, предъявляемой на испытания.

Состав программной документации должен включать в себя:

1) техническое задание;

1) пояснительная записка;

3) руководство пользователя.

4.2. Специальные требования.

Специальные требования к программной документации не предъявляются.

5. СРЕДСТВА И ПОРЯДОК ИСПЫТАНИЙ.

5.1. Программные средства, используемые во время испытаний.

Системные программные средства «deikstra.exe», должны быть представлены локализованной версией операционной системы Windows 7, Windows 8 или Windows 10.

5.2. Порядок проведения испытаний.

Испытания проводятся в два этапа:

1 этап - ознакомительный.

2 этап - испытания.

5.2.1. Перечень проверок проводимых на первом этапе испытаний.

Перечень проверок, проводимых на первом этапе испытаний, должен включать в себя:

а) проверку комплектности программной документации;

б) проверку комплектности и состава технических и программных средств.

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

5.2.2. Перечень проверок проводимых на втором этапе испытаний.

Перечень проверок, проводимых на втором этапе испытаний, должен включать в себя:

а) проверку соответствия технических характеристик программы;

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

· авторизация пользователей;

· ввод и редактировании оперативной информации: стоимость перевозки из одного пункта в другой, начальная и конечная точки маршрута;

· решение задачи оптимизации по выбору маршрута;

· формирование отчетов: принятие решения о перемещении по заданному маршруту, его расстояние, стоимость перевозки по маршруту в целом.

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

5.3. Количественные и качественные характеристики, подлежащие оценке.

5.3.1. Количественные характеристики, подлежащие оценке.

В ходе проведения приемо-сдаточных испытаний оценке подлежат количественные характеристики, такие как:

а) комплектность программной документации;

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

5.3.2. Качественные характеристики, подлежащие оценке.

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

а) проверка работоспособности программы;

б) проверка на сообщение об ошибке.

5.4. Условия проведения испытаний.

5.4.1. Климатические условия.

Испытания должны проводиться в нормальных климатических условиях по ГОСТ 22261-94. Условия проведения испытаний приведены ниже:

- температура окружающего воздуха, °С 20 ± 5;

- относительная влажность, % - от 30 до 80;

- атмосферное давление, кПа - от 84 до 106;

- частота питающей электросети, Гц - 50 ± 0,5;

- напряжение питающей сети переменного тока, В - 220 ± 4,4.

5.4.2. Условия начала и завершения отдельных этапов испытаний.

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

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

5.4.3. Ограничения в условиях испытаний.

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

5.4.4. Меры, обеспечивающие безопасность и безаварийность испытаний.

При проведении испытаний должно быть обеспечено соблюдение требований безопасности, установленных ГОСТ 12.2.007.0-75 8), «Правилами техники безопасности при эксплуатации электроустановок потребителей», и «Правилами технической эксплуатации электроустановок потребителей».

6. МЕТОДЫ ИСПЫТАНИЙ.

6.1. Методика проведения проверки комплектности программной документации.

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

...