=18+10+11+9+19=67.

Индекс квадратности -

Аналогичный расчет позволяет определить максимальные потери, которые составляют 167 ед. Между наилучшим и наихудшим решением имеется разница 100 ед. и существует ещё 118 промежуточных решений.

Лабораторная работа № 6 (4 часа)

Решение задач методом динамического программирования

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

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

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

НЕ нашли? Не то? Что вы ищете?

Реализация названных принципов дает гарантию того, что решение, принимаемое на очередном шаге, окажется наилучшем с точки зрения всего процесса в целом, а не "узких" интересов данного этапа.

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

Такой подход позволяет определить набор условных оптимальных решений. Далее рассматривают аналогичную задачу применительно к предпоследнему этапу процесса, но требует при этом, чтобы желаемый эффект был достигнут не на этом тапе отдельно, а на двух последних этапах вместе взятых, что позволяет найти новый набор условных оптимальных решений. Повторив подобные операции можно решить задачу в целом.

Рассмотрим задачу о распределении дополнительных ресурсов между n функциональными подсистемами. Известны F(X, I) – эффективности i-той функциональной подсистемы, если ей выделено
xi – ресурсов, на которые наложены ограничения:

(1)

Определить такое распределение ресурсов, чтобы эффективность системы была бы наибольшей.

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

Можно было бы вычислить эффективность, соответствующую каждой комбинации:

(x1, x2,…xn):

(1, 1,…) или (1010…)

(2, 1,…) или (11010…)

В этом случае пришлось бы просмотреть вариантов.

Но если возникнет необходимость знать оптимальное решение в случае, когда общий объем ресурсов не превышает bn и составляет 0, 1, 2, … bn, то число вариантов, которые надо было просмотреть, окажется в несколько раз больше:

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

Пусть для любого набора (x1,.x2, …xn) существует аддитивный критерий:

Предположим, что ограничения, наложенные на аргументы xi, такие, что существует верхняя (sup Fn) или нижняя (inf Fn) граница множества аддитивных критериев, т. е.

(2)

Определим набор (x1,.x2, …xn) для соответствующих функций f1(x1), f2(x2) … F(X, I) такой, чтобы, удовлетворив ограничению (1), получить экстремальное значение (2).

Предположим, что из совокупности xi выделена и зафиксирована величина xn. Если в этой ситуации найти экстремальное значение:

то окажется, что значение аддитивного критерия Fn будет зависеть от выбранного значения xn:

При любом значении xn переменные x1,.x2, …xn-1 должны удовлетворять неравенству:

Введя обозначения:

можно утверждать, что

(3)

Таким образом, если известна граница аддитивного критерия , первоначальная задача сводится к одномерной задаче оптимизации.

Имея в виду, что – верхняя (нижняя) границы множества
Fn-1, нетрудно видеть, что задача отыскания полностью совпадает с исходной задачей, - различие лишь в числе переменных.

Следовательно, выделив xn-1 и повторив все предыдущие рассуждения приходим к выводу:

(4)

Систематизируя изложенное, получим рекуррентные зависимости: (5), (4), (3):

(5)

т. к. .

В некоторых задачах целевая функция носит мультипликативный характер:

(6)

В этом случае такие задачи могут быть сведены к задаче с аддитивным критерием с помощью логарифмирование выражения (6). Однако вся процедура для этого случая может быть построена и непосредственно:

Пример:

Пусть n = 3, bn = 4, ai = 1, m = 4.

Ф2(x) – наилучшая эффективность, когда x ресурсов выделяют первой и второй задаче (0 ≤ x ≤ bn).

(j, i) – способ распределения ресурсов соответствующий Ф2(х),

i ресурсов выделяют задаче 1,

j ресурсов выделяют задаче 2.

i + j = x.

Ф3(х) – наивысшая эффективность, когда x ресурсов выделяют трем задачам.

(k, j, i) – способ распределения ресурсов, соответствующий Ф3(х),
k + j + i = x, k ресурсов выделяют задаче 3.

X	f1(x)	f2(x)	f3(x)	Ф2(х)	Ф3(х)	(j, i)	(k, j, i)
0	0	0	0	0	0	0,0	0,0,0
1	0,1	0,2	0,3	0,2	0,3	1,0	1,0,0
2	0,3	0,2	0,3	0,3	0,5	1,1 0,2	1,1,0
3	0,4	0,3	0,4	0,5	0,6	1,2	1,1,1 1,0,2
4	0,4	0,6	0,5	0,6	0,8	1,3 4,0	1,1,2