Динамическая задача распределение инвестиций как решить

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

Данный раздел представлен следующими калькуляторами:

1. Задача распределения инвестиций. Распределении инвестиций между предприятиями П₁, П₂. П_n. Инвестируемая сумма E усл. ден. ед.
2. Задача распределения ресурсов. Планируется работа двух предприятий на n лет. Начальные ресурсы равны s₀ .
3. Метод прогонки.
4. Задача замены оборудования.
5. Складская задача: составить оптимальную программу выпуска продукции X , которая минимизирует суммарные издержки предприятия.
6. Задача Джонсона.
7. Задача о рюкзаке (решение задачи о загрузке транспортного средства).
8. Динамическая оптимизация в планировании работ
   В условиях задачи производственного планирования найти оптимальные сроки начала строительства каждого из объектов так, чтобы суммарный срок строительства всех объектов был бы минимальным.
   

   Объекты / Стадии	№1	№2	№3	№4
   A1	2	5	4	3
   A2	1	4	2	6
   A3	3	4	3	4

Задача распределения инвестиций

Таблицы могут иметь разный вид.
Таблица 1 — Первый вариант таблицы исходных данных

x	f1(x)	f2(x)	f3(x)
1	6.3	4	5
2	5.2	6	7
3	4.3	4.6	7.8
4	5	6	3
5*	7	6.3	8.2

* — здесь значение 5 — максимальное значение (сумма для распределения).

Таблица 2 — Второй вариант таблицы исходных данных

x	0	10	20	30	40
f1(x)	0	4	5	7	8
f2(x)	0	3	3	4	6
f3(x)	0	4	4	5	6

Пример задачи.
Для двух предприятий выделено A единиц средств. Как распределить все средства в течение 4 лет, чтобы доход был наибольшим, если известно, что доход от x единиц средств, вложенных в первое предприятие, равен f₁(х), а доход от y единиц средств, вложенных во второе предприятие, равен f₂(y). Остаток средств к концу года составляет g₁(x) для первого предприятия и g₂(y) для второго предприятия. Задачу решить методом динамического программирования.

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

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

Метод прогонки

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

Источник

Динамическое программирование. Задача о распределении инвестиций — видеоурок с решением задачи в Excel

>Ниже приведено условие задачи и текстовая часть решения. Закачка полного решения, файлы doc и xls в архиве zip, начнется автоматически через 10 секунд. Видеоурок по решению этих задач — внизу страницы.

Указать оптимальные размеры и потоки инвестирования, если прибыль от вложений (Х i ) в проекты (А i ) распределилась следующим образом:

Теперь для решения этой задачи воспользуемся Excel .

Для этого выделим шаги тренда t i , вложения x i и прибыли A i . Затем для каждого из четырех проектов построим средствами MS Excel графическую зависимость прибыли А от шага тренда ( t = 1, 2, 3, 4, 5 , 6 ). Активизируем точки графика, щелкнув по ним левой клавишей мыши, затем нажмем правую клавишу и выберем режим «Добавить линию тренда» . Для всех четырех проектов наилучшим типом является полиномиальный 5 -о й степени. С помощью полученных уравнений трендов находим теоретические значения прибыли при различных значениях шага тренда t i . Уравнения моделей тренда, коэффициенты аппроксимации и теоретические значения при были, представлены на рисунке 1.

Рис. 1. Графические зависимости прибыли от вложений и полиномиальные тренды этих зависимостей.

В ячейку М32 вводим выражение для общей (суммарной) прибыли, которую надо максимизировать, — это сумма всех четырех полиномиальных функций. Зависимыми переменными в этой функции являются искомые значения шагов тренда, которые будут располагаться в ячейках E 32 — H 32 . Суммарные вложения не должны превышать 5 0 тыс. ед., следовательно, вводим ограничение 1 0 *(E32+F32+G32 +H32 -4) в ячейку D 37 .

Выбираем из главного меню MS Excel режим «Поиск решения» и заполним открывшееся диалоговое окно в соответствии с требованиями. Нажмем клавишу «выполнить» и получим результат оптимизации.

Рис. 2. Модель максимизации прибыли.

