Тема 10. Поиск наилучших решений методами динамического программирования Лекция 10. Поиск наилучших решений методами динамического программирования

При поиске наилучших решений в оптимизационных задачах методами классического математического анализа предполагается следующее:

1. Этот анализ предназначен для непрерывных функций (переменных) и их производных. В действительности переменные могут быть дискретными (булевыми, целочисленными).

2. Обращение в нуль первой производной есть необходимое, но недостаточное условие наличия экстремума (существуют точки перегиба).

3. Отсутствие ограничений в виде неравенств. Во всех темах, где мы встречались с задачами оптимизации, ограничения обязательно присутствуют.

4. Требование единственной точки экстремума (обязательного условия выпуклости функций) может и не выполняться.

Преимущества динамического метода оптимизации Гамильто- на – Якоби – Беллмана перед методами классического математического анализа состоят в следующем.

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

2. Наличие ограничений на переменные не усложняет, а упрощает определение экстремума, поскольку сокращается число анализируемых вариантов.

3. Метод пригоден и для непрерывных переменных, если заранее оговорить точность отыскиваемого решения.

4. Безусловность выполнения принципа оптимальности: оптимальное решение на каждом последующем шаге ищется относительно решения, найденного на предыдущем шаге.

5. Возможность получения не единственного оптимального решения, что позволяет лучше учесть особенности экономической ситуации.

6. Возможность использования метода для многомерных задач (например, при распределении множества ресурсов).

Метод Гамильтона – Якоби – Беллмана носит и другое название метода динамического программирования (МДП).

Приведем конкретный пример использования этого метода МДП.

Пример. Самолет загружается неделимыми предметами трех типов, каждый весом: P₁ = 34, P₂ = 28, P₃ = 25 кг, и стоимостью, соответственно, С₁ = 100, С₂ = 70, С₃ = 65 денежных единиц за предмет. Грузоподъемность самолета P_с=100 кг. Сколько предметов каждого типа X_j надо загрузить, чтобы суммарная стоимость перевозки была максимальной?

1. Если самолет загружать только предметами первого типа (вариант, для которого n = 1), то максимальная стоимость груза составит:

C₁X₁ = f₁(P_c) (1)

Естественно, что P₁X₁  P_с и тогда X₁ P_c/ P₁. Значит, для первого варианта (n = 1) максимальную стоимость груза можно будет записать, равной:

С₁( P_с / P₁) = f₁(P_c) (2)

2. При загрузке самолета предметами и первого X₁, и второго типа X₂ (вариант n = 2) в самолет нельзя взять больше, чем разницу (P_с  P₂X₂) предметов первого типа. Тогда стоимость предметов первого типа будет:

f₁(P_с  P₂X₂) (3)

Отсюда максимальная стоимость груза для предметов первого и второго типа ( для варианта n = 2) составит значение:

f₂(P_с) = max [f₁(P_с  P₂X₂) + C₂X₂] (4)

При этом, значение: 0  X₂  P_с / P₂ (5)

3. Для стоимости, при загрузке тремя типами груза (n = 3), получим формулу:

f₃(P_с) = max [f₂(P_с  P₃X₃) + C₃X₃] (6)

При этом, значение: 0  X₃  P_с / P₃ (7)

4. Следовательно, для любого конечного значения n предметов можно записать:

f_n(P_с) = max [f_n-1(P_с  P_nX_n) + C_nX_n] (8)

При этом, значение: 0  X_n  P_с / P_n (9)

Обращаем ваше внимание на то, что число предметов можно интерпретировать, как число шагов по объектам любой природы. Это значит, что в рекуррентной формуле (8) заложен алгоритм решения любых распределительных задач. К их числу относятся: транспортные перевозки, планирование производственной программы, распределение и замена оборудования, производство и хранение продукции, поставки сырья, распределение нагрузки по генераторам электростанций и другие.

Полученные результаты по этому алгоритму для нашей задачи следует сопоставить с решением этой же задачи для линейной целевой функции:

Z =  P_jX_j  max (10)

Ограничение относится только к грузоподъемности самолета:

34X₁ + 28X₂ + 25X₃  100 (11)

Решение задачи (10) – (11) дает следующее: Для нецелочисленных переменных значение Z = 294,12 денежных единиц. Оптимальные значения переменных X₁ = 2,941; X₂ = 0; X₃ = 0.

Для целочисленных переменных значение Z = 270 денежных единиц. Оптимальные значения переменных X₁ = 2; X₂ = 1; X₃ = 0. Причем, в запасе остается еще 4 кг груза.

Метод Гамильтона – Якоби – Беллмана имеет глубокие математические обоснования [9]. Различают два понятия: программа управления и синтез. Программа управления отождествляется с принятием решений на перспективу и возможной потери свойств оптимальности. Синтез – отслеживание и принятие оперативных решений без потери свойств оптимальности. Синтез обеспечивает определение оптимального управления экономикой в каждый момент времени для любого состояния экономики и для любых начальных условий.

Для непрерывных переменных метод Гамильтона – Якоби  Беллмана позволяет отыскивать оптимальные решения путем решения задачи Коши для системы обыкновенных дифференциальных уравнений. Весь вычислительный процесс при этом опирается на теорему о достаточных условиях оптимальности.

Для дискретных переменных (и многошаговых процедурах) используются рекуррентные функциональные уравнения типа (8). Приведем следующий пример решения оптимизационной задачи и покажем ее преимущества для качества информационных ресурсов.

Пример. Управление ресурсами для экономического развития четырех заводов.

Каждому из четырех заводов (n = 4) запланирован прирост продукции в количестве g_i (x) в зависимости от суммы выделенного капитала . Требуется распределить общую сумму выделенного капитала между заводами так, чтобы общий прирост выпуска продукции был максимальным.