Лекция: Задача распределения ресурса
Постановка задачи. Имеется некоторый однотипный ресурс (нефть, зерно) в объёме. Этот ресурс можно использовать в технологических процессах и причём известно, что если -му процессу выделить ресурс в объёме, то получим прибыль. Требуется распределить ресурс между процессами таким образом, чтобы суммарная прибыль была максимальной.
Математическая модель. Целевая функция (суммарная прибыль) будет
(1)
Ограничения:
(2)
(В (2) можно использовать и неравенство, однако, как правило, ресурс используется полностью.)
(3)
(2)-(3)– прямые ограничения. (1)-(3) – математическая модель задачи. Задача (1)-(3) относится к задачам сепарабельного программирования, так как и целевая функция и все ограничения в ней задаются с помощью сепарабельных функций.
Определение.Функция переменных называется сепарабельной, если она представима в виде линейной комбинации функций одной переменной.
К таким задачам, в частности, всегда применим метод динамического программирования.Общая схема метода динамического программирования
Метод, как правило, включает 3 этапа:
I этап: инвариантное погружение. На этом этапе исходная задача погружается в семейство подобных ей задач, зависящие от 2-х параметров, один из которых обычно динамический(время, этап). Оптимальное значение целевой функции отдельной задачи этого семейства (при фиксированных значениях параметров) называется функцией Беллмана.
II этап: строится уравнение Беллмана для этой функции. На этом этапе используется принцип оптимальности Беллмана, который формулируется следующим образом: любая часть оптимального решения (которая представляет из себя некоторую траекторию во времени или развивается поэтапно) начинающаяся с любого момента является сама оптимальной относительно достигнутого состояния.
Пример.
Пусть имеется оптимальная траектория, связывающая две точки, для – начальный момент, – конечный момент; – начальное состояние, – конечное состояние. Эта траектория оптимальная в связи с некоторой целевой функцией. Предположим, что в некоторый момент мы достигаем состояния и пытаемся из этого состояния и из этого момента достигнуть оптимальным образом. Тогда принцип оптимальности Беллмана утверждает, что решением этой задачи будет соответствующий (оставшийся) кусок траектории .
III этап: заключается в решении уравнения Беллмана (при всех значениях параметров определяется функцией Беллмана) и построению по этому решению оптимального плана исходной задачи.
Инвариантное погружение для задачи (1)-(3)
Рассмотрим в (1)-(3) первых технологических процесса и выделим для них ресурс в объёме и будем этот ресурс для этих процессов распределять оптимально, тогда приходим к задаче:
(4)
это и есть искомое семейство. Если в (4) положить, то придём к исходной задаче (1)-(3). То есть погружение осуществлено корректно. Оптимум целевой функции семейства (4) при фиксированных и, то есть максимальную прибыль, которую можно получить, если распределить среди первых процессов ресурс называется функцией Беллмана и обозначается .