Составители:
Рубрика:
Из последнего правила следует, что если у занятой клетки один из
индексов известен, то другой равен разности ее расстояния и известного
индекса, т.е.
Ui = L
ij
– V
j
и V
j
= L
ij
– U
i
(1)
Запишем в матрицу индекс U
1
= 0. Тогда у занятых клеток A
1
Б
1
, А
1
Б
3
и
А
1
Б
4
один индекс известен и можно, используя равенство (1), определить
индексы V
1
, V
2
и V
4
(табл.9):
V
1
= L
11
– U
1
= 9-0=9
V
3
= L
13
– U
1
= 5-0=5
V
4
= L
14
– U
1
= 8-0=8
Теперь у занятой клетки А
2
Б
1
известен индекс V
1
и можно найти индекс U
2
= L
22
– U
2
= 4-9 = -5. После этого определяем индекс V
2
, а затем индекс U
3
:
V
2
=L
22
– U
2
= 9 – (-5) = -5 и U
3
= L
32
– V
2
= 22 – 14 = 8
Таблица 9
Пункт назначения
Б
1
Б
2
Б
3
Б
4
Пункт
отправле
ния
Вспомога
тельные
9 14 5 8
Наличие
груза
А
1
0 10
9 15
40
5
30
8
80
А
2
-5 20
4
30
9 6
5
50
А
3
8
16
40
22 10
18
40
Потребность, т 30 70 40 30 170
Таким образом, все индексы найдены (табл. 9) и можно приступить к
проверке плана, которая сводится к сравнению расстояния каждой незанятой
клетки матрицы с суммой соответствующих ей индексов с целью выявления
клеток, в которых расстояние меньше указанной суммы. В нашем примере
имеем:
(U
1
+ V
2
= 0 + 14) < (L
12
= 15)
(U
2
+ V
3
= -5 + 5 = 0) < (L
23
= 6)
(U
2
+ V
4
= -5 + 8 = 3) < (L
24
= 5)
(U
3
+ V
1
= 8 + 9 =17) > (L
31
= 16)
(U
3
+ V
3
= 8 + 5 = 13) > (L
33
= 10)
(U
3
+ V
4
= 8 + 8) < (L
34
= 18)
У незанятых клеток А
3
Б
1
и А
3
Б
3
расстояние меньше суммы их индексов.
Следовательно, составленный план не является оптимальным.
4. Улучшение неоптимального плана. Выявленные на предыдущем этапе
вычислений клетки А
3
Б
1
и А
3
Б
3
являются резервом улучшения плана и потому
их называют потенциальными, а превышение суммы индексов над расстоянием
- потенциалом.
Страницы
- « первая
- ‹ предыдущая
- …
- 12
- 13
- 14
- 15
- 16
- …
- следующая ›
- последняя »
