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

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

Шаг 5

С₂₃→ ∞;

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

1	2	3	4	5	6	hi
1	∞	0	11	17	55	65	0
2	0	∞	∞	14	61	85	11
3	35	0	∞	41	92	120	0
4	0	10	0	∞	3	43	0
5	28	54	48	0	∞	0	0
6	45	78	76	37	0	∞	0
Hj	0	0	37	0	0	0

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

Шаг 5.1

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

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

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

Ө(1,2)=11+0=11; Ө(2,1)=14+0=14; Ө(3,2)=35+0=35; Ө(4,1)=0+0=0; Ө(4,3)=11+0=11; Ө(5,4)=14+0=14; Ө(5,6)=43+0=43; Ө(6,5)=3+37=40;

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

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

ξ(G²₂)=264+43=307;

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

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

1	2	3	4	5	hi
1	∞	0	11	17	52	0
2	0	∞	∞	14	58	0
3	35	0	∞	41	89	0
4	0	10	0	∞	0	0
6	8	41	39	0	∞	37
Hj	0	0	0	0	3

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

ξ(G²₁)=264+40=304;

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

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

Шаг 5.2.

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

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

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

Ө(1,2)=11+0=11; Ө(2,1)=14+0=14; Ө(3,2)=35+0=35; Ө(4,1)=0+0=0; Ө(4,3)=11+0=11; Ө(4,5)=52+0=52; Ө(6,4)=8+14=22;

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

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

ξ(G³₂)=304+52=356;

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

таблица 15(С³₁ )

1	2	3	4	hi
1	∞	0	11	17	0
2	0	∞	∞	14	0
3	35	0	∞	41	0
6	0	33	31	∞	8
Hj	0	0	11	14

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

ξ(G³₁)=304+33=337;

Вывод:

Так как ξ(G³₁)=337> ξ(G⁶₁)=305 дальнейшее ветвление на подмножества не имеет смысла, так как длина данного цикла будет увеличиваться.

Шаг 6

С₅₆→ ∞;

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

1	2	4	5	6	hi
1	∞	0	17	55	22	0
3	0	∞	6	57	42	0
4	0	10	∞	3	0	0
5	28	54	0	∞	∞	0
6	45	78	37	0	∞	0
Hj	0	0	0	0	43

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

Шаг 6.1

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

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

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

Ө(1,2)=17+10=27; Ө(3,1)=0+6=6; Ө(4,1)=0+0=0; Ө(4,6)=22+0=22; Ө(5,4)=6+28=34; Ө(6,5)=3+37=40;

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

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

ξ(G³₂)=294+40=334;

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

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

1	2	4	6	hi
1	∞	0	17	22	0
3	0	∞	6	42	0
4	0	10	∞	0	0
5	28	54	0	∞	0
Hj	0	0	0	0

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

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

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

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

Шаг 6.2

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

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

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

Ө(1,2)=17+10=27; Ө(3,1)=0+6=6; Ө(4,1)=0+0=0; Ө(4,6)=0+22=22; Ө(5,4)=6+28=34;

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

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

ξ(G⁴₂)=294+34=328;

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

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

1	2	6	hi
1	∞	0	0	0
3	0	∞	20	0
4	0	10	∞	0
Hj	0	0	22

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

ξ(G⁴₁)=294+22=316;

Вывод:

Так как ξ(G⁴₁)=316> ξ(G⁶₁)=305 дальнейшее ветвление на подмножества не имеет смысла, так как длина данного цикла будет увеличиваться.

Вывод:

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

Издержки на транспортировку продукции по данному маршруту будут равны: (22+24+82+48+42+87)*0,5=152,5 у.д.е.

2. Решаем задачу для автомобилей для складов № 4.

Таблица 17

Расстояние между оптовым складом и сетью розничных магазинов

Склады и магазины	Расстояние между складами и магазинами, км
	Склад№4	1	2	3	4	5
Склад№4	∞	11	39	63	58	100
1	11	∞	30	53	55	90
2	45	30	∞	28	40	60
3	63	61	28	∞	60	50
4	58	55	34	60	∞	60
5	100	90	60	58	60	∞

Пользуясь методом ветвей и границ, определим порядок посещения автомобилем склада и пяти магазинов. Сформируем начальную «матрицу» и осуществим ее приведение по строкам и столбцам.

Таблица 17а

JI	Расстояние между складами и магазинами, км
	Склад№4	1	2	3	4	5	Hi
Склад№4	∞	11	39	63	58	100	11
1	11	∞	30	53	55	90	11
2	45	30	∞	28	40	60	28
3	63	61	28	∞	60	50	28
4	58	55	34	60	∞	60	34
5	100	90	60	58	60	∞	58
Hj

Таблица 17б

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

Таблица 17в