Модели динамического программирования распределение инвестиций по проектам реферат

Обновлено: 05.07.2024

Для учеников 1-11 классов и дошкольников
Бесплатные сертификаты учителям и участникам

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

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

1.4. Перекрывающиеся подзадачи . 6

1.5. Нисходящая динамика . 6

1.6. Восходящая динамика . 6

2. Практическая часть . 7

2.1 Вывод рекуррентных формул . 8

2.2 Задачи на поиск оптимального решения. Часть 1 . 10

2.3 Задачи на вычисление количества решений . 11

2.4 Задачи на поиск оптимального решения. Часть 2 . 13

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

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

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

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

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

В ходе выполнения работы были поставлены следующие задачи:

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

2. Изучить класс задач, связанных с использованием этого метода

3. Научиться применять этот метод к олимпиадным задачам

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

Предметом - олимпиадные задачи, использующие этот метод.

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

Методы, которые помогали в решении поставленной задачи:

3. Эксперимент
ГЛАВА 1

Теоретическая часть

Динамическое программирование - метод решения задач путем составления последовательности из подзадач таким образом, что:

· первый элемент последовательности (возможно несколько элементов) имеет тривиальное решение

· последний элемент этой последовательности - это исходная задача

каждая задача этой последовательности может быть решена с использованием решения подзадач с меньшими номерами

Другими словами, для решения задачи T методом ДП составляется некоторая последовательность подзадач T₁, T₂, . T_n такая, что решение задачи T₁ уже имеет решение, T = T_n, и самое главное, что зная решения задач T₁, T₂, . T_i-1 можно вывести решение задачи T_i для любого i = 2..n .

Идея динамического программирования:

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

1. Разбиение задачи на подзадачи меньшего размера.

2. Построение таблицы решений.

3. Решение задачи с помощью построенной таблицы.

Подзадача - та же задача, но

· с меньшим числом параметров

· либо с меньшим значением одного из параметров

Подзадачи решаются делением их на подзадачи ещё меньшего размера и т. д., пока не приходят к тривиальному случаю задачи, решаемой за константное время (ответ можно сказать сразу). К примеру, если нам нужно найти n !, то тривиальной задачей будет 1! = 1 (или 0! = 1).

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

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

Динамическое программирование обычно придерживается двух подходов к решению задач:

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

Практическая часть

Задача: Найти количество К _N цепочек, состоящих из N нулей и единиц, в которых нет двух стоящих подряд нулей.

Для решения данной задачи методом динамического программирования самое главное вывести рекуррентную формулу, выражающую К _N _, через решение аналогичных задач меньшей размерности. Рассмотрим цепочку из N бит, первый член которой 1. Поскольку дополнительная 1 не может привести к существованию двух нулей подряд, то подходящих последовательностей длиной N с

Теперь давайте рассмотрим простые случаи. Очевидно, что есть две подходящие последовательности длиной 1(0 и 1), то есть К₁ = 2. Также существует 3 подходящих последовательности длиной 2(11, 01 и 10), следовательно К₂ = 3.

В результате получаем рекуррентную формулу:

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

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

В таблице сразмерами k * n , с элементами 1 и 0, найти квадратный блок максимально возможного размера, состоящий из одних единиц. При n = 5, k =6 искомый блок выделен цветом.

Положение любого квадратного блока определяется его размером и нижней правой вершиной. В данном случае максимальный размер блока равен 3, координаты правой нижней вершины квадрата равны b = 4, c = 5.

Пусть F [ i ][ j ] – функция значение которой равно размеру максимального квадратного блока правый нижний угол которого расположен в ячейке ( i , j ). Значение её в 1 строке и в 1 столбце совпадают с элементами m [1][ j ] и m [ i ][1] .

F [1][ j ] = m [1][ j ], F [ i ][1] = m [ i ][1]. Допустим, мы находимся в ячейке ( i , j ) и все предыдущие ячейки таблицы уже заполнены. Тогда значение F [ i ][ j ] будет равно 0, только если m [ i ][ j ] = 0(ведь квадрат размером 1 мы точно можем составить, несмотря на предыдущие результаты, если m [ i ][ j ] != 0).

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

1. F[i][j] = 0, если m[i][j] = 0

2. F[i][j] = min(F[i-1][j], F[i][j-1], F[i-1][j-1]) + 1 , при m[i][j] = 1.

Для приведенного примера справа составлена таблица значений

Для вывода ответа найдем максимальный элемент в таблице.

Программа для языка С++ приведена в приложении 2.

Пример 3 Задача о садовнике

Садовник посадил N деревьев в один ряд. После посадки деревьев садовнику нужно их покрасить. В его распоряжении есть краска трех цветов: белая, синяя и оранжевая. Сколько способов покраски деревьев есть у него, если никакие два соседних дерева нельзя красить в одинаковый цвет?

Решение задачи приведено в приложении 7.

