.1 Составление первоначального базисного распределения
Сотавляем таблицу 2.2 (матрицу) по закреплению маршрутов методом абсолютного двойного предпочтения. Для этого отмечаем звёздочками клетки по столбцам и строкам, имеющие наименьшие расстояния. В первую очередь заносим корреспонденцию в отмеченные двумя звёздочками клетки, затем одной звёздочкой и, наконец, в другие клетки с наименьшим расстоянием. Загружают корреспонденциями Qij клетки в порядке возрастания в них lij.
Объём корреспонденции Qij,
заносимый в клетку ji
определяют как минимум объёма по строке и объёма по столбцу с учётом ранее
назначенных других перевозок.
Qij = (Qi
, Qj).
Затем определяют число загруженных клеток
базисного распределения:
N = m
+ n - 1.
где m - число строк,
n - число столбцов.
N = 11 + 7 - 1 = 17.
После этого подсчитаем количество занятых клеток в таблице 2.2 и сравним его с рассчитанным. Эти числа совпадают, а это значит что вспомогательные величины (потенциалы) определяются.
Определим вспомогательные величины:
Если из расстояния каждой i
-ой строки вычесть Ui
и из расстояний каждого j
-го столбца Uj, то
относительной оценкой любой клетки может вместо lij
служить параметр Uij.
Uij = lij
- Uj - Ui.
Принимая для загруженных клеток Uij
= 0, определяем значения Ui
и Uj:
Ui = lij - Uj = 0.
Uj = lij - Ui = 0.
= 0.= 12 - 0 = 12.= 18 - 12 = 6.= 15 - 6 = 9.= 14 - 9 = 5.= 4 - 9 = -5.= 6 - 9 = -3.= 12 - 9 =3.= 8 - 9 = -1.= 10 - 3 =7.= 8 - 7 = 1.= 6 - 1 = 5.= 8 - 7 = 1.= 6 - 1 = 5.= 9 - 5 = 4.1 = 6 - 4 = 2.
UB7 = 4 - 2 = 2.
UA5 = 8 - 2 = 6.
Полученные значения расчётов заносим в таблицу 2.2.
Определим Uij (оценочный параметр) для всех свободных клеток и полученные значения записываем в левом верхнем углу таблицы 2.2. Причём должно выполняться условие для свободной клетки:
Uij >= 0
В нашем случае это условие выполняется для всех клеток.
Для проверки оптимальности распределения
определим вспомогательные величины Ui
и Uj, а затем определим
оценочные параметры Uij,
определив предварительно N
и, сравнив его значения с m+n-1.
Значения этих величин приведены в таблице 2.2. Минимальное количество Uij
> 0 говорит том, что закрепления потребителей за поставщиками является
оптимальным.
Таблица 2.2 - Первоначальный и улучшенный вариант базисного распределения.
|
Грузо полу ча тель ВJ |
Вспомога- тельная величина |
Грузоотправитель Ai |
Завоз, т |
|||||||||||||
|
|
|
А1 |
А2 |
А3 |
А4 |
А5 |
А6 |
А7 |
|
|||||||
|
|
UJ |
Ui |
|
|||||||||||||
|
|
|
2 |
5 |
5 |
7 |
6 |
9 |
12 |
|
|||||||
|
B1 |
0 |
13 |
15 |
4 |
9 |
3 |
8 |
5 |
12 |
8 |
14 |
4 |
13 |
0 |
12 |
28 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
28 |
|
|
B2 |
1 |
15 |
18 |
0 |
6 |
4 |
10 |
0 |
8 |
5 |
12 |
-2 |
8 |
1 |
14 |
40 |
|
|
|
|
|
|
31 |
|
|
|
9 |
|
|
|
|
|
|
|
|
B3 |
-5 |
13 |
10 |
4 |
4 |
15 |
15 |
13 |
15 |
7 |
8 |
0 |
4 |
1 |
8 |
54 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
54 |
|
|
|
|
B4 |
5 |
8 |
15 |
5 |
15 |
15 |
25 |
4 |
16 |
4 |
15 |
0 |
14 |
1 |
18 |
32 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
32 |
|
|
|
|
B5 |
6 |
0 |
8 |
2 |
3 |
14 |
3 |
16 |
4 |
16 |
0 |
15 |
0 |
18 |
60 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
12 |
|
48 |
|
|
B6 |
1 |
3 |
6 |
10 |
16 |
0 |
6 |
0 |
8 |
9 |
16 |
30 |
40 |
7 |
20 |
87 |
|
|
|
|
|
|
|
|
60 |
|
27 |
|
|
|
|
|
|
|
|
B7 |
2 |
0 |
4 |
7 |
14 |
7 |
14 |
3 |
12 |
0 |
8 |
3 |
14 |
-4 |
10 |
84 |
|
|
|
|
28 |
|
|
|
|
|
|
|
56 |
|
|
|
|
|
|
B8 |
-3 |
11 |
10 |
11 |
13 |
6 |
8 |
8 |
12 |
9 |
12 |
0 |
6 |
15 |
24 |
56 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
56 |
|
|
|
|
B9 |
4 |
0 |
6 |
0 |
9 |
1 |
10 |
3 |
14 |
2 |
12 |
16 |
29 |
0 |
16 |
95 |
|
|
|
|
40 |
|
55 |
|
|
|
|
|
|
|
|
|
|
|
|
B10 |
3 |
3 |
8 |
2 |
10 |
1 |
9 |
0 |
10 |
7 |
16 |
0 |
12 |
-1 |
14 |
90 |
|
|
|
|
|
|
|
|
|
|
48 |
|
|
|
42 |
|
|
|
|
B11 |
-1 |
8 |
9 |
15 |
19 |
3 |
7 |
3 |
9 |
15 |
20 |
0 |
8 |
2 |
13 |
76 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
76 |
|
|
|
|
Вывоз, т |
68 |
86 |
60 |
84 |
56 |
272 |
76 |
702 |
||||||||
.2 Выбор маршрутов
Для выбора маршрутов используем метод
совмещённых планов. Для этого дополнив таблицу 2.2. данными об объёмах
перевозок от поставщика Ai
к потребителю Bj, получим
таблицу совмещённого плана 2.3. В полученной таблице объём перевозок и возврат
автомобилей обозначены следующим образом: например для ячейки В10 А6, 90 -
объём перевозок, 42 - возврат автомобилей.
Таблица 2.3 - Совмещённый план.
|
Грузополу чатель ВJ |
Грузоотправитель Ai |
|||||||||||||
|
|
А1 |
А2 |
А3 |
А4 |
А5 |
А6 |
А7 |
|||||||
|
B1 |
13 |
15 |
4 |
9 |
3 |
8 |
5 |
12 |
8 |
14 |
4 |
13 |
0 |
12 |
|
|
28 |
|
|
|
|
|
|
|
|
|
|
|
|
28 |
|
B2 |
15 |
18 |
0 |
6 |
4 |
10 |
0 |
8 |
5 |
12 |
-2 |
8 |
1 |
14 |
|
|
40 |
|
|
31 |
|
|
|
9 |
|
|
|
|
|
|
|
B3 |
13 |
10 |
4 |
4 |
15 |
15 |
13 |
15 |
7 |
8 |
0 |
4 |
1 |
8 |
|
|
|
|
54 |
|
|
|
|
|
|
|
|
54 |
|
|
|
B4 |
8 |
15 |
5 |
15 |
15 |
25 |
4 |
16 |
4 |
15 |
0 |
14 |
1 |
18 |
|
|
|
|
32 |
|
|
|
|
|
|
|
|
32 |
|
|
|
B5 |
0 |
8 |
2 |
13 |
3 |
14 |
3 |
16 |
4 |
16 |
0 |
15 |
0 |
18 |
|
|
|
|
|
|
60 |
|
|
|
|
|
|
12 |
|
48 |
|
B6 |
3 |
6 |
10 |
16 |
0 |
6 |
0 |
8 |
9 |
16 |
30 |
40 |
7 |
20 |
|
|
|
|
|
|
|
60 |
|
27 |
|
|
87 |
|
|
|
|
B7 |
0 |
4 |
7 |
14 |
7 |
14 |
3 |
12 |
0 |
8 |
3 |
14 |
-4 |
10 |
|
|
|
28 |
|
|
|
|
84 |
|
|
56 |
|
|
|
|
|
B8 |
11 |
10 |
11 |
13 |
6 |
8 |
8 |
12 |
9 |
12 |
0 |
6 |
15 |
24 |
|
|
|
|
|
|
|
|
|
|
56 |
|
|
56 |
|
|
|
B9 |
0 |
6 |
0 |
9 |
1 |
10 |
3 |
14 |
2 |
12 |
16 |
29 |
0 |
16 |
|
|
|
40 |
|
55 |
|
|
|
|
|
|
95 |
|
|
|
|
B10 |
3 |
8 |
2 |
10 |
1 |
9 |
0 |
10 |
7 |
16 |
0 |
12 |
-1 |
14 |
|
|
|
|
|
|
|
|
|
48 |
|
|
90 |
42 |
|
|
|
B11 |
8 |
9 |
15 |
19 |
3 |
7 |
3 |
9 |
15 |
20 |
0 |
8 |
2 |
13 |
|
|
|
|
|
|
|
|
|
|
|
|
|
76 |
76 |
|
Количество тонн груза, на каждом маятниковом
маршруте (таблица 2.4), используемом для клеток, где имеется объём перевозок и
возврат авто - тонн, определяется меньшей из двух цифр в этих клетках.
Результаты сводим в таблицу 2.5.
Таблица 2.4 - Определение маятникового маршрута №1.
|
Грузополу чатель ВJ |
Грузоотправитель Ai |
|||||||||||||||||||||||||||
|
|
А1 |
А2 |
А3 |
А4 |
А5 |
А6 |
А7 |
13 |
15 |
4 |
9 |
3 |
8 |
5 |
12 |
8 |
14 |
4 |
13 |
0 |
12 |
|||||||
|
|
28 |
|
|
|
|
|
|
|
|
|
|
|
|
28 |
||||||||||||||
|
B2 |
15 |
18 |
0 |
6 |
4 |
10 |
0 |
8 |
5 |
12 |
-2 |
8 |
1 |
14 |
||||||||||||||
|
|
40 |
|
|
31 |
|
|
|
9 |
|
|
|
|
|
|
||||||||||||||
|
B3 |
13 |
10 |
4 |
4 |
15 |
15 |
13 |
15 |
7 |
8 |
0 |
4 |
1 |
8 |
||||||||||||||
|
|
|
|
54 |
|
|
|
|
|
|
|
|
54 |
|
|
||||||||||||||
|
B4 |
8 |
15 |
5 |
15 |
15 |
25 |
4 |
16 |
4 |
15 |
0 |
14 |
1 |
18 |
||||||||||||||
|
|
|
|
32 |
|
|
|
|
|
|
|
|
32 |
|
|
||||||||||||||
|
B5 |
0 |
8 |
2 |
13 |
3 |
14 |
3 |
16 |
4 |
16 |
0 |
15 |
0 |
18 |
||||||||||||||
|
|
|
|
|
|
60 |
|
|
|
|
|
|
12 |
|
48 |
||||||||||||||
|
B6 |
3 |
6 |
10 |
16 |
0 |
6 |
0 |
8 |
9 |
16 |
30 |
40 |
7 |
20 |
||||||||||||||
|
|
|
|
|
|
|
60 |
|
27 |
|
|
87 |
|
|
|
||||||||||||||
|
B7 |
0 |
4 |
7 |
14 |
7 |
14 |
3 |
12 |
0 |
8 |
3 |
14 |
-4 |
10 |
||||||||||||||
|
|
|
28 |
|
|
|
|
84 |
|
|
56 |
|
№1 |
|
|
||||||||||||||
|
B8 |
11 |
10 |
11 |
13 |
6 |
8 |
8 |
12 |
9 |
12 |
0 |
6 |
15 |
24 |
||||||||||||||
|
|
|
|
|
|
|
|
|
|
56 |
|
|
56 |
|
|
||||||||||||||
|
B9 |
0 |
6 |
0 |
9 |
1 |
10 |
3 |
14 |
2 |
12 |
16 |
29 |
0 |
16 |
||||||||||||||
|
|
|
40 |
|
55 |
|
|
|
|
|
|
95 |
|
|
|
||||||||||||||
|
B10 |
3 |
8 |
2 |
10 |
1 |
9 |
0 |
10 |
7 |
16 |
0 |
12 |
-1 |
14 |
||||||||||||||
|
|
|
|
|
|
|
|
|
48 |
|
|
90 |
42 |
|
|
||||||||||||||
|
B11 |
8 |
9 |
15 |
19 |
3 |
7 |
3 |
9 |
15 |
20 |
0 |
8 |
2 |
13 |
||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
76 |
76 |
|
||||||||||||||
Таблица 2.5 - Маятниковые маршруты.
|
Маршрут |
Длина маршрута, км |
Объём перевозок, т |
|
№1 А6 - В10 - А6 |
12 |
42 |
Таблица 2.6 - Выбор кольцевых маршрутов №2, №3.
|
Грузополу чатель ВJ |
Грузоотправитель Ai |
|||||||||||||
|
|
А1 |
А2 |
А3 |
А4 |
А5 |
А6 |
А7 |
|||||||
|
B1 |
13 |
15 |
4 |
9 |
3 |
8 |
5 |
12 |
8 |
14 |
4 |
13 |
0 |
12 |
|
|
28 |
|
|
|
|
|
|
|
|
|
|
|
|
28 |
|
B2 |
15 |
18 |
0 |
6 |
4 |
10 |
0 |
8 |
5 |
12 |
-2 |
8 |
1 |
14 |
|
|
40 |
|
|
31 |
|
|
|
9 |
|
|
|
|
|
|
|
B3 |
13 |
10 |
4 |
4 |
15 |
15 |
13 |
15 |
7 |
8 |
0 |
4 |
1 |
8 |
|
|
|
|
54 |
|
|
|
|
|
|
|
|
54 |
|
|
|
B4 |
8 |
15 |
5 |
15 |
15 |
25 |
4 |
16 |
4 |
15 |
0 |
14 |
1 |
18 |
|
|
|
|
32 |
|
|
|
|
|
|
|
|
32 |
|
|
|
B5 |
0 |
8 |
2 |
13 |
3 |
14 |
3 |
16 |
4 |
16 |
0 |
15 |
0 |
18 |
|
|
|
|
|
|
60 |
|
|
|
|
|
|
12 |
|
48 |
|
B6 |
3 |
6 |
10 |
16 |
0 |
6 |
0 |
8 |
9 |
16 |
30 |
40 |
7 |
20 |
|
|
|
|
|
|
|
60 |
|
27 |
|
|
87 |
|
|
|
|
B7 |
0 |
4 |
7 |
14 |
7 |
14 |
3 |
12 |
0 |
8 |
3 |
14 |
-4 |
10 |
|
|
|
28 |
|
|
|
|
84 |
|
|
56 |
|
№2 |
|
|
|
B8 |
11 |
10 |
11 |
13 |
6 |
8 |
8 |
12 |
9 |
12 |
0 |
6 |
15 |
24 |
|
|
|
|
|
|
|
|
|
|
56 |
|
|
|||
|
B9 |
0 |
6 |
0 |
9 |
1 |
10 |
3 |
14 |
2 |
12 |
16 |
29 |
0 |
16 |
|
|
|
40 |
|
55 |
|
|
|
|
|
|
95 |
|
|
|
|
B10 |
3 |
8 |
2 |
10 |
1 |
9 |
0 |
10 |
7 |
16 |
0 |
12 |
-1 |
14 |
|
|
|
|
|
|
|
|
|
48 |
|
|
48 |
|
|
№3 |
|
B11 |
8 |
9 |
15 |
19 |
3 |
7 |
3 |
9 |
15 |
20 |
0 |
8 |
2 |
13 |
|
|
|
|
|
|
|
|
|
|
|
|
|
76 |
76 |
|
Кольцевой маршрут №2 А2 - В4 - А6 - В9 - А2 - 32 тонны. L=67 км.
Кольцевой маршрут №3 А1 - В1 - А7 - В11 - А6 -
В9 - А1 - 28 тонн. L=83км.
Таблица 2.7 - Выбор кольцевых маршрутов №4, №5.
|
Грузополу чатель ВJ |
Грузоотправитель Ai |
|||||||||||||
|
|
А1 |
А2 |
А3 |
А4 |
А5 |
А6 |
А7 |
|||||||
|
B1 |
13 |
15 |
4 |
9 |
3 |
8 |
5 |
12 |
8 |
14 |
4 |
13 |
0 |
12 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
B2 |
15 |
18 |
0 |
6 |
4 |
10 |
0 |
8 |
5 |
12 |
-2 |
8 |
1 |
14 |
|
|
40 |
|
|
31 |
|
|
|
9 |
|
|
|
|
|
|
|
B3 |
13 |
10 |
4 |
4 |
15 |
15 |
13 |
15 |
7 |
8 |
0 |
4 |
1 |
8 |
|
|
|
|
54 |
|
|
|
|
|
|
|
|
54 |
|
|
|
B4 |
8 |
15 |
5 |
15 |
15 |
25 |
4 |
16 |
4 |
15 |
0 |
14 |
1 |
18 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
B5 |
0 |
8 |
2 |
13 |
3 |
14 |
3 |
16 |
4 |
16 |
0 |
15 |
0 |
18 |
|
|
|
|
|
|
60 |
|
|
|
|
|
|
12 |
|
48 |
|
B6 |
3 |
6 |
10 |
16 |
0 |
6 |
0 |
8 |
9 |
16 |
30 |
40 |
7 |
20 |
|
|
|
|
|
|
|
60 |
|
27 |
|
|
87 |
|
|
№4 |
|
B7 |
0 |
4 |
7 |
14 |
7 |
14 |
3 |
12 |
0 |
8 |
3 |
14 |
-4 |
10 |
|
|
|
28 |
|
|
|
|
84 |
|
|
56 |
|
|
|
|
|
B8 |
11 |
10 |
11 |
13 |
6 |
8 |
8 |
12 |
9 |
12 |
0 |
6 |
15 |
24 |
|
|
|
|
|
|
|
|
|
|
56 |
|
|
56 |
|
|
|
B9 |
0 |
6 |
0 |
9 |
1 |
10 |
3 |
14 |
2 |
12 |
16 |
29 |
0 |
16 |
|
|
|
12 |
|
23 |
|
№5 |
|
|
|
|
35 |
|
|
|
|
B10 |
3 |
8 |
2 |
10 |
1 |
9 |
0 |
10 |
7 |
16 |
0 |
12 |
-1 |
14 |
|
|
|
|
|
|
|
|
|
48 |
|
|
48 |
|
|
|
|
B11 |
8 |
9 |
15 |
19 |
3 |
7 |
3 |
9 |
15 |
20 |
0 |
8 |
2 |
13 |
|
|
|
|
|
|
|
|
|
|
|
|
|
48 |
48 |
|