РЕШЕНИЕ ЗАДАЧИ «Расчет кратчайшей сети заданной конфигурации»
Л.И.
Абросимов,
(г. Москва, Московский
энергетический институт (Технический университет), Россия
)
Формулировка
задачи
Задана конфигурация сети
S- последовательная
двунаправленная шина, дуги которой соединяют узлы ai
1ó2ó3ó4ó5ó6ó7ó8ó9
Конфигурацию S можно записать в виде
матрицы S.
Матрица S:
|
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
2 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
|
3 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
|
4 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
|
5 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
|
6 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
|
7 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
|
8 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
|
9 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
Рисунок
1
Известно также распределение
точек ba в
пространстве:
Расстояния между точками
также записываются в виде матрицы M.
Требуется распределить узлы
по точкам ba , размещённым в
пространстве на расстоянии
mab друг от друга таким образом, чтобы
суммарная взвешенная длина рассматриваемой сети была
минимальной.
Матрица M:
|
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
1 |
0 |
15 |
24 |
25 |
50 |
70 |
75 |
60 |
100 |
|
2 |
15 |
0 |
15 |
11 |
35 |
55 |
50 |
48 |
90 |
|
3 |
24 |
15 |
0 |
25 |
50 |
70 |
75 |
60 |
100 |
|
4 |
25 |
11 |
25 |
0 |
25 |
45 |
40 |
35 |
60 |
|
5 |
50 |
35 |
50 |
25 |
0 |
40 |
30 |
26 |
70 |
|
6 |
70 |
55 |
70 |
45 |
40 |
0 |
12 |
30 |
40 |
|
7 |
75 |
50 |
75 |
40 |
30 |
12 |
0 |
18 |
28 |
|
8 |
60 |
48 |
60 |
35 |
26 |
30 |
18 |
0 |
40 |
|
9 |
100 |
90 |
100 |
60 |
70 |
40 |
28 |
40 |
0 |
Рисунок
2
Иначе говоря, требуется
«раскидать шары по лункам».
a1
ai …
a9
b1
ba
…
b9
Рисунок
3
Распределение записывается в
виде списка y таким образом:
y={ai}.
В списке перечисляются номера 
гнёзд
ba
, а порядок i их размещения в списке по
номерам i узлов ai. Например,{2, 4, 5….}
означает, что 1-й узел сети «положили» во 2-е гнездо, 2-ой узел – в 4-е гнездо и
т. д.
Решение задачи.
Алгоритм
решения.
1. Исходные данные:
N=9, || Sij
||, i,j=1,…,N; || mab || , a,b=1,…,N; Начальное значение целевой
функции Q0=∞;
{yi}*= {0}
(i=1,…,N), ω = № варианта mod 9 = 1 mod 9 = 1
2. Формирование для варианта
ω исходного списка {yi}ω по соотношению (1)
для
i=1,…, N:
(i + ω –1) для 1
≤ i ≤ (N –ω +1);
yi ω =
(1)
(i + ω – N –1) для i
> (N –ω +1).
3. Расчёт цен Сi
0ω для i=1,…, N по соотношению (2) и
формирование списка {Сi
0ω}
|
|
(2) |
|
|
|
4. Расчёт цен
Сij
Пω для i,j=1,…,N по соотношению (3) и
формирование матрицы
||Сij
Пω||
|
|
(3) |
5.
Расчёт оценки Qijω по соотношению
(4).
(4)
6. Расчёт минимальной
оценки min Q и фиксирование номеров
i*,j*, которые соответствуют min Q.
7. Проверка, если
min Q <0, то перейти к п. 8,
иначе – к п. 9.
8. Корректировка исходного
списка {yi}ω за счёт перестановок
p:=yi* , v:=yj*
yi*:=v , yj*:=p и переход к
п.3
9. Расчёт Qω
по
соотношению (5)
N=9
N=9
Qω = ∑ ∑ Sij · myi
yj
(5)
i=1
j=1
10. Если Qω < Q0, то перейти к п.11, если
Qω≥Q0, то перейти к
п.12
11. Корректировка
оптимального значения целевой функции Q0 := Qω и списка оптимального решения {yi}*={yi}ω
12. Корректировка номера
исходного варианта ω:=ω+1
13. Если номер исходного
варианта ω≤N, то перейти к п.2, иначе –
к п.14
14. Вывод результата расчёта
оптимального значения целевой функции Q0 и списка оптимального решения {yi}*.
Пример пошагового решения задачи по заданным выше исходным данным, соответствующим П1
Для иллюстрации представим расположение в
пространстве гнезд соответствующее матрице М следующим
образом:
b6
b1
b7
b 2
b 5
b9
b 4
b3
b8
Рисунок 4
П.2
алгоритма
Для первого варианта ω =
1
y
= { 1, 2, 3, 4, 5, 6, 7, 8, 9}
Рисунок
5
П.3
алгоритма
Итерация 1:
С1
01
=S[1,1]*m[1,1] + S[1,1]*m[1,1] + S[1,2]*m[1,2] + S[2,1]*m[2,1] +
S[1,3]*m[1,3] + S[3,1]*m[3,1] + S[1,4]*m[1,4] + S[4,1]*m[4,1] + S[1,5]*m[1,5] +
S[5,1]*m[5,1] + S[1,6]*m[1,6] + S[6,1]*m[6,1] + S[1,7]*m[1,7] + S[7,1]*m[7,1] +
S[1,8]*m[1,8] + S[8,1]*m[8,1] + S[1,9]*m[1,9] +
S[9,1]*m[9,1]
С2
01 =S[2,1]*m[2,1] +
S[1,2]*m[1,2] + S[2,2]*m[2,2] + S[2,2]*m[2,2] + S[2,3]*m[2,3] +
S[3,2]*m[3,2] + S[2,4]*m[4,2] + S[4,2]*m[4,2] + S[2,5]*m[2,5] +
S[5,2]*m[5,2] + S[2,6]*m[2,6] + S[6,2]*m[6,2] + S[2,7]*m[2,7] + S[7,2]*m[7,2] +
S[2,8]*m[2,8] + S[8,2]*m[8,2] + S[2,9]*m[2,9]+
S[9,2]*m[9,2]
С3
01=S[3,1]*m[3,1]
+ S[1,3]*m[1,3] + S[3,2]*m[3,2] + S[2,3]*m[2,3] + S[3,3]*m[3,3] +
S[3,3]*m[3,3] + S[3,4]*m[3,4] + S[4,3]*m[4,3] + S[3,5]*m[3,5] +
S[5,3]*m[5,3] + S[3,6]*m[3,6] + S[6,3]*m[6,3] + S[3,7]*m[3,7] + S[7,3]*m[7,3] +
S[3,8]*m[3,8] + S[8,3]*m[8,3] + S[3,9]*m[3,9] +
S[9,3]*m[9,3]
С4
01
=S[4,1]*m[4,1] + S[1,4]*m[1,4] + S[4,2]*m[4,2] + S[2,4]*m[2,4] +
S[4,3]*m[4,3] + S[3,4]*m[3,4] + S[4,4]*m[1,1] + S[4,4]*m[1,1] +
S[4,5]*m[4,5] + S[5,4]*m[5,4] + S[4,6]*m[4,6] + S[6,4]*m[6,4] +
S[4,7]*m[4,7] + S[7,4]*m[7,4] + S[4,8]*m[4,8] + S[8,4]*m[8,4] + S[4,9]*m[4,9]+
S[9,4]*m[9,4]
С5
01
=S[5,1]*m[5,1] + S[1,5]*m[1,5] + S[5,2]*m[5,2] + S[2,5]*m[2,5] + S[5,3]*m[5,3] +
S[3,5]*m[3,5] + S[5,4]*m[5,4] + S[4,5]*m[4,5] + S[5,5]*m[5,5] +
S[5,5]*m[5,5] + S[5,6]*m[5,6] + S[6,5]*m[6,5] + S[5,7]*m[5,7] +
S[7,5]*m[7,5] + S[5,8]*m[5,8] + S[8,5]*m[8,5] + S[5,9]*m[5,9] +
S[9,5]*m[9,5]
С6
01
=S[6,1]*m[6,1] + S[1,6]*m[1,6] + S[6,2]*m[6,2] + S[2,6]*m[2,6] + S[6,3]*m[6,3] +
S[3,6]*m[3,6] + S[6,4]*m[6,4] + S[4,6]*m[4,6] + S[6,5]*m[6,5] +
S[5,6]*m[5,6] + S[6,6]*m[6,6] + S[6,6]*m[6,6] + S[6,7]*m[6,7] +
S[7,6]*m[7,6] + S[6,8]*m[6,8] + S[8,6]*m[8,6] + S[6,9]*m[6,9] +
S[9,6]*m[9,6]
С7
01
=S[7,1]*m[7,1] + S[1,7]*m[1,7] + S[7,2]*m[7,2] + S[2,7]*m[2,7] + S[7,3]*m[7,3] +
S[3,7]*m[3,7] + S[7,4]*m[7,4] + S[4,7]*m[4,7] + S[7,5]*m[7,5] + S[5,7]*m[5,7] +
S[7,6]*m[7,6] + S[6,7]*m[6,7] + S[7,7]*m[7,7] + S[7,7]*m[7,7] +
S[7,8]*m[7,8] + S[8,7]*m[8,7] + S[7,9]*m[7,9]+
S[9,7]*m[9,7]
С8
01
=S[8,1]*m[8,1] + S[1,8]*m[1,8] + S[8,2]*m[8,2] + S[2,8]*m[2,8] + S[8,3]*m[8,3] +
S[3,8]*m[3,8] + S[8,4]*m[8,4] + S[4,8]*m[4,8] + S[8,5]*m[8,5] + S[5,8]*m[5,8] +
S[8,6]*m[8,6] + S[6,8]*m[6,8] + S[8,7]*m[8,7] + S[7,8]*m[7,8] +
S[8,8]*m[8,8] + S[8,8]*m[8,8] + S[8,9]*m[8,9] +
S[9,8]*m[9,8]
С9
01
=S[9,1]*m[9,1] + S[1,9]*m[1,9] + S[9,2]*m[9,2] + S[2,9]*m[2,9] + S[9,3]*m[9,3] +
S[3,9]*m[3,9] + S[9,4]*m[9,4] + S[4,9]*m[4,9] + S[9,5]*m[9,5] + S[5,9]*m[5,9] +
S[9,6]*m[9,6] + S[6,9]*m[6,9] + S[9,7]*m[9,7] + S[7,9]*m[7,9] +
S[9,8]*m[9,8] + S[8,9]*m[8,9] + S[9,9]*m[9,9] +
S[9,9]*m[9,9]
С
01
={30, 60, 80, 100, 130, 104, 60 , 116, 80 }
П.
4
алгоритма
С11
Пω
=
S[1,1]*m[1,1] + S[1,1]*m[1,1] + S[1,2]*m[1,2] + S[2,1]*m[2,1] +
S[1,3]*m[1,3] + S[3,1]*m[3,1] + S[1,4]*m[1,4] + S[4,1]*m[4,1] + S[1,5]*m[1,5] +
S[5,1]*m[5,1] + S[1,6]*m[1,6] + S[6,1]*m[6,1] + S[1,7]*m[1,7] + S[7,1]*m[7,1] +
S[1,8]*m[1,8] + S[8,1]*m[8,1] + S[1,9]*m[1,9] + S[9,1]*m[9,1] + S[1,1]*m[1,1] +
S[1,1]*m[1,1]
С12
Пω
=
S[1,1]*m[2,1] + S[1,1]*m[1,2] + S[1,2]*m[2,2] + S[2,1]*m[2,2] + S[1,3]*m[2,3] +
S[3,1]*m[3,2] + S[1,4]*m[2,4] + S[4,1]*m[4,2] + S[1,5]*m[2,5] + S[5,1]*m[5,2] +
S[1,6]*m[2,6] + S[6,1]*m[6,2] + S[1,7]*m[2,7] + S[7,1]*m[7,2] + S[1,8]*m[2,8] +
S[8,1]*m[8,2] + S[1,9]*m[2,9] + S[9,1]*m[9,2] + S[1,2]*m[1,2] +
S[2,1]*m[2,1]
C13 Пω
= S[1,1]*m[3,1] + S[1,1]*m[1,3] + S[1,2]*m[3,2] + S[2,1]*m[2,3] +
S[1,3]*m[3,3] + S[3,1]*m[3,3] + S[1,4]*m[3,4] + S[4,1]*m[4,3] + S[1,5]*m[3,5] +
S[5,1]*m[5,3] + S[1,6]*m[3,6] + S[6,1]*m[6,3] + S[1,7]*m[3,7] + S[7,1]*m[7,3] +
S[1,8]*m[3,8] + S[8,1]*m[8,3] + S[1,9]*m[3,9] + S[9,1]*m[9,3] + S[1,3]*m[1,3] +
S[3,1]*m[3,1]
С14
Пω
=
S[1,1]*m[4,1] + S[1,1]*m[1,4] + S[1,2]*m[4,2] + S[2,1]*m[2,4] +
S[1,3]*m[4,3] + S[3,1]*m[3,4] + S[1,4]*m[4,4] + S[4,1]*m[4,4] + S[1,5]*m[4,5] +
S[5,1]*m[5,4] + S[1,6]*m[4,6] + S[6,1]*m[6,4] + S[1,7]*m[4,7] + S[7,1]*m[7,4] +
S[1,8]*m[4,8] + S[8,1]*m[8,4] + S[1,9]*m[4,9] + S[9,1]*m[9,4] + S[1,4]*m[1,4] +
S[4,1]*m[4,1]
С15
Пω =
S[1,1]*m[5,1] + S[1,1]*m[1,5] + S[1,2]*m[5,2] + S[2,1]*m[2,5] +
S[1,3]*m[5,3] + S[3,1]*m[3,5] + S[1,4]*m[5,4] + S[4,1]*m[4,5] + S[1,5]*m[5,5] +
S[5,1]*m[5,5] + S[1,6]*m[5,6] + S[6,1]*m[6,5] + S[1,7]*m[5,7] + S[7,1]*m[7,5] +
S[1,8]*m[5,8] + S[8,1]*m[8,5] + S[1,9]*m[5,9] + S[9,1]*m[9,5] + S[1,5]*m[1,5] +
S[5,1]*m[5,1]
С16
Пω =
S[1,1]*m[6,1] + S[1,1]*m[1,6] + S[1,2]*m[6,2] + S[2,1]*m[2,6] +
S[1,3]*m[6,3] + S[3,1]*m[3,6] + S[1,4]*m[6,4] + S[4,1]*m[4,6] + S[1,5]*m[6,5] +
S[5,1]*m[5,6] + S[1,6]*m[6,6] + S[6,1]*m[6,6] + S[1,7]*m[6,7] + S[7,1]*m[7,6] +
S[1,8]*m[6,8] + S[8,1]*m[8,6] + S[1,9]*m[6,9] + S[9,1]*m[9,6] + S[1,6]*m[1,6] +
S[6,1]*m[6,1]
С17
Пω =
S[1,1]*m[7,1] + S[1,1]*m[1,7] + S[1,2]*m[7,2] + S[2,1]*m[2,7] +
S[1,3]*m[7,3] + S[3,1]*m[3,7] + S[1,4]*m[7,4] + S[4,1]*m[4,7] + S[1,5]*m[7,5] +
S[5,1]*m[5,7] + S[1,6]*m[7,6] + S[6,1]*m[6,7] + S[1,7]*m[7,7] + S[7,1]*m[7,7] +
S[1,8]*m[7,8] + S[8,1]*m[8,7] + S[1,9]*m[7,9] + S[9,1]*m[9,7] + S[1,7]*m[1,7] +
S[7,1]*m[7,1]
С18
Пω =
S[1,1]*m[8,1] + S[1,1]*m[1,8] + S[1,2]*m[8,2] + S[2,1]*m[2,8] +
S[1,3]*m[8,3] + S[3,1]*m[3,8] + S[1,4]*m[8,4] + S[4,1]*m[4,8] + S[1,5]*m[8,5] +
S[5,1]*m[5,8] + S[1,6]*m[8,6] + S[6,1]*m[6,8] + S[1,7]*m[8,7] + S[7,1]*m[7,8] +
S[1,8]*m[8,8] + S[8,1]*m[8,8] + S[1,9]*m[8,9] + S[9,1]*m[9,8] + S[1,8]*m[1,8] +
S[8,1]*m[8,1]
С19
Пω
[1,9]= S[1,1]*m[9,1] + S[1,1]*m[1,9] + S[1,2]*m[9,2] +
S[2,1]*m[2,9] + S[1,3]*m[9,3] + S[3,1]*m[3,9] + S[1,4]*m[9,4] +
S[4,1]*m[4,9] + S[1,5]*m[9,5] + S[5,1]*m[5,9] + S[1,6]*m[9,6] + S[6,1]*m[6,9] +
S[1,7]*m[9,7] + S[7,1]*m[7,9] + S[1,8]*m[9,8] + S[8,1]*m[8,9] + S[1,9]*m[9,9] +
S[9,1]*m[9,9] + S[1,9]*m[1,9] + S[9,1]*m[9,1]
С21
Пω =
S[2,1]*m[1,1] + S[1,2]*m[1,1] + S[2,2]*m[1,2] + S[2,2]*m[2,1] +
S[2,3]*m[1,3] + S[3,2]*m[3,1] + S[2,4]*m[1,4] + S[4,2]*m[4,1] +
S[2,5]*m[1,5] + S[5,2]*m[5,1] + S[2,6]*m[1,6] + S[6,2]*m[6,1] + S[2,7]*m[1,7] +
S[7,2]*m[7,1] + S[2,8]*m[1,8] + S[8,2]*m[8,1] + S[2,9]*m[1,9] + S[9,2]*m[9,1] +
S[2,1]*m[2,1] + S[1,2]*m[1,2]
………………………………………………………………
С99
Пω =
S[9,1]*m[9,1] + S[1,9]*m[1,9] + S[9,2]*m[9,2] + S[2,9]*m[2,9] + S[9,3]*m[9,3] +
S[3,9]*m[3,9] + S[9,4]*m[9,4] + S[4,9]*m[4,9] + S[9,5]*m[9,5] + S[5,9]*m[5,9] +
S[9,6]*m[9,6] + S[6,9]*m[6,9] + S[9,7]*m[9,7] + S[7,9]*m[7,9] +
S[9,8]*m[9,8] + S[8,9]*m[8,9] + S[9,9]*m[9,9] + S[9,9]*m[9,9] +
S[9,9]*m[9,9] + S[9,9]*m[9,9]
Получили матрицу С
Пω :
|
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
1 |
30 |
30 |
30 |
22 |
70 |
110 |
100 |
96 |
180 |
|
2 |
78 |
60 |
78 |
100 |
200 |
280 |
300 |
240 |
400 |
|
3 |
80 |
52 |
80 |
72 |
120 |
200 |
180 |
166 |
300 |
|
4 |
148 |
100 |
150 |
100 |
150 |
220 |
210 |
172 |
340 |
|
5 |
190 |
132 |
192 |
140 |
130 |
170 |
104 |
130 |
200 |
|
6 |
250 |
170 |
250 |
130 |
140 |
104 |
84 |
88 |
196 |
|
7 |
260 |
206 |
260 |
160 |
132 |
84 |
60 |
96 |
160 |
|
8 |
350 |
280 |
350 |
200 |
200 |
104 |
92 |
116 |
136 |
|
9 |
120 |
96 |
120 |
70 |
52 |
60 |
36 |
80 |
80 |
Рисунок
6
Найдём элементы матрицы
Qω по выражению
(4):
|
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
1 |
0 |
18 |
0 |
40 |
100 |
226 |
270 |
300 |
196 |
|
2 |
18 |
0 |
-10 |
40 |
142 |
286 |
386 |
344 |
356 |
|
3 |
0 |
-10 |
0 |
42 |
100 |
266 |
300 |
320 |
260 |
|
4 |
40 |
40 |
42 |
0 |
60 |
146 |
210 |
156 |
230 |
|
5 |
100 |
142 |
100 |
60 |
0 |
76 |
46 |
84 |
42 |
|
6 |
226 |
286 |
266 |
146 |
76 |
0 |
4 |
-28 |
72 |
|
7 |
270 |
386 |
300 |
210 |
46 |
4 |
0 |
12 |
56 |
|
8 |
300 |
344 |
320 |
156 |
84 |
-28 |
12 |
0 |
20 |
|
9 |
196 |
356 |
260 |
230 |
42 |
72 |
56 |
20 |
0 |
Рисунок
7
Получили: min Q= -28
<0
p:=y6=6 , v:=y8=8 è y6:=v=8 , y8:=p=6 и переход к п.3 (т.е. к
Итерации 2)
(т.е. у нас y = { 1, 2, 3, 4, 5, 8, 7, 6,
9})
Рисунок
8
Итерация
2:
С1
01 =
S[1,1]*m[1,1] + S[1,1]*m[1,1] + S[1,2]*m[1,2] + S[2,1]*m[2,1] +
S[1,3]*m[1,3] + S[3,1]*m[3,1] + S[1,4]*m[1,4] + S[4,1]*m[4,1] + S[1,5]*m[1,5] +
S[5,1]*m[5,1] + S[1,6]*m[1,8] + S[6,1]*m[8,1] + S[1,7]*m[1,7] + S[7,1]*m[7,1] +
S[1,8]*m[1,6] + S[8,1]*m[6,1] + S[1,9]*m[1,9] +
S[9,1]*m[9,1]
С2
01 = S[2,1]*m[2,1] +
S[1,2]*m[1,2] + S[2,2]*m[2,2] + S[2,2]*m[2,2] + S[2,3]*m[2,3] +
S[3,2]*m[3,2] + S[2,4]*m[2,4] + S[4,2]*m[4,2] + S[2,5]*m[2,5] +
S[5,2]*m[5,2] + S[2,6]*m[2,8] + S[6,2]*m[8,2] + S[2,7]*m[2,7] + S[7,2]*m[7,2] +
S[2,8]*m[2,6] + S[8,2]*m[6,2] + S[2,9]*m[2,9] +
S[9,2]*m[9,2]
С3
01=
S[3,1]*m[3,1] + S[1,3]*m[1,3] + S[3,2]*m[3,2] + S[2,3]*m[2,3] +
S[3,3]*m[3,3] + S[3,3]*m[3,3] + S[3,4]*m[3,4] + S[4,3]*m[4,3] +
S[3,5]*m[3,5] + S[5,3]*m[5,3] + S[3,6]*m[3,8] + S[6,3]*m[8,3] + S[3,7]*m[3,7] +
S[7,3]*m[7,3] + S[3,8]*m[3,6] + S[8,3]*m[6,3] + S[3,9]*m[3,9] +
S[9,3]*m[9,3]
С4
01 =
S[4,1]*m[4,1] + S[1,4]*m[1,4] + S[4,2]*m[4,2] + S[2,4]*m[2,4] +
S[4,3]*m[4,3] + S[3,4]*m[3,4] + S[4,4]*m[4,4] + S[4,4]*m[4,4] +
S[4,5]*m[4,5] + S[5,4]*m[5,4] + S[4,6]*m[4,8] + S[6,4]*m[8,4] +
S[4,7]*m[4,7] + S[7,4]*m[7,4] + S[4,8]*m[4,6] + S[8,4]*m[6,4] + S[4,9]*m[4,9] +
S[9,4]*m[9,4]
С5
01 =
S[5,1]*m[5,1] + S[1,5]*m[1,5] + S[5,2]*m[5,2] + S[2,5]*m[2,5] + S[5,3]*m[5,3] +
S[3,5]*m[3,5] + S[5,4]*m[5,4] + S[4,5]*m[4,5] + S[5,5]*m[5,5] +
S[5,5]*m[5,5] + S[5,6]*m[5,8] + S[6,5]*m[8,5] + S[5,7]*m[5,7] +
S[7,5]*m[7,5] + S[5,8]*m[5,6] + S[8,5]*m[6,5] + S[5,9]*m[5,9] +
S[9,5]*m[9,5]
С6
01 =
S[6,1]*m[8,1] + S[1,6]*m[1,8] + S[6,2]*m[8,2] + S[2,6]*m[2,8] + S[6,3]*m[8,3] +
S[3,6]*m[3,8] + S[6,4]*m[8,4] + S[4,6]*m[4,8] + S[6,5]*m[8,5] +
S[5,6]*m[5,8] + S[6,6]*m[8,8] + S[6,6]*m[8,8] + S[6,7]*m[8,7] +
S[7,6]*m[7,8] + S[6,8]*m[8,6] + S[8,6]*m[6,8] + S[6,9]*m[8,9] +
S[9,6]*m[9,8]
С7
01 =
S[7,1]*m[7,1] + S[1,7]*m[1,7] + S[7,2]*m[7,2] + S[2,7]*m[2,7] + S[7,3]*m[7,3] +
S[3,7]*m[3,7] + S[7,4]*m[7,4] + S[4,7]*m[4,7] + S[7,5]*m[7,5] + S[5,7]*m[5,7] +
S[7,6]*m[7,8] + S[6,7]*m[8,7] + S[7,7]*m[7,7] + S[7,7]*m[7,7] +
S[7,8]*m[7,6] + S[8,7]*m[6,7] + S[7,9]*m[7,9] +
S[9,7]*m[9,7]
С8
01 =
S[8,1]*m[6,1] + S[1,8]*m[1,6] + S[8,2]*m[6,2] + S[2,8]*m[2,6] + S[8,3]*m[6,3] +
S[3,8]*m[3,6] + S[8,4]*m[6,4] + S[4,8]*m[4,6] + S[8,5]*m[6,5] + S[5,8]*m[5,6] +
S[8,6]*m[6,8] + S[6,8]*m[8,6] + S[8,7]*m[6,7] + S[7,8]*m[7,6] +
S[8,8]*m[6,6] + S[8,8]*m[6,6] + S[8,9]*m[6,9] +
S[9,8]*m[9,6]
С9
01 =
S[9,1]*m[9,1] + S[1,9]*m[1,9] + S[9,2]*m[9,2] + S[2,9]*m[2,9] + S[9,3]*m[9,3] +
S[3,9]*m[3,9] + S[9,4]*m[9,4] + S[4,9]*m[4,9] + S[9,5]*m[9,5] + S[5,9]*m[5,9] +
S[9,6]*m[9,8] + S[6,9]*m[8,9] + S[9,7]*m[9,7] + S[7,9]*m[7,9] +
S[9,8]*m[9,6] + S[8,9]*m[6,9] + S[9,9]*m[9,9] +
S[9,9]*m[9,9]
С
01
={30, 60, 80, 100, 102, 88, 60 , 104, 80 }
С11
Пω
=
S[1,1]*m[1,1] + S[1,1]*m[1,1] + S[1,2]*m[1,2] + S[2,1]*m[2,1] +
S[1,3]*m[1,3] + S[3,1]*m[3,1] + S[1,4]*m[1,4] + S[4,1]*m[4,1] + S[1,5]*m[1,5] +
S[5,1]*m[5,1] + S[1,6]*m[1,8] + S[6,1]*m[8,1] + S[1,7]*m[1,7] + S[7,1]*m[7,1] +
S[1,8]*m[1,6] + S[8,1]*m[6,1] + S[1,9]*m[1,9] + S[9,1]*m[9,1] + S[1,1]*m[1,1] +
S[1,1]*m[1,1]
С12
Пω
=
S[1,1]*m[2,1] + S[1,1]*m[1,2] + S[1,2]*m[2,2] + S[2,1]*m[2,2] + S[1,3]*m[2,3] +
S[3,1]*m[3,2] + S[1,4]*m[2,4] + S[4,1]*m[4,2] + S[1,5]*m[2,5] + S[5,1]*m[5,2] +
S[1,6]*m[2,8] + S[6,1]*m[8,2] + S[1,7]*m[2,7] + S[7,1]*m[7,2] + S[1,8]*m[2,6] +
S[8,1]*m[6,2] + S[1,9]*m[2,9] + S[9,1]*m[9,2] + S[1,2]*m[1,2] +
S[2,1]*m[2,1]
C13 Пω
= S[1,1]*m[3,1] + S[1,1]*m[1,3] + S[1,2]*m[3,2] + S[2,1]*m[2,3] +
S[1,3]*m[3,3] + S[3,1]*m[3,3] + S[1,4]*m[3,4] + S[4,1]*m[4,3] + S[1,5]*m[3,5] +
S[5,1]*m[5,3] + S[1,6]*m[3,8] + S[6,1]*m[8,3] + S[1,7]*m[3,7] + S[7,1]*m[7,3] +
S[1,8]*m[3,6] + S[8,1]*m[6,3] + S[1,9]*m[3,9] + S[9,1]*m[9,3] + S[1,3]*m[1,3] +
S[3,1]*m[3,1]
С14
Пω
=
S[1,1]*m[4,1] + S[1,1]*m[1,4] + S[1,2]*m[4,2] + S[2,1]*m[2,4] +
S[1,3]*m[4,3] + S[3,1]*m[3,4] + S[1,4]*m[4,4] + S[4,1]*m[4,4] + S[1,5]*m[4,5] +
S[5,1]*m[5,4] + S[1,6]*m[4,8] + S[6,1]*m[8,4] + S[1,7]*m[4,7] + S[7,1]*m[7,4] +
S[1,8]*m[4,6] + S[8,1]*m[6,4] + S[1,9]*m[4,9] + S[9,1]*m[9,4] + S[1,4]*m[1,4] +
S[4,1]*m[4,1]
С15
Пω =
S[1,1]*m[5,1] + S[1,1]*m[1,5] + S[1,2]*m[5,2] + S[2,1]*m[2,5] +
S[1,3]*m[5,3] + S[3,1]*m[3,5] + S[1,4]*m[5,4] + S[4,1]*m[4,5] + S[1,5]*m[5,5] +
S[5,1]*m[5,5] + S[1,6]*m[5,8] + S[6,1]*m[8,5] + S[1,7]*m[5,7] + S[7,1]*m[7,5] +
S[1,8]*m[5,6] + S[8,1]*m[6,5] + S[1,9]*m[5,9] + S[9,1]*m[9,5] + S[1,5]*m[1,5] +
S[5,1]*m[5,1]
С16
Пω =
S[1,1]*m[8,1] + S[1,1]*m[1,8] + S[1,2]*m[8,2] + S[2,1]*m[2,8] +
S[1,3]*m[8,3] + S[3,1]*m[3,8] + S[1,4]*m[8,4] + S[4,1]*m[4,8] + S[1,5]*m[8,5] +
S[5,1]*m[5,8] + S[1,6]*m[8,8] + S[6,1]*m[8,8] + S[1,7]*m[8,7] + S[7,1]*m[7,8] +
S[1,8]*m[8,6] + S[8,1]*m[6,8] + S[1,9]*m[8,9] + S[9,1]*m[9,8] + S[1,6]*m[1,8] +
S[6,1]*m[8,1]
С17
Пω =
S[1,1]*m[7,1] + S[1,1]*m[1,7] + S[1,2]*m[7,2] + S[2,1]*m[2,7] +
S[1,3]*m[7,3] + S[3,1]*m[3,7] + S[1,4]*m[7,4] + S[4,1]*m[4,7] + S[1,5]*m[7,5] +
S[5,1]*m[5,7] + S[1,6]*m[7,8] + S[6,1]*m[8,7] + S[1,7]*m[7,7] + S[7,1]*m[7,7] +
S[1,8]*m[7,6] + S[8,1]*m[6,7] + S[1,9]*m[7,9] + S[9,1]*m[9,7] + S[1,7]*m[1,7] +
S[7,1]*m[7,1]
С18
Пω =
S[1,1]*m[6,1] + S[1,1]*m[1,6] + S[1,2]*m[6,2] + S[2,1]*m[2,6] +
S[1,3]*m[6,3] + S[3,1]*m[3,6] + S[1,4]*m[6,4] + S[4,1]*m[4,6] + S[1,5]*m[6,5] +
S[5,1]*m[5,6] + S[1,6]*m[6,8] + S[6,1]*m[8,6] + S[1,7]*m[6,7] + S[7,1]*m[7,6] +
S[1,8]*m[6,6] + S[8,1]*m[6,6] + S[1,9]*m[6,9] + S[9,1]*m[9,6] + S[1,8]*m[1,6] +
S[8,1]*m[6,1]
С19
Пω
[1,9]= S[1,1]*m[9,1] + S[1,1]*m[1,9] + S[1,2]*m[9,2] +
S[2,1]*m[2,9] + S[1,3]*m[9,3] + S[3,1]*m[3,9] + S[1,4]*m[9,4] +
S[4,1]*m[4,9] + S[1,5]*m[9,5] + S[5,1]*m[5,9] + S[1,6]*m[9,8] + S[6,1]*m[8,9] +
S[1,7]*m[9,7] + S[7,1]*m[7,9] + S[1,8]*m[9,6] + S[8,1]*m[6,9] + S[1,9]*m[9,9] +
S[9,1]*m[9,9] + S[1,9]*m[1,9] + S[9,1]*m[9,1]
С21
Пω =
S[2,1]*m[1,1] + S[1,2]*m[1,1] + S[2,2]*m[1,2] + S[2,2]*m[2,1] +
S[2,3]*m[1,3] + S[3,2]*m[3,1] + S[2,4]*m[1,4] + S[4,2]*m[4,1] +
S[2,5]*m[1,5] + S[5,2]*m[5,1] + S[2,6]*m[1,8] + S[6,2]*m[8,1] + S[2,7]*m[1,7] +
S[7,2]*m[7,1] + S[2,8]*m[1,6] + S[8,2]*m[6,1] + S[2,9]*m[1,9] + S[9,2]*m[9,1] +
S[2,1]*m[2,1] + S[1,2]*m[1,2]
………………………………………………………………
С99
Пω =
S[9,1]*m[9,1] + S[1,9]*m[1,9] + S[9,2]*m[9,2] + S[2,9]*m[2,9] + S[9,3]*m[9,3] +
S[3,9]*m[3,9] + S[9,4]*m[9,4] + S[4,9]*m[4,9] + S[9,5]*m[9,5] + S[5,9]*m[5,9] +
S[9,6]*m[9,8] + S[6,9]*m[8,9] + S[9,7]*m[9,7] + S[7,9]*m[7,9] +
S[9,8]*m[9,6] + S[8,9]*m[6,9] + S[9,9]*m[9,9] + S[9,9]*m[9,9] +
S[9,9]*m[9,9] + S[9,9]*m[9,9]
Получили матрицу С
Пω :
|
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
1 |
30 |
30 |
30 |
22 |
70 |
96 |
100 |
110 |
180 |
|
2 |
78 |
60 |
78 |
100 |
200 |
240 |
300 |
280 |
400 |
|
3 |
80 |
52 |
80 |
72 |
120 |
166 |
180 |
200 |
300 |
|
4 |
148 |
100 |
150 |
100 |
150 |
172 |
210 |
220 |
340 |
|
5 |
170 |
118 |
170 |
120 |
102 |
122 |
116 |
150 |
200 |
|
6 |
250 |
170 |
250 |
130 |
112 |
88 |
96 |
104 |
196 |
|
7 |
260 |
206 |
260 |
160 |
132 |
96 |
60 |
84 |
160 |
|
8 |
350 |
280 |
350 |
200 |
200 |
116 |
80 |
104 |
136 |
|
9 |
140 |
110 |
140 |
90 |
80 |
60 |
24 |
80 |
80 |
Рисунок
9
Найдём элементы матрицы
Qω по выражению
(4):
|
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
1 |
0 |
18 |
0 |
40 |
108 |
228 |
270 |
326 |
210 |
|
2 |
18 |
0 |
-10 |
40 |
156 |
262 |
386 |
396 |
370 |
|
3 |
0 |
-10 |
0 |
42 |
108 |
248 |
300 |
366 |
280 |
|
4 |
40 |
40 |
42 |
0 |
68 |
114 |
210 |
216 |
250 |
|
5 |
108 |
156 |
108 |
68 |
0 |
44 |
86 |
144 |
98 |
|
6 |
228 |
262 |
248 |
114 |
44 |
0 |
44 |
28 |
88 |
|
7 |
270 |
386 |
300 |
210 |
86 |
44 |
0 |
0 |
44 |
|
8 |
326 |
396 |
366 |
216 |
144 |
28 |
0 |
0 |
32 |
|
9 |
210 |
370 |
280 |
250 |
98 |
88 |
44 |
32 |
0 |
Рисунок
10
Получили: min Q= -10
<0
p:=y2=2 , v:=y3=3 è y2:=v=3 , y3:=p=2 и переход к п.3 (т.е. к
Итерации 2)
(т.е. у нас y = { 1, 3, 2, 4, 5, 8, 7, 6,
9})
Рисунок
11
Итерация
3:
С1
01 =
S[1,1]*m[1,1] + S[1,1]*m[1,1] + S[1,2]*m[1,3] + S[2,1]*m[3,1] +
S[1,3]*m[1,2] + S[3,1]*m[2,1] + S[1,4]*m[1,4] + S[4,1]*m[4,1] + S[1,5]*m[1,5] +
S[5,1]*m[5,1] + S[1,6]*m[1,8] + S[6,1]*m[8,1] + S[1,7]*m[1,7] + S[7,1]*m[7,1] +
S[1,8]*m[1,6] + S[8,1]*m[6,1] + S[1,9]*m[1,9] +
S[9,1]*m[9,1]
С2
01 = S[2,1]*m[3,1] +
S[1,2]*m[1,3] + S[2,2]*m[3,3] + S[2,2]*m[3,3] + S[2,3]*m[3,2] +
S[3,2]*m[2,3] + S[2,4]*m[3,4] + S[4,2]*m[4,3] + S[2,5]*m[3,5] +
S[5,2]*m[5,3] + S[2,6]*m[3,8] + S[6,2]*m[8,3] + S[2,7]*m[3,7] + S[7,2]*m[7,3] +
S[2,8]*m[3,6] + S[8,2]*m[6,3] + S[2,9]*m[3,9] +
S[9,2]*m[9,3]
С3
01=
S[3,1]*m[2,1] + S[1,3]*m[1,2] + S[3,2]*m[2,3] + S[2,3]*m[3,2] +
S[3,3]*m[2,2] + S[3,3]*m[2,2] + S[3,4]*m[2,4] + S[4,3]*m[4,2] +
S[3,5]*m[2,5] + S[5,3]*m[5,2] + S[3,6]*m[2,8] + S[6,3]*m[8,2] + S[3,7]*m[2,7] +
S[7,3]*m[7,2] + S[3,8]*m[2,6] + S[8,3]*m[6,2] + S[3,9]*m[2,9] +
S[9,3]*m[9,2]
С4
01 =
S[4,1]*m[4,1] + S[1,4]*m[1,4] + S[4,2]*m[4,3] + S[2,4]*m[3,4] +
S[4,3]*m[4,2] + S[3,4]*m[2,4] + S[4,4]*m[4,4] + S[4,4]*m[4,4] +
S[4,5]*m[4,5] + S[5,4]*m[5,4] + S[4,6]*m[4,8] + S[6,4]*m[8,4] +
S[4,7]*m[4,7] + S[7,4]*m[7,4] + S[4,8]*m[4,6] + S[8,4]*m[6,4] + S[4,9]*m[4,9] +
S[9,4]*m[9,4]
С5
01 =
S[5,1]*m[5,1] + S[1,5]*m[1,5] + S[5,2]*m[5,3] + S[2,5]*m[3,5] + S[5,3]*m[5,2] +
S[3,5]*m[2,5] + S[5,4]*m[5,4] + S[4,5]*m[4,5] + S[5,5]*m[5,5] +
S[5,5]*m[5,5] + S[5,6]*m[5,8] + S[6,5]*m[8,5] + S[5,7]*m[5,7] +
S[7,5]*m[7,5] + S[5,8]*m[5,6] + S[8,5]*m[6,5] + S[5,9]*m[5,9] +
S[9,5]*m[9,5]
С6
01 =
S[6,1]*m[8,1] + S[1,6]*m[1,8] + S[6,2]*m[8,3] + S[2,6]*m[3,8] + S[6,3]*m[8,2] +
S[3,6]*m[2,8] + S[6,4]*m[8,4] + S[4,6]*m[4,8] + S[6,5]*m[8,5] +
S[5,6]*m[5,8] + S[6,6]*m[8,8] + S[6,6]*m[8,8] + S[6,7]*m[8,7] +
S[7,6]*m[7,8] + S[6,8]*m[8,6] + S[8,6]*m[6,8] + S[6,9]*m[8,9] +
S[9,6]*m[9,8]
С7
01 =
S[7,1]*m[7,1] + S[1,7]*m[1,7] + S[7,2]*m[7,3] + S[2,7]*m[3,7] + S[7,3]*m[7,2] +
S[3,7]*m[2,7] + S[7,4]*m[7,4] + S[4,7]*m[4,7] + S[7,5]*m[7,5] + S[5,7]*m[5,7] +
S[7,6]*m[7,8] + S[6,7]*m[8,7] + S[7,7]*m[7,7] + S[7,7]*m[7,7] +
S[7,8]*m[7,6] + S[8,7]*m[6,7] + S[7,9]*m[7,9] +
S[9,7]*m[9,7]
С8
01 =
S[8,1]*m[6,1] + S[1,8]*m[1,6] + S[8,2]*m[6,3] + S[2,8]*m[3,6] + S[8,3]*m[6,2] +
S[3,8]*m[2,6] + S[8,4]*m[6,4] + S[4,8]*m[4,6] + S[8,5]*m[6,5] + S[5,8]*m[5,6] +
S[8,6]*m[6,8] + S[6,8]*m[8,6] + S[8,7]*m[6,7] + S[7,8]*m[7,6] +
S[8,8]*m[6,6] + S[8,8]*m[6,6] + S[8,9]*m[6,9] +
S[9,8]*m[9,6]
С9
01 =
S[9,1]*m[9,1] + S[1,9]*m[1,9] + S[9,2]*m[9,3] + S[2,9]*m[3,9] + S[9,3]*m[9,2] +
S[3,9]*m[2,9] + S[9,4]*m[9,4] + S[4,9]*m[4,9] + S[9,5]*m[9,5] + S[5,9]*m[5,9] +
S[9,6]*m[9,8] + S[6,9]*m[8,9] + S[9,7]*m[9,7] + S[7,9]*m[7,9] +
S[9,8]*m[9,6] + S[8,9]*m[6,9] + S[9,9]*m[9,9] +
S[9,9]*m[9,9]
С
01
={48,
78,
52,
72,
102, 88, 60 , 104, 80 }
С11
Пω
=
S[1,1]*m[1,1] + S[1,1]*m[1,1] + S[1,2]*m[1,3] + S[2,1]*m[3,1] +
S[1,3]*m[1,2] + S[3,1]*m[2,1] + S[1,4]*m[1,4] + S[4,1]*m[4,1] + S[1,5]*m[1,5] +
S[5,1]*m[5,1] + S[1,6]*m[1,8] + S[6,1]*m[8,1] + S[1,7]*m[1,7] + S[7,1]*m[7,1] +
S[1,8]*m[1,6] + S[8,1]*m[6,1] + S[1,9]*m[1,9] + S[9,1]*m[9,1] + S[1,1]*m[1,1] +
S[1,1]*m[1,1]
С12
Пω
=
S[1,1]*m[3,1] + S[1,1]*m[1,3] + S[1,2]*m[3,3] + S[2,1]*m[3,3] + S[1,3]*m[3,2] +
S[3,1]*m[2,3] + S[1,4]*m[3,4] + S[4,1]*m[4,3] + S[1,5]*m[3,5] + S[5,1]*m[5,3] +
S[1,6]*m[3,8] + S[6,1]*m[8,3] + S[1,7]*m[3,7] + S[7,1]*m[7,3] + S[1,8]*m[3,6] +
S[8,1]*m[6,3] + S[1,9]*m[3,9] + S[9,1]*m[9,3] + S[1,2]*m[1,3] +
S[2,1]*m[3,1]
C13 Пω
= S[1,1]*m[2,1] + S[1,1]*m[1,2] + S[1,2]*m[2,3] + S[2,1]*m[3,2] +
S[1,3]*m[2,2] + S[3,1]*m[2,2] + S[1,4]*m[2,4] + S[4,1]*m[4,2] + S[1,5]*m[2,5] +
S[5,1]*m[5,2] + S[1,6]*m[2,8] + S[6,1]*m[8,2] + S[1,7]*m[2,7] + S[7,1]*m[7,2] +
S[1,8]*m[2,6] + S[8,1]*m[6,2] + S[1,9]*m[2,9] + S[9,1]*m[9,2] + S[1,3]*m[1,2] +
S[3,1]*m[2,1]
С14
Пω
=
S[1,1]*m[4,1] + S[1,1]*m[1,4] + S[1,2]*m[4,3] + S[2,1]*m[3,4] +
S[1,3]*m[4,2] + S[3,1]*m[2,4] + S[1,4]*m[4,4] + S[4,1]*m[4,4] + S[1,5]*m[4,5] +
S[5,1]*m[5,4] + S[1,6]*m[4,8] + S[6,1]*m[8,4] + S[1,7]*m[4,7] + S[7,1]*m[7,4] +
S[1,8]*m[4,6] + S[8,1]*m[6,4] + S[1,9]*m[4,9] + S[9,1]*m[9,4] + S[1,4]*m[1,4] +
S[4,1]*m[4,1]
С15
Пω =
S[1,1]*m[5,1] + S[1,1]*m[1,5] + S[1,2]*m[5,3] + S[2,1]*m[3,5] +
S[1,3]*m[5,2] + S[3,1]*m[2,5] + S[1,4]*m[5,4] + S[4,1]*m[4,5] + S[1,5]*m[5,5] +
S[5,1]*m[5,5] + S[1,6]*m[5,8] + S[6,1]*m[8,5] + S[1,7]*m[5,7] + S[7,1]*m[7,5] +
S[1,8]*m[5,6] + S[8,1]*m[6,5] + S[1,9]*m[5,9] + S[9,1]*m[9,5] + S[1,5]*m[1,5] +
S[5,1]*m[5,1]
С16
Пω =
S[1,1]*m[8,1] + S[1,1]*m[1,8] + S[1,2]*m[8,3] + S[2,1]*m[3,8] +
S[1,3]*m[8,2] + S[3,1]*m[2,8] + S[1,4]*m[8,4] + S[4,1]*m[4,8] + S[1,5]*m[8,5] +
S[5,1]*m[5,8] + S[1,6]*m[8,8] + S[6,1]*m[8,8] + S[1,7]*m[8,7] + S[7,1]*m[7,8] +
S[1,8]*m[8,6] + S[8,1]*m[6,8] + S[1,9]*m[8,9] + S[9,1]*m[9,8] + S[1,6]*m[1,8] +
S[6,1]*m[8,1]
С17
Пω =
S[1,1]*m[7,1] + S[1,1]*m[1,7] + S[1,2]*m[7,3] + S[2,1]*m[3,7] +
S[1,3]*m[7,2] + S[3,1]*m[2,7] + S[1,4]*m[7,4] + S[4,1]*m[4,7] + S[1,5]*m[7,5] +
S[5,1]*m[5,7] + S[1,6]*m[7,8] + S[6,1]*m[8,7] + S[1,7]*m[7,7] + S[7,1]*m[7,7] +
S[1,8]*m[7,6] + S[8,1]*m[6,7] + S[1,9]*m[7,9] + S[9,1]*m[9,7] + S[1,7]*m[1,7] +
S[7,1]*m[7,1]
С18
Пω =
S[1,1]*m[6,1] + S[1,1]*m[1,6] + S[1,2]*m[6,3] + S[2,1]*m[3,6] +
S[1,3]*m[6,2] + S[3,1]*m[2,6] + S[1,4]*m[6,4] + S[4,1]*m[4,6] + S[1,5]*m[6,5] +
S[5,1]*m[5,6] + S[1,6]*m[6,8] + S[6,1]*m[8,6] + S[1,7]*m[6,7] + S[7,1]*m[7,6] +
S[1,8]*m[6,6] + S[8,1]*m[6,6] + S[1,9]*m[6,9] + S[9,1]*m[9,6] + S[1,8]*m[1,6] +
S[8,1]*m[6,1]
С19
Пω
[1,9]= S[1,1]*m[9,1] + S[1,1]*m[1,9] + S[1,2]*m[9,3] +
S[2,1]*m[3,9] + S[1,3]*m[9,2] + S[3,1]*m[2,9] + S[1,4]*m[9,4] +
S[4,1]*m[4,9] + S[1,5]*m[9,5] + S[5,1]*m[5,9] + S[1,6]*m[9,8] + S[6,1]*m[8,9] +
S[1,7]*m[9,7] + S[7,1]*m[7,9] + S[1,8]*m[9,6] + S[8,1]*m[6,9] + S[1,9]*m[9,9] +
S[9,1]*m[9,9] + S[1,9]*m[1,9] + S[9,1]*m[9,1]
С21
Пω =
S[2,1]*m[1,1] + S[1,2]*m[1,1] + S[2,2]*m[1,3] + S[2,2]*m[3,1] +
S[2,3]*m[1,2] + S[3,2]*m[2,1] + S[2,4]*m[1,4] + S[4,2]*m[4,1] +
S[2,5]*m[1,5] + S[5,2]*m[5,1] + S[2,6]*m[1,8] + S[6,2]*m[8,1] + S[2,7]*m[1,7] +
S[7,2]*m[7,1] + S[2,8]*m[1,6] + S[8,2]*m[6,1] + S[2,9]*m[1,9] + S[9,2]*m[9,1] +
S[2,1]*m[3,1] + S[1,2]*m[1,3]
………………………………………………………………
С99
Пω =
S[9,1]*m[9,1] + S[1,9]*m[1,9] + S[9,2]*m[9,3] + S[2,9]*m[3,9] + S[9,3]*m[9,2] +
S[3,9]*m[2,9] + S[9,4]*m[9,4] + S[4,9]*m[4,9] + S[9,5]*m[9,5] + S[5,9]*m[5,9] +
S[9,6]*m[9,8] + S[6,9]*m[8,9] + S[9,7]*m[9,7] + S[7,9]*m[7,9] +
S[9,8]*m[9,6] + S[8,9]*m[6,9] + S[9,9]*m[9,9] + S[9,9]*m[9,9] +
S[9,9]*m[9,9] + S[9,9]*m[9,9]
Получили матрицу С
Пω :
|
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
1 |
48 |
48 |
30 |
50 |
100 |
120 |
150 |
140 |
200 |
|
2 |
78 |
78 |
60 |
72 |
170 |
216 |
250 |
250 |
380 |
|
3 |
98 |
80 |
52 |
72 |
150 |
190 |
230 |
230 |
320 |
|
4 |
130 |
130 |
92 |
72 |
120 |
148 |
160 |
190 |
320 |
|
5 |
170 |
170 |
118 |
120 |
102 |
122 |
116 |
150 |
200 |
|
6 |
250 |
250 |
170 |
130 |
112 |
88 |
96 |
104 |
196 |
|
7 |
260 |
260 |
206 |
160 |
132 |
96 |
60 |
84 |
160 |
|
8 |
350 |
350 |
280 |
200 |
200 |
116 |
80 |
104 |
136 |
|
9 |
140 |
140 |
110 |
90 |
80 |
60 |
24 |
80 |
80 |
Рисунок
12
Найдём элементы матрицы
Qω по выражению
(4):
|
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
1 |
0 |
0 |
28 |
60 |
120 |
234 |
302 |
338 |
212 |
|
2 |
0 |
0 |
10 |
52 |
160 |
300 |
372 |
418 |
362 |
|
3 |
28 |
10 |
0 |
40 |
114 |
220 |
324 |
354 |
298 |
|
4 |
60 |
52 |
40 |
0 |
66 |
118 |
188 |
214 |
258 |
|
5 |
120 |
160 |
114 |
66 |
0 |
44 |
86 |
144 |
98 |
|
6 |
234 |
300 |
220 |
118 |
44 |
0 |
44 |
28 |
88 |
|
7 |
302 |
372 |
324 |
188 |
86 |
44 |
0 |
0 |
44 |
|
8 |
338 |
418 |
354 |
214 |
144 |
28 |
0 |
0 |
32 |
|
9 |
212 |
362 |
298 |
258 |
98 |
88 |
44 |
32 |
0 |
Рисунок
13
Получили: min Q= 0 ³ 0, следовательно переходим
к п. 12
П. 12 . Корректировка номера исходного
варианта
ω = ω +1 =
2;
П. 13
ω£N, значит переходим к п.
2
П. 2 Формирование
для варианта ω исходного списка {yi}ω
y = { 2, 3, 4, 5, 6, 7, 8, 9,
1}
Рисунок
14
П.
3
Итерация
1:
С1
02 =
S[1,1]*m[2,2] + S[1,1]*m[2,2] + S[1,2]*m[2,3] + S[2,1]*m[3,2] +
S[1,3]*m[2,4] + S[3,1]*m[4,2] + S[1,4]*m[2,5] + S[4,1]*m[5,2] + S[1,5]*m[2,6] +
S[5,1]*m[6,2] + S[1,6]*m[2,7] + S[6,1]*m[7,2] + S[1,7]*m[2,8] + S[7,1]*m[8,2] +
S[1,8]*m[2,9] + S[8,1]*m[9,2] + S[1,9]*m[2,1] +
S[9,1]*m[1,2]
С2
02 = S[2,1]*m[3,2] +
S[1,2]*m[2,3] + S[2,2]*m[3,3] + S[2,2]*m[3,3] + S[2,3]*m[3,4] +
S[3,2]*m[4,3] + S[2,4]*m[3,5] + S[4,2]*m[5,3] + S[2,5]*m[3,6] +
S[5,2]*m[6,3] + S[2,6]*m[3,7] + S[6,2]*m[7,3] + S[2,7]*m[3,8] + S[7,2]*m[8,3] +
S[2,8]*m[3,9] + S[8,2]*m[9,3] + S[2,9]*m[3,1] +
S[9,2]*m[1,3]
С3
02=
S[3,1]*m[4,2] + S[1,3]*m[2,4] + S[3,2]*m[4,3] + S[2,3]*m[3,4] +
S[3,3]*m[4,4] + S[3,3]*m[4,4] + S[3,4]*m[4,5] + S[4,3]*m[5,4] +
S[3,5]*m[4,6] + S[5,3]*m[6,4] + S[3,6]*m[4,7] + S[6,3]*m[7,4] + S[3,7]*m[4,8] +
S[7,3]*m[8,4] + S[3,8]*m[4,9] + S[8,3]*m[9,4] + S[3,9]*m[4,1] +
S[9,3]*m[1,4]
С4
02 =
S[4,1]*m[5,2] + S[1,4]*m[2,5] + S[4,2]*m[5,3] + S[2,4]*m[3,5] +
S[4,3]*m[5,4] + S[3,4]*m[4,5] + S[4,4]*m[5,5] + S[4,4]*m[5,5] +
S[4,5]*m[5,6] + S[5,4]*m[6,5] + S[4,6]*m[5,7] + S[6,4]*m[7,5] +
S[4,7]*m[5,8] + S[7,4]*m[8,5] + S[4,8]*m[5,9] + S[8,4]*m[9,5] + S[4,9]*m[5,1] +
S[9,4]*m[1,5]
С5
02 =
S[5,1]*m[6,2] + S[1,5]*m[2,6] + S[5,2]*m[6,3] + S[2,5]*m[3,6] + S[5,3]*m[6,4] +
S[3,5]*m[4,6] + S[5,4]*m[6,5] + S[4,5]*m[5,6] + S[5,5]*m[6,6] +
S[5,5]*m[6,6] + S[5,6]*m[6,7] + S[6,5]*m[7,6] + S[5,7]*m[6,8] +
S[7,5]*m[8,6] + S[5,8]*m[6,9] + S[8,5]*m[9,6] + S[5,9]*m[6,1] +
S[9,5]*m[1,6]
С6
02 =
S[6,1]*m[7,2] + S[1,6]*m[2,7] + S[6,2]*m[7,3] + S[2,6]*m[3,7] + S[6,3]*m[7,4] +
S[3,6]*m[4,7] + S[6,4]*m[7,5] + S[4,6]*m[5,7] + S[6,5]*m[7,6] +
S[5,6]*m[6,7] + S[6,6]*m[7,7] + S[6,6]*m[7,7] + S[6,7]*m[7,8] +
S[7,6]*m[8,7] + S[6,8]*m[7,9] + S[8,6]*m[9,7] + S[6,9]*m[7,1] +
S[9,6]*m[1,7]
С7
02 =
S[7,1]*m[8,2] + S[1,7]*m[2,8] + S[7,2]*m[8,3] + S[2,7]*m[3,8] + S[7,3]*m[8,4] +
S[3,7]*m[4,8] + S[7,4]*m[8,5] + S[4,7]*m[5,8] + S[7,5]*m[8,6] + S[5,7]*m[6,8] +
S[7,6]*m[8,7] + S[6,7]*m[7,8] + S[7,7]*m[8,8] + S[7,7]*m[8,8] +
S[7,8]*m[8,9] + S[8,7]*m[9,8] + S[7,9]*m[8,1] +
S[9,7]*m[1,8]
С8
02 =
S[8,1]*m[9,2] + S[1,8]*m[2,9] + S[8,2]*m[9,3] + S[2,8]*m[3,9] + S[8,3]*m[9,4] +
S[3,8]*m[4,9] + S[8,4]*m[9,5] + S[4,8]*m[5,9] + S[8,5]*m[9,6] + S[5,8]*m[6,9] +
S[8,6]*m[9,7] + S[6,8]*m[7,9] + S[8,7]*m[9,8] + S[7,8]*m[8,9] +
S[8,8]*m[9,9] + S[8,8]*m[9,9] + S[8,9]*m[9,1] +
S[9,8]*m[1,9]
С9
02 =
S[9,1]*m[1,2] + S[1,9]*m[2,1] + S[9,2]*m[1,3] + S[2,9]*m[3,1] + S[9,3]*m[1,4] +
S[3,9]*m[4,1] + S[9,4]*m[1,5] + S[4,9]*m[5,1] + S[9,5]*m[1,6] + S[5,9]*m[6,1] +
S[9,6]*m[1,7] + S[6,9]*m[7,1] + S[9,7]*m[1,8] + S[7,9]*m[8,1] +
S[9,8]*m[1,9] + S[8,9]*m[9,1] + S[9,9]*m[1,1] +
S[9,9]*m[1,1]
С
02
={30, 80, 100, 130, 104, 60, 116, 280, 200}
П.
4
С11
Пω
=
S[1,1]*m[2,2] + S[1,1]*m[2,2] + S[1,2]*m[2,3] + S[2,1]*m[3,2] +
S[1,3]*m[2,4] + S[3,1]*m[4,2] + S[1,4]*m[2,5] + S[4,1]*m[5,2] + S[1,5]*m[2,6] +
S[5,1]*m[6,2] + S[1,6]*m[2,7] + S[6,1]*m[7,2] + S[1,7]*m[2,8] + S[7,1]*m[8,2] +
S[1,8]*m[2,9] + S[8,1]*m[9,2] + S[1,9]*m[2,1] + S[9,1]*m[1,2] + S[1,1]*m[2,2] +
S[1,1]*m[2,2]
С12
Пω
=
S[1,1]*m[3,2] + S[1,1]*m[2,3] + S[1,2]*m[3,3] + S[2,1]*m[3,3] + S[1,3]*m[3,4] +
S[3,1]*m[4,3] + S[1,4]*m[3,5] + S[4,1]*m[5,3] + S[1,5]*m[3,6] + S[5,1]*m[6,3] +
S[1,6]*m[3,7] + S[6,1]*m[7,3] + S[1,7]*m[3,8] + S[7,1]*m[8,3] + S[1,8]*m[3,9] +
S[8,1]*m[9,3] + S[1,9]*m[3,1] + S[9,1]*m[1,3] + S[1,2]*m[2,3] +
S[2,1]*m[3,2]
C13 Пω
= S[1,1]*m[4,2] + S[1,1]*m[2,4] + S[1,2]*m[4,3] + S[2,1]*m[3,4] +
S[1,3]*m[4,4] + S[3,1]*m[4,4] + S[1,4]*m[4,5] + S[4,1]*m[5,4] + S[1,5]*m[4,6] +
S[5,1]*m[6,4] + S[1,6]*m[4,7] + S[6,1]*m[7,4] + S[1,7]*m[4,8] + S[7,1]*m[8,4] +
S[1,8]*m[4,9] + S[8,1]*m[9,4] + S[1,9]*m[4,1] + S[9,1]*m[1,4] + S[1,3]*m[2,4] +
S[3,1]*m[4,2]
С14
Пω
=
S[1,1]*m[5,2] + S[1,1]*m[2,5] + S[1,2]*m[5,3] + S[2,1]*m[3,5] +
S[1,3]*m[5,4] + S[3,1]*m[4,5] + S[1,4]*m[5,5] + S[4,1]*m[5,5] + S[1,5]*m[5,6] +
S[5,1]*m[6,5] + S[1,6]*m[5,7] + S[6,1]*m[7,5] + S[1,7]*m[5,8] + S[7,1]*m[8,5] +
S[1,8]*m[5,9] + S[8,1]*m[9,5] + S[1,9]*m[5,1] + S[9,1]*m[1,5] + S[1,4]*m[2,5] +
S[4,1]*m[5,2]
С15
Пω =
S[1,1]*m[6,2] + S[1,1]*m[2,6] + S[1,2]*m[6,3] + S[2,1]*m[3,6] +
S[1,3]*m[6,4] + S[3,1]*m[4,6] + S[1,4]*m[6,5] + S[4,1]*m[5,6] + S[1,5]*m[6,6] +
S[5,1]*m[6,6] + S[1,6]*m[6,7] + S[6,1]*m[7,6] + S[1,7]*m[6,8] + S[7,1]*m[8,6] +
S[1,8]*m[6,9] + S[8,1]*m[9,6] + S[1,9]*m[6,1] + S[9,1]*m[1,6] + S[1,5]*m[2,6] +
S[5,1]*m[6,2]
С16
Пω =
S[1,1]*m[7,2] + S[1,1]*m[2,7] + S[1,2]*m[7,3] + S[2,1]*m[3,7] +
S[1,3]*m[7,4] + S[3,1]*m[4,7] + S[1,4]*m[7,5] + S[4,1]*m[5,7] + S[1,5]*m[7,6] +
S[5,1]*m[6,7] + S[1,6]*m[7,7] + S[6,1]*m[7,7] + S[1,7]*m[7,8] + S[7,1]*m[8,7] +
S[1,8]*m[7,9] + S[8,1]*m[9,7] + S[1,9]*m[7,1] + S[9,1]*m[1,7] + S[1,6]*m[2,7] +
S[6,1]*m[7,2]
С17
Пω =
S[1,1]*m[8,2] + S[1,1]*m[2,8] + S[1,2]*m[8,3] + S[2,1]*m[3,8] +
S[1,3]*m[8,4] + S[3,1]*m[4,8] + S[1,4]*m[8,5] + S[4,1]*m[5,8] + S[1,5]*m[8,6] +
S[5,1]*m[6,8] + S[1,6]*m[8,7] + S[6,1]*m[7,8] + S[1,7]*m[8,8] + S[7,1]*m[8,8] +
S[1,8]*m[8,9] + S[8,1]*m[9,8] + S[1,9]*m[8,1] + S[9,1]*m[1,8] + S[1,7]*m[2,8] +
S[7,1]*m[8,2]
С18
Пω =
S[1,1]*m[9,2] + S[1,1]*m[2,9] + S[1,2]*m[9,3] + S[2,1]*m[3,9] +
S[1,3]*m[9,4] + S[3,1]*m[4,9] + S[1,4]*m[9,5] + S[4,1]*m[5,9] + S[1,5]*m[9,6] +
S[5,1]*m[6,9] + S[1,6]*m[9,7] + S[6,1]*m[7,9] + S[1,7]*m[9,8] + S[7,1]*m[8,9] +
S[1,8]*m[9,9] + S[8,1]*m[9,9] + S[1,9]*m[9,1] + S[9,1]*m[1,9] + S[1,8]*m[2,9] +
S[8,1]*m[9,2]
С19
Пω
[1,9]= S[1,1]*m[1,2] + S[1,1]*m[2,1] + S[1,2]*m[1,3] +
S[2,1]*m[3,1] + S[1,3]*m[1,4] + S[3,1]*m[4,1] + S[1,4]*m[1,5] +
S[4,1]*m[5,1] + S[1,5]*m[1,6] + S[5,1]*m[6,1] + S[1,6]*m[1,7] + S[6,1]*m[7,1] +
S[1,7]*m[1,8] + S[7,1]*m[8,1] + S[1,8]*m[1,9] + S[8,1]*m[9,1] + S[1,9]*m[1,1] +
S[9,1]*m[1,1] + S[1,9]*m[2,1] + S[9,1]*m[1,2]
С21
Пω =
S[2,1]*m[2,2] + S[1,2]*m[2,2] + S[2,2]*m[2,3] + S[2,2]*m[3,2] +
S[2,3]*m[2,4] + S[3,2]*m[4,2] + S[2,4]*m[2,5] + S[4,2]*m[5,2] +
S[2,5]*m[2,6] + S[5,2]*m[6,2] + S[2,6]*m[2,7] + S[6,2]*m[7,2] + S[2,7]*m[2,8] +
S[7,2]*m[8,2] + S[2,8]*m[2,9] + S[8,2]*m[9,2] + S[2,9]*m[2,1] + S[9,2]*m[1,2] +
S[2,1]*m[3,2] + S[1,2]*m[2,3]
………………………………………………………………
С99
Пω =
S[9,1]*m[1,2] + S[1,9]*m[2,1] + S[9,2]*m[1,3] + S[2,9]*m[3,1] + S[9,3]*m[1,4] +
S[3,9]*m[4,1] + S[9,4]*m[1,5] + S[4,9]*m[5,1] + S[9,5]*m[1,6] + S[5,9]*m[6,1] +
S[9,6]*m[1,7] + S[6,9]*m[7,1] + S[9,7]*m[1,8] + S[7,9]*m[8,1] +
S[9,8]*m[1,9] + S[8,9]*m[9,1] + S[9,9]*m[1,1] + S[9,9]*m[1,1] +
S[9,9]*m[1,1] + S[9,9]*m[1,1]
Получили матрицу С
Пω :
|
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
1 |
30 |
30 |
50 |
100 |
140 |
150 |
120 |
200 |
48 |
|
2 |
52 |
80 |
72 |
120 |
200 |
180 |
166 |
300 |
80 |
|
3 |
100 |
150 |
100 |
150 |
220 |
210 |
172 |
340 |
148 |
|
4 |
132 |
190 |
140 |
130 |
170 |
104 |
130 |
200 |
190 |
|
5 |
170 |
250 |
130 |
140 |
104 |
84 |
88 |
196 |
250 |
|
6 |
206 |
260 |
160 |
132 |
84 |
60 |
96 |
160 |
260 |
|
7 |
280 |
350 |
200 |
200 |
104 |
92 |
116 |
136 |
350 |
|
8 |
126 |
168 |
120 |
152 |
200 |
186 |
200 |
280 |
320 |
|
9 |
180 |
200 |
120 |
140 |
80 |
56 |
80 |
200 |
200 |
Рисунок
15
Найдём элементы матрицы
Qω по выражению
(4):
|
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
1 |
0 |
-28 |
20 |
72 |
176 |
266 |
254 |
16 |
-2 |
|
2 |
-28 |
0 |
42 |
100 |
266 |
300 |
320 |
108 |
0 |
|
3 |
20 |
42 |
0 |
60 |
146 |
210 |
156 |
80 |
-32 |
|
4 |
72 |
100 |
60 |
0 |
76 |
46 |
84 |
-58 |
0 |
|
5 |
176 |
266 |
146 |
76 |
0 |
4 |
-28 |
12 |
26 |
|
6 |
266 |
300 |
210 |
46 |
4 |
0 |
12 |
6 |
56 |
|
7 |
254 |
320 |
156 |
84 |
-28 |
12 |
0 |
-60 |
114 |
|
8 |
16 |
108 |
80 |
-58 |
12 |
6 |
-60 |
0 |
40 |
|
9 |
-2 |
0 |
-32 |
0 |
26 |
56 |
114 |
40 |
0 |
Рисунок
16
Получили: min Q= -60
<0
p:=y7=8 , v:=y8=9 è y7:=v=9 , y8:=p=8 и переход к п.3 (т.е. к
Итерации 2)
(т.е. у нас y = { 2, 3, 4, 5, 6, 7, 9, 8,
1})
Рисунок
17
Итерация
2:
С1
02 =
S[1,1]*m[2,2] + S[1,1]*m[2,2] + S[1,2]*m[2,3] + S[2,1]*m[3,2] +
S[1,3]*m[2,4] + S[3,1]*m[4,2] + S[1,4]*m[2,5] + S[4,1]*m[5,2] + S[1,5]*m[2,6] +
S[5,1]*m[6,2] + S[1,6]*m[2,7] + S[6,1]*m[7,2] + S[1,7]*m[2,9] + S[7,1]*m[9,2] +
S[1,8]*m[2,8] + S[8,1]*m[8,2] + S[1,9]*m[2,1] +
S[9,1]*m[1,2]
С2
02 = S[2,1]*m[3,2] +
S[1,2]*m[2,3] + S[2,2]*m[3,3] + S[2,2]*m[3,3] + S[2,3]*m[3,4] +
S[3,2]*m[4,3] + S[2,4]*m[3,5] + S[4,2]*m[5,3] + S[2,5]*m[3,6] +
S[5,2]*m[6,3] + S[2,6]*m[3,7] + S[6,2]*m[7,3] + S[2,7]*m[3,9] + S[7,2]*m[9,3] +
S[2,8]*m[3,8] + S[8,2]*m[8,3] + S[2,9]*m[3,1] +
S[9,2]*m[1,3]
С3
02=
S[3,1]*m[4,2] + S[1,3]*m[2,4] + S[3,2]*m[4,3] + S[2,3]*m[3,4] +
S[3,3]*m[4,4] + S[3,3]*m[4,4] + S[3,4]*m[4,5] + S[4,3]*m[5,4] +
S[3,5]*m[4,6] + S[5,3]*m[6,4] + S[3,6]*m[4,7] + S[6,3]*m[7,4] + S[3,7]*m[4,9] +
S[7,3]*m[9,4] + S[3,8]*m[4,8] + S[8,3]*m[8,4] + S[3,9]*m[4,1] +
S[9,3]*m[1,4]
С4
02 =
S[4,1]*m[5,2] + S[1,4]*m[2,5] + S[4,2]*m[5,3] + S[2,4]*m[3,5] +
S[4,3]*m[5,4] + S[3,4]*m[4,5] + S[4,4]*m[5,5] + S[4,4]*m[5,5] +
S[4,5]*m[5,6] + S[5,4]*m[6,5] + S[4,6]*m[5,7] + S[6,4]*m[7,5] +
S[4,7]*m[5,9] + S[7,4]*m[9,5] + S[4,8]*m[5,8] + S[8,4]*m[8,5] + S[4,9]*m[5,1] +
S[9,4]*m[1,5]
С5
02 =
S[5,1]*m[6,2] + S[1,5]*m[2,6] + S[5,2]*m[6,3] + S[2,5]*m[3,6] + S[5,3]*m[6,4] +
S[3,5]*m[4,6] + S[5,4]*m[6,5] + и +
S[5,5]*m[6,6] + S[5,5]*m[6,6] + S[5,6]*m[6,7] + S[6,5]*m[7,6] +
S[5,7]*m[6,9] + S[7,5]*m[9,6] + S[5,8]*m[6,8] + S[8,5]*m[8,6] + S[5,9]*m[6,1] +
S[9,5]*m[1,6]
С6
02 =
S[6,1]*m[7,2] + S[1,6]*m[2,7] + S[6,2]*m[7,3] + S[2,6]*m[3,7] + S[6,3]*m[7,4] +
S[3,6]*m[4,7] + S[6,4]*m[7,5] + S[4,6]*m[5,7] + S[6,5]*m[7,6] +
S[5,6]*m[6,7] + S[6,6]*m[7,7] + S[6,6]*m[7,7] + S[6,7]*m[7,9] +
S[7,6]*m[9,7] + S[6,8]*m[7,8] + S[8,6]*m[8,7] + S[6,9]*m[7,1] +
S[9,6]*m[1,7]
С7
02 =
S[7,1]*m[9,2] + S[1,7]*m[2,9] + S[7,2]*m[9,3] + S[2,7]*m[3,9] + S[7,3]*m[9,4] +
S[3,7]*m[4,9] + S[7,4]*m[9,5] + S[4,7]*m[5,9] + S[7,5]*m[9,6] + S[5,7]*m[6,9] +
S[7,6]*m[9,7] + S[6,7]*m[7,9] + S[7,7]*m[9,9] + S[7,7]*m[9,9] +
S[7,8]*m[9,8] + S[8,7]*m[8,9] + S[7,9]*m[9,1] +
S[9,7]*m[1,9]
С8
02 =
S[8,1]*m[8,2] + S[1,8]*m[2,8] + S[8,2]*m[8,3] + S[2,8]*m[3,8] + S[8,3]*m[8,4] +
S[3,8]*m[4,8] + S[8,4]*m[8,5] + S[4,8]*m[5,8] + S[8,5]*m[8,6] + S[5,8]*m[6,8] +
S[8,6]*m[8,7] + S[6,8]*m[7,8] + S[8,7]*m[8,9] + S[7,8]*m[9,8] +
S[8,8]*m[8,8] + S[8,8]*m[8,8] + S[8,9]*m[8,1] +
S[9,8]*m[1,8]
С9
02 =
S[9,1]*m[1,2] + S[1,9]*m[2,1] + S[9,2]*m[1,3] + S[2,9]*m[3,1] + S[9,3]*m[1,4] +
S[3,9]*m[4,1] + S[9,4]*m[1,5] + S[4,9]*m[5,1] + S[9,5]*m[1,6] + S[5,9]*m[6,1] +
S[9,6]*m[1,7] + S[6,9]*m[7,1] + S[9,7]*m[1,9] + S[7,9]*m[9,1] +
S[9,8]*m[1,8] + S[8,9]*m[8,1] + S[9,9]*m[1,1] +
S[9,9]*m[1,1]
С
02 ={
30,
80,
100,
130,
104,
80,
136,
200,
120}
П.
4
С11
Пω
=
S[1,1]*m[2,2] + S[1,1]*m[2,2] + S[1,2]*m[2,3] + S[2,1]*m[3,2] +
S[1,3]*m[2,4] + S[3,1]*m[4,2] + S[1,4]*m[2,5] + S[4,1]*m[5,2] + S[1,5]*m[2,6] +
S[5,1]*m[6,2] + S[1,6]*m[2,7] + S[6,1]*m[7,2] + S[1,7]*m[2,9] + S[7,1]*m[9,2] +
S[1,8]*m[2,8] + S[8,1]*m[8,2] + S[1,9]*m[2,1] + S[9,1]*m[1,2] + S[1,1]*m[2,2] +
S[1,1]*m[2,2]
С12
Пω
=
S[1,1]*m[3,2] + S[1,1]*m[2,3] + S[1,2]*m[3,3] + S[2,1]*m[3,3] + S[1,3]*m[3,4] +
S[3,1]*m[4,3] + S[1,4]*m[3,5] + S[4,1]*m[5,3] + S[1,5]*m[3,6] + S[5,1]*m[6,3] +
S[1,6]*m[3,7] + S[6,1]*m[7,3] + S[1,7]*m[3,9] + S[7,1]*m[9,3] + S[1,8]*m[3,8] +
S[8,1]*m[8,3] + S[1,9]*m[3,1] + S[9,1]*m[1,3] + S[1,2]*m[2,3] +
S[2,1]*m[3,2]
C13 Пω
= S[1,1]*m[4,2] + S[1,1]*m[2,4] + S[1,2]*m[4,3] + S[2,1]*m[3,4] +
S[1,3]*m[4,4] + S[3,1]*m[4,4] + S[1,4]*m[4,5] + S[4,1]*m[5,4] + S[1,5]*m[4,6] +
S[5,1]*m[6,4] + S[1,6]*m[4,7] + S[6,1]*m[7,4] + S[1,7]*m[4,9] + S[7,1]*m[9,4] +
S[1,8]*m[4,8] + S[8,1]*m[8,4] + S[1,9]*m[4,1] + S[9,1]*m[1,4] + S[1,3]*m[2,4] +
S[3,1]*m[4,2]
С14
Пω
=
S[1,1]*m[5,2] + S[1,1]*m[2,5] + S[1,2]*m[5,3] + S[2,1]*m[3,5] +
S[1,3]*m[5,4] + S[3,1]*m[4,5] + S[1,4]*m[5,5] + S[4,1]*m[5,5] + S[1,5]*m[5,6] +
S[5,1]*m[6,5] + S[1,6]*m[5,7] + S[6,1]*m[7,5] + S[1,7]*m[5,9] + S[7,1]*m[9,5] +
S[1,8]*m[5,8] + S[8,1]*m[8,5] + S[1,9]*m[5,1] + S[9,1]*m[1,5] + S[1,4]*m[2,5] +
S[4,1]*m[5,2]
С15
Пω =
S[1,1]*m[6,2] + S[1,1]*m[2,6] + S[1,2]*m[6,3] + S[2,1]*m[3,6] +
S[1,3]*m[6,4] + S[3,1]*m[4,6] + S[1,4]*m[6,5] + S[4,1]*m[5,6] + S[1,5]*m[6,6] +
S[5,1]*m[6,6] + S[1,6]*m[6,7] + S[6,1]*m[7,6] + S[1,7]*m[6,9] + S[7,1]*m[9,6] +
S[1,8]*m[6,8] + S[8,1]*m[8,6] + S[1,9]*m[6,1] + S[9,1]*m[1,6] + S[1,5]*m[2,6] +
S[5,1]*m[6,2]
С16
Пω =
S[1,1]*m[7,2] + S[1,1]*m[2,7] + S[1,2]*m[7,3] + S[2,1]*m[3,7] +
S[1,3]*m[7,4] + S[3,1]*m[4,7] + S[1,4]*m[7,5] + S[4,1]*m[5,7] + S[1,5]*m[7,6] +
S[5,1]*m[6,7] + S[1,6]*m[7,7] + S[6,1]*m[7,7] + S[1,7]*m[7,9] + S[7,1]*m[9,7] +
S[1,8]*m[7,8] + S[8,1]*m[8,7] + S[1,9]*m[7,1] + S[9,1]*m[1,7] + S[1,6]*m[2,7] +
S[6,1]*m[7,2]
С17
Пω =
S[1,1]*m[9,2] + S[1,1]*m[2,9] + S[1,2]*m[9,3] + S[2,1]*m[3,9] +
S[1,3]*m[9,4] + S[3,1]*m[4,9] + S[1,4]*m[9,5] + S[4,1]*m[5,9] + S[1,5]*m[9,6] +
S[5,1]*m[6,9] + S[1,6]*m[9,7] + S[6,1]*m[7,9] + S[1,7]*m[9,9] + S[7,1]*m[9,9] +
S[1,8]*m[9,8] + S[8,1]*m[8,9] + S[1,9]*m[9,1] + S[9,1]*m[1,9] + S[1,7]*m[2,9] +
S[7,1]*m[9,2]
С18
Пω =
S[1,1]*m[8,2] + S[1,1]*m[2,8] + S[1,2]*m[8,3] + S[2,1]*m[3,8] +
S[1,3]*m[8,4] + S[3,1]*m[4,8] + S[1,4]*m[8,5] + S[4,1]*m[5,8] + S[1,5]*m[8,6] +
S[5,1]*m[6,8] + S[1,6]*m[8,7] + S[6,1]*m[7,8] + S[1,7]*m[8,9] + S[7,1]*m[9,8] +
S[1,8]*m[8,8] + S[8,1]*m[8,8] + S[1,9]*m[8,1] + S[9,1]*m[1,8] + S[1,8]*m[2,8] +
S[8,1]*m[8,2]
С19
Пω
S[1,1]*m[1,2] + S[1,1]*m[2,1] + S[1,2]*m[1,3] + S[2,1]*m[3,1] +
S[1,3]*m[1,4] + S[3,1]*m[4,1] + S[1,4]*m[1,5] + S[4,1]*m[5,1] + S[1,5]*m[1,6] +
S[5,1]*m[6,1] + S[1,6]*m[1,7] + S[6,1]*m[7,1] + S[1,7]*m[1,9] + S[7,1]*m[9,1] +
S[1,8]*m[1,8] + S[8,1]*m[8,1] + S[1,9]*m[1,1] + S[9,1]*m[1,1] + S[1,9]*m[2,1] +
S[9,1]*m[1,2]
С21
Пω =
S[2,1]*m[2,2] + S[1,2]*m[2,2] + S[2,2]*m[2,3] + S[2,2]*m[3,2] +
S[2,3]*m[2,4] + S[3,2]*m[4,2] + S[2,4]*m[2,5] + S[4,2]*m[5,2] +
S[2,5]*m[2,6] + S[5,2]*m[6,2] + S[2,6]*m[2,7] + S[6,2]*m[7,2] + S[2,7]*m[2,9] +
S[7,2]*m[9,2] + S[2,8]*m[2,8] + S[8,2]*m[8,2] + S[2,9]*m[2,1] + S[9,2]*m[1,2] +
S[2,1]*m[3,2] + S[1,2]*m[2,3]
………………………………………………………………
С99
Пω =
S[9,1]*m[1,2] + S[1,9]*m[2,1] + S[9,2]*m[1,3] + S[2,9]*m[3,1] + S[9,3]*m[1,4] +
S[3,9]*m[4,1] + S[9,4]*m[1,5] + S[4,9]*m[5,1] + S[9,5]*m[1,6] + S[5,9]*m[6,1] +
S[9,6]*m[1,7] + S[6,9]*m[7,1] + S[9,7]*m[1,9] + S[7,9]*m[9,1] +
S[9,8]*m[1,8] + S[8,9]*m[8,1] + S[9,9]*m[1,1] + S[9,9]*m[1,1] +
S[9,9]*m[1,1] + S[9,9]*m[1,1]
Получили матрицу С
Пω :
|
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
1 |
30 |
30 |
50 |
100 |
140 |
150 |
200 |
120 |
48 |
|
2 |
52 |
80 |
72 |
120 |
200 |
180 |
300 |
166 |
80 |
|
3 |
100 |
150 |
100 |
150 |
220 |
210 |
340 |
172 |
148 |
|
4 |
132 |
190 |
140 |
130 |
170 |
104 |
200 |
130 |
190 |
|
5 |
170 |
250 |
130 |
140 |
104 |
84 |
196 |
88 |
250 |
|
6 |
290 |
340 |
210 |
220 |
104 |
80 |
136 |
140 |
340 |
|
7 |
196 |
270 |
150 |
112 |
84 |
92 |
136 |
116 |
270 |
|
8 |
210 |
248 |
170 |
240 |
220 |
206 |
280 |
200 |
320 |
|
9 |
96 |
120 |
70 |
52 |
60 |
36 |
80 |
120 |
120 |
Рисунок
18
дём
элементы матрицы Qω по выражению
(4):
|
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
1 |
0 |
-28 |
20 |
72 |
176 |
330 |
230 |
100 |
-6 |
|
2 |
-28 |
0 |
42 |
100 |
266 |
360 |
354 |
134 |
0 |
|
3 |
20 |
42 |
0 |
60 |
146 |
240 |
254 |
42 |
-2 |
|
4 |
72 |
100 |
60 |
0 |
76 |
114 |
46 |
40 |
-8 |
|
5 |
176 |
266 |
146 |
76 |
0 |
4 |
40 |
4 |
86 |
|
6 |
330 |
360 |
240 |
114 |
4 |
0 |
12 |
66 |
176 |
|
7 |
230 |
354 |
254 |
46 |
40 |
12 |
0 |
60 |
94 |
|
8 |
100 |
134 |
42 |
40 |
4 |
66 |
60 |
0 |
120 |
|
9 |
-6 |
0 |
-2 |
-8 |
86 |
176 |
94 |
120 |
0 |
Рисунок
19
Получили: min Q= -28
<0
p:=y1=2 , v:=y2=3 è y1:=v=3 , y2:=p=2 и переход к п.3 (т.е. к
Итерации 3)
(т.е. у нас y = { 3, 2, 4, 5, 6, 7, 9, 8,
1})
Рисунок
20
Все промежуточные
результаты, иллюстрирующие основные промежуточные значения для всех итераций и
вариантов ω=1…9 (по алгоритму), приведены в таблице рисунка
21.
|
Вариант v |
Итер ация |
Y1 |
Y2 |
Y3 |
Y4 |
Y5 |
Y6 |
Y7 |
Y8 |
Y9 |
Min
Q |
Q0 |
|
1 |
1 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
-28 |
|
|
2 |
1 |
2 |
3 |
4 |
5 |
8 |
7 |
6 |
9 |
-10 |
| |
|
3 |
1 |
3 |
2 |
4 |
5 |
8 |
7 |
6 |
9 |
0 |
342 | |
|
2 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
1 |
-60 |
|
|
2 |
2 |
3 |
4 |
5 |
6 |
7 |
9 |
8 |
1 |
-28 |
| |
|
3 |
3 |
2 |
4 |
5 |
6 |
7 |
9 |
8 |
1 |
-8 |
| |
|
4 |
3 |
2 |
4 |
1 |
6 |
7 |
9 |
8 |
5 |
-42 |
| |
|
5 |
3 |
2 |
1 |
4 |
6 |
7 |
9 |
8 |
5 |
-10 |
| |
|
6 |
3 |
1 |
2 |
4 |
6 |
7 |
9 |
8 |
5 |
0 |
402 | |
|
3 |
1 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
1 |
2 |
-60 |
|
|
2 |
3 |
4 |
5 |
6 |
7 |
9 |
8 |
1 |
2 |
-24 |
| |
|
3 |
3 |
4 |
5 |
6 |
7 |
9 |
8 |
2 |
1 |
-6 |
| |
|
4 |
3 |
2 |
5 |
6 |
7 |
9 |
8 |
4 |
1 |
-6 |
| |
|
5 |
3 |
2 |
4 |
6 |
7 |
9 |
8 |
5 |
1 |
0 |
454 | |
|
4 |
1 |
4 |
5 |
6 |
7 |
8 |
9 |
1 |
2 |
3 |
-70 |
|
|
2 |
9 |
5 |
6 |
7 |
8 |
4 |
1 |
2 |
3 |
-76 |
| |
|
3 |
9 |
8 |
6 |
7 |
5 |
4 |
1 |
2 |
3 |
-32 |
| |
|
4 |
9 |
7 |
6 |
8 |
5 |
4 |
1 |
2 |
3 |
-10 |
| |
|
5 |
9 |
7 |
6 |
8 |
5 |
4 |
2 |
1 |
3 |
0 |
342 | |
|
5 |
1 |
5 |
6 |
7 |
8 |
9 |
1 |
2 |
3 |
4 |
-128 |
|
|
2 |
9 |
6 |
7 |
8 |
5 |
1 |
2 |
3 |
4 |
-60 |
| |
|
3 |
9 |
6 |
7 |
8 |
5 |
4 |
2 |
3 |
1 |
0 |
342 | |
|
6 |
1 |
6 |
7 |
8 |
9 |
1 |
2 |
3 |
4 |
5 |
-60 |
|
|
2 |
6 |
7 |
9 |
8 |
1 |
2 |
3 |
4 |
5 |
-28 |
| |
|
3 |
6 |
7 |
9 |
8 |
5 |
2 |
3 |
4 |
1 |
-40 |
| |
|
4 |
6 |
7 |
9 |
8 |
5 |
4 |
3 |
2 |
1 |
-20 |
| |
|
5 |
9 |
7 |
6 |
8 |
5 |
4 |
3 |
2 |
1 |
-10 |
| |
|
6 |
9 |
7 |
6 |
8 |
5 |
4 |
2 |
3 |
1 |
0 |
342 | |
|
7 |
1 |
7 |
8 |
9 |
1 |
2 |
3 |
4 |
5 |
6 |
-60 |
|
|
2 |
7 |
9 |
8 |
1 |
2 |
3 |
4 |
5 |
6 |
-44 |
| |
|
3 |
9 |
7 |
8 |
1 |
2 |
3 |
4 |
5 |
6 |
-20 |
| |
|
4 |
9 |
7 |
6 |
1 |
2 |
3 |
4 |
5 |
8 |
-12 |
| |
|
5 |
9 |
7 |
6 |
2 |
1 |
3 |
4 |
5 |
8 |
0 |
420 | |
|
8 |
1 |
8 |
9 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
-80 |
|
|
2 |
9 |
8 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
-20 |
| |
|
3 |
9 |
8 |
1 |
2 |
3 |
4 |
5 |
7 |
6 |
-10 |
| |
|
4 |
9 |
8 |
4 |
2 |
3 |
1 |
5 |
7 |
6 |
-2 |
| |
|
5 |
9 |
8 |
4 |
1 |
3 |
2 |
5 |
7 |
6 |
0 |
432 | |
|
9 |
1 |
9 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
-60 |
|
|
2 |
8 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
9 |
-20 |
| |
|
3 |
5 |
1 |
2 |
3 |
4 |
8 |
6 |
7 |
9 |
-18 |
| |
|
4 |
4 |
1 |
2 |
3 |
5 |
8 |
6 |
7 |
9 |
-60 |
| |
|
5 |
3 |
1 |
2 |
4 |
5 |
8 |
6 |
7 |
9 |
0 |
342 |
Рисунок
21
П. 14. Вывод результатов
расчёта оптимального значения целевой функции Q0 и списка оптимальных
решений {yi}*:
Получили несколько вариантов с одинаковыми значениями целевых функций
Q0 =
342
{9, 7, 6,
8, 5, 4, 2, 1, 3} (вариант 4
)
{9, 6, 7, 8, 5, 4, 2, 3, 1}
(вариант 5
)
{yi}* = {9, 7, 6,
8, 5, 4, 2, 3, 1} (вариант 6
)
{1, 3, 2, 4, 5, 8, 7, 6, 9}
(вариант 1 )
{3, 1, 2, 4, 5, 8, 6, 7, 9}
(вариант 9
)
Принимаем в качестве решения
вариант 1