На прямой дощечке вбиты n гвоздиков. Для каждого гвоздя известна его координата на прямой OX , m [ i ]. Любые 2 гвоздя можно соединить ниточкой. Надо соединить некоторые пары гвоздиков так, что к каждому гвоздику привязана хотя бы 1 ниточка, а сумма длин всех нитей была минимальной.

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

Как обычно, начнем с рассмотрения простых случаев. Если гвоздь 1, то длина нити равна L [0] = 0. Если гвоздей 2, то длина нити равна ( L [1] = m [1] – m [0]). Если гвоздей 3, то длина нити равна ( L [2] = m [2] – m [0]). Если гвоздей 4, то необходимо соединить первые два и последние два ( L [3] = L [1] + m [3] – m [0]). Когда у нас пять гвоздей, то мы обязательно связываем ниткой первые два и последние два, а для 3-его гвоздика выбираем минимальную длину ниток, то есть длина нитки равна L [4] = min ( L [2] + m [4] – m [3]; L [3] + m [4] – m [2]).

В результате получаем рекуррентную формулу:

L[n] = min (L[n-2] + m[n] – m[n-1]; L[n-3] + m[n] – m[n-2])

Реализация программы на языке С++ приведена в приложении 5.

Цистерна объёмом N литров доверху заполнена молоком. У молочника в наличии бидоны объёмом 1, 5 и 6 литров. Он хочет разлить все молоко по бидонам, так чтобы все бидоны оказались доверху заполненными, но сам он не хочет нести большое количество бидонов. Помогите ему узнать какие бидоны нужно использовать, чтобы их количество оказалось минимальным.

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

Представим, что мы выбираем бидоны постепенно. Тогда последний выбранный бидон может иметь объём, например, 1 литр, в этом случае K_N = 1 + K_n _-1 . Если последний бидон имеет объём 5 литров, то K_n =1+ K_n _-5 . Если 6 литров – K_N = 1 + K_N _-6.

Так как нам нужно минимизировать кол-во бидонов, то K_N = 1 + min ( K_N _-1 , K_N _-5 , K_N _-6 ) . Вариант, выбранный при поиске минимума, определяет последний добавленный бидон, то результат этого выбора будем хранить в некотором массиве М. Этот массив будет использован для определения количества выбранных бидонов каждого типа. В качестве начальных значений возьмем К₀ = 0 и M ₀ = 0.

Полученная формула применима для N >= 6. Для меньших N используются только те данные, которые уже есть в таблице. Например

Общая постановка задачи: совет директоров фирмы изучает предложение по наращиванию мощностей 3-x принадлежащих ей предприятий. Для расширения всех трех предприятий фирма выделяет 5 млн $. Каждое предприятие представляет на рассмотрение проекты, которые характеризуются величинами в млн. $ суммарных затрат © и доходов ®, связанных с реализацией каждого проекта. Исходя из решения, можно сделать… Читать ещё >

распределение инвестиций методом динамического программирования

Распределение инвестиций методом динамического программирования ( реферат , курсовая , диплом , контрольная )

Сетевая модель

Общая постановка задачи: совет директоров фирмы изучает предложение по наращиванию мощностей 3-x принадлежащих ей предприятий. Для расширения всех трех предприятий фирма выделяет 5 млн $. Каждое предприятие представляет на рассмотрение проекты, которые характеризуются величинами в млн. $ суммарных затрат (C) и доходов (R), связанных с реализацией каждого проекта.

Цель фирмы является получение max дохода от инвестиций.

Метод прямой прогонки

Решение ЗДП при помощи принципа оптимальности Беллмана

динамический программирование инвестиция моделирование управление

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

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

Если выполняются оба принципа, то работает принцип оптимальности Беллмана:

n Принцип отсутствия последействия

Каждый следующий шаг зависит только от предыдущего.

n Принцип аддитивности целевой функции

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

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

2. Практическая часть

Решение задачи методом обратной прогонки.

В основе метода лежит принцип оптимальности Беллмана:

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

2.1 Постановка задачи

Иностранный капитал в экономике Москвы составил 9 млрд долл. Правительство планирует инвестировать их в «Оптовую и розничную торговлю"(1), «Обрабатывающее производство"(2), «Транспорт и связь"(3), «Операции с недвижимым имуществом"(4), «Финансовую деятельность"(5). Каждая отрасль представляет на рассмотрение проекты, кот. Характеризуются величинами (в млрд. долл.) суммарных затрат © и доходов ®, связанных с реализацией каждого из проектов. Соответствующие данные приведены в таблице, в которую включены также проекты с нулевыми затратами. Это позволяет учесть возможность отказа от расширения какого-либо предприятия. Цель фирмы — получение максимального дохода от инвестиций в объеме 9 млрд долл. Найти оптимальный способ инвестирования ("https://referat.bookap.info", 17).

Для составления математической модели исходим из предположений:

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

