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

L=∑c_j ∙x_j (4)

j=1

при ограничениях

n

∑а_ij ∙x_j ≤b_i , i=1, …,m(5)

j=1

x_j Є{0;1}, j=1, …,n

причем с_j ≥0, a_ij ≥0.

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

Эффективность вычислительных алгоритмов зависит от точности и простоты способа определения верхней границы возможных решений и точности определения приближенного решения. Чем точнее способ определения верхней границы целевой функции, тем больше бесперспективных ветвей отсекается в процессе оптимизации. Однако увеличение точности расчета верхних границ связано с возрастанием объема вычислений. Например, если для оценки верхней границы использовать симплекс-метод, то результат будет достаточно точным, но потребует большого объема вычислительной работы.

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

Обозначим: U – множество переменных x_j ; S – множество фиксированных переменных, вошедших в допустимое решение; E_s – множество зависимых переменных, которые не могут быть включены в множество S, так как для них выполняется неравенство

а_ij > b_i - ∑а_ij ∙x_j , i=1, …,m

x_j ЄS

G_S – множество свободных переменных, из которых производится выбор для включения в S очередной переменной.

Рассмотрим первоначально одномерную задачу, когда m=1 и задача (4) имеет только одно ограничение вида (5).

Обозначим h_{1 j} = c_j /a_{1 j} и допустим, что x_j ЄS (j=1, …,k<n) и выполняются условия

h_{1, k +1} ≥ h_{1, k +2} ≥ …≥ h_{1 l} , l≤n,

l

∑a_{1 j} >b₁ - ∑ a_{1 j} ∙x_j ,

j=k+1x_j ЄS

l-1

∑a_{1 j} ≤b₁ - ∑ a_{1 j} ∙x_j ,

j=k+1 x_j ЄS

Условия означают, что во множество S без нарушения неравенства (5) можно дополнительно ввести элементы x_{k +1} , x_{k +2} , …, x_{l -1.} При введении во множество S элементов x_{k +1} , x_{k +2} , …, x_l неравенство (5) не выполняется.

Для определения верхней границы решения может быть использовано выражение

H_s =∑c_j ∙x_j + L_s ^’ ,

x_j ЄS

где