Составители:
226
Рис. 6.8 - Алгоритм решения транспортной задачи венгерским методом по критерию
времени
В
ыделить знаком
"
+
"
стол
б
цы, в
которых δ
j
= 0
Выделить эту строку знаком " + "
Построить исходный план: индекс у нуля
равен минимуму из того, что есть на базе, и того, что
Все δ
i
= 0?
Есть ли невыделенные нули?
О
тметить один невыделенны
й
нуль
знаком ' (штрих)
δ
i
=
0
в строке с отмеченным
нулём?
Есть ли в этой строке нули с индексом
в выделенных столбцах?
В
се эти нули отметить знаком
"
*
"
(звёздочка).
Выделение столбцов с такими нулями
б
Построить матрицу T
0
: в каждом столбце и в
каждой строке найти минимальный элемент и из них
выбрать
максимальный; все времена, меньшие или
З
адача решена.
Записать X
0
и F(X
0
)
О
пределить t:
t = min (невыделенные элементы)
П
рео
б
разовать матрицу
T
: все времена,
меньшие или равные t, заменить нулями; остальные
элементы – без изменений.
Выделение строк и
столбцов, а также штрихи и звёздочки у нулей
убрать.
Есть ли нули, для которых δi>0
Д
ора
б
отать план: индексы у этих
нулей равны min(δi , δj)
П
остроить цепочк
у
: от
δi
>
0
горизонтали к нулю со штрихом, от него –
по вертикали к нулю со звёздочкой, далее
– по горизонтали к нулю со штрихом и
т.п.; в конце от нуля со штрихом по
вертикали к δj >0.
О
пределить
q
:
q = min (δi , δj, индексы у нулей со
звёздочкой в цепочке)
Н
овы
й
план перевозок: в цепочке
δi , δj, индексы у нулей со звёздочкой
уменьшить на q, а ин
дексы у нулей со
штрихом
увеличить на q.
Выделение строк и столбцов, а также
штрихи и звё
з
дочки у нулей убрать.
Страницы
- « первая
- ‹ предыдущая
- …
- 224
- 225
- 226
- 227
- 228
- …
- следующая ›
- последняя »
