<<
>>

Алгоритм решения задачи.

1 шаг. Положим ho = 0. Определим контур m положительной длины. Если таких контуров нет, то задача решена (h = h0 = 0). Если L(mj) > 0, то полагаем длины дуг равными 1ij- hi, где

h1 = LiO

1 n(m)

(h(m) - число дуг контура ц).

k-й шаг.

Определяем контур |mk положительной длины, при длинах дуг lij- hk-1. LkЕсли Lk = L(mk) < 0, то h = hk-1. Если L(mk) > 0, то определяем

1

hk =—Lk, nk

где nk = n(mk), и переходим к следующему шагу.

За конечное число шагов будет получена величина h такая, что в графе отсутствуют контуры положительной длины при длинах дуг 1ij - h. Соответствующие потенциалы вершин {1i} и величина h определяют оптимальное решение задачи (1.2.11), а значит (1.2.10) и (1.2.7). Определив 5i, мы можем найти уi и, следовательно, получить полное описание операции.

Пример 1.2. Возьмем t11 = 2, t21 = 3, t12 = 1, t22 = 2. Имеем

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

Х,о X

12 22

1 21 2

q21 = max

X,, X

11 21

= max | —;— I = —. 2 3 0 3

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

Усиление контура

(1,2,1) равно 4/3 > 1. Следовательно, e = у^, w1 = 1, w2 = л/3 . Имеем

= 1

Q1 = 1, Q2 =

max| QL;Q2|- mini Q1 ; Q

X, , X

X, , X

11 12

51 =

0,09

11 12

max| | + min| Q1 • Q2

X, , X

X, , X

11 12

11 12

max| -QL;Q2 j-mini Q1 • Q2

Хо, X

Хо, X

21 22

52 =

< 0,06 .

21 22

^ Q1 Q21

^ Q1 • Q21

max

+ min

V 21 22 0

VT 21 22 0

Соответственно получаем

Q1 Q2

0,92

VT

0,94

max

V 11 12 0

(

Q1 Q2

y1 =(1 -51 )•

max

y2

3

V 21 L22

= (1 -52 )•

<< | >>
Источник: Баркалов С.А., Бурков В.Н., Гилязов Н.М.. Методы агрегирования в управлении проектами. М.: ИПУ РАН, 1999- 55 с.. 1999

Еще по теме Алгоритм решения задачи.: