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

Шаг 5

С₂₁→ ∞;

Таблица 18

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

Таблица 18а

1	2	3	4	5	6	hi
1	∞	0	28	52	45	67	0
2	∞	∞	0	23	23	38	19
3	17	2	∞	0	10	10	0
4	35	33	0	∞	30	0	0
5	24	21	0	26	∞	4	0
6	42	32	2	0	0	∞	0
Hj	17	0	0	0	0	0

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

1	2	3	4	5	6	hi
1	∞	0	28	52	45	67	0
2	∞	∞	0	23	23	38	19
3	0	2	∞	0	10	10	0
4	18	33	0	∞	30	0	0
5	7	21	0	26	∞	4	0
6	25	32	2	0	0	∞	0
Hj	17	0	0	0	0	0

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

Шаг 5.1

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

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

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

Ө(1,2)=2+28=30; Ө(2,3)=0+23=23; Ө(3,1)=7+0=7; Ө(3,4)=0+0=0; Ө(4,3)=0+0=0; Ө(4,6)=4+0=4; Ө(5,3)=4+0=4; Ө(6,4)=0+0=0; Ө(6,5)=0+10=10;

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

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

ξ(G²₂)=230+30=260;

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

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

1	3	4	5	6	hi
2	∞	0	23	23	38	0
3	0	∞	0	10	10	0
4	18	0	∞	30	0	0
5	7	0	26	∞	4	0
6	25	2	0	0	∞	0
Hj	0	0	0	0	0

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

ξ(G²₁)=230+0=230;

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

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

Шаг 5.2

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

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

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

Ө(2,3)=23+0=23; Ө(3,1)=7+0=7; Ө(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;

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

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

ξ(G³₂)=230+23=253;

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

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

1	4	5	6	hi
3	∞	0	10	10	0
4	15	∞	30	0	0
5	0	22	∞	0	4
6	22	0	0	∞	0
Hj	3	0	0	0

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

ξ(G³₁)=230+7=237;

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

Шаг 5.3

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

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

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

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

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

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

ξ(G⁴₂)=237+15=252;

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

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

1	4	5	hi
3	∞	0	10	0
5	0	22	∞	0
6	22	∞	0	0
Hj	0	0	0

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

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

G³₁= G⁴₁UG⁴₂ где = G⁴₁ {4,6},а = G⁴₂{4,6}

Шаг 5.4

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

C34 =0; C51=0; C65=0;

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

Ө(3,4)=10+22=32; Ө(5,1)=22+22=44; Ө(6,5)=22+10=32;

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

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

ξ(G⁵₂)=237+44=281;

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

таблица 18(С⁴₁)

4	5	Hi
3	0	∞	0
6	∞	0	0
Hj	0	0

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

ξ(G⁵₁ )=237+0=237;

Вывод:

Так как ξ(G⁵₁)=237< ξ(G⁶₁)=245 дальнейшее ветвление на подмножества не имеет смысла.

Вывод:

В результате проверки данных подмножеств выяснилась, что полученная длина новых циклов меньше, чем длина предыдущего. Следовательно, маршрут 1→2→3→4→6→5→1, является оптимальным.

Издержки на транспортировку продукции по данному маршруту будут равны:(11+30+28+50+60+58)*0,5=118,5

Шаг 6

С₃₂→ ∞;

Таблица 19(С⁰)

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

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

Шаг 6.1

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

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

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

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

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

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

ξ(G³₂)=243+17=260;

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

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

2	4	5	6	hi
3	∞	0	10	10	0
4	12	∞	30	0	0
5	0	26	∞	4	0
6	11	0	0	∞	0
Hj	0	0	0	0

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

ξ(G³₁)=243+0=243;

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

Шаг 6.2

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

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

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

Ө(3,4)=10+0=10; Ө(4,6)=12+4=16; Ө(5,2)=4+11=15; Ө(6,4)=0+0=0; Ө(6,5)=0+10=10;

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