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

 

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

 

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

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

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

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

 

¹

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

 

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

 

²

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

 

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

 

³

Рисунок 1.3

 

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

 

⁴

Рисунок 1.4

 

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

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

 

 

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

 

⁵

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

 

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

⁶

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

 

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

 

⁷

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

 

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

 

⁸

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

 

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

 

⁹

Рисунок 6

 

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

 

¹⁰

Рисунок 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 с.

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