Комбинирование методов поиска оптимальных решений
Где Wj (Xj), t (x), V:(x) — соответственно показатель экономической эффективности, расход ресурсов и продолжительность выполнении производства j-го вида продукции по х-му варианту, у = 1,…, N. Рассмотрим пример оптимизации эффективности производственной программы (ситуация 3), в котором целевая функция и ограничения задачи имеют вид. Метод динамического программирования может применяться… Читать ещё >
Комбинирование методов поиска оптимальных решений (реферат, курсовая, диплом, контрольная)
Метод динамического программирования может применяться не только как самостоятельный, но и как метод, применяющийся совместно с другими.
Так, одним из важных вопросов при реализации алгоритмов, основанных на методе ветвей и границ, является выбор способа оптимистической оценки вариантов на дереве решений. Такая оценка, как правило, производится с помощью решения вспомогательной (релаксационной) задачи оптимизации. При этом вспомогательную оптимизационную задачу выбирают таким образом, чтобы она, с одной стороны, достаточно точно характеризовала перспективность рассматриваемого варианта, а с другой — решалась достаточно просто.
Рассмотрим пример оптимизации эффективности производственной программы (ситуация 3), в котором целевая функция и ограничения задачи имеют вид.
где Wj (Xj), t (x), V:(x) — соответственно показатель экономической эффективности, расход ресурсов и продолжительность выполнении производства j-го вида продукции по х-му варианту, у = 1,…, N.
Оценку верхней границы решения на дереве вариантов будем вычислять, но формуле 
где.
при ограничении.
При этом третье слагаемое верхней границы будем рассматривать как вспомогательную задачу, решение которой возможно с помощью функционального уравнения динамического программирования.
Решение задачи выполним при N = 4, Т = 25, V = 15 и другим данным, приведенным в табл. 11.3.15.
Таблица 11.3.15
Исходные данные задачи.
j | ||||
|
|
|
| |
|
|
|
| |
|
|
|
| |
|
|
|
|
Последовательность построения дерева вариантов показана на рис. 11.3.2. Расчеты верхней границы приводятся в табл. 11.3.16.
Вспомогательную задачу для оценки верхней границы будем решать табличным способом (табл. 11.3.17 и 11.3.18).
Рис. 11.3.2. Поиск решения на дереве вариантов.
Таблица 11.3.16
Порядок расчетов верхней границы для вершин дерева вариантов.
w yvn-1. | n | T 1 n+1. | н, ю | |||
|
|
|
|
| ||
|
|
|
|
| ||
|
|
|
|
| ||
|
|
|
|
|
Таблица 11.3.17
Определение членов функционального уравнения /7,(71,) для 5= 3.
t3(^> |
|
|
|
На первом ярусе дерева вариантов (см. рис. 11.3.2) имеем верхние границы #,(1) = 52 и #,(2) = 55. Вторая вершина имеет большую границу, поэтому в первую очередь из нее проводим очередное ветвление. По такому же правилу осуществляем и последующие ветвления. На последнем ярусе получаем решение W* = 55 для вектора X* = (2, 1, 1, 2).
Как видим, все верхние границы неветвленных вершин не больше значения W*. Следовательно, полученное решение является оптимальным.
Х. ад. т3 Щ (х2) t2(x2) |
|
|
|
|
|
|