Материал: Оптимизация транспортных потоков при перевозке грузов с использованием автомобильного транспорта
Из таблицы 3.4 видно, что наибольшее значение суммы констант приведения получается на пересечении 6й строки и 7-го столбца и 7й строки и 6го столбца и составляет 5100. Рассмотрим первый вариант.
Априорно исключаем из
гамильтонова контура дугу (6,7), заменяя
элементы а7,6 = 0
в матрице расстояний на 
. В
результате исключения данной дуги будет образовано подмножество гамильтоновых
контуров {
}.
Приводим полученную матрицу
расстояний и определяем нижнюю границу 
подмножества гамильтоновых контуров
{}.
Таблица 3.5 - Исключение 6 строки и 7 столбца
|
Из/В |
Б |
М1 |
М2 |
М3 |
М4 |
М5 |
|
Б |
|
|
|
|
|
|
|
М1 |
0 |
|
|
|
|
|
|
М2 |
4600 |
1100 |
|
|
|
|
|
М3 |
8500 |
5000 |
0 |
|
|
|
|
М4 |
3500 |
0 |
4500 |
700 |
|
|
|
М6 |
6400 |
2900 |
7900 |
11000 |
5200 |
|
Таблица 3.6 - Приведение матрицы по строкам
|
Из/В |
Б |
М1 |
М2 |
М3 |
М4 |
М5 |
|
|
Б |
|
|
|
|
|
|
|
|
М1 |
0 |
|
|
|
|
|
|
|
М2 |
4600 |
1100 |
|
|
|
|
|
|
М3 |
8500 |
5000 |
0 |
|
|
|
|
|
М4 |
3500 |
0 |
4500 |
700 |
|
|
|
|
М6 |
6400 |
2900 |
7900 |
11000 |
5200 |
|
|
Таблица 3.7- Приведение матрицы по столбцам
|
Из/В |
Б |
М1 |
М2 |
М3 |
М4 |
М5 |
|
Б |
|
|
|
|
|
|
|
М1 |
0 |
|
|
|
|
|
|
М2 |
4600 |
1100 |
|
|
|
|
|
М3 |
8500 |
5000 |
0 |
|
|
|
|
М4 |
3500 |
0 |
4500 |
700 |
|
|
|
М6 |
3500 |
0 |
5000 |
8100 |
2300 |
|
|
|
|
|
|
|
|
|
000002200
Тогда 
а
Матрица,
полученная после приведения по строкам и столбцам приведена в таблице 3.8.
Каждый нуль в полученной
матрице условно заменяем на 
и находим сумму констант приведения
. Значения 
записываем
в соответствующие клетки рядом с нулями (таблица 3.9).
Таблица 3.8 - Полностью приведенная матрица
|
Из/В |
Б |
М1 |
М2 |
М3 |
М4 |
М5 |
|
Б |
|
|
|
|
|
|
|
М1 |
0 |
|
|
|
|
|
|
М2 |
4600 |
1100 |
|
|
|
|
|
М3 |
5000 |
0 |
|
|
|
|
|
М4 |
3500 |
0 |
4500 |
700 |
|
|
|
М6 |
3500 |
0 |
5000 |
8100 |
2300 |
|
Таблица 3.9 - Определение сумм констант приведения
|
Из/В |
Б |
М1 |
М2 |
М3 |
М4 |
М5 |
|
Б |
|
|
|
|
|
|
|
М1 |
0(3500) |
|
|
|
|
|
|
М2 |
4600 |
1100 |
|
|
|
|
|
М3 |
8500 |
5000 |
0(1800) |
|
|
|
|
М4 |
3500 |
0(0) |
4500 |
700 |
|
|
|
М6 |
3500 |
0(3500) |
5000 |
8100 |
2300 |
|
Из таблицы 3.9
видно, что наибольшее значение суммы констант приведения получается на
пересечении 5 строки и 6
столбца и составляет 5000.
Априорно исключаем из гамильтонова контура дугу (5,6)
и проводим расчеты аналогичные предыдущим.
Таблица 3.10 - Исключение 5й строки и 6го столбца
|
Из/В |
Б |
М1 |
М2 |
М3 |
М4 |
|
Б |
|
|
|
|
|
|
М1 |
0 |
|
|
|
|
|
М2 |
4600 |
1100 |
|
|
|
|
М3 |
8500 |
5000 |
0 |
|
|
|
М6 |
3500 |
0 |
5000 |
8100 |
|
Таблица 3.11 - Приведение матрицы по строкам
|
Из/В |
Б |
М1 |
М2 |
М3 |
М4 |
|
|
Б |
|
|
|
|
|
|
|
М1 |
0 |
|
|
|
|
|
|
М2 |
4600 |
1100 |
|
|
|
|
|
М3 |
8500 |
5000 |
0 |
|
|
|
|
М6 |
3500 |
0 |
5000 |
8100 |
|
|
Таблица 3.12 - Приведение матрицы по столбцам
|
Из/В |
Б |
М1 |
М2 |
М3 |
М4 |
|
Б |
|
|
|
|
|
|
М1 |
0 |
|
|
|
|
|
М2 |
4600 |
1100 |
|
|
|
|
М3 |
8500 |
5000 |
0 |
|
|
|
М6 |
3500 |
0 |
5000 |
8100 |
|
|
|
|
|
|
|
|
Тогда 
а
Матрица,
полученная после приведения по строкам и столбцам приведена в таблице 3.13.
Каждый нуль в полученной
матрице условно заменяем на и находим сумму констант приведения
. Значения записываем
в соответствующие клетки рядом с нулями (таблица 3.14).
Таблица 3.13 - Полностью приведенная матрица
|
Из/В |
Б |
М1 |
М2 |
М3 |
М4 |
|
Б |
|
|
|
|
|
|
М1 |
0 |
|
|
|
|
|
М2 |
4600 |
1100 |
|
|
|
|
М3 |
8500 |
5000 |
0 |
|
|
|
М6 |
3500 |
0 |
5000 |
8100 |
|
Таблица 3.14 - Определение сумм констант приведения
|
Из/В |
Б |
М1 |
М2 |
М3 |
М4 |
|
Б |
|
|
|
|
|
|
М1 |
0(3500) |
|
|
|
|
|
М2 |
4600 |
1100 |
|
|
|
|
М3 |
8500 |
5000 |
0(1800) |
|
|
|
М6 |
3500 |
0 |
5000 |
8100 |
|