Метод динамического программирования

Министерство  образования и науки российской федерации   Федеральное государственное  бюджетное образовательное учреждение высшего профессионального  образования «Оренбургский государственный университет»   КОЛЛЕДЖ ЭЛЕКТРОНИКИ  И БИЗНЕСА   Кафедра физико-математических дисциплин             КУРСОВОЙ ПРОЕКТ   по дисциплине: «Математические методы»   Метод динамического  программирования   КЭиБ ОГУ 230105.4008.22 П4                 Руководитель   _________________Попова  Л.А. «___» _________________2012 г. Исполнитель Студент группы 44П-4 _______________Смирнов  А.С. «___» _________________2012 г.                       Оренбург 2012       Министерство  образования и науки российской федерации   Федеральное государственное  бюджетное образовательное учреждение высшего профессионального  образования «Оренбургский государственный университет»   КОЛЛЕДЖ ЭЛЕКТРОНИКИ  И БИЗНЕСА   Кафедра физико-математических дисциплин     Задание на курсовой проект по дисциплине: «Математические методы» Метод динамического  программирования       Исходные  данные: Модель соединения городов, расстояние между городами _________________________________________________ _________________________________________________ _________________________________________________ _________________________________________________ _________________________________________________             Дата выдачи задания  «____»___________2012 г. Руководитель __________________ Попова Л.А. Исполнитель Студент группы 44П-4__________ Смирнов А.С. Срок защиты работы «____»___________2012 г.                     Оренбург 2012 г.

 

Содержание

 Введение 4

1 Приложение А - Текст программы 17

Сложение Б - Формы программы 22

 

 

Аннотация

 

 

 

 Отчет по курсовому проекту содержит  12 страниц пояснительной записки, рисунков – 8, таблиц – 5, формул – 1, использованных источников – 9, дополнительных приложений – 2 .

 

 

 

 

 

 

 

 

Введение

 

Темой курсового проекта является «Метод динамического программирования».

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

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

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

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

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

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

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

 

 

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

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

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1 Постановка задачи

 

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

 

Рисунок 1 – Модель соединения городов

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

 

1. Требования к системе и ее структуре

 

Для работы программы  необходимо:

• процессор не  ниже Pentium 4 2Ггц;
• память ОЗУ не меньше 256 Мб;
• дисковод CD-ROM;

Необходимо  также наличие клавиатуры, монитора, мыши и печатающего  устройства, на ПК должна быть установлена операционная система Windows версии 98/NT/2000/Me/XP/Vista/7  и с установленной программой Delphi.

 

2. Требования к функциям, выполняемым системой

 

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

2) При решении  задачи обработка входной информации  заключена во вводе данных, проверка  корректности ввода, сохранение  информации.

3) Требования  к периодичности решения задачи: работа с данными  может  происходить:

• Ежедневно;
• По требованию.

 

 

 

 

 

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

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

6) Источники  входной информации для решения  задачи: граф, веса соединений.

7) Пользователи  задачи: программой пользуются работники  предприятия, имеющие навыки работы  с компьютером.

 

1.3 Требования  к программно-аппаратному обеспечению

 

Условия решения  задачи с использованием средств  вычислительной техники: программа разработана в среде Delphi 7.

• процессор не  ниже Pentium 4 2Ггц;
• память ОЗУ не меньше 256 Мб;
• дисковод CD-ROM;

Необходимо  также наличие клавиатуры, монитора, мыши и печатающего  устройства, на ПК должна быть установлена операционная система Windows версии 98/NT/2000/Me/XP/Vista/7  и с установленной программой Delphi.

 

1.4 Требования  к техническому обеспечению

 

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

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

Комплекс технических  средств должен включать средства резервирования и восстановления данных.

Комплекс технических  средств должен легко адаптироваться к изменению числа пользователей.

 

1.5 Требования  к эргономике и технической  эстетике

 

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

 

 

 

Данная программа отвечает требованиям эргономике и технической эстетике.

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

Чтобы не перегружать  память человека-оператора исключается:

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