Метод оптимального распределения денежных средств методом динамического программирования

Размещено на http://www.allbest.ru

СОДЕРЖАНИЕ

Введение

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

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

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

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

2. Оптимальное распределение денежных средств

3. Оптимальное распределение денежных средств с использованием ПК

Заключение

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



Введение

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

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

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

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

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

3) Использование полученного решения подзадач для конструирования решения исходной задачи.

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

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

Задачи:

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

Охарактеризовать общую структуру динамического программирования.

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

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

Теоретико-методологической основой при написании данной курсовой работы послужили труды отечественных и зарубежных авторов, как учебник Окулова С.М. «Динамическое программирование». В данной книге систематизирован материал по одному из методов проектирования алгоритмов в информатике - динамическому программированию. В работе Визгунова Н.П. «Динамическое программирование в экономических задачах c применением системы SciLab» на примерах показано, как решать экономические задачи, которые сводятся к задачам динамического программирования. Задачи решаются не только вручную, но и предлагаются соответствующие программы в системе SciLab.

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



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

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

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

1940 году Ричардом Беллманом был впервые разработан метод, который является важнейшей основой для решения сложных современных задач. «Метод Беллмана» или «Метод динамического программирования» - широко известный математический метод для решения сложных задач путем разбиения их на более простые пересекающиеся подзадачи [15, c.18].

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

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

Чтобы доказать, что улучшаем наше решение, нужна статистика, которую можно сравнить. Для этого необходимо использовать бенчмарк Google, чтобы помочь профилировать решения [14, c.132].

Тест будет выглядеть так:

Имя эталона: название эталона.

Время выполнения: время, необходимое нашей функции для возврата результата.

Итераций/сек: количество раз, которое функция могла быть вызвана за 1 секунду.

Предметов/сек: количество предметов, обработанных за 1 секунду.

Классическим примером для объяснения динамического программирования является вычисление Фибоначчи, которое можно формализовать следующим образом (рис 1.1).

Рис.1.1 Пример вычисление Фибоначчи.

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

Рис. 1.2 Наивный рекурсивный подход

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

Таблица 1.1

Результаты тестов приведенного выше кода

Название эталона	Продолжительность	Итерации / сек	Продукты / сек
FibonacciRecursive / 10	0 мс	2488889	17.0685M
FibonacciRecursive / 20	0 мс	21333	303.026k
FibonacciRecursive / 30	8 мс	179	3.60887k
FibonacciRecursive / 40	997 мс	1	40
FibonacciRecursive / 50	124510 мс	1	0,40282

Хотя этот метод возвращает почти мгновенно при n <= 30, он занимает чуть меньше aВ секунды при n = 40 и примерно 2 минуты для n = 50. Рассмотрим это для n = 6, чтобы было проще (рис 1.3).

Рис. 3. Серия Фибоначчи.

Глядя на изображение, можно увидеть, что для вычисления Фибоначчи (6) вычисляется Фибоначчи (5) 1 В, Фибоначчи (4) 2 В раза, Фибоначчи (3) 3 В раза, Фибоначчи (2) 5 раз, Фибоначчи (1) 8 раз и Фибоначчи (0) 5 раз. На протяжении всего стека вызовов постоянно вычисляются значения, которые уже вычислились. Этот объем дублирующейся работы продолжает увеличиваться по мере того, как n становится больше [12, c.29].

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

Рис. 1.4. Нисходящий рекурсивный подход с Memoization



Метод topВ является основным методом. Все, что он делает, это добавляет 2 базовых случая на карту, а затем вызывает метод bottom с картой в качестве одного из аргументов. Этот нижний метод является рекурсивным методом. В этом методе проверяется, содержит ли карта вычисленное значение. Если это does.В то просто вернуть это значение, в противном случае, вычисляется значение для п-1 Anda п-2 . Далее модифицируется результат, используя 1000000007, чтобы избежать переполнения. Перед тем, как вернуть их сумму, сохраняем значение на карте.

Таблица 1.2

Результаты тестов приведенного выше кода.

Название эталона	Продолжительность	Итерации / сек	Продукты / сек
FibonacciMemonized / 1000	0 мс	4073	3.60284M
FibonacciMemonized / 5000	2 мс	+896	2.90891M
FibonacciMemonized / 10000	3 мс	407	2.82288M
FibonacciMemonized / 15000	5 мс	242	2.66937M
FibonacciMemonized / 20000	7 мс	187	2.65432M

