Задача о распределении ресурса

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

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

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

В качестве параметра состояния y_n выступает объем денежных средств, вкладываемых в n финансовых инструментов.

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

y_n-1 = y_n - x_n

Ограничения для данной задачи следующие:

а) объем денежных средств, вкладываемых в n финансовых инструментов, не может превышать общего объема денежных средств:

y_n  ≤ y_N

б) объем денежных средств, вкладываемых в n-ый финансовый инструмент, не может превышать объем денежных средств, вкладываемых в n финансовых инструментов:

x_n ≤ y_n

Рекуррентное соотношение имеет вид:

где:

f_n(x_n) -доходность n го финансового инструмента при вложении в него x_n денежных средств;

F_n(y_n) - суммарная максимальная доходность n финансовых инструментов при вложении в них y_n денежных средств.

Пример.

Пусть имеется 50 у.е. денежных средств и 4 финансовых инструмента, в которые эти средства можно вложить. Известна доходность каждого финансового инструмента при вложении в них 10, 20, 30, 40 и 50 у.е. денежных средств. Значения доходности представлены в табл. 1:

Таблица 1

Решение:

1. n = 1 F₁(y₁) = f₁(x₁).

При этом ясно, что y_{1 =} x₁ , поскольку и y₁ и x₁ - денежные средства, вкладываемые в первый финансовый инструмент.

2. n = 2 F₂(y₂) =

у₂ = 10 х₂ = 0     a = f₂(0) + F₁(10 - 0) = 0 + 10 = 10

            х₂ = 10   a = f₂(10)+F₁(10 - 10)=8 + 0 = 8

            F₂ (10) = max (10; 8) =10 при х₂ = 0

У₂ = 20 х₂ = 0                 a = f₂(0) + F₁(20 - 0) = 0 + 19 = 19

  х₂ = 10   a = f₂(10) + F₁(20 - 10) = 8 + 10 = 18

  х₂ = 20   a = f₂(20)+F₁(20 - 20) = 15 + 0 = 15

  F₂(20) = max(19;18;15) = 19    при х₂ = 0.

Аналогично производится расчет для У₂ = 30, У₂ = 40 У₂ = 50. Результаты расчетов заносятся в таблицу 2.

Произведя подобные расчеты при n = 3 и n = 4, определяем F₃(y₃) и F₄(y₄) . Результаты расчетов заносятся в табл. 3 и табл.4.

Таблица 2

х2 У2	0	10	20	30	40	50	x2* (y2)	F2(y2)
10	10	8	—	—	—	—	0	10
20	19	18	15	_	—	—	0	19
30	26	27	25	22	_	—	10	27
40	33	34	34	32	28	—	10, 20	34
50	39	41	41	41	38	34	10, 20, 30	41

Таблица 3

х3 У3	0	10	20	30	40	50	x3* (y3)	F3(y3)
10	10	12	—	—	—	—	10	12
20	19	22	20	—	_	—	10	22
30	27	31	30	28	—	—	10	31
40	34	39	39	38	36	—	10, 20	39
50	41	46	47	47	46	45	20, 30	47

Таблица 4

х4 У4	0	10	20	30	40	50	x4* (y4)	F4(y4)
50	47	50	51	47	44	41	20	51

Таким образом, из расчета в таблице 4 следует, что х*₄ = 20, следовательно, из имеющихся 50 у.е. в четвертый финансовый инструмент следует вложить 20 у.е., а в три оставшихся необходимо вложить

у₃ =у₄ - х₄ = 50 - 20 = 30 у.е.

В таблице 3 объему денежных средств 30 у.е. соответствует х*₃ = 10, следовательно

У₂ = Уз – х_З = 30 - 10 = 20 у.е.

По таблице 2 определяется х*₂ = 0 и, следовательно,

х*₁ = 20 у.е.

Таким образом, суммарная максимальная доходность составляет 51 единицу при вложении в первый финансовый инструмент 20 у.е., в третий - 10 у.е., в четвертый - 20 у.е., т.е.

х* =(20; 0; 10; 20).

СПИСОК РЕКОМЕНДУЕМОЙ ЛИТЕРАТУРЫ:

1. Ашманов С.А. Линейное программирование. М.: Наука, 1981.

2. Бэллман Р. Динамическое программирование. - М.: ИЛ, 1960.

3. Бэллман Р., Дрейфус С. Прикладные задачи динамического программирования. - М.: Наука, 1965,

4. Вагнер Г. Основы исследования операций. - М.: Мир, 1972.

5. Калихман И.Л. Сборник задач по математическому программированию. - М.: Высшая школа, 1975.

6. Капустин В.Ф. Практические занятия по курсу математического программирования: ЛГУ, 1976.

КОНТРОЛЬНЫЕ ЗАДАНИЯ

Контрольная работа включает в себя решение трех задач:

1. Двухэтапная транспортная задача.

2. Транспортная задача в сетевой постановке.

3. Задача о распределении ресурса.

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

а третья задача- по специальному условию: