Формирование логистической цепи (стр. 6 из 10)

ξ(G⁰)=22+24+35+45+42+42+6=216

1.1.Выберем пары складов и магазинов для ветвления, т. е. (i,j), для которых Сij=0:

С_{Склад№3 1}=0, С₁₂=0, С₂₁=0, С_{3Склад№3}=0, С₄₃=0, С₄₅=0, С₅₄=0;

Для выявления претендентов подсчитаем оценки:

Ө(Склад№3,1)=17+0=17;

Ө(1,2)=11+37=48;

Ө(2,1)=35+0=35;

Ө(3,Склад№3)=11+3=14;

Ө(4,3)=0+17=17;

Ө(4,5)=0+43=43;

Ө(5,4)=37+3=40;

Для ветвления выберем пару претендентов с максимальной оценкой, т. е. пару (1,2), так как max Ө(1,2)=48;

1.2.Вычислим оценку для ветвления G¹₂:

ξ(G¹₂)=216+48=264

1.3.Построим матрицу С¹₁, для этого вычеркнем в матрице C⁰ первую строку и второй столбец. Чтобы избежать образования замкнутых циклов, запретим переезд из 2 в 1, полагая, что С₂₁→ ∞и выполним процесс приведения. В результате получим матрицу С¹₁:

Таблица 14(С¹₁)

Склад№3	1	3	4	5	h i
Склад№3	∞	0	17	55	65	0
2	35	∞	41	92	120	35
3	0	10	∞	3	43	0
4	28	54	0	∞	0	0
5	45	78	37	0	∞	0

Склад№3	1	3	4	5
Склад№3	∞	0	17	55	65
2	0	∞	6	57	85
3	0	10	∞	3	43
4	28	54	0	∞	0
5	45	78	37	0	∞
h j	0	0	0	0	0

Склад№3	1	3	4	5
Склад№3	∞	0	17	55	65
2	0	∞	6	57	85
3	0	10	∞	3	43
4	28	54	0	∞	0
5	45	78	37	0	∞

1.4.Вычислим оценку для ветвления G¹₁:

ξ(G¹₁)=216+35=251

1.5.Произведем ветвление G⁰=G¹₁UG¹₂, где G¹₁={1, 2}, G¹₂={1, 2}

Шаг 2

1.1. Выберем пары складов и магазинов для ветвления, т. е.(i,j), для которых Сij=0:

С_{Склад№31}=0, С_{2Склад№3}=0, С_{3Склад№3}=0, С₄₃=0, С₄₅=0, С₅₄=0;

Для выявления претендентов подсчитаем оценки:

Ө(Склад№3,1)=17+10=27;

Ө(2,Склад№3)=6+0=6;

Ө(3,Склад№3)=3+0=3;

Ө(4,3)=6+0=6;

Ө(4,5)=43+0=43;

Ө(5,4)=37+3=40;

Для ветвления выберем пару претендентов с максимальной оценкой, т. е. пару (4,5), так как max Ө(4,5)=43;

1.2. Вычислим оценку для ветвления G²₂:

ξ(G²₂)=251+43=294;

1.3. Построим матрицу С²₁, для этого вычеркнем в матрице C¹₁ четвертую строку и пятый столбец. Чтобы избежать образования замкнутых циклов, запретим переезд из 5 в 4: полагая, что С₅₄→ ∞и выполним процесс приведения. В результате получим матрицу С²₁:

Таблица 14(С²₁)

Склад№3	1	3	4	h i
Склад№3	∞	0	17	55	0
2	0	∞	6	57	0
3	0	10	∞	3	0
5	45	78	37	∞	37

Склад№3	1	3	4
Склад№3	∞	0	17	55
2	0	∞	6	57
3	0	10	∞	3
5	8	41	0	∞
h j	0	0	0	3

Склад№3	1	3	4
Склад№3	∞	0	17	52
2	0	∞	6	54
3	0	10	∞	0
5	8	41	0	∞

1.4. Вычислим оценку для ветвления G²₁:

ξ(G²₁)=251+40=291;

1.5. Произведем ветвление.

Так как ξ(G¹₁)< ξ(G¹₂), то на следующем шаге разбиваем подмножество ξ(G¹₁).

G¹₁=G²₁UG²₂, где G²₁={4,5}, G²₂={4,5}

Шаг 3