Рис. 3. Оптимальное распределение капиталовложений между проектами.

Имя файла: dinprogr.zip

Размер файла: 129.98 Kb

Если закачивание файла не начнется через 10 сек, кликните по этой ссылке

Источник

2.1. задача о распределении инвестиций

2.1. задача о распределении инвестиций

«Условие задачи. В производственное объединение входят три предприятия Пі, ТІ2, Щ. Руководство объединения решило инвестировать в свои предприятия 5 условных денежных единиц (усл. ден. ед.) в общей сумме. Проведенные маркетинговые исследования прогнозируют величину ожидаемой прибыли каждого из предприятий в зависимости от объема инвестированных средств. Эти данные представлены в приведенной ниже таблице. Считается, что при нулевых инвестициях ожидается нулевая прибыль.

Требуется найти такое распределение инвестиций между предприятиями, которое обеспечило бы максимум суммарной ожидаемой прибыли.

Решение. В данной задаче управляемой системой является рассматриваемое производственное объединение, многошаговым процессом — процесс выделения средств предприятиям. Отметим, что структура многошагового процесса в данной задаче определяется не течением времени, а порядком планирования распределения инвестиций. Экономический эффект представляет суммарная величина ожидаемой прибыли, и при этом задача решается на поиск максимума.

Для решения поставленной задачи построим прежде всего ее экономико-математическую модель в соответствии с пп. 1-5 разд. 1.7 гл. 1.

Число шагов ./V в данной задаче следует принять равным 3, соответствующим числу входящих в производственное объединение предприятий: на первом шаге планируется выделение средств предприятию П, на втором шаге — предприятию Я2, на третьем шаге — предприятию Щ.

В качестве фазовой переменной х, определяющей состояние системы в ходе процесса распределения инвестиций, примем суммарный объем средств, выделенных предприятиям после каждого шага процесса. Именно, переменная х представляет объем средств, выделенных предприятиям после первого шага процесса (т. е. только предприятию П), Х2 — объем средств, выделенных после второго шага (предприятиям П и Д2), х3 —объем средств, выделенных после третьего шага процесса (всем предприятиям П, Я2 и Яз). Поскольку в начальный момент общая сумма выделенных средств равна 0, то начальное состояние системы характеризуется значением xq = 0. По условию задачи общая сумма инвестируемых средств равна 5 усл. ден. ед., т. е. обязательно выполняется условие хз = 5. Поскольку по смыслу задачи на каждом шаге процесса значения фазовой переменной не убывают, то выполняется ограничение Zj ^ 5. Отметим, что проведенный выбор фазовой переменной с указанным экономическим смыслом не является единственно возможным. Например, в рассматриваемой задаче можно было выбрать в качестве переменной х остаток нераспределенных средств.

В качестве управляющей переменной и примем объем средств, выделяемых предприятиям на каждом из шагов процесса. Именно, переменная щ представляет объем средств, выделяемых предприятию Щ (на 1-м шаге процесса), и2 — объем средств, выделяемых предприятию П2 (на 2-м шаге), из — объем средств, выделяемых предприятию 773 (на 3-м шаге). Будем считать, что средства предприятиям выделяются суммами но целому числу усл. ден. ед.; соответственно все управления принимают только целочисленные значения 0, 1, 2. .

Функция процесса хі = /і(хі-і,щ), определяющая закон изменения состояния системы, для данной задачи представляется формулой

и имеет следующий простой смысл: суммарный объем средств хі, выделенных предприятиям нарастающим итогом после текущего шага с номером г, равен суммарному объему средств выделенных предприятиям после предшествующего шага с номером і — 1 (или, что то же самое, до текущего шага), плюс объем средств щ, выделенных предприятию Щ на текущем шаге.

Функция Zi, определяющая частный экономический эффект на шаге с номером г процесса, зависит только от объема щ инвестированных средств в предприятие Щ, т. е. Zi = Zi(m), и определяется по таблице данных задачи по столбцу, отвечающему этому предприятию. Например, z(2) = 4 (из столбца, отвечающего предприятию Пі), z2(3) = 6, 23 (4) = 9.

