Автор работы: Пользователь скрыл имя, 04 Февраля 2011 в 15:29, шпаргалка
Работа содержит ответы к Госам по дисциплине "Бухгалтерский учет".
h надо сделать с удаленными вариантами (т.е. 1,4).
1 2 3 5 6 Cij
| 1 | 15 | 29 | 24 | |
| 15 | 13 | 5 | 0 | |
| 0 | 9 | 2 | 2 | |
| 2 | 41 | 22 | 0 | |
| 13 | 0 | 0 | 0 |
2
3
4
5
6
Графически появляется 1,4.
Надо
запретить 4,1. Затем осуществляется
приведение матрицы по строкам и
столбцам.
1 2 3 5 6 Cij
| 14 | 28 | 23 | ||
| 15 | 13 | 5 | 0 | |
| 0 | 9 | 2 | 2 | |
| 2 | 41 | 22 | 0 | |
| 13 | 0 | 0 | 0 |
2 14+2=16
3 5+0=5
4 2+0=2
5 2+0=2
6 0+0, 0+9, 0+2
2 3 5 6 Cij
| 13 | 5 | 0 | |
| 9 | 2 | 2 | |
| 41 | 22 | 0 | |
| 0 | 0 | 0 |
3
4 2
5
6
2 3 5 6 Cij
| 13 | 5 | ||
| 7 | 0 | 0 | |
| 22 | |||
| 0 | 0 |
3 5+0=5
4 0+0, 0+0
5 22+0
6 0+13=13, 0+7=7, 0+0=0
Каждый раз просматриваем концевые вершины, чтобы определить вершины ветвления !
2 3 5 Cij
| 13 | 5 | |
| 7 | 0 | |
| 0 | 0 |
3 5
4
6
2 3 5 Cij
| 7 | 0 | |
| 0 | 0 |
3 8+0=8
4 7+0=7
6 0+8, 0+7
2 3 Cij 2 3 Cij
| 7 | |
| 0 |
| 0 | |
| 0 |
4 4
6 6
Получается матрица 2х2, из которой очевидным образом выявляются недостающие звенья Гамильтонова контура:
НО по правилам ветвления предстоит вернуться в вершину , так как из 3х чисел 63, 64, 58 – 58 самое маленькое число.
Возвращаемся к таблице того размера и того состояния, которое было после первого ветвления. Поскольку это ветвление осуществляется из , следует запретить там 1,4. Из-за этого запрета не будет наибольшей та , которая была. Появится ветвление на и 6,3. Это можно увидеть, так как 0+9.
Далее все так же: появится 67, 63.
Таким образом, оптимальным решением будет Гамильтонов контур:
1 – 4 – 3 – 5 – 6 – 2 – 1
L*=16+25+5+5+5+7=63
Комментарий к матрице 1: На первой итерации W(x)=h – сумме приводящих констант. В последующих W(x)= = границе издержек соответствующей концевой вершины.
Комментарий к матрице 3: Здесь запрещаетяс маршрут, ведение которого приводит к контуру (не Гамильтонову).
Комментарий к матрице 9: В матрице 2х2 остаются 2 маршрута, ведение которых и создает искомый Гамильтонов контур.
Комментарий к шагу 12: Здесь запрещается маршрут, указание на запрещение которого содержит выбранная на шаге 7 концевая вершина.
W(x)=48
48+1=49
58
58+9=67 63 49+16=65 49+
51+22=73 51+5=56
56+8=64
56+7=63
1 4
6
2
3
5
1 5
2 6
3
7
нет
4
10
нет
8
да
да
9
11
12