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