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

JI	Расстояние между складами и магазинами, км
	Склад№4	1	2	3	4	5	Hi
Склад№4	∞	0	28	52	45	67	11
1	0	∞	19	42	42	57	11
2	17	2	∞	0	10	10	28
3	35	33	0	∞	30	0	28
4	24	21	0	26	∞	4	34
5	42	32	2	0	0	∞	58
Hj	0	0	0	0	2	22

2. Определим оценку G⁰, вычислив сумму приводящих констант:

ξ(G⁰)=170+24=194;

Таблица 17(C⁰)

1	2	3	4	5	6	hi
1	∞	0	28	52	45	67	11
2	0	∞	19	42	42	57	11
3	17	2	∞	0	10	10	28
4	35	33	0	∞	30	0	28
5	24	21	0	26	∞	4	34
6	42	32	2	0	0	∞	58
Hj	0	0	0	0	2	22

Шаг 1

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

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

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

Ө(1,2)=28+2=30; Ө(2,1)=17+19=36; Ө(3,4)=2+0=2; Ө(4,3)=0+0=0; Ө(4,6)=4+0=4; Ө(5,3)=0+4=4; Ө(6,4)=0+0=0; Ө(6,5)=10+0=10;

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

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

ξ(G¹₂)=194+36=230;

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

Таблица 17(C¹₁)

2	3	4	5	6	hi
1	∞	0	24	17	39	28
3	0	∞	0	10	10	0
4	31	0	∞	30	0	0
5	19	0	26	∞	4	0
6	30	2	0	0	∞	0
Hj	2	0	0	0	0

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

ξ(G¹₁)=194+30=224;

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

G⁰=G¹₁UG¹₂, где G¹₁={2, 1}, а G¹₂={2, 1}

Шаг 2

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

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

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

Ө(1,3)=17 +0=17; Ө(3,2)=0+19=19; Ө(3,4)=0+0=0; Ө(4,3)=0+0=0; Ө(4,6)=4+0=4; Ө(5,3)=0+4=4; Ө(6,4)=0+0=0; Ө(6,5)=0+10=10;

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

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

ξ(G²₂)=224+19=243;

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

Таблица 17(C²₁)

3	4	5	6	hi
1	∞	7	0	22	17
4	0	∞	30	0	0
5	0	26	∞	4	0
6	2	0	0	∞	0
Hj	0	0	0	0

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

ξ(G²₁)=224+17=241;

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

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

G¹₁=G²₁UG²₂, где G²₁={3,2}, а G²₂={3,2}

Шаг 3

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

С₁₅=0, С₄₃=0, С₄₆=0, С₅₃=0, С₆₄=0, С₆₅=0

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

Ө(1,5)=7+0=7; Ө(4,3)=0+0=0; Ө(4,6)=4+0=4; Ө(5,3)=0+4=4; Ө(6,4)=0+7=7; Ө(6,5)=0+0=0;

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

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

ξ(G³₂)=241+7=248;

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

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

3	4	6	hi
4	0	∞	0	0
5	∞	22	0	4
6	2	0	∞	0
Hj	0	0	0

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

ξ(G³₁)=241+4=245;

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

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

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

Шаг 4

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

С₄₃=0, С₄₆=0, С₅₆=0, С₆₄=0;

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

Ө(4,3)=2+0=0; Ө(4,6)=0+0=0; Ө(5,6)=0+22=22; Ө(6,4)=2+22=24;

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

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

ξ(G⁴₂)=245+24=269;

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

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

3	6	hi
4	0	∞	0
5	∞	0	0
Hj	0	0

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

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

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

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

G⁰=194

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

194+30=224 194+36=230

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

224+17=241 224+19=243.

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

241+4=245 241+7=248

G⁴₁(6,4) G⁴₂(6,4)

245+0=245 245+24=269

G⁵₁(4,3)

245+0=245

G⁶₁(5,6)

245+0=245

Вывод:

Так как полученная матрица- приведенная, то ξ(G⁴₁)= ξ(G³₁)=245.

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

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

Эти подмножества могут привести к образованию цикла с меньшей оценкой, поэтому оно должно быть подвергнуто анализу.