Отметим, что резко сократилось количество времени. Даже при n = 20000 результат мгновенный. Однако при таком подходе есть проблема. И проблема состоит в том, что каждый рекурсивный вызов занимает некоторое место в стеке. Достаточно высокое n, появляется риск исчерпания памяти. Рассмотрим, почему это происходит на примере, где n = 100. Поскольку нет результата при запуске, вызываем метод рекурсивно для 999, 998, 997 ... 1. В этот момент есть все вычисленные результаты в таблице. Рассмотрим, можно ли избавиться от этого с помощью итеративного подхода. Вместо того, чтобы начинать с окончательного значения, начнем с наименьшего значения n и построим результаты (рис. 1.5).

Рис. 1.5. Подход снизу вверх с динамическим программированием.

В приведенной выше функции есть массив n + 1 для хранения результатов. Инициализируем массив для базовых случаев n = 0 и n = 1 **, а затем начинаем итерацию с ** 2 до n. На каждом шаге можно использовать 2 ранее вычисленных значения и, наконец, вернуть результат.

Таблица 1.3

Результаты тестов приведенного выше кода

Название эталона	Продолжительность	Итерации / сек	Продукты / сек
FibonacciDP / 100000	1 мс	1906	130.711M
FibonacciDP / 600000	5 мс	280	111.456M
FibonacciDP / 1100000	10 мс	145	110.626M
FibonacciDP / 1600000	14 мс	100	112.249M
FibonacciDP / 2100000	18 мс	81	110.448M

Даже когда n = 210 000, этот подход возвращается почти мгновенно. В то же время, поскольку этот алгоритм не является рекурсивным по своей природе, резко сократился объем требуемого пространства. Можно убедиться в этом, сравнив элементы/сек, которые уменьшаются гораздо медленнее, хотя n увеличивается быстрее, чем раньше.

В последнем алгоритме количество требуемого пространства пропорционально n. Избавившись от массива, используя всего 3 переменные ? 2 для сохранения предыдущих результатов и 1 для сохранения текущего результата (рис. 1.6).

Рис. 1.6. Подход снизу вверх с динамическим программированием (оптимизированный)

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



Таблица 1.4

Результаты тестов приведенного выше кода

Название эталона	Продолжительность	Итерации / сек	Продукты / сек
FibonacciDPOptimized / 100000	0 мс	2987	202.569M
FibonacciDPOptimized / 600000	3 мс	498	207.242M
FibonacciDPOptimized / 1100000	5 мс	280	202.138M
FibonacciDPOptimized / 1600000	7 мс	187	205.188M
FibonacciDPOptimized / 2100000	10 мс	128	205.0708M

Здесь можно увидеть, что, хотя ** n ** увеличивается, количество элементов в секунду более или менее одинаково. Это лучшее, что можно сделать, и дальнейшая оптимизация невозможна.

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

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

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

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

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

Математические модели при описании экономических процессов должны отражать реальные ситуации. Как правило, переменные этих процессов связаны между собой нелинейными законами. К задачам нелинейного распределения и планирования, решение которых можно рассматривать как многошаговый процесс, применим метод динамического программирования. Главная идея, лежащая в основе динамического программирования, известна как принцип оптимальности, сформулированный Р. Беллманом. Основная его суть заключается в следующем: оптимальная политика обладает тем свойством, что каковы бы ни были начальное состояние и начальное решение, последующие решения должны соответствовать оптимальной политике по отношению к состоянию, вытекающему из первого решения [10, c.54].

Рис. 1.7. Геометрическое представление принципа оптимальности

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

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

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

Решение задач динамического программирования основано на составлении и анализе рекуррентных соотношений, уравнений Беллмана. Для большинства задач, рассматриваемых в курсе математики на экономических направлениях подготовки уравнения Беллмана имеют громоздкий вид. Их трудно привести к виду удобному для анализа и нахождения оптимального значения. В связи с чем работа с задачами динамического программирования вызывает трудности у студентов [7, c.21].

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

