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

Содержание:

ВВЕДЕНИЕ 3

Глава 1. Теоретическая часть 5

1.1 Динамическое программирование 5

1.2. Основные принципы динамического программирования 6

1.3. Преимущества и недостатки динамического программирования 11

1.4. Области применения 13

1.5. Применение динамического программирования в землеустройстве 14

ЗАКЛЮЧЕНИЕ 21

СПИСОК ИСПОЛЬЗУЕМОЙ ЛИТЕРАТУРЫ 22

Введение:

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

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

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

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

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

Объект исследования: программирование.

Предмет исследования: применение динамического программирования в землеустройство.

Цель исследования: изучить методы динамического программирования и применение в землеустройстве.

На основании цели и предмета исследования определены следующие цели исследования:

— изучить понятие динамического программирования;

— выявить преимущества и недостатки динамического программирования;

— описать применение динамического программирования в землеустройстве.

Структура исследования состоит из введения, одной главы, заключения, списка литературы.

Заключение:

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

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

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

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

Фрагмент текста работы:

Глава 1. Теоретическая часть

1.1 Динамическое программирование

Работу разработчика часто можно сравнить с решением головоломок. Как в настоящей головоломке, разработчику приходится тратить существенные ресурсы не столько на реализацию конкретного решения, сколько на выбор оптимального подхода. Иногда задача решается легко и эффективно, а порой – только полным перебором всех возможных вариантов. Такой подход часто называют наивным решением. Он имеет существенный минус – временные затраты [4].

Представим хакера, который пытается взломать какой-то пароль перебором всех комбинаций символов. Если пароль допускает 10 цифр, 26 маленьких букв, 26 больших букв и 32 специальных символа (например, значок доллара), то для каждого символа в пароле есть 94 кандидата. Значит, чтобы взломать перебором пароль, состоящий из одного символа, потребуется 94 проверки.

Если в пароле два символа – 94 кандидата на первую позицию, 94 кандидата на вторую позицию – то придется перебрать аж 94*94 = 8836 возможных пар. Для пароля из десяти символов потребуется уже перебор 94^10 комбинаций.

Если обобщить, то для взлома пароля с произвольной длиной N требуется O(94^N) операций. Такие затраты часто называют «экспоненциальными»: появление каждой новой позиции влечёт за собой увеличение количества операций в 94 раза.

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

Экспоненциальное время – это долго. Даже O(2^N) – это просто непозволительно долго. Настолько долго, что никому и в голову не придет запустить подобный алгоритм даже на простых данных – ведь на решение такой задачи с сотней элементов потребуются тысячи, миллионы или миллиарды лет вычислений. А в реальной жизни нужно решать задачи с намного большим количеством элементов. Как же быть?

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

1.2. Основные принципы динамического программирования

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

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

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

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

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

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

Вклад Беллмана в динамическое программирование был увековечен в названии уравнения Беллмана, центрального результата теории динамического программирования, который переформулирует оптимизационную задачу в рекурсивной форме. В конце 1950 года Ричард Беллман работал в RAND Corp.

Он занимался многоступенчатыми процессами принятия решений (multistage decision processes). Но эти годы не были подходящими для математических исследований. RAND Corp основали ВВС и начальство терпеть не могло слова: математика, исследования и др.

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

Другими словами название динамическое программирование на самом деле ничего не означает.

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

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

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