ВУЗ:
Составители:
Рубрика:
7
Система потенциалов содержит
m + n – 1 уравнений с m+ n неизвест-
ными. Уравнений на одно меньше, чем неизвестных, поэтому система яв-
ляется неопределённой и одному неизвестному (обычно
u
1
) придают нуле-
вое значение
u
1
= 0. Решаем систему:
u
1
= 0 v
1
= 3
u
2
= 1 v
2
= 1
u
3
= 4 v
3
= 1
v
4
= 2.
2. Проверка выполнения условия оптимальности для незанятых клеток.
Просматриваем строки и для каждой незанятой клетки проверяем выпол-
нение условия
u
i
+ v
j
≤
с
i j
. Если это условие выполнено для всех клеток, то
план оптимален. Если для некоторых клеток
u
i
+ v
j
> с
i j
, то план неоптима-
лен. Для каждой клетки, в которой
u
i
+ v
j
> с
i j
, находим
(
)
ijjiij
cvu
−
+=
δ
.
В нашем примере:
u
1
+ v
1
= 0 + 3 < 5
u
1
+ v
2
= 0 + 1 < 4
u
2
+ v
3
= 1 + 1 < 6
u
3
+ v
2
= 4 + 1 > 3 235
32
=−=
δ
u
3
+ v
3
= 4 + 1 = 5
u
3
+ v
4
= 4 + 2 > 4 246
34
=−=
δ
В двух клетках нарушено условие оптимальности.
3. Выбор клетки, в которую необходимо послать перевозку.
Загрузке подлежит в первую очередь клетка, которой соответствует
max
ij
δ
= max (u
i
+ v
j
- с
i j
).
В нашем примере
3432
δ
δ
=
, поэтому можем взять любую из этих кле-
ток. Например, возьмём клетку (3, 2). Нужно определить, сколько единиц
груза должно быть перераспределено в неё.
4. Построение цикла и определение величины перераспределения груза.
Для определения количества единиц груза, подлежащих перераспределе-
нию, отмечаем знаком «+» незанятую клетку, которую надо загрузить. Это
означает, что клетка присоединяется к занятым
. В таблице занятых клеток
станет
m+n, поэтому появится цикл, все вершины которого, за исключени-
ем клетки, отмеченной знаком «+», находятся в занятых клетках, причём
этот цикл единственный. Отыскиваем цикл и, начиная движение от клетки,
отмеченной знаком «+», поочерёдно проставляем знаки «-» и «+». Затем
находим
ij
xmin
0
=
θ
, где
ij
x - перевозки, стоящие в вершинах цикла, отме-
ченных знаком «-». Величина
0
θ
определяет, сколько единиц груза можно
перераспределить по циклу. Значение
0
θ
записываем в незанятую клетку,
отмеченную знаком «+», двигаясь по циклу, вычитаем
0
θ
из
ij
x , которые
7
Система потенциалов содержит m + n – 1 уравнений с m+ n неизвест-
ными. Уравнений на одно меньше, чем неизвестных, поэтому система яв-
ляется неопределённой и одному неизвестному (обычно u1) придают нуле-
вое значение u1= 0. Решаем систему:
u1 = 0 v1= 3
u2 = 1 v2= 1
u3 = 4 v3= 1
v4= 2.
2. Проверка выполнения условия оптимальности для незанятых клеток.
Просматриваем строки и для каждой незанятой клетки проверяем выпол-
нение условия ui + vj ≤ сi j. Если это условие выполнено для всех клеток, то
план оптимален. Если для некоторых клеток ui + vj > сi j, то план неоптима-
( )
лен. Для каждой клетки, в которой ui + vj > сi j, находим δ ij = ui + v j − cij .
В нашем примере:
u1 + v1 = 0 + 3 < 5
u1 + v2 = 0 + 1 < 4
u2 + v3 = 1 + 1 < 6
u3 + v2 = 4 + 1 > 3 δ 32 = 5 − 3 = 2
u3 + v3 = 4 + 1 = 5
u3 + v4 = 4 + 2 > 4 δ 34 = 6 − 4 = 2
В двух клетках нарушено условие оптимальности.
3. Выбор клетки, в которую необходимо послать перевозку.
Загрузке подлежит в первую очередь клетка, которой соответствует
max δ ij = max (ui + vj - сi j).
В нашем примере δ 32 = δ 34 , поэтому можем взять любую из этих кле-
ток. Например, возьмём клетку (3, 2). Нужно определить, сколько единиц
груза должно быть перераспределено в неё.
4. Построение цикла и определение величины перераспределения груза.
Для определения количества единиц груза, подлежащих перераспределе-
нию, отмечаем знаком «+» незанятую клетку, которую надо загрузить. Это
означает, что клетка присоединяется к занятым. В таблице занятых клеток
станет m+n, поэтому появится цикл, все вершины которого, за исключени-
ем клетки, отмеченной знаком «+», находятся в занятых клетках, причём
этот цикл единственный. Отыскиваем цикл и, начиная движение от клетки,
отмеченной знаком «+», поочерёдно проставляем знаки «-» и «+». Затем
находим θ 0 = min xij , где xij - перевозки, стоящие в вершинах цикла, отме-
ченных знаком «-». Величина θ 0 определяет, сколько единиц груза можно
перераспределить по циклу. Значение θ 0 записываем в незанятую клетку,
отмеченную знаком «+», двигаясь по циклу, вычитаем θ 0 из xij , которые