Рассмотрим предложенную схему работы с задачей динамического программирования на конкретном примере. В качестве примера выберем задачу нахождения оптимального маршрута: между пунктами 1 и 14 необходимо построить автомобильную дорогу. Трасса может пройти через некоторые населенные пункты. Стоимость всех участков данной трассы между конкретными населенными пунктами представлена в таблице 1.5. Требуется определить, как можно построить автодорогу так, чтобы расходы на ее строительство оказались минимальными.

Таблица 1.5

Стоимость всех участков данной трассы между конкретными населенными пунктами

Ветки
1-2	1-3	2-4	2-5	2-6	3-4	3-5	3-6	3-7	4-8	4-9	5-8	5-9
5	6	6	14	16	18	18	5	2	12	6	10	16
Ветки
5-10	6-8	6-9	6-10	7-9	7-10	8-11	8-12	8-13	9-11	9-12
17	7	13	4	15	12	15	13	11	7	10
Ветки
9-12	9-13	10-11	10-12	10-13	11-14	12-14	13-14	А
10	4	10	6	1	5	12	14	10

Решение: Формулировка условия задачи предполагает графическое представление предложенной автомобильной дороги.

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

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

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

При пошаговом решении задачи постепенно отбрасываются заведомо невыгодные варианты [6, c.92].

Решение задачи следует начинать с того пункта, про который что-либо известно из условий. В данной задаче необходимо так провести решение, чтобы в последнем пункте 14 не осталось средств для дальнейшего продвижения, но и отрицательного значения в этом пункте быть не должно. А значит, в 14 пункте должно оказаться только значение 0 ден.ед.

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

Для того чтобы построить участок пути от 13 до 14 пункта потребуется, чтобы в пункте 13 имелось 14 ден.ед. Для построения участка от 12 до 14 необходимо в 12 пункте иметь 12 ден.ед., а в 11 пункте 5 ден.ед. Для этих пунктов решение может быть проведено однозначно, а, следовательно, находясь в любом из пунктов 11, 12, 13 продвижение возможно в пункт 14 только по одной ветке. Те значения стоимости, которые должны оказаться в пунктах 11, 12, 13 к предпоследнему шагу отразим на сети (рис.1.9).

Рис. 1.9. Предпоследний шаг при решении задачи

Рассмотрим возможность продвижения из пункта 10. До конечного пункта 14 из пункта 10 можно добраться через пункты 11, 12 и 13. При этом, двигаясь маршрутом 1013-14 в пункте 10 необходимо иметь 1+14=15 ден.ед., по маршруту 10-12-14 в пункте 10 должно быть 6+12=18 ден.ед., а для маршрута 10-11-14 нужно в пункте 10 иметь 10+5=15 ден.ед. Так как поставлена задача найти маршрут минимальной стоимости, то оптимальное значение в пункте 10 соответствует минимальному среди найденных стоимостей, т.е. min{1+14, 6+12, 10+5}=15. Ветки, соответствующие минимальным значениям выделяем стрелками (рис.1.10).

На этом же шаге рассматриваем стоимость пути из пунктов 9 и 8 до пункта 14, так как переход к 14 пункту из 8 и 9 осуществляется также, как и из 10 пункта через пункты 11, 12 и 13, информация о которых уже получена (рис.1.10).

Для пункта 9 приходится выбирать минимальную среди сумм 4+14, что соответствует переходу через 13 пункт, 10+12 - переход через пункт 12 и 7+5 переход через 11 пункт. В результате из 9 пункта целесообразнее всего двигаться в пункт 11, а количество средств, которые необходимо иметь в 9 пункте составляет 12 ден.ед.

Для пункта 8 минимально возможное количество средств, которое позволит построить автодорогу из этого населенного пункта до конечного составляет 20 ден.ед. Переход предстоит осуществлять через 11 пункт (выделено стрелкой). Переходы через 12 и 13 пункты обойдутся дороже, а именно 13+12 и 11+14, т.е. 25 ден.ед. Эти участки пути не выделяются.

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

Рассматриваем пункт 7. Его связь с конечным 14 пунктом происходит через пункты 9 и 10, информация о которых нами уже найдена на предыдущем шаге. Поэтому нет необходимости просматривать решение от пункта 7 до конечного пункта 14, достаточно принять решение на промежуточном шаге: 7-9 или 7-10. Для того чтобы удалось построить дорогу на участке пути 7-9 требуется 15 ден.ед., согласно условию задачи, и, кроме того после строительства должно остаться 12 ден.ед. для продолжения работ после 9 пункта, а значит в пункте 7 должно быть 27 ден.ед. При строительстве ветки 7-10 тратится 12 ден.ед., а остается 15 в пункте 10, т.е. в пункте 7 должно быть 12+15=27 ден.ед. Итак, движение из 7 пункта может быть осуществлено как в пункт 9 так и в пункт 10, при этом количество средств в 7 пункте составляет 27 ден.ед.

Для расчета стоимости всех необходимых работ из пункта 6 до пункта 14 достаточно принять оптимальное решение при выборе маршрута из точки 6 в пункты 8, 9 и 10, и найти минимальное среди чисел, полученных в результате нахождения сумм {4+15, 13+12, 7+20}. Минимальная стоимость всех работ в пункте 6 составляет 19 ден.ед.

Аналогичные расчеты проводим для пункта 5. Для перехода 5-8 требуется 10+20=30 ден.ед.в пункте 5, переход 5-9 предполагает наличие 16+12=28 ден.ед. в пункте 5, а стоимость перехода 5-10 составляет 17+15=32 ден.ед. Минимум {10+20, 16+12, 17+15}=28, а переход осуществляем через 9 пункт.

Пункт 4 непосредственно связан только с двумя пунктами: 8 и 9. Поэтому для расчета средств в пункте 4 выбрать минимальное нужно из двух чисел 12+20=32 - переход из пункта 4 в пункт 8 или 6+12=18 - переход из 4 в 9.

Уже на этом шаге замечаем, что пункты 8 и 12 в условиях данной задачи не выгодные. Автодорога не пройдет через эти пункты, они дороже по сравнению с рядом расположенными с ними пунктами.

Расчет для пункта 3, как минимума из чисел {18+18, 18+28, 5+19, 2+27}=24 ден.ед. позволяет утверждать, что переход стоит осуществлять через пункт 6. Из пункта 2 оптимальный переход будет осуществлен через пункт 4 и количество средств, необходимых в пункте 2 составляет min{6+18, 14+28, 16+19}=24 ден.ед.

Для пункта 1 необходимо выбрать минимальное среди 24+5 и 24+6, что составляет 29 ден.ед., а маршрут следует проложить через пункт 2 (рис.1.11).

Рис. 1.11. Графическое изображение полного решения задачи

Итак, минимальная стоимость трассы 29 ден.ед. Автотрасса должна пройти по пунктам: 1-2-4-9-11-14, на схеме найденный оптимальный путь выделен жирными стрелками.

При решении задачи удалось избежать трудоемкого процесса составления и анализа рекуррентных соотношений. Решение задачи проведено графически. Кроме того, построенная графическая модель позволяет достаточно быстро пересчитать стоимость затрат при изменении начальных условий. Например, пересмотреть маршрут и его стоимость в случае если путь должен пройти через заранее заданный пункт. Причем при решении такой задачи нет необходимости пересчитывать все последующие за заданным пунктом точки. Достаточно проанализировать только предшествующие ему пункты [2, c.12].

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



2. ОПТИМАЛЬНОЕ РАСПРЕДЕЛЕНИЕ ДЕНЕЖНЫХ СРЕДСТВ

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

Таблица 2.1

Исходная информация

Участок	Число избирателей	Необходимые средства (руб.)
1	3100	35000
2	2600	25000
3	3500	40000
4	2800	30000
5	2400	20000

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

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

Тогда целевая функция примет вид.

Это количество изибраетелей, охваченных предвыборной кампанией.

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

Условия по ограченному бюджету:

35000x1 + 25000x2+40000x3+30000x4+20000x5 100000

Условие двоичности числа: пусть xi = 1, если предвыборная кампания на этом участке будет проводиться, и xi = 0 в противном случае. Следовательно, xi - двоичное.

xi 1

Условие целого числа:

xi = целое

денежный динамический программирование



3. ОПТИМАЛЬНОЕ РАСПРЕДЕЛЕНИЕ ДЕНЕЖНЫХ СРЕДСТВ С ИСПОЛЬЗОВАНИЕМ ПК

Для решения данной задачи с помощью MS Excel, воспользуемся надстройкой «Поиск решения».

Составим таблицу, где в столбце D будет отображено участие данного участка в предвыборной кампании (значение данного столбца или 0 или 1).