На этом действия, предписываемые пп. 1-5 разд. 1.7 гл. 1 выполнены, что означает завершение математической формализации поставленной задачи, т. е. построение соответствующей экономико-математической модели. Заметим, что после проведенной указанным образом формализации основные допущения метода ДП выполняются: отсутствие последействия следует из явных формул для вычисления Хі и Zi, а аддитивность целевой функции

Z = Zi(ui) + Z2 (и2) + 23(м3)

обусловлена самой постановкой задачи.

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

Предварительный этап. Данный этап решения задачи проводится в естественном порядке для і = 1, 2,3 и не связан непосредственно с вычислением функций Беллмана Ві(хі). Заполняются только первая строка вспомогательной таблицы и четыре левых столбца основной таблицы.

Вспомогательная таблица заполняется соответственно начальному условию xq = 0 и имеет вид

Заполнение основной таблицы проводится следующим образом. Для заданного единственного допустимого значения xq = 0 выбираем все возможные значения управления щ (оно может принимать все целочисленные значения от 0 до 5 включительно) и заносим их во второй столбец таблицы. По формуле xi — xq + щ (следующей из общей формулы хг = Xi-i + щ при і = 1) проводим расчет соответствующих значений переменной хх и заносим их в третий столбец. Для заполнения четвертого столбца значения ожидаемой прибыли zx берем из столбца таблицы исходных данных задачи, отвечающего предприятию Пі. для щ — 1 по этой таблице zj = 2, для и = 2 по таблице zi — 4 и т. д. Для щ = 0 по условию задачи zi = 0. Получаем следующую основную таблицу:

Источник

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

Инвестор выделяет средства в размере D условных единиц, которые должны быть распределены между n-предприятиями. Каждое k-тое предприятие при инвестировании в него средств x приносит прибыль W_k (S, x_k) условных единиц, k=1. n. Нужно выбрать оптимальное распределение инвестиций между предприятиями, обеспечивающее максимальную прибыль.

Выигрышем F в данной задаче является прибыль, приносимая n-предприятиями.

Построение математической модели:

1. Определение числа шагов. Число шагов n равно числу предприятий, в которые осуществляется инвестирование.

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

3. Выбор шаговых управлений. Управление на k-м шаге является количество средств, инвестируемых в k-тое предприятие.

4. Функция выигрыша на k-м шаге:

(53.1)

это прибыль, которую приносит k-тое предприятие при инвестировании в него средств .

, (53.2)

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

5. Определение функции перехода в новое состояние.

. (53.3)

Таким образом, если на k-м шаге система находилась в состоянии , а выбрано управление , то на (k+1)-м шаге система будет находиться в состоянии . Другими словами, если в наличии имеются средства в размере у.е., и в k-тое предприятие инвестируется у.е., то для дальнейшего инвестирования остается ( ) у.е.

6. Составление функционального уравнения для k=n:

, (53.4)

. (53.5)

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

7. Составление основного функционального уравнения.

Подставив в формулу (53.2) выражения (53.1) и (53.3), получим следующее функциональное уравнение:

(53.6)

Поясним данное уравнение. Пусть перед k-м шагом у инвестора остались средства в размере у.е. Тогда у.е. он может вложить в k-тое предприятие, при этом оно принесет доход , а оставшиеся ( ) у.е.—в остальные предприятия с k+1-го до n-го. Условный оптимальный выигрыш от такого вложения . Оптимальным будет то условное управление , при котором сумма и максимальна.

Пример: D=5000, n=3. Значения , заданы в таблице 34.1.

тыс. усл. ед.	тыс. усл. ед.	тыс. усл.ед.	тыс. усл.ед.
1,5	1,7
2,1	2,4
2,5	2,3	2,7
3,5	3,2
3,6	3,5

Для _. (53.7)

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

Проведем условную оптимизацию.

По ее результатам заполняется таблица 53.2.

S	k=3	k=2	k=1
1,7
2,4	3,7
2,7	4,4
3,2	4,7
3,5	1/4	5,2	6,4

В первой колонке таблицы записываются возможные состояния системы S=1..5, в верхней строке — номера шагов i=1..3. На каждом шаге определяются условные оптимальные управления и уcловные оптимальные выигрыши .

· Проведение условной оптимизации для последнего шага i=3. Функциональное уравнение на последнем шаге имеет вид:

, (53.8)

поэтому два столбца таблицы 33.2, соответствующие i=3, заполняются автоматически по таблице 33.1 исходных данных.

· Условная оптимизация для i=2. Функциональное уравнение

. (53.9)

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

1,7	1,7

, следовательно , .

2,4	2,4
1,7	3,7
2,1	2,1

, следовательно ;

2,7	2,7
2,4	4,4
2,1	1,7	3,8
2,3	2,3

, следовательно ;

3,2	3,2
2,7	4,7
2,1	2,4	4,5
2,3	1,7
3,5	3,5

, следовательно ; .

3,5	3,5
3,2	5,2
2,1	2,7	4,8
2,3	2,4	4,7
3,5	1,7	5,2

Для S=5 возможны два условных варианта управления: и .

· Условная оптимизация для i=1.

Перед первым шагом состояние системы известно.

S=D=5 тыс. у.е., и условную оптимизацию следует проводить только для этого значения

S=5

5,2	5,2
1,5	4,7	6,2
4,4	6,4
2,5	3,7	6,2
3,6	3,6

, следовательно, , .

Оптимальная прибыль, приносимая тремя предприятиями при инвестировании в них 5000 у.е., равна 6,4 тыс. у.е.

.

Проведем безусловную оптимизацию.

Ее результаты отмечены в таблице 34.2.

Для i=1 ; .

Для i=2 по формуле (34.3) .

; .

Для i=3 .

; .

.

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

Теория игр. Игровые модели.

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

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

В теории игр участников конкурирующего взаимодействия называют игроками, каждый из них имеет непустое множество допустимых действий, совершаемых им по ходу игры, которые называются ходами или выборами. Набор всех возможных ходов по одному из списка возможных ходов каждого игрока (участвующих в парах, тройках и т.д. ходов) называется стратегией. Грамотно построенные стратегии взаимно исключают друг друга, т.е. взаимно исчерпывают все способы поведения игроков. Исходом игры называется реализация игроком выбранной им стратегии. Каждому исходу игры соответствует определяемое игроками значение полезности (выигрыша), называемое платежом.

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

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

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

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

· бескоалиционные: игроки не имеют права вступать в соглашения, образовывать коалиции;

· коалиционные (кооперативные) – игроки могут вступать в коалиции.

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

4. По характеру выигрышей игры делятся на:

· игры с нулевой суммой (общий капитал всех игроков не меняется, а перераспределяется между игроками; сумма выигрышей всех игроков равна нулю);

· игры с ненулевой суммой.

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

Матричная игра – это конечная парная игра двух игроков с нулевой суммой, в которой задаётся выигрыш игрока 1 в виде матрицы (строка матрицы соответствует номеру применяемой стратегии игрока 2, столбец – номеру применяемой стратегии игрока 2; на пересечении строки и столбца матрицы находится выигрыш игрока 1, соответствующий применяемым стратегиям).

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

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

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

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

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

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

· Минимаксная стратегия (выбор из максимальных (наихудших) проигрышей минимальных (наилучших).

· Максиминная стратегия (выбор из минимальных (наихудших) выигрышей максимальных (наилучших).

Развитием теории игр с использованием методов вероятностного анализа является математическая теория принятия решений. Эта теория оперирует не действительным (актуальным) решением, а средним, которое есть ожидаемое решение игры в течение ее многократного повторения. Данное свойство актуально для решения правовых задач, поскольку нормативный характер права означает, что оно ориентировано на неопределенного субъекта и предполагает многократное повторение правоотношений. Чтобы не вдаваться в глубокие математические выкладки, отметим лишь, что теория принятия решений предлагает систему критериев (например, критерий Гурвица, Хаджи-Лемана, критерий ожидаемого значения), которые с помощью вероятностного анализа исходов игр позволяют осуществить выбор оптимального решения в условиях риска и неопределенности.

Источник