1.1. Выберем пары складов и магазинов для ветвления, т. е. (i,j), для которых

Сij=0;

С_{Склад№3 1}=0, С_{2Склад№3}=0, С_{3Склад№3}=0, С₃₄=0, С₅₃=0;

Для выявления претендентов подсчитаем оценки:

Ө(Склад№3,1)=17+10=27;

Ө(2,Склад№3)=6+0=6;

Ө(3,Склад№3)=0+0=0;

Ө(3,4)=0+54=54;

Ө(5,3)=8+6=14;

Для ветвления выберем пару претендентов с максимальной оценкой, т. е. пару (3,4), так как max Ө(3,4)=54;

1.2. Вычислим оценку для ветвления G³₂:

ξ(G³₂)=291+54=345;

1.3. Построим матрицу С³₁, для этого вычеркнем в матрице C²₁ третью строку и четвертый столбец. Чтобы избежать образования замкнутых циклов, запретим переезд из 5 в 3: полагая, что С₅₃→ ∞и выполним процесс приведения. В результате получим матрицу С³₁:

Таблица 14(С³₁)

1	2	4	min i
1	∞	0	11	0
3	0	∞	0	0
6	0	33	∞	8
min j	0	0	6

Склад№3	1	3
Склад№3	∞	0	17
2	0	∞	6
5	8	41	0

1.4. Вычислим оценку для ветвления G³₁:

ξ(G³₁)=291+14=305;

1.5. Произведем ветвление;

Так как ξ(G²₁)< ξ(G²₂), то на следующем шаге разбиваем подмножество ξ(G²₁).

G²₁=G³₁UG³₂, где G³₁= {4, 5}, а G³₂={4, 5}

Шаг 4

1.1. Выберем пары магазин-склад - претендентов на ветвление, т. е., (i,j), для которых Сij=0;

С₁₂=0, С₃₁=0, С₆₁=0;

Для выявления претендентов подсчитаем оценки:

Ө(1,2)=11+33=44; Ө(3,1)=0+0=0; Ө(3,4)=11+0=11; Ө(6,1)=0+33=33;

Для ветвления выберем пару претендентов с максимальной оценкой, т. е. пару (1,2), так как max Ө(1,2)=44;

1.2. Вычислим оценку для ветвления G⁴₂:

ξ(G⁴₂)=305+44=349;

1.3. Построим матрицу С⁴₁, для этого вычеркнем в матрице C³₁ первую строку и второй столбец.Чтобы избежать образования замкнутых циклов, запретим переезд из 3 в 1: полагая, что С₃₁→ ∞и выполним процесс приведения. В результате получим матрицу С⁴₁:

Таблица 14(С⁴₁)

1	4	min i
3	∞	0	0
6	0	∞	0
min j	0	0

1.4. Вычислим оценку для ветвления G⁴₁:

ξ(G⁴₁)=305+0=305;

1.5. Произведем ветвление;

Так как ξ(G³₁)< ξ(G³₂), то на следующем шаге разбиваем подмножество ξ(G³₁).

G⁰=216

G¹₁(2,3) G¹₂(2,3)

216+35=251 216+48=264

G²₁(5,6) G²₂(5,6)

251+40=291 251+43=294

G³₁(4,5) G³₂(4,5)

291+14=305 291+52=343

G⁴₁(1,2) G⁴₂(1,2)

305+0=305 305+44=349

G⁵₁(3,4)

305+0=305

G⁶₁(6,1)

305+0=305

Вывод:

Так как полученная матрица- приведенная, то ξ(G⁴₁)= ξ(G³₁)=305. Матрица (С⁴₁) имеет размерность 2x2 и допускает в маршрут только двух пар (6,1) и (3,4), что соответствует шагам 5-6. В результате получаем цикл t={(2,3), (5,6), (4,5), (1,2), (6,1), (3,4)}, отвечающий подмножеству G⁶₁. Длина цикла t равна оценке для подмножества G⁶₁: 1(t)= ξ(G⁶₁)=305.

Сравним длину этого цикла с полученными ранее оценками для неветвленных подмножества. Подмножество G¹₂ ,G²₂ ,имеют меньшую оценку, чем построенный цикл: ξ(G¹₂)=264<ξ(G⁶₁)=305; ξ(G²₂)=294<ξ(G⁶₁)=305;