В ячейке Е7 введем целевую функцию. Данные ячейки (искомые и целевая) связываем вместе формулой, которую пишем в целевой ячейке Е7 следующим образом = СУММ(Е2:Е6), где ячейки E2:E6 содержат итоговое количество избирателей, в случае проведения предвыборной кампании на данном участке.

В ячейке F7 - функция ограничения бюджета.

Таблица 3.1

Таблица для решения задачи

	A	B	C	D	E	F
1	Участок	Число избирателей	Необходимые средства (руб.)	Участие в избирательной кампании	Количество избирателей	Бюджет
2	1	3100	35000		=В1*D1	=C1*D1
3	2	2600	25000		=В2*D2	=C2*D2
4	3	3500	40000		=В3*D3	=C3*D3
5	4	2800	30000		=В4*D4	=C4*D4
6	5	2400	20000		=В5*D5	=C5*D5
7	Итого:	14400	150000		=СУММ(Е2:Е6)	=СУММ(F2:F6)

Запустим сервис «Поиск решения», для этого выберем вкладку «Данные», затем «Анализ» и «Поиск решения» (рис. 3.1)



Рис. 3.1. «Поиск решения» в MS Excel

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

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

Следующее для заполнения поле - «Изменяя ячейки». В него нужно внести координаты искомой ячейки, содержащей определенное значение. Это значение и есть условие того будет ли на данном избирательном участке проводиться предвыборная кампания или нет. Также, как и с выбором целевой ячейки, координаты можно написать вручную, либо кликнуть по нужной ячейке в самой таблице.

Далее нужно отредактировать раздел «Ограничения», в котором задаем ограничения используемых данных. Это делается через кнопку «Добавить».

Откроется вспомогательное окно, позволяющее добавить ограничения во время вычислений. В первом поле указываем координаты определенной ячейки или области ячеек, для которых это условие должно действовать. Согласно нашей задаче, указываем координаты искомых ячеек, в которых будет выводиться значение 1 или 0. Следующий шаг - определить знак сравнения. Устанавливаем «меньше или равно», чтобы итоговое число не могло быть больше 1. «Ограничение», которое устанавливается во втором поле, в этом случае будет равно целому, поскольку избирательная кампания или будет проводиться (1) на данном участке, или нет (0). В третьем поле устанавливаем ограничение по бюджету, который может быть меньше или равен 100000 руб.

Рис. 3.2. Определение параметров поиска решения

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

Рис. 3.3. Результаты поиска решения



При этом сразу же откроется окно «Результаты поиска решения», где можно сохранить/отменить результаты или настроить параметры поиска заново. Если результаты нас устраивают, оставляем отметку напротив опции «Сохранить найденное решение» и нажимаем ОК (рис.3.3).

Результат решения задачи представлен на рисунке 3.4.

Рис. 3.4. Результат решения задачи

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



ЗАКЛЮЧЕНИЕ

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

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

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

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

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



СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

Анфиногентова, М. Д. Распределение инвестиций при помощи методов динамического программирования / М. Д. Анфиногентова, Г. В. Щербаков, М. В. Курганова // Modern Science. - 2021. - № 5-3. - С. 36-39.

Бахтиярова, О. Н. Динамическое программирование. Задача распределения ресурсов / О. Н. Бахтиярова ; ФГБВОУ ВО "Академия гражданской защиты МЧС России". - Химки : Академия гражданской защиты МЧС России, 2018. - 32 с.

Габдулхаков, А. А. Динамическая оптимизация сложных маршрутов в транспортной логистике / А. А. Габдулхаков, Д. С. Завалищин // Современные наукоемкие технологии. - 2021. - № 5. - С. 33-38.

Голованова, Е. В. Динамическое программирование в распределении инвестиций / Е. В. Голованова, С. Н. Толстопятов // Цифровые и инженерные технологии в АПК : Материалы Национальной научно-практической конференции, Майский, 25 ноября 2021 года / Председатель оргкомитета: Стребков С.В. Заместитель председателя Голованова Е. В. Члены оргкомитета: Водолазская Н. В. Ломазов В.А. Миронов А.Л.. - Майский: Белгородский государственный аграрный университет имени В.Я. Горина, 2022. - С. 202-204.

