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

Содержание

Введение ……………………………………………………………………… 3

1.Оптимальное распределение ресурсов ………………………………………………………………………. 4

2.Динамическое программирование.......................................................................................... 4

3.Принцип оптимальности Беллмана ……………………………………………………………………... 5

4. Задача распределения инвестиций на компьютере …………………………………………………………………... 9

Приложение ………………………………………………………………… 12

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

Введение

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

Общая запись задач оптимизации задаёт большое разнообразие их классов. От класса задачи зависит подбор метода (эффективность её решения). Классификацию задач определяют: целевая функция и допустимая область (задаётся системой неравенств и равенств или более сложным алгоритмом).^[2]

Методы оптимизации классифицируют в соответствии с задачами оптимизации:

·​ Локальные методы: сходятся к какому-нибудь локальному экстремуму целевой функции. В случае унимодальной целевой функции, этот экстремум единственен, и будет глобальным максимумом/минимумом.

·​ Глобальные методы: имеют дело с многоэкстремальными целевыми функциями. При глобальном поиске основной задачей является выявление тенденций глобального поведения целевой функции.

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

1.​ детерминированные;

2.​ случайные (стохастические);

3.​ комбинированные.

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

Оптимальное распределение ресурсов

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

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

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

Динамическое программирование - это вычислительный метод для решения задач определенной структуры. Динамическое программирование возникло и сформировалось в 1950–1953 гг. благодаря работам Ричарда Беллмана и его сотрудников. Беллман (Bellman) Ричард Эрнест (1920-84) – американский математик. Основные труды по вычислительной математике и теории оптимального управления. Разработал метод динамического программирования. Задачи управления запасами были первыми задачами, которые решались этим методом. В этой работе рассматривается несколько достаточно простых задач, которые решаются на основе идей динамического программирования. В том числе и решена классическая задача управления запасами. Для каждой из рассмотренных задача составлена программа на языке SciLab, которая может решить не только маленькую учебную задачу, но и претендует на решение реальных задач, с тысячами переменных. Чтобы убедиться, что программа правильно решает задачи методом динамического программирования, написаны также программы полного перебора — для проверки основного алгоритма, и для более ясного понимания каждой из рассмотренных экономических задач. Пакет SciLab – бесплатный французский пакет. Взять его можно на сайте www.scilab.org. Является одним из аналогов широко известного па- кета MatLab. Язык пакета SciLab несколько отличается от MatLab, но чаще всего в лучшую сторону, так как этот язык создан позднее. Другим известным аналогом MatLab является бесплатный пакет Octave, который широка используется в американских университетах. Программы MatLab идут без каких-либо изменений в системе Octave, но есть проблемы с русским языком, непросто установить в Windows и медленно работает. Очередным преимуществом пакета SciLab является постоянное обновление. Последнее обновление было в марте 2011 года — выпущена версия 5.3.1. Все программы набраны не в CP −1251, как делается обычно в Windows разных версий, а в кодовой таблице UT F − 8. Эта кодировка становится всё более популярной, так как позволяет использовать сразу несколько языков. Наряду с русским и английским языками можно использовать любые другие языки, например, китайские иероглифы, причём в одной программе.