Программное обеспечение вычислительной техники и автоматизированных систем

Методические указания к выполнению курсового проекта по дисциплине

«Математические методы»

Для студентов специальности

Программное обеспечение вычислительной техники и автоматизированных систем

Рассмотрено на заседании ЦК информатики

Протокол №_____

От «___»_____________2013г.

Методист_______________

Содержание

Аналитический раздел

1. Описание метода. Виды задач, решаемых методом динамического программирования

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

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

2.Общая постановка задачи динамического программирования

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

Пусть имеется некоторая система S находящаяся в некотором локальном состояний S₀ и являющаяся управляемой. Пусть под воздействием некоторого управления U система переходит из начального состояния S₀ в S_к и пусть этот переход осуществляется за n шагов. Пусть на каждом шаге состояния систем характеризуется рядом параметром в частности на к-ом шаге x^(k) =(x₁^(k), x₂^(k),… x_m^(k)).

Эффективность реализуемого управления U характеризуется значением ω(U) которую признано называть выигрышем.

Управление U_к обеспечивающее переход системы из состояния в состояние называется шаговым управлением. Совокупность всех шаговых управлений называется управлением операции в целом U = (u_1; u_2; …u_n)

Выигрыш полученный в результате реализации шагового управления u_к называется выигрышем на к шаге и обозначается ω_к

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

ω(U) =

Задача ДП заключается в том чтобы из множества возможных управлений найти управление U ^x=(U₁^x; U₂^x..U ^x _n) при котором функция ω(U) при оптимальное значения max(min).

Принцип оптимальности, принцип аддитивности целевой функции, уравнение Беллмана в общем виде

3.Общий алгоритм решения поставленной задачи

Дата добавления: 2015-08-13