Голубин, С. П. Модели оптимального управления финансовыми средствами компании / С. П. Голубин // Электронный мультидисциплинарный научный журнал с порталом международных научно-практических конференций Интернетнаука. - 2017. - № 4. - С. 64-77.

Двоерядкина, Н. Н. Методика обучения решению задач динамического программирования студентов экономических направлений подготовки / Н. Н. Двоерядкина // Вопросы педагогики. - 2019. - № 3. - С. 92-97.

Ермильев, А. Н. Практическое применение динамического программирования / А. Н. Ермильев // Интернаука. - 2018. - № 22-1(56). - С. 21-23.

Жокабине, Н. Ф. Планирование финансовых ресурсов в системе управления финансовыми ресурсами предприятия / Н. Ф. Жокабине // Вестник Луганского национального университета имени Владимира Даля. - 2020. - № 4(34). - С. 83-87.

Киселева, И. А. Оптимальное распределение финансовых средств индивидуальным инвестором / И. А. Киселева, Н. Е. Симонович // Аудит и финансовый анализ. - 2014. - № 5. - С. 195-198.

Красс, М.С. Математика в экономике: математические методы и модели: учебник для бакалавров / М.С. Красс, Б.П. Чупрынов; под ред. М.С. Красса. - 2-е изд., испр. и доп. - М.: Издательство Юрайт, 2017. - 541 с.

Кристалинский, В. Р. Решение задач динамического программирования в системе Wolfram Mathematica / В. Р. Кристалинский, С. Н. Черный // International Journal of Open Information Technologies. - 2019. - Т. 7, № 2. - С. 42-48.

Окулов, С.М. Динамическое программирование / С.М. Окулов. - Москва: БИНОМ. Лаборатория знаний, 2017. -- 298 с.

Ревякина, К. О. Решение логистических проблем розничной торговли методами имитационного моделирования / К. О. Ревякина, Ю. В. Хицкова // Научный вестник Воронежского государственного архитектурно-строительного университета. Серия: Информационные технологии в строительных, социальных и экономических системах. - 2016. - № 2(8). - С. 57-59.

Рогачев, А.Ф. Оптимизация распределения ресурсов между стратегическими единицами бизнеса на основе динамического программирования / А.Ф. Рогачев, И.В. Скопина // Экономика и мат. методы. - 2015. - Т. 41, № 1. - С. 132-135.

Романовская А.М., Мендзив М.В. Динамическое программирование: Учебное пособие. - Омск: Издатель Омский институт (филиал) РГТЭУ, 2020. - 58 с.

Рыжов, Д. О. Распараллеливание алгоритмов решения 0-1 задачи о рюкзаке с помощью технологий OpenMP и MPI / Д. О. Рыжов // Заметки по информатике и математике : Сборник научных статей. Том Выпуск 11. - Ярославль : Ярославский государственный университет им. П.Г. Демидова, 2019. - С. 158-165.

Рябова, И. А. О содержании и моделях управления финансовыми ресурсами организации / И. А. Рябова, Н. Ю. Грошева, Е. В. Клейтман // Экономика: вчера, сегодня, завтра. - 2021. - Т. 11, № 7-1. - С. 61-70.

Сидоренко, Г. Г. Динамическое программирование для решения некоторых задач предупреждения и ликвидации чрезвычайных ситуаций / Г. Г. Сидоренко, О. Г. Сидоренко // Гражданская оборона на страже мира и безопасности : материалы V Международной научно-практической конференции, посвященной Всемирному дню гражданской обороны, Москва, 01 марта 2021 года. Том Часть IV. - Москва: Академия Государственной противопожарной службы Министерства Российской Федерации по делам гражданской обороны, чрезвычайным ситуациям и ликвидации последствий стихийных бедствий, 2021. - С. 240-246.

Старостина, Т. Г. Управление финансовыми ресурсами предприятия / Т. Г. Старостина, В. А. Игнатьева // Проблемы и перспективы экономических отношений предприятий авиационного кластера : Сборник научных трудов VII Всероссийской научной конференции, Ульяновск, 24-26 октября 2022 года. - Ульяновск: Ульяновский государственный технический университет, 2023. - С. 91-94.

Сутягина, Н. И. Метод динамического программирования при принятии микроэкономического решения//Вестник НГИЭИ. - 2014. - №. 11 (42). - С. 13.

Размещено на Allbest.ru

...