Рассмотрим алгоритм решения задачи методом ветвей и границ с простым и эффективным способом оценки верхней границы целевой функции.
Обозначим: U - множество переменных xj; S - множество фиксированных переменных, вошедших в допустимое решение; Es - множество зависимых переменных, которые не могут быть включены в множество S, так как для них выполняется неравенство
аij> bi - ?аij•xj, i=1, …,m
xjЄS
GS - множество свободных переменных, из которых производится выбор для включения в S очередной переменной.
Рассмотрим первоначально одномерную задачу, когда m=1 и задача (4) имеет только одно ограничение вида (5).
Обозначим h1j = cj/a1j и допустим, что xjЄS (j=1, …,k<n) и выполняются условия
h1,k+1? h1,k+2? …? h1l, l?n,
l
?a1j>b1 - ? a1j•xj,
j=k+1 xjЄS
l-1
?a1j? b1 - ? a1j•xj,
Условия означают, что во множество S без нарушения неравенства (5) можно дополнительно ввести элементы xk+1, xk+2, …, xl-1. При введении во множество S элементов xk+1, xk+2, …, xl неравенство (5) не выполняется.
Для определения верхней границы решения может быть использовано выражение
Hs =?cj•xj + Ls',
где
Ls' = ?сj + h1l? b1 ,
j=k+1
? b1 = b1 - ? a1j•xj - ?a1j.
xjЄS j=k+1
Из условий следует, что Ls' не меньше максимального значения величины
?cj•xj
xjЄGS
при ограничениях
? a1j •xj b1 - ? a1j•xj = b1',
xjЄGS xjЄS
xjЄ {0;1}, xjЄGS ,
Выбор очередной переменной для включения во множество S производится с помощью условия
h1r(xr) = max h1j(xj)
2.2 Практическая часть
Ручной счёт
Данные для расчета:
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)
hj
0.034
0.0375
0.045
0.0217
0.0267
0.035
0.0067
Таблица 5
n
0.02167
№
S
Es
Gs
Hs
xr
Hs(xr)
L0
1…10
0.61
x1
0.5767
2…10
x2
0.5734
x1,x2
3…10
x3
0.5967
x1,x2,x3
4…10
x4
0.56167
x1,x2,x3,x4
5…10
x5
0.5934
x1,x2,x3,x4,x5
6…10
x6
0.56334
x1,x2,x3,x4,x5,x6
8,9,10
x7
x1,x2,x3,x4,x5,x6,x7
-
Страницы: 1, 2, 3, 4
