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

Министерство  образования и науки российской федерации   Федеральное государственное  бюджетное образовательное учреждение высшего профессионального  образования «Оренбургский государственный университет»   КОЛЛЕДЖ ЭЛЕКТРОНИКИ  И БИЗНЕСА   Кафедра физико-математических дисциплин             КУРСОВОЙ ПРОЕКТ   по дисциплине: «Математические методы»   Метод динамического  программирования   КЭиБ ОГУ 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 Требования  к эргономике и технической  эстетике

 

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

 

 

 

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

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

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

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

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

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

Понятный интерфейс снижает количество человеческих ошибок.

 

1.6 Требования  к надежности и хранению информации

 

В целях избежание  не корректной работы программы  не рекомендуется:

• Удаление данных и файлов и каталога программы;
• Изменение структуры и целостности кода программы;
• Переименование и перемещение файлов в каталоге программы;

Объем программы  составляет 584 кб. Приложения можно  хранить на любых носителях. Ограничения  на транспортировку отсутствуют.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2 Основная  часть

 

2.1 Математическая  модель

 

Математическая модель - это математическое представление  реальности.

Математическое моделирование - процесс построения и изучения математических моделей.

Модель - объект произвольной природы, который отражает главные, с точки зрения решаемой задачи, свойства объекта моделирования.

Главные функции модели:

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

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

1. Разбиение задачи на подзадачи меньшего размера;
2. Нахождение оптимального решения подзадач рекурсивно, проделывая такой же трех шаговый алгоритм;
3. Использование полученного решения подзадач для конструирования решения исходной задачи.

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

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

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

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

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

 

 

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

 

2.2 Метод  решения задачи

 

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

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

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

1. выделить и описать подзадачи, через решение которых будет выражаться искомое решение;
2. выписать рекуррентные соотношения (уравнения), связывающие оптимальные значения параметра для подзадач;
3. вычислить оптимальное значение параметра для всех подзадач;
4. построить само оптимальное решение, используя полученную информацию.

Если нас интересует только значение параметра, то шаг 4 в  алгоритме не нужен (такая ситуация характерна, например, для задач  подсчета количеств допустимых вариантов или некоторых конфигураций, в том числе и комбинаторных). Однако, в случае необходимости построения самого оптимального решения иногда приходится в процессе выполнения шага 3 алгоритма получать и хранить дополнительную информацию. Зачастую именно шаг 4 оказывается самым сложным при реализации подобных алгоритмов.

Ниже приведен пример аналитического решением относительно предметной области, где:

Ui - выбор дороги на i - м шаге по которому направляется груз из данного пункта в соседний пункт;

Fi - итог предыдущего шага местонахождение транспорта с грузом в пункте в котором пребывает перед следующим шагом;

Zi – затраты на перевозку единиц груза из данного пункта в соседний.

Рассмотрим  решение задачи на данном примере. Дана модель соединения городов:

 

 

 

 

 

 

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

 Основные этапы решения задачи представлены в таблицах 8 – 12.

 Таблица 8 - разбиение вершин по группам

I	I	III	IV	V
с1	с2	с5	с8	с10
	с3	с6	с9
	с4	с7

После чего составим основное функциональное уравнение динамического  программирования:

F_i (x_i – 1, U_i) = extr (Z_i (x_i – 1, U_i) + F_i + 1 (x_i));

Для n шага уравнение примет следующий вид:

Fn (x_n – 1, U_n) = extr (Z_n (x_n – 1, U_n – 1, U_n) + F_n + 1 (x_n));

Таблица 9 - первый этап

х3	U4	Z3	х4	f4
с8	(8,10)	1	С10	1
с9	(9,10)	7	С10	7

 

 

 

 

Для первого этапа  уравнение примет следующий вид:

F4 (x₃ – 1, U₄) = extr (Z₃ (x₃ – 1, U₄ – 1, U₄) + F₄ + 1 (x₃));

Таблица 10 - второй этап

X2	U3	Х3	Z3	F4	Z3+F4	F3
с5	(5,8)	с8	7	1	8	8
	(5,9)	с9	2	7	5	-
с6	(6,8)	с8	9	1	10	-
	(6,9)	с9	2	7	9	9
с7	(7,9)	с9	8	7	15	11

Для второго этапа  уравнение примет следующий вид:

F3 (x₂ – 1, U₃) = extr (Z₃ (x₂ – 1, U₃ – 1, U₃) + F₃ + 1 (x₂));

Таблица 11 - третий этап

X1	U2	Х2	Z2	F4	Z2+F3	F2
с2	(2,5)	с5	1	8	9	9
	(2,7)	с7	6	15	21	-
с3	(3,5)	с5	2	8	10	10
	(3,6)	с6	7	9	16	-
	(3,7)	с7	4	15	19	-
с4	(4,5)	с5	6	8	14	14
	(4,6)	с6	8	9	17	-
	(4,7)	с7	3	15	18	-

 

Для третьего этапа уравнение  примет следующий вид:

F2 (x₁ – 1, U₂) = extr (Z₂ (x₁ – 1, U₂ – 1, U₂) + F₂ + 1 (x₁));

Таблица 12 – четвертый этап

X0	U1	Х1	Z1	F2	Z1+F2	F1
с1	(1,2)	с2	3	9	12	12
	(1,3)	с3	5	10	15	-
	(1,4)	с4	4	14	18	-

 

 

 

 

 

Для четвертого этапа уравнение примет следующий вид:

F1 (x₀ – 1, U₁) = extr (Z₁ (x₀ – 1, U₁ – 1, U₁) + F₁ + 1 (x₀));

Наиболее экономичный  маршрут доставки груза из пункта 1 в пункт 10 это: 1-2-5-8-10, а минимальные расстояние составляют 12 тыс.км.

2.3 Структурная схема программы

Структурная схема программы проиллюстрирована на рисунке 3.

 

 

 

 

Рисунок 3 - Пример структурной схемы программы

 

2.4 Схема  взаимодействия модулей

Схема взаимодействия модулей представлен на рисунке 4.

Рисунок 4 - Схема взаимодействия модулей

 

 

 

 

 

 

 

 

 

3 Руководство  программисту

 

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

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

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

 

4 Руководство  пользователя

 

4.1 Общие  сведения

 

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