Принцип оптимальности Беллмана
Каким бы ни был путь достижения некоторого пункта, последующие решения должны принадлежать оптимальной стратегии для части пути, начинающейся с этого пункта.
Метод динамического программирования состоит в том, что оптимальное управление строится постепенно. На каждом шаге оптимизируется управление только этого шага. Вместе с тем на каждом шаге управление выбирается с учетом последствий, так как управление, оптимизирующее целевую функцию только для данного шага, может привести к неоптимальному эффекту всего процесса. Управление на каждом шаге должно быть оптимальным с точки зрения процесса в целом. Это основное правило динамического программирования, сформулированное американским математиком Беллманом, и называется принципом оптимальности.
Итак, каково бы не было начальное состояние системы перед очередным шагом, управление на этом этапе выбирается так, чтобы выигрыш на данном шаге плюс оптимальный выигрыш на всех последующих шагах был оптимальным.
Так как природа каждого этапа решения зависит от конкретной оптимизационной задачи, ДП не предлагает вычислительных алгоритмов непосредственно для каждого этапа. Вычислительные аспекты решения оптимизационных подзадач на каждом этапе проектируются и реализуются по отдельности (но это не исключает того, что может быть применен единый алгоритм для всех этапов).
Укажем два признака, характерные для задач, решаемых методами ДП.
|
|
|
Задача обладает свойством оптимальности для подзадач, т.е. оптимальное решение задачи содержит оптимальные решения ее подзадач.
Задача имеет перекрывающиеся подзадачи, т.е. при рекурсивном решении мы многократно выходим на одни и те же подзадачи.
Вычисления в ДП выполняются рекуррентно в том смысле, что оптимальные решения одной подзадачи используются в качестве исходных данных для следующей подзадачи. Способ выполнения рекуррентных вычислений зависит от того, как выполняются декомпозиции исходной задачи. В данной ситуации возможно несколько вариантов. Первый из них это проводить вычисления последовательно от первого до последнего этапа, такая последовательность известна как алгоритм прямой прогонки.
Задача может быть также решена с помощью алгоритма обратной прогонки, в соответствии с которым вычисления проводятся от последнего этапа до первого.
Очевидно, что алгоритмы прямой и обратной прогонки приводят к одному и тому же решению. Обычно более логичным представляется использовать алгоритм прямой прогонки, но в общем случае алгоритм обратной прогонки может быть более эффективным с вычислительной точки зрения. Продемонстрируем ДП на решение конкретных задач.
|
|
|
Задача о загрузке (о рюкзаке)
Задача о загрузке — это задача о рациональной загрузке судна (самолета, автомашины, и т. п.), которое имеет ограничения по объему или грузоподъемности. Каждый помещенный на судно груз приносит определенную прибыль. Задача состоит в том, чтобы определении загрузки, такими грузами которые приносят наибольшую прибыль.
Отметим также, что данная задача известна как задача о рюкзаке, в который турист должен определить наиболее ценные предметы, подлежащие загрузке в рюкзак.
Формализуем нашу задачу. Пусть W — грузоподъемность нашего судна и в наличии имеется n наименований предметов, которые подлежат загрузке. Пусть m i — количество предметов i-ого наименования (именно эти целочисленные величины подлежат определению в процессе решения задачи ДП !), r i — прибыль, которую приносит один загруженный предмет i-ого наименования, w i — вес одного предмета i-ого наименования. Тогда общая задача имеет вид следующей целочисленной задачи линейного программирования.
Максимизировать целевую функцию 
при условии, что:
Заметим, что если целевая функция задачи (иногда говорят про выигрыш !) за всю операцию складывается из выигрышей на отдельных этапах, т.е. 
, где fi – выигрыш на i-ом этапе, то такой критерий выигрыша называют аддитивным критерием.
|
|
|
Несложно видеть, что при любом 
очевидно имеем, что 
, где принято следующее обозначение [X] — целая часть числа X, т.е. [X] - максимальное целое число, не превосходящее X.
Рассмотрим далее алгоритм решения поставленной задачи ДП. При решении каждой конкретной задачи обратим внимание три основных элемента модели динамического программирования.
§ Определение этапов решения.
§ Определения на каждом этапе вариантов решения задачи (возможных альтернатив).
§ Определения состояний системы на каждом этапе решения.
Из перечисленных выше элементов понятие состояние, как правило, представляется весьма сложным для восприятия. Определение этого понятия может меняться в зависимости от конкретной ситуации. При рассмотрении каждого приложения полезно ответить на следующие вопросы.
1. Какие соотношения связывают этапы решения вместе ?
2. Какая информация необходима для того, чтобы получить допустимые решения на текущем этапе без повторной проверки решений, полученных на предыдущих этапах решения ?
В приведенной задаче о загрузке эти три элемента модели динамического программирования определяются следующим образом.
|
|
|
1. Этап (шаг) решения i ставится в соответствие предмету i-ого наименования, 
. Задача будет решена с помощью алгоритма обратной прогонки, в соответствии с которым вычисления проводятся от последнего этапа до первого. Предварительно договоримся, что все наши n предметов упорядочены по возрастанию величин 
(прим. по смыслу задачи 
– это максимально допустимое количество предметов каждого типа).
2. Варианты решения на этапе i описываются количеством предметов 
предметов i-ого наименования, подлежащих загрузке. Соответствующая прибыль равна 
. Как уже отмечено, значение m i заключено в пределах от 0 до [W/w i], причем максимально возможное число предметов любого вида не может превысить значения 
.
3. Общее ограничение по суммарному весу W является единственным, которое связывает воедино все n этапов решения задачи.
Найдем для каждого i-ого шага условный оптимальный выигрыш (от этого шага и до конца), если мы подошли к данному шагу с ограничением по общему весу в S (S £ W). Обозначим условный оптимальный выигрыш как 
, а соответствующее ему оптимальное управление – количество выбранных предметов на этом этапе – как 
.
Определим следующее рекуррентное уравнение, выразив функцию в терминах выигрыша шага i=n+1, т.е. рекуррентно свяжем значения 
и 
:
,
где S – варьируемое значение ресурса (S £ W), 
и необходимо определить такое значение 
, при котором выигрыш максимален, т.е.
,
где значение 
берется по всевозможным значениям 
.
При 
(т.е. на последнем шаге) имеем 
, что соответствует получению на последнем n-ом шаге максимальной выгоды от вложения всех доступных ресурсов в n–ый предмет, т.е. выигрыш на этом шаге равен 
, а оптимальное решение равно 
.
Продолжая рассуждения подобным образом, можно дойти до значения i=1. Здесь уже не нужно варьировать S, т.к. точно известно, что суммарный общий вес перед первым шагом равен W:
.
Итак, максимальный выигрыш 
найден. Теперь остается только «прочесть полученные рекомендации» в обратную сторону.
То значение 
, при котором получен максимум 
, есть оптимальное управление на первом шаге i=1. После того, как мы здесь выбираем предметов весом 
, у нас общий вес к распределению уменьшится и к распределению останется вес уже в 
единиц. Тогда при i=2 мы должны взять в качестве оптимального значения 
то решение, которое было получено на этом шаге именно при значении 
, т.е. 
, и т.д. до конца, т.е. до i= n.
Задача об оптимальной загрузке является типичной представительницей класса задач на распределение ресурсов, в которой некоторый ограниченный ресурс распределяется между конечным числом заданных состояний.
Дата добавления: 2022-06-11; просмотров: 18; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!