Программная реализация метода динамического программирования для нахождения кратчайшего маршрута транспортной задачи в сетевой постано
Автор: Evgeny0211 • Январь 8, 2019 • Курсовая работа • 5,042 Слов (21 Страниц) • 720 Просмотры
Содержание
Введение ……………………………………………………………..………......… | 5 |
1 Постановка задачи …………………….……………..…………..………….… | 6 |
1.1 Требования к системе и ее структуре ……………………………………...… | 7 |
1.2 Требования к функциям, выполняемым системой …………..…………...…. | 7 |
1.3 Требования к программно - аппаратному обеспечению ……..…………....... | 8 |
1.4 Требования к техническому обеспечению …………………..……………..... | 8 |
1.5 Требования к эргономике и технической эстетике …………..…………....... | 8 |
1.6 Требования к надежности и хранению информации ……….……..………… | 11 |
2 Основная часть …………………………….…………….……..……………… | 12 |
2.1 Математическая модель ………………………………………………………. | 12 |
2.2 Метод решения задачи …………………………………….…..……………… | 12 |
2.3 Структурная схема программы ………………………………..…………… | 18 |
2.4 Схема взаимодействия модулей ………………………………..……….….… | 18 |
3 Руководство программисту …………………………………...…...………….. | 20 |
4 Руководство пользователю …………………………………………………… | 22 |
4.1 Общие сведения ……………………………………..………………..…….…. | 22 |
4.2 Работа с помощью ……………………………………..………….…..…….…. | 22 |
4.3 Наиболее вероятные ошибки …………………………………….……............ | 22 |
Заключение ……………………………………..…………………………….......... | 24 |
Список использованных источников ………………………………………….…. | 25 |
Приложение А Текст программы………………………………………………… | 26 |
Приложение Б Формы программы……………………………………………...... | 38 |
Приложение В Диск с программой……………………………………………..... | 42 |
Введение
Математическое моделирование является в настоящее время одной из важнейших составляющих научно – технического прогресса. Без применения этой методологии в развитых странах не реализуется ни один крупномасштабный технологический, экологический или экономический проект. Решение проблем жизнеобеспечения на современном этапе основывается на широком использовании математического моделирования и вычислительного эксперимента.
Динамическое программирование связано с возможностью представления процесса управления в виде цепочки последовательных действий или шагов, развернутых во времени и ведущих к цели. Таким образом, процесс управления можно разделять на части и представить его в виде динамической последовательности и интерпретировать в виде пошаговой программы, развернутой во времени. Это позволяет спланировать программу будущих действий. Поскольку вариантов возможных планов - программ множество, то, необходимо из них выбрать лучший, оптимальный по какому-либо критерию в соответствии с поставленной целью.
Целью курсового проекта является программная реализация метода динамического программирования для нахождения кратчайшего маршрута транспортной задачи в сетевой постановке.
Для достижения постановленной цели необходимо решение следующих задач
- изучения теоретического материала по теме работы;
- рассмотрение основных положений теории графов;
- изучения метода динамического программирования;
- изучения теоретических основ программирования;
- программная реализация метода динамического программирования в среде программирования Delphi 7.
1 Постановка задачи
Разработать программу для нахождения кратчайшего пути методом динамического программирования.
К основным характеристикам функциональных задач относятся:
- цель и назначение данной задачи состоит в том, чтобы решить задачу динамического программирования в общем виде;
- условия решения задачи с использованием средств вычислительной техники:
- компьютер - ACPI на базе x64;
- процессор - Intel(R) Core(TM) i5-2450M CPU;
- частота ЦП - 2,55GHz;
- объем оперативной памяти - 6 Гб ОЗУ;
- видеокарта - Intel(R) HD Graphics 3000;
- жесткий диск - HDD 240 Gb;
- привод - DVD+R/RW&CDRW;
- монитор - Универсальный монитор PnP;
- клавиатура - PS/2 KeyBoard;
- содержание функций обработки входной информации для решения задачи – ввод информации, проверка ее на корректность и сохранение;
- требование к периодичности решения задачи – по необходимости;
- ограничение по срокам и точности выходной информации – информация предоставляется сразу после завершения процесса обработки входной информации, а именно после ввода данных;
- форма представления выходной информации – предоставляется в электронном;
- состав представления выходной информации – оптимальное значение вершин графов, оптимальный план, симплекс таблицы;
- источники входной информации для решения задачи – постановка задачи в виде системы вершин графов;
- пользователями программы будут все пользователи, имеющие навыки работы с ПК, которым необходимо решить задачу динамического программирования.
Схема взаимодействия входной и выходной информации отображена на рисунке 1.
[pic 1]
[pic 2][pic 3][pic 4][pic 5][pic 6][pic 7][pic 8]
...