7. Динамическое программирование
Пусть на некоторый период времени Т, состоящий из т лет, планируется деятельность группы промышленных предприятий. В начале планируемого периода на развитие предприятий выделяются основные средства Q0, которые необходимо распределить между предприятиями. В процессе функционирования предприятий выделенные им средства частично расходуются.
Однако каждое из этих предприятий за определенный период времени (хозяйственный год) получает прибыль, зависящую от объема вложенных средств. В начале каждого года имеющиеся средства могут перераспределяться между предприятиями. Требуется определить, сколько средств надо выделить каждому предприятию в начале каждого года, чтобы суммарный доход от всей группы предприятий за весь период времени Т был максимальным.
Процесс решения такой задачи является многошаговым. Шагом управления (планирования) здесь будет хозяйственный год. Управление процессом состоит в распределении (перераспределении) средств в начале каждого хозяйственного года.
Пусть имеется груз, состоящий из неделимых предметов различных типов, который нужно погрузить в самолет грузоподъемностью Р. Стоимость и масса каждого предмета j-го
типа известны и составляют соответственно сj, и pj единиц ( j =1,n ). Требуется определить, сколько предметов каждого типа надо загрузить в самолет, чтобы суммарная стоимость груза
была наибольшей, а масса не превышала грузоподъемности самолета.
Математически задача записывается следующим образом: найти такие целые неотрицательные значения хj ( j =1,n ), которые бы максимизировали функцию
где хj — количество груза j-го типа, позволяющее достичь max f(x).
Процесс решения рассматриваемой задачи не является многоэтапным. Она относится к классу задач целочисленного линейного программирования. Однако ее можно решить методом
динамического программирования. Для этого весь процесс решения потребуется разбить на этапы искусственно. На первом этапе рассматривают всевозможные варианты загрузки самолета предметами первого типа и среди них находят оптимальный. На втором этапе определяют вариант загрузки самолета предметами первого и второго типов и т. д. Процесс решения задачи продолжается до тех пор, пока не будет найден оптимальный вариант загрузки самолета предметами n типов.
7.2 Принцип оптимальности и рекуррентные соотношения
Метод динамического программирования позволяет одну задачу со многими переменными заменить рядом последовательно решаемых задач с меньшим числом переменных. Процесс решения задачи разбивается на шаги. При этом нумерация шагов, как правило, осуществляется от конца к началу.
Основным принципом, на котором базируются оптимизация многошагового процесса, а также особенности вычислительного метода динамического программирования, является
принцип оптимальности Р. Беллмана.
Принцип оптимальности. Оптимальное поведение обладает тем свойством, что каковы бы ни были начальное состояние и начальное решение, последующие решения должны быть оптимальными относительно состояния, полученного в результате первоначального решения.
Принцип оптимальности имеет конструктивный характер и непосредственно указывает процедуру нахождения оптимального решения. Математически он записывается выражением вида
где fn- l − — оптимальное значение эффекта, достигаемого за n − l шагов; п — количество шагов (этапов); — состояние системы на l-м шаге; — решение (управление), выбранное на l-м шаге;Rl — непосредственный эффект, достигаемый на l-м шаге.
«Optimum» в выражении (1) означает максимум или минимум в зависимости от условия задачи.
Все вычисления, дающие возможность найти оптимальное значение эффекта, достигаемого за п шагов, f n (S0 ) , проводятся по формуле (1), которая носит название основного функционального уравнения Беллмана или рекуррентного соотношения. Действительно, при вычислении очередного значения функции fn- l − используются значение функции fn−(l+1) , полученное на предыдущем шаге, и непосредственное значение эффекта R l+1 (S l , U l+1 ) , достигаемого в результате выбора решения Ul+1 при заданном состоянии системы Sl . Процесс вычисления значений функции fn- l (l = 0, n −1) осуществляется при естественном начальном условии f 0 (S n ) = 0 , которое означает, что за пределами конечного состояния системы эффект равен нулю.
Глава 7. Динамическое программирование §1. Примеры задач динамического программирования
В рассмотренных ранее задачах оптимизации решение находилось как бы за один шаг. Однако процедуру принятия решений во многих задачах планирования и управления можно представить как многошаговый процесс, т.е. состоящий из нескольких шагов.
Динамическое программирование — это математический метод оптимизации многошаговых процессов, разработанный в начале 50-х годов американским ученым Р. Беллманом. Его использование позволяет свести решение сложной задачи к последовательному решению серии более простых «подзадач». Название метода связано с тем, что первоначально с его помощью проводилась оптимизация динамических систем, т.е. систем, изменяющихся во времени. Однако затем он стал применяться и для решения задач, в которых временной фактор отсутствует, в частности для задач целочисленного программирования.
В настоящее время динамическое программирование является одним из наиболее распространенных оптимизационных методов, пригодным для решения различных прикладных задач: распределения ресурсов, управления запасами, замены оборудования, и т.п. Типичным примером задачи, для решения которой можно применить этот метод, является следующая задача перспективного планирования.
Пример 1.1. Планируется производственная деятельность фирмы на период времени в n лет. Для ее развития выделены капиталовложения в объеме K, которые нужно распределить по годам планового периода. Известно, что годовой доход фирмы зависит от объема средств, вложенных в начале года. Нужно определить, сколько капиталовложений следует выделить фирме в начале каждого года, чтобы общий доход за n лет был максимальным.
Это типичная задача динамического программирования. Распределение капиталовложений можно представить в виде многошагового процесса, где шагом является выделение средств фирме в начале каждого года планового периода.
Управление uk на k-м шаге (k = ) этого процесса — величина капиталовложений, полученных фирмой в начале k-го года. Управление u в целом представляет собой совокупность всех пошаговых управлений:
Обозначим xk — величину средств, доступных для выделения фирме после k-го года (остаток капиталовложений). Переменная xk характеризует состояние управляемого процесса после k-го шага. Ясно, что
Из этих соотношений видно, что состояние системы в конце любого шага зависит только от предшествующего состояния и управления на этом шаге. Очевидно, что объем средств, выделяемых фирме в текущем году, не может быть больше, чем остаток капиталовложений после предыдущего года. Поэтому управление k-го шага должно удовлетворять неравенству:
Управление u = (u1, u2,…, un), для которого эти условия выполнены, будем называть допустимым.
Обозначим fk(uk) — доход, который получит фирма в k-м году, если ей выделить в начале этого года средства в объеме uk. Функция fk характеризует эффективность управления на k-м шаге.
Общая эффективность управления u оценивается при помощи показателя Z — суммарного дохода фирмы за весь плановый период. Этот показатель равен сумме пошаговых показателей эффективностей (годовых доходов):
Таким образом, задача состоит в выборе таких допустимых управлений , т.е. распределения капиталовложений, при котором функция Z достигнет максимума.
В этом примере многошаговый характер процесса управления, по сути, был задан его условиями, согласно которым средства выделяются в начале каждого года. Однако иногда, чтобы использовать метод динамического программирования, «многошаговость» управления приходится вводить искусственно.
Пример 1.2. Имеется груз, состоящий из неделимых предметов n видов, который нужно погрузить на баржу грузоподъемностью Р. Известны стоимость ck и вес pk каждого предмета k-го вида (k = ). Нужно определить, сколько предметов каждого вида следует погрузить на баржу, чтобы суммарная стоимость груза была максимальной, а его общий вес не превышал грузоподъемности баржи.
Обозначим uk — количество предметов k-го вида, загружаемых на баржу. Тогда математическая модель этой задачи выглядит так:
uk — целые числа для всех k = .
Это задача линейного целочисленного программирования, но для нахождения ее оптимального решения можно использовать динамическое программирование. Для этого процесс загрузки следует представить в виде многошагового управляемого процесса, состоящего из n шагов, причем на каждом шаге баржа загружается предметами одного вида.
Будем считать, что на первом шаге баржа загружается предметами первого вида, на втором шаге — второго вида и т.д. Управление uk на k-м шаге (k = ) — это количество предметов k-го вида, загружаемых на баржу. Параметры состояния xk на k-м шаге — это количество груза, которое еще можно погрузить на баржу после того как на нее погрузили предметы первых k видов. Ясно, что
Так как на каждом шаге должны выполняться неравенства xk ≥ 0, то управления на каждом шаге должны удовлетворять неравенствам:
Управление u = (u1, u2,…, un), для которого эти условия выполнены, назовем допустимым.
Эффективность управления на k-м шаге определяется стоимостью всех предметов, загруженных на этом шаге, т.е. она равна ckuk. Эффективность всего процесса управления Z равна сумме эффективностей всех шагов, т.е. суммарной стоимостью загруженных предметов:
Оптимальное управление доставляет максимальное значение этой функции на множестве всех допустимых управлений.
Пример 1.3. Решается задача оптимального распределения дефицитного ресурса (сырье, оборудование, инвестиции) между n объектами, причем общий объем ресурса равен S. Для каждого объекта считается известной зависимость между размером ресурса и величиной прибыли, полученной в результате выделения ресурса данному объекту. Эта зависимость, вообще говоря, имеет нелинейный характер. Нужно найти распределение ресурса, дающее максимальную общую прибыль.
Обозначим fk(uk) (k = ) — величину прибыли, получаемую от k—го объекта при выделении ему ресурса в объеме uk. единиц. Математическая модель этой задачи имеет следующий вид:
Z = f1(u1) + … + fn(un) → max,
Это задача нелинейного программирования. Если все функции fk вогнутые, то она является задачей выпуклого программирования, и ее оптимальное решение можно найти при помощи какого-либо метода решения задач этого класса, например, при помощи метода множителей Лагранжа. Если же хотя бы одна из функций прибыли не является вогнутой, то использование методов нелинейного программирования может не привести к нужному результату, так как в этом случае найденный локальный максимум может не быть глобальным (см. п.6 §2 главы 5).
В такой ситуации для нахождения оптимального решения целесообразно использовать аппарат динамического программирования. Для этого нужно, представить распределение ресурса как многошаговый процесс, состоящий из n шагов, причем на каждом шаге ресурс выделяется одному из объектов. Будем считать, что на первом шаге ресурс выделяется первому объекту, на втором шаге — второму и т.д.
Управление uk на k-м шаге (k = ) — это количество ресурса, выделяемого k-му объекту, а параметры состояния xk — это остатки ресурса после его выделения первым k объектам, задаваемые формулами:
Управление uk на каждом шаге должно удовлетворять условию:
Управление u = (u1, u2,…, un), для которого эти условия выполнены, будем называть допустимым.
Эффективность управления uk на k-м шаге определяется величиной прибыли, получаемой от k—го объекта, т.е. она равна fk(uk). Эффективность всего процесса управления Z равна сумме эффективностей всех шагов:
Оптимальное управление доставляет максимальное значение этой функции на множестве всех допустимых управлений.