Пример 2.

Математическая формулировка задачи имеет следующий вид:

Решение.

Перепишем задачу в форме е-ограничений: с учетом .Функция Лагранжа имеет следующий вид:

Подставляя сюда выражения для , и используя метод неопределенных множителей Лагранжа, получаем:

Заметим, что функция не обязательно должна быть «основной», а функции должны выполнять роль ограничений.

Рассматриваемая задача может быть записана в ином виде, например:

с учетом ограничений ,

Функция Лагранжа для задачи, записанной в этой форме, имеет следующий вид:

Решая эту задачу с помощью метода неопределенных множителей Лагранжа, получим:

Результаты решения рассматриваемой задачи приведены в табл. 2.

Таблица 2

Неулучшаемые решения задачи


6,88	17,29	19,73	111.93	0,42	0,19
8,25	32,06	10,06	80,56	0,50	0,50
9,63	52,70	6,14	54,84	0,70	1,00
11,00	79,00	8,00	35,00	1,00	2,00
12,38	111,22	15,66	20.86	2,17	5,17

На рис. 6 представлено множество неулучшаемых решений (множество Парето) в

пространстве управляемых переменных .

6. Постановка задачи динамического программирования

Динамическое программирование – это поэтапное планированиемногошагового процесса, при котором на каждом этапе оптимизируется толькоодин шаг. Управление на каждом шаге должно выбираться с учетом всех его последствий в будущем. В общем виде постановка задачи ДП сводится к следующему. Имеется некоторая управляемая операция или целенаправленное действие, распадающаяся естественно или искусственно на n шагов. На каждом шаге осуществляется распределение и перераспределение ресурсов, участвующих в операции, с целью улучшения ее результата в целом. Это распределение ДП называется управлением операции и обозначается Y.

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

w(u) = w(u1,u2,…,un).

Управление, при котором показатель достигает максимума, называется оптимальным управлением.

w(u^*) = max w(u)

Оптимальное управление многошаговым процессом состоит из совокупности оптимальных пошаговых управлений.

u* = (u₁^*, u₂^*,…,u_n^*)

Задача ДП – определит оптимальное управление на каждом шаге и тем самым оптимальное управление всей операцией в целом.

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

Выделим особенности модели динамического программирования:

- задача оптимизации интерпретируется как n-шаговый процесс управления;

- целевая функция равна сумме целевых функций каждого шага;

- выбор управления на k-м шаге зависит только от состояния системы к этому шагу и не влияет на предшествующие шаги (нет обратной связи);

- состояние s_k после k-го шага управления зависит только от предшествующего состояния s_k_-1 и управления Х_k (отсутствие последействия);

- на каждом шаге управление Х_k зависит от конечного числа управляющих переменных, а состояние s_k - от конечного числа параметров.