L_s ^’ = ∑с_j + h_{1 l} ∆b₁ ,

j=k+1

l-1

∆b₁ = b₁ - ∑ a_{1 j} ∙x_j - ∑a_{1 j} .

x_j ЄSj=k+1

Из условий следует, что L_s ^’ не меньше максимального значения величины

∑c_j ∙x_j

x_j ЄG_S

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

∑ a_1j ∙x_j b₁ - ∑ a_1j ∙x_j = b₁ ^’ ,

x_j ЄG_S x_j ЄS

x_j Є {0;1}, x_j ЄG_S ,

Выбор очередной переменной для включения во множество S производится с помощью условия

h_1r (x_r ) = max h_1j (x_j )

x_j ЄG_S

Для выбранной переменной x_r определяются величины H_s (x_r ) и H_s (x_r ), т.е. в S включаются x_r = 1 или x_r = 0.

Если в процессе решения окажется, что во множестве G_S нет элементов, которые могут быть введены во множество S без нарушения ограничения (5), то полученное решение L_s =∑c_j ∙x_j принимается в качестве первого приближенного x_j ЄSрешения L₀ .

Все вершины дерева возможных вариантов, для которых выполняются условия

H_s ≤ L₀ , из дальнейшего рассмотрения исключаются.

Из оставшихся ветвей выбирается ветвь с максимальным значением H_s , и процесс поиска оптимального варианта продолжается. Если в процессе решения будет найдено L_s = ∑c_j ∙x_j > L₀ , то полученное решение принимается

x_j ЄS

в качестве нового приближенного результата. Вычислительная процедура заканчивается, если для оставшихся ветвей выполняется условие H_s ≤ L₀ .

2.2 Практическая часть

Ручной счёт

Данные для расчета:

С≤16

Таблица 4

N	1	2	3	4	5	6	7	8	9	10
Qi	0.17	0.03	0.15	0.09	0.13	0.08	0.07	0.02	0.06	0.04
с(xi)	5	1	4	2	6	3	2	3	1	1
hj	0.034	0.03	0.0375	0.045	0.0217	0.0267	0.035	0.0067	0.06	0.04

Для удобства расчетов проранжируем таблицу 4 в порядке убывания h_j и присвоим новые номера элементам, следующим образом:

Таблица 5

N	1	2	3	4	5	6	7	8	9	10
n	9	4	10	3	7	1	2	6	5	8
Qi	0.06	0.09	0.04	0.15	0.07	0.17	0.03	0.08	0.13	0.02
с(xi)	1	2	1	4	2	5	1	3	6	3
hj	0.06	0.045	0.04	0.0375	0.035	0.034	0.03	0.0267	0.02167	0.0067

Для формирования таблицы 6 произведем расчеты:

1)

8

∑с_j =19>b₁ - ∑ c_j ∙x_j =16-0=16;