Исследование операций. Линейное, динамическое программирование



         

Исследование операций - часть 80


По существу же оба подхода совершенно равносильны.

2. Задача о распределении ресурсов. Метод динамического программирования позволяет с успехом решать многие экономические задачи (см., например, [6, 10]). Рассмотрим одну из простейших таких задач. В нашем распоряжении имеется какой-то запас средств (ресурсов) К, который должен быть распределен между т предприятиями П1, П2, ..., Пm. Каждое из предприятий Пi при вложении в него каких-то средств х приносит доход, зависящий от x, т. е. представляющий собой какую-то функцию

(x). Все функции
(x) (i = 1, 2, ..., т)

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

Эта задача легко решается методом динамического программирования.. Хотя в своей постановке она не содержит упоминания о времени, можно все же операцию распределения средств мысленно развернуть в какой-то последовательности, считая за первый шаг вложение средств в предприятие П1, за второй — в П2

и т. д.

Управляемая система S в данном случае — средства или ресурсы, которые распределяются. Состояние системы S перед каждым шагом характеризуется одним числом S — наличным запасом еще не вложенных средств. В этой задаче «шаговыми управлениями» являются средства х1, х2, ..., х3,

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

..., хm, при которой суммарный доход максимален:

           (13.1)

Решим эту задачу сначала в общем, формульном виде, а потом — для конкретных числовых данных. Найдем для каждого i-го шага условный оптимальный выигрыш (от этого шага и до конца), если мы подошли к данному шагу с запасом средств S. Обозначим условный оптимальный выигрыш Wi(S), а соответствующее ему условное оптимальное управление — средства, вкладываемые в i-е предприятие, — xi(S).

Начнем оптимизацию с последнего, т - го шага. Пусть мы подошли к этому шагу с остатком средств S. Что нам делать? Очевидно, вложить всю сумму S целиком в предприятие Пm.


Содержание  Назад  Вперед