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

⇐ ПредыдущаяСтр 7 из 17Следующая ⇒

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

Предположим, некая корпорация распределяет 100 ден. ед. инвестиционных ресурсов между 4-мя подразделениями. В каждом подразделении на альтернативной основе можно выбрать для реализации один из 5-ти инвестиционных проектов, стоимость каждого из которых кратна 20. Известен прирост объема продаж, достигаемый в результате реализации соответствующего проекта в каждом подразделении. Требуется выбрать вариант распределения инвестиционных ресурсов, максимизирующий суммарный прирост объема продаж.

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

Множество состояний - возможные варианты остатка запаса инвестиционных средств перед выделением его -му подразделению. Поскольку возможны варианты распределения средств (от 0 до 100 ден. ед.) в кратных 20-ти суммах, то состояния системы пред -м шагом могут характеризоваться величинами: 0,20,40,60,80,100.

Принимаемое на -м шаге решение будет зависеть от остатка запаса, а потому оно может характеризоваться определенным набором элементов множества . Данное множество образуют величины 0,20,40,60,80,100. Множество состояний – возможные варианты остатка запаса средств после их выделения - му подразделению. Возможные величины остатков, как можно предположить, также 0,20,40,60,80,100.

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

В таблице 15 отражены показатели прироста объема продаж в каждом из 4-х подразделений в зависимости от величины выделенных инвестиций.

Таблица 15. Эффект инвестиций в подразделениях корпорации

	Прирост объема продаж (ден. ед.)
Инвестиционные затраты (ден. ед.)	1-ое подразделение	2-ое подразделение	3-е подразделение	4-е подразделение
20 40 60 80 100	10 31 42 62 78	12 26 36 54 78	11 36 45 60 77	16 37 46 63 80

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

Условная оптимизация начинается с анализа 4-го шага (табл. 16). Прокомментируем подход к его реализации.

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

Таблица 16. Анализ 4-го шага.

x₃	u₄		Z₄	F₄
0 20 40 60 80 100	0 20 40 60 80 100	0 0 0 0 0 0	0 16 37 46 63 80	0 16 37 46 63 80

Результаты, достигнутые на 4-ом шаге, используются в таблице для анализа 3-го шага (табл. 17) в виде элементов множества . Важным отличием 3-го шага от заключительного является наличие альтернатив принятия решения для элементов множества (за исключением =0). Действительно, наличие определенного остатка средств создает спектр возможностей – либо ничего не выделить третьему получателю, либо выделить сумму, кратную 20-ти. Выбор варианта решения определяет значение остатка средств после выделения их 3-ему подразделению

( элементы множества ), а также эффект в виде прироста объема продаж в третьем подразделении . Суммируя эффект, достигаемый на 3-ем и 4-ом шагах, определяем по максимальной сумме условно-оптимальное значение целевой функции .

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

Таблица 17. Анализ 3-го шага.

x₂	u₃	x₃	Z₃	F₄	Z₃+F₄	F₃
0	0	0	0	0	0	0
20	0 20	20 0	0 11	16 0	16 11	16 -
40	0 20 40	40 20 0	0 11 36	37 16 0	37 27 36	37 - -
60	0 20 40 60	60 40 20 0	0 11 36 45	46 37 16 0	46 48 52 45	- - 52 -
80	0 20 40 60 80	80 60 40 20 0	0 11 36 45 60	63 46 37 16 0	63 57 73 61 60	- - 73 - -
100	0 20 40 60 80 100	100 80 60 40 20 0	0 11 36 45 60 77	80 63 46 37 16 0	80 74 82 82 76 77	- - 82 82 - -

Приведенные выше рассуждения справедливы для 2-го и для 1-го шагов.

Ниже представлена характеристика 2-го шага (табл. 18), на котором рассматривается выделение инвестиционных средств второму получателю. Результат реализации данного шага – определение условно- оптимальных значений целевой функции на шагах от 2-го до 4-го включительно ( элементы множества , отраженные в последней колонке таблицы 18).

Таблица 18. Анализ 2-го шага.

x₁	u₂	x₂	Z₂	F₃	Z₂+F₃	F₂
0	0	0	0	0	0	0
20	0 20	20 0	0 12	16 0	16 12	16 -
40	0 20 40	40 20 0	0 12 26	37 16 0	37 28 26	37 - -
60	0 20 40 60	60 40 20 0	0 12 26 36	52 37 16 0	52 49 42 36	52 - - -
80	0 20 40 60 80	80 60 40 20 0	0 12 26 36 54	73 52 37 16 0	73 64 61 52 54	73 - - - -
100	0 20 40 60 80 100	100 80 60 40 20 0	0 12 26 36 54 78	82 73 52 37 16 0	82 85 78 73 70 78	- 85 - - - -

По завершении анализа 1-го шага (табл. 19) оказалось выявлено максимальное значение суммарного прироста объема продаж – 85 ден. ед. Таким образом, условная оптимизация закончена. Ее результатом является, как и ожидалось, экстремальное значение целевой функции:

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

Таблица 19. Анализ 1-го шага.

x₀	u₁	x₁	Z₁	F₂	Z₁+F₂	F₁
0	0	0	0	0	0	0
20	0 20	20 0	0 10	16 0	16 10	16 -
40	0 20 40	40 20 0	0 10 31	37 16 0	37 26 31	37 - -
60	0 20 40 60	60 40 20 0	0 10 31 42	52 37 16 0	52 47 47 42	52 - - -
80	0 20 40 60 80	80 60 40 20 0	0 10 31 42 62	73 52 37 16 0	73 62 68 57 62	73 - - - -
100	0 20 40 60 80 100	100 80 60 40 20 0	0 10 31 42 62 76	85 73 52 37 16 0	85 83 83 79 78 76	85 - - - - -

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

В таблице 19 экстремальное значение целевой функции 85 соответствует . Иными словами, первому получателю средств выделять не следует, и запас в 100 ед. целиком остается для последующего распределения. В таблице 18 находим и определяем альтернативу решения, которая соответствует условно-оптимальному значению целевой функции: . То есть, второму получателю следует выделить 20 ден. ед. инвестиционных средств. Остается 80 ден. ед. запаса. В таблице 17 находим и определяем альтернативу решения, которая соответствует условно-оптимальному значению целевой функции: . Третьему получателю надлежит выделить 40 ден. ед. запаса. Естественно, остаток 40 ден. ед. должен быть выделен четвертому получателю: . В итоге вектор оптимальных управлений будет иметь следующий состав .

Дата добавления: 2018-05-02; просмотров: 500; Мы поможем в написании вашей работы!

Поделиться с друзьями:

⇐ Предыдущая 2 3 4 5 678 9 10 11 Следующая ⇒

Мы поможем в написании ваших работ!