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

Таблица 14(С21)

	Склад №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. Вычислим оценку для ветвления G21:

ξ(G21)=251+40=291;

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

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

G11=G21U G22, где G21={4,5}, G22={4,5}

Шаг 3

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

Сij=0;

ССклад№3 1=0, С2Склад№3=0, С3Склад№3=0, С34=0, С53=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. Вычислим оценку для ветвления G32:

ξ(G32)=291+54=345;

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

Таблица 14(С31)

	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. Вычислим оценку для ветвления G31:

ξ(G31)=291+14=305;

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

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

G21=G31U G32, где G31= {4, 5}, а G32={4, 5}

Шаг 4

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

С12=0, С31=0, С61=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. Вычислим оценку для ветвления G42:

ξ(G42)=305+44=349;

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

Таблица 14(С41)

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

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

ξ(G41)=305+0=305;

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

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

G0=216

G11(2,3) G12(2,3)

216+35=251 216+48=264

G21(5,6) G22(5,6)

251+40=291 251+43=294

G31(4,5) G32(4,5)

291+14=305 291+52=343

G41(1,2) G42(1,2)

305+0=305 305+44=349

G51(3,4)

305+0=305

G61(6,1)

305+0=305

Вывод:

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

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

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

Шаг 5

С23→ ∞;

Таблица 15(C11)

	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

ξ(G12)=216+48=264;

Шаг 5.1

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

С12=0, С21=0, С32=0, С41=0, С43=0, С54=0, С56=0, С65=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. Вычислим оценку для ветвления G22:

ξ(G22)=264+43=307;

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

Таблица 15(С21)

	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. Вычислим оценку для ветвления G21:

ξ(G21)=264+40=304;

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

G12=G21U G22, где G11={5, 6}, а G12={5, 6}

Шаг 5.2.

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

С12=0, С21=0, С32=0, С41=0, С43=0, С45=0, С64=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. Вычислим оценку для ветвления G32:

ξ(G32)=304+52=356;

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

таблица 15(С31 )

	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. Вычислим оценку для ветвления G31:

ξ(G31)=304+33=337;

Вывод:

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

Шаг 6

С56→ ∞;

Таблица 16(С21)

	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

ξ(G22)=251+43=294;

Шаг 6.1

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

С12=0, С31=0, С41=0, С46=0, С54=0, С65=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. Вычислим оценку для ветвления G32:

ξ(G32)=294+40=334;

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

Таблица 16(С31)

	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. Вычислим оценку для ветвления G31:

ξ(G31)=294+0=294;

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

G22=G31U G32, где G31={6, 5}, а G32={6, 5}

Шаг 6.2

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

С12=0, С31=0, С41=0, С46=0, С54=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. Вычислим оценку для ветвления G42:

ξ(G42)=294+34=328;

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

таблица 16(С41 )

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

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

ξ(G41)=294+22=316;

Вывод:

Так как ξ(G41)=316> ξ(G61)=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а

J I	Расстояние между складами и магазинами, км
J I	Склад№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б

J I	Расстояние между складами и магазинами, км
J I	Склад№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в

J I	Расстояние между складами и магазинами, км
J I	Склад№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

Страницы: 1, 2, 3, 4, 5