Функция "чтения" служит для ознакомления с работой. Разметка, таблицы и картинки документа могут отображаться неверно или не в полном объёме!

1 Теоретическая часть. Модели динамического программирования4

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

1.2 Постановка задачи динамического программирования6

1.3 Принципоптимальностииматематическоеописаниединамического процесса управления8

1.4 Оптимальное распределение инвестиций10

1.5 Выбор оптимальной стратегии обновления оборудования13

2 Расчетная часть16

Список использованных источников31

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

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

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

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

1.1 ПРЕДМЕТ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ Динамическое программирование представляет собой математический аппарат, который подходит к решению некоторого класса задач путем их разложения на части, небольшие и менее сложные задачи. При этом отличительной особенностью является решение задач по этапам, через фиксированные интервалы, промежутки времени, что и определило появление термина динамическое программирование. Следует заметить, что методы динамического программирования успешно применяются и при решении задач, в которых фактор времени не учитывается. В целом математический аппарат можно представить как пошаговое или поэтапное программирование. Решение задач методами динамического программирования проводится на основе сформулированного Р. Э. Беллманом принципа оптимальности: оптимальное поведение обладает тем свойством, что каким бы ни было первоначальное состояние системы и первоначальное решение, последующее решение должно определять оптимальное поведение относительно состояния, полученного в результате первоначального решения.

ОПТИМАЛЬНОЕ РАСПРЕДЕЛЕНИЕ ИНВЕСТИЦИЙ МЕТОДАМИ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ

Текст работы размещён без изображений и формул.
Полная версия работы доступна во вкладке "Файлы работы" в формате PDF

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

Шаг 1. k = 4. Предполагается, что все средства направляются на инвестирование одного предприятия (например, четвертого). Объем инвестиций для предприятия 4: . Запишем уравнение Беллмана для этого шага:

В соответствии с формулой (1) в зависимости от начальной суммы С получаем значения Z ₄ и х₄ * :

при С₄=100:

при С₄=120:

Шаг 2. k = 3. Предполагается, что все средства направляются на инвестирование двух предприятий (например, третьего и четвертого). Объем инвестиций для двух предприятий может составить: ; при этом третьему предприятию из этой суммы можно выделить любое количество . Запишем уравнение Беллмана для шага 2:

В соответствии с формулой (1.2):

Результаты расчетов на шаге 2 представлены в табл. 2.

Шаг 3. k =2. Инвестиции распределяем между тремя предприятиями (например, между вторым, третьим и четвертым). Объем инвестиций для трех предприятий может составить: ; при этом второму предприятию из этой суммы можно выделить любое количество . Запишем уравнение Беллмана для шага 3:

Найдем значения функции (1.3) для всех допустимых комбинаций С₂ и х₂:

Результаты расчетов на шаге 3 представлены в табл. 3.

Шаг 4. k =1. Инвестиции распределяем между всеми предприятиями. Между ними нужно распределить все имеющиеся денежные средства, поэтому С₁=120, при этом первому предприятию из этой суммы можно выделить любое количество: .

Уравнение Беллмана для шага 4 запишется следующим образом:

Найдем значения функции (4) для С₁ = 120:

Результаты расчетов на шаге 4 (для всех возможных значений С₁) представлены в табл. 4.

Шаг 1. По данным табл. 4 максимальная прибыль при распределении 120 млн. руб. между четырьмя предприятиями составит Z ₁=64 млн. руб., при этом первому предприятию нужно выделить млн. руб.

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

По данным табл. 3 находим, что при С₂ = 120: Z ₂ = 64, х₂* = 40. Это означает, что второму предприятию следует выделить 40 млн. руб.

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

По данным табл. 2 находим, что при С₃ = 80: Z ₃ = 44, х₃* = 40. Это означает, что третьему предприятию следует выделить 40 млн. руб. При этом максимальная прибыль второго предприятия составит:

Шаг 4. Определим величину оставшихся денежных средств, приходящихся на долю четвертого предприятия:

По данным табл. 1 находим, что при С₄ = 40: Z ₄ = 23, х₄* = 40.

Максимальная прибыль третьего предприятия составит:

а четвертого предприятия соответственно:

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

Таким образом, максимальная прибыль на четырех предприятиях при распределении между ними 120 млн. руб. составит 64 млн. руб. и будет получена, если первому предприятию средств не выделять, а второму, третьему и четвертому выделить по 40 млн. руб.

Вентцель, Е.С. Исследование операций: задачи, принципы, методология: учебное пособие / Е.С. Вентцель. – 5-е изд., стер. – М.: КНОРУС, 2010. – 192 с.

Давыдов, Е.Г. Элементы исследования операций: учебное пособие / Давыдов Е.Г. – М.: КНОРУС, 2010. – 160 с.

Костевич, Л.С. Математическое программирование: Информационные технологии оптимальных решений: учебное пособие / Л.С. Костевич. – М.: Новое знание, 2003. – 424 с.

Читайте также: