Решение задач динамического программирования

33

Курсовая работа

на тему:

Решение задач динамического программирования

Содержание

Введение

1. ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ

1.1 Задача динамического программирования

1.2 Общая структура динамического программирования

2. Решение задач в динамическом программировании

2.1 Основная идея и особенности вычислительного метода динамического программирования

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

3. программа MathCAD в задачах динамического программирования

Заключение

Список литературы

ВВЕДЕНИЕ

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

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

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

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

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

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

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

1. ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ

1.1 Задача динамического программирования

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

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

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

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

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

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

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

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

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

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

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

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

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

2. Расчленить операцию на этапы (шаги).

3. Выяснить набор шаговых управлений x_i для каждого шага и налагаемые на них ограничения.

4. Определить какой выигрыш приносит на i-ом шаге управление x_i, если перед этим система была в состоянии S, т.е. записать «функцию выигрыша»:

.(1)

5. Определить, как изменяется состояние S системы S под влиянием управление x_i на i-ом шаге: оно переходит в новое состояние

. (1.1)

6. Записать основное рекуррентное уравнение динамического программирования, выражающее условный оптимальный выигрыш W_i(S) (начиная с i-го шага и до конца) через уже известную функцию W_i+1(S):

. (1.2)

Этому выигрышу соответствует условное оптимальное управление на i-м шаге x_i(S) (причем в уже известную функцию W_i+1(S) надо вместо S подставить измененное состояние )

7. Произвести условную оптимизацию последнего (m-го) шага, задаваясь гаммой состояний S, из которых можно за один шаг дойти до конечного состояния, вычисляя для каждого из них условный оптимальный выигрыш по формуле (1.3)

8. Произвести условную оптимизацию (m-1)-го, (m-2)-го и т.д. шагов по формуле (1.2), полагая в ней i=(m-1),(m-2),…, и для каждого из шагов указать условное оптимальное управление x_i(S), при котором максимум достигается.

Заметим, что если состояние системы в начальный момент известно, то на первом шаге варьировать состояние системы не нужно - прямо находим оптимальный выигрыш для данного начального состояния S₀. Это и есть оптимальный выигрыш за всю операцию

(1.4)

9. Произвести безусловную оптимизацию управления, «читая» соответствующие рекомендации на каждом шаге. Взять найденное оптимальное управление на первом шаге ; изменить состояние системы по формуле (1.1); для вновь найденного состояния найти оптимальное управление на втором шаге х₂^* и т.д. до конца.

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

(1.5)

(если только выигрыши w_i положительны). Эти задачи решаются точно так же, как задачи с аддитивным критерием, с той единственной разницей, что в основном уравнении (1.2) вместо знака «плюс» ставится знак «умножения»: .(1.6)

1.2 Общая структура динамического программирования

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

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

Если число решений очень велико, то можно построить относительные оценки состояний так, чтобы оценки, отвечающие каждой паре последовательных решений, отличались друг от друга на постоянную величину, представляющую собой средний «доход» на решение. Также можно выполнять дисконтирование доходов от будущих решений. Необходимость в этом иногда появляется в том случае, когда решение принимаются редко, скажем раз в году. Тогда уже не нужно рассматривать последовательно 1,2,3…решения, чтобы достичь решения с большим номером. Вместо этого можно непосредственно оперировать функциональным уравнением, что, как правило, дает существенную выгоду с точки зрения сокращения объема вычислений.

2. Решение задач в динамическом программировании

2.1 Основная идея и особенности вычислительного метода динамического программирования

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

максимизировать  (2)

при условиях

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

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

(2.1)

причем

 .

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

 .

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

Очевидно, что

 .

Для вычисления определим  и  для всех допустимых значений  и выберем максимальное . Одновременно найдем оптимальное решение . Таким образом, если бы была известна функция , то вся задача свелась бы к задаче с одной переменной.

Покажем, как вычислить .

Обозначим

при условии

 .

Повторив вышеприведенные выкладки, получим

 , (2.2)

где

 ,

причем максимум в уравнении отыскивается при условии

 .

Аналогичным образом вычисляем и т.д. В конце концов на -м шаге мы используем 'основное рекуррентное соотношение (ОРС) динамического программирования'

(2.3)

при условии, что

 .

Используя ОРС , организуем процесс вычислений, как многошаговый процесс, следующим образом. На первом шаге, зафиксировав начало интервала 0 и изменяя его правый конец , вычисляем

 (2.4)

для всех возможных значений =0, 1, . , b. Оптимальное решение первого шага обозначим через . Составляем таблицу динамического программирования первого шага (табл. 7.1) и заполняем ее результатами вычислений.

На втором шаге (=2) находим  в соответствии с соотношением

 , (2.5)

причем значения  берем из табл. 1.1.

Вычисляем последовательно  для всех значений = 0,1,.,, используя результаты табл. 1.1. Одновременно находим  и . Результаты вычислений заносим в таблицу второго шага (табл. 1.2).

Таблица 1.1		Таблица 1.2
0				0
1				1

Дале, пользуясь соотношением, последовательно вычисляем  для всех значений  = 0, 1, 2, ., .

В конце концов, на последнем шаге при  находим

 , (2.6)

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

 .(2.7)

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

Сравним метод динамического программирования по числу необходимых операций с простым перебором вариантов. Для упрощения расчетов примем .

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

 . (2.8)

Например, при  = 5,  = 20, = 10626.

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

Для вычисления  при фиксированном  необходимо выполнить (+1) вычислений функции  при . Следовательно, чтобы заполнить одну таблицу (при =0,1, .,) необходимо  операций.

Таким образом, для вычисления всех функций  ,  необходимо  операций.

С учетом вычислений функции  общее число операций составляет

 .(2.9)

Это значительно меньше, чем , то есть имеем существенное сокращение объема вычислений сравнительно с простым перебором.

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

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

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

Задача должна допускать интерпретацию как -шаговый процесс принятия решений.

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

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

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

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

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

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

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

 , (3)

где  - вектор состояния предыдущего ()-го шага при условиях  и . В рассматриваемой задаче .

Сформулируем принцип оптимальности Беллмана, который обосновывает это соотношения.

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

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

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

Будем считать, что состояниерассматриваемой системы S на k-м шаге (k = 1, 2, ..., п) определяется совокупностью чисел

(3.1)

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

Пусть также выполняются два условия:

1. Условие отсутствия последействия. Состояниев которое перешла система S, зависит от исходного состоянияи выбранного управленияи не зависит от того, каким образом система S перешла в состояние

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

(3.2)

где

Задача состоит в нахождении оптимальной стратегии управления, т. е. такой совокупности управлений в результате реализации которых система S за п шагов переходит из начального состояния в конечное и при этом функция дохода G(m) принимает наибольшее значение. Принцип оптимальности Беллмана. Каково бы ни было состояние системы перед очередным шагом, надо выбрать управление на этом шаге так, чтобы доход на данном шаге плюс оптимальный доход на всех последующих шагах был максимальный. Из принципа оптимальности следует, что оптимальную стратегию управления можно получить, если сначала найти оптимальную стратегию управления на n-м шаге, затем на двух последних шагах, затем на трех последних шагах и т. д., вплоть до первого шага. Таким образом, решение рассматриваемой задачи динамического программирования целесообразно начинать с определения оптимального решения на последнем, n-м шаге. Для того чтобы найти это решение, очевидно, нужно сделать различные предположения о том, как мог окончиться предпоследний шаг, и с учетом этого выбрать управлениеобеспечивающее максимальное значение функции дохода Такое управление, выбранное при определенных предположениях о том, как окончился предыдущий шаг, называется условно оптимальным. Следовательно, принцип оптимальности требует находить на каждом шаге условно оптимальное управление для любого из возможных исходов предшествующего шага. Чтобы построить алгоритм решения задач, дадим математическую формулировку принципа оптимальности. Для этого введем некоторые дополнительные обозначения. Обозначив через максимальный доход, получаемый за п шагов при переходе системы S из начального состояния в конечное состояние при реализации оптимальной стратегии управления , а через-- максимальный доход, получаемый при переходе из любого состоянияв конечное состояние при оптимальной стратегии управления на оставшихся (n - k) шагах. Тогда

(3.3)

В можно считать известным. Используя теперь уравнение и рассматривая всевозможные допустимые состояния системы S на (n - 1)-м шаге находим условные оптимальные решения

(3.4)

и соответствующие значения функции:

(3.5)

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

Перейдем теперь к рассмотрению функционального уравнения при k = n - 2:

(3.6)

Решая функциональное уравнение при различных состояниях на (n - 2)-м шаге, получим условно оптимальные управления Каждое из этих управлений совместно с уже выбранным управлением на последнем шаге обеспечивает максимальное значение дохода на двух последних шагах. Последовательно осуществляя описанный выше итерационный процесс, дойдем до первого шага. На этом шаге известно, в каком состоянии может находиться система. Поэтому уже не требуется делать предположений о допустимых состояниях системы, а остается лишь только выбрать управление, которое является наилучшим с учетом условно оптимальных управлений, уже принятых на всех последующих шагах. Чтобы найти оптимальную стратегию управления, т. е. определить искомое решение задачи, нужно теперь пройти всю последовательность шагов, только на этот раз от начала к концу. На первом шаге в качестве оптимального управлениявозьмем найденное условно оптимальное управление. На втором шаге найдем состояниев которое переводит систему управление Это состояние определяет найденное условно оптимальное управлениекоторое теперь будем считать оптимальным. Зная находим значит, определяем и т. д. В результате этого находим решение задачи, т. е. максимально возможный доход и оптимальную стратегию управления, включающую оптимальные управления на отдельных шагах.

3. программа MathCAD в задачах динамического программирования

Широкую известность и заслуженную популярность еще в середине 80-х годов приобрели интегрированные системы для автоматизации математических расчетов класса MathCAD, разработанные фирмой MathSoft (США). По сей день они остаются единственными математическими системами, в которых описание решения математических задач дается с помощью привычных математических формул и знаков. Такой же вид имеют и результаты вычислений. Так что системы MathCAD вполне оправдывают аббревиатуру CAD (Computer Aided Design), говорящую о принадлежности к наиболее сложным и продвинутым системам автоматического проектирования -- САПР. С момента своего появления системы класса MathCAD имели удобный пользовательский интерфейс -- совокупность средств общения с пользователем в виде масштабируемых и перемещаемых окон, клавиш и иных элементов. У этой системы есть и эффективные средства типовой научной графики, они просты в применении и интуитивно понятны. Словом, системы MathCAD ориентированы на массового пользователя -- от ученика начальных классов до академика. MathCAD -- математически ориентированные универсальные системы. Помимо собственно вычислений они позволяют с блеском решать задачи, которые с трудом поддаются популярным текстовым редакторам или электронным таблицам. С их помощью можно не только качественно подготовить тексты статей, книг, диссертаций, научных отчетов, дипломных и курсовых проектов, они, кроме того, облегчают набор самых сложных математических формул и дают возможность представления результатов, в изысканном графическом виде.

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

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

Важно отметить, что даже при записи документов со сложными рисунками используется не запись их BitMap-копии, а именно программы вывода документа. Поэтому файлы с расширением mcd невелики по размеру и их легко передавать по современным средствам телекоммуникаций, например по Internet. Они требуют небольшого свободного пространства на дисках для записи. Помимо обычных операций работы с файлами (их запись на диск и загрузка с диска) предусмотрены возможности распечатки документов принтерами различного типа. Если сделать позицию File (Файл) главного меню активной, появится ниспадающее подменю (рисунок 1.1)

Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. Глава 15. Динамическое программирование // Алгоритмы: построение и анализ. -- 2-е изд. -- М.: «Вильямс», 2006.-1296 с.

Рисунок 1.1 Переднее панно системы MathCAD с активной позицией File главного меню.

Операция New [Ctrl+ N] (Создать) обычно используется, когда пользователь намерен создать новый документ. Она выводит на экран новое текущее окно редактирования и переводит систему в режим редактирования. Отличительной особенностью новой версии MathCAD является возможность выбора стиля нового документа. При исполнении операции New выводится окно выбора стиля документа, показанное на рисунке 1. 2.

Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. Глава 15. Динамическое программирование // Алгоритмы: построение и анализ. -- 2-е изд. -- М.: «Вильямс», 2006.-1296 с.

Рисунок 1. 2 Окно выбора стиля документа

При этом только стиль Normal (Нормальный) создает пустое окно редактирования Другие стили создают окно с заготовками (шаблонами) документов. Эти заготовки пользователь может использовать для своего документа. На рисунке 1. 3 показана часть документа со стилем Bookone. В шуточной форме показано заполнение ее в заданном стиле русскоязычными надписями Можно просмотреть и остальные стили и использовать их для своих целей Оформление документов в определенном стиле является одним из правил подготовки документов высокого полиграфического качества

 Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. Глава 15. Динамическое программирование // Алгоритмы: построение и анализ. -- 2-е изд. -- М.: «Вильямс», 2006.-1296 с.

Рисунок 1.3

Графики в системе MathCAD могут иметь различные размеры и перемещаться в окне редактирования документа. Для наиболее распространенных графиков в декартовой и в полярной системах координат в MathCAD предусмотрен упрощенный и очень удобный способ построе. Именно так построены графики на рисунке 1.4. Для упрощенного построения двумерных графиков некоторой функции f (x) надо вывести их шаблон, по вертикали указать эту функцию, а по горизонтали -- независимую переменную х. Таким образом можно строить на одном рисунке и графики многих функций, просто опишите их у вертикальной оси, используя запятые для разделения описаний функций. Графики будут построены линиями разного типа и цвета. ния графиков без предварительного задания функции и ранжирования независимой переменной.

 Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. Глава 15. Динамическое программирование // Алгоритмы: построение и анализ. -- 2-е изд. -- М.: «Вильямс», 2006.-1296 с.

Рисунок 1.4

Вввод данных в программе Mathcad напоминает работу в редакторе формул, программы Word, но тем не менее есть свои отличительные особенности, рассмотрим самый простой пример: допустим требуется произвести расчет следующего выражения , а именно найти значение "а" при известных значения "b" и "с" , знак := это локальный оператор присваивания, в система Mathcad таким знаком производится присваивание значений символам. Пусть нам заданы следующие значения ,

остается сложить "b" и "c" и получить значение "a", в программе Mathcad данный расчет производится так, записываем уравнение вычисления переменной "a", ниже записываем переменную "a" со знаком равенства =. Программа произведет автоматически расчет уравнения и выдаст результат вычислений. Выражение будет иметь следующий вид:

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

Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. Глава 15. Динамическое программирование // Алгоритмы: построение и анализ. -- 2-е изд. -- М.: «Вильямс», 2006.-1296 с.

Рисунок 2 - Панель инструментов

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

Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. Глава 15. Динамическое программирование // Алгоритмы: построение и анализ. -- 2-е изд. -- М.: «Вильямс», 2006.-1296 с.

Рисунок 3- Внешний вид закладки КАЛЬКУЛЯТОР

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

 Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. Глава 15. Динамическое программирование // Алгоритмы: построение и анализ. -- 2-е изд. -- М.: «Вильямс», 2006.-1296 с.

Рисунок 4 - Закладка ГРАФИКИ

Закладка ГРАФИКИ предназначена для вставки в документы различных графиков и диаграмм. Используя данные инструменты, можно составить и решить не сложные уравнения.

Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. Глава 15. Динамическое программирование // Алгоритмы: построение и анализ. -- 2-е изд. -- М.: «Вильямс», 2006.-1296 с.

Рисунок 5-График

И так график получен, но назвать его удобочитаемым нельзя, поэтому кликаем правой кнопкой мыши по графику и в контекстном меню выбираем "Формат", рисунок 6.

Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. Глава 15. Динамическое программирование // Алгоритмы: построение и анализ. -- 2-е изд. -- М.: «Вильямс», 2006.-1296 с.

Рисунок 6

Ниже, на рисунке 7, показано меню форматирования графика, как видно из рисунка меню имеет четыре закладки. Закладка "Оси X-Y" позволяет включать/отключать сетку отдельно для каждой оси, задавать количество ячеек сетки и др. Закладка "Следы" содержит настройки линий графика, т.е. позволяет задать вид линии сплошная, пунктирная, штрихпунктирная и вид точек на графики. Переключившись на закладку "Метки" можно подписать оси и вести название графика. И на конец закладка "Умолчания", установив галочку "Использовать как умолчания" (в моей версии перевода программы выглядит именно так) мы сохраняем данные настройки как настройки по умолчанию, т.е. эти настройки будут применены ко всем следующим графикам автоматически.

Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. Глава 15. Динамическое программирование // Алгоритмы: построение и анализ. -- 2-е изд. -- М.: «Вильямс», 2006.-1296 с.

Рисунок 7

Установив все требуемые настройки получим график (Приложение А).

Если нужно разместить два графика на одних осях, то вторую функцию записывают ниже, для этого требуется нажать клавишу с русской "б" (Приложение Б). Если требуется подробнее рассмотреть какой либо участок на графики, то можно воспользоваться функцией масштабирования, вызывается с панели "Графики" рисунок 2. Выделив нужный регион нажимаем ОК. Не менее полезная функция "След", она позволяет точно определить значение функции в любой точки графика, функция "След" вызывается все с той же панели "Графики" рисунок 2. Для примера приведены графики ЧХЗ полосового фильтра (Приложение В,Г).

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

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

ЗАКЛЮЧЕНИЕ

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

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

В третьей части курсовой работы мной была подробна рассмотрена программа MathCAD, предназначающаяся для решения задач динамического программирования. Mathcad универсальная программа позволяющая производить математические расчеты любой сложности, данная программа применима для расчетов в любой области. Отличительной особенностью данной программы является высокая визуализация процесса ввода данных в программу. Решение уравнений и различных задач в программе Mathcad не составляет большого труда даже для неопытного пользователя. Уровень визуализации процессов на столько высок, что процесс работы в Mathcad очень схож с работой стандартного редактора формул в программе Word.

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

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

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

СПИСОК ЛИТЕРАТУРЫ

1. Заварыкин В.М., Житомирский В.Г., Лапчик М.П. Численные методы. - М.: Просвещение, 1991 г.-176 с.

2.Информатика. Учебник. /Под ред. И.В.Макаровой. - 3-е изд.перераб. М.:Финансы и статистика, 2005-768 с.

3. Конюховский П.В. Математические методы исследования операций: пособие для подготовки к экзамену. - Спб.:Питер, 2001-192 с.

4. Давыдов, Э.Г. Исследование операций : учеб. пособие для студ. вузов / Э.Г. Давыдов. - М. : Высш. школа, 1990. - 383 с.

5. Курицкий Б.К. Поиск оптимальных решений средствами Excel 7.0. - Спб.: BHV, 1997.-384 с.

6. Шикин Е.В. Чхартишвили А.Г. Математические методы и модели в управлении: Учебник для ВУЗов. - М.: Дело, 2000.-440 с.

7. Беллман Р., Дрейфус С. Прикладные задачи динамического программирования. - М.:Наука,1965.-458 с.

8. Вилкас Э.И. Оптимальность в играх и решениях. - М.: Наука,1990.-256 с.

9.Интрилигатор М. Математические методы оптимизации и экономическая теория. - М.: Прогресс, 1975.-576 с.

10. Петросян Л.А., Зенкевич Н.А., Семина Е.А. Теория игр: Учебное пособие для университетов. - М.: Высшая школа, Книжный дом “Университет”, 1998.-300 с.

11. Методологические аспекты динамического программирования // Динамические системы, 2007, вып. 22.-368 с.

12. Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. Глава 15. Динамическое программирование // Алгоритмы: построение и анализ. -- 2-е изд. -- М.: «Вильямс», 2006.-1296 с.

13. Щербина О.А. О несериальной модификации локального алгоритма декомпозиции задач дискретной оптимизации // Динамические системы, 2005, вып. 19-179 с.

14. Мищенко А.В., Попов А.А. Некоторые подходы к оптимизации инвестиционного портфеля , "Менеджмент в России и за рубежом", №2 / 2002.-144 с.

15. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. -- М.: МЦНМО, 2000.-960 с.