logo
Методичка по исследованию операций

2.8. Иллюстративный пример

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

Графическое представление (рис. 2.4).

Рис. 2.4

Матричное представление:

1

2

3

4

5

6

7

1

2

4

3

5

6

7

Еi

1

×

4

5

9

2

1

×

4

9

5

2

Е0

2

×

5

6

2

×

5

6

Е1

3

×

3

7

→

4

×

10

8

4

10

×

8

3

×

3

7

Е2

5

×

1

5

×

1

Е3

6

×

3

6

×

3

7

×

7

×

Е4

Решаем задачу на max F прямым ходом.

Условная opt-ция (вычислительная схема) проводится по формуле I(ak) = I(ak–1) + v(ak–1, ak):

I(a0)

(a0, a1)

I(a1)

(ai, a2), i < 2

I(a2)

1(0)

(1, 2) →0 + 4 = 4

2(4)

(1, 6) → 0 + 2 = 2

6(9)

(1, 4) →0 + 9 = 9

4(9)

(2, 6) → 4 + 5 = 9

(4, 3) → 9 + 10 = 19

3(19)

(1, 3) → 0 + 5 = 5

(ai, a3), i < 3

I(a3)

(ai, a4), i < 4

I(a4)

(4, 5) →9 + 8 = 17

5(22)

(6, 7) → 9 + 3 = 12

7(26)

(3, 5) →19 + 3 = 22

(2, 7) → 4 + 6 = 10

(5, 7) → 22 + 1 = 23

(3, 7) → 19 + 7 = 26

1) max F = I(7) = 26.

Безусловная opt-ция проводится обратным ходом по вычислительной схеме:

2) S(a4, a0) = S(7, 1) = ‹7 ← 3 ← 4 ← 1› = <7, 3, 4, 1>

S(1, 7) = ‹1, 4, 3, 7›!

Задача решена.

Обратным ходом решение выглядит аналогично.

Условная opt-ция: I(ak) = I(ak+1) + v(ak, ak+1):

I(a4)

(a3, a4)

I(a3)

(a2, ai), i > 2

I(a2)

7(0)

(5, 7) →0 + 1 = 1

5(1)

(6, 7) → 0 + 3 = 3

6(3)

(3, 5) → 1 + 3 = 4

(3, 7) → 0 + 7 = 7

3(7)

(ai, ai), i > 1

I(a1)

(a0, ai), i > 0

I(a0)

(2, 6) → 3 + 5 = 8

2(8)

(1, 6) → 3 + 2 = 5

1(26)

(2, 7) → 0 + 6 = 6

(1, 2) → 8 + 4 = 12

(4, 5) → 1 + 8 = 9

4(17)

(1, 4) → 17 + 9 = 26

(4, 3) → 7 + 10 = 17

(1, 3) → 7 + 5 = 12

1) max F = I(1) = 26.

Безусловная opt-ция проводится прямым ходом по вычислительной схеме:

2) S(a0, a4) = ‹1 ← 4 ← 3 ← 7› = ‹1, 4, 3, 7›.

Задача решена.

Построение opt деревьев в обоих случаях предоставляется читателю.

Yandex.RTB R-A-252273-3
Yandex.RTB R-A-252273-4