Информационные технологии на автомобильном транспорте. Информационные технологии на транспорте. Костенко В.И - 18 стр.

UptoLike

ВУЗ: 

СЗТУ | Санкт-Петербург

Составители: 

Рубрика: 

В случае если число занятых клеток в матрице больше, чем m+n—1,
поступают следующим образом. В табл. 15 - семь занятых клеток вместо
необходимых шести (m+n-1=3+4—1=6). Наличие лишней занятой клетки
приводит к тому, что индексы определяются неоднозначно. В первом случае
U
2
=9—15= - 6, во втором U
2
=6—5= 1.
Таблица 15
Вспомогательные Пункт назначения
Б
1
Б
2
Б
3
Б
4
Пункт
отправления
строка
столбец
15 5 8
Наличие
груза, т
А
1
0
9
15
20
⎯
5
+
30
8
30
80
А
2
-6,1
4
9
40 +
6
⎯10
5
50
А
3
16
30
22
10
10
18
40
Потребность в грузе, т 30 70 40 30 170
Уменьшение числа занятых клеток производится следующим образом. В
матрице строят замкнутую цепочку из горизонтальных и вертикальных
отрезков так, чтобы все ее вершины находились в занятых клетках (см. табл.
16). Такая цепочка в матрице с числом занятых клеток более m+n -1 всегда
имеется. На вершинах цепочки, начиная с клетки, имеющей наименьшую
загрузку, расставляют
попеременно знаки минус и плюс, после чего загрузки со
знаком минус уменьшают, а со знаком плюс увеличивают на величину
наименьшей из них. В результате число занятых клеток уменьшится не менее
чем на одну (табл.17). При необходимости данную процедуру повторяют
столько раз, сколько это необходимо для получения m+n -1 занятых клеток.
Таблица 16
Вспомогательные Пункт назначения
Б
1
Б
2
Б
3
Б
4
Пункт
отправления
строка
столбец
Наличи
е груза,
т
А
1
9
15
10
5
40
8
30
80
А
2
4
9
50
6 5
50
А
3
16
30
22
10
10
18
40
Потребность в грузе, т 30 70 40 30 170

Страницы