Математические методы и модели в фармацевтической науке и практике. Зубов Н.Н - 214 стр.

UptoLike

ВУЗ: 

ВМА им. Кирова | Санкт-Петербург

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

Рубрика: 

214
Для решения транспортных задач ввиду их специфичности были разработаны особые
методы, такие как метод северо-западного угла, метод наименьшего элемента, метод
потенциалов, метод запрещенных клеток [3], венгерский метод и др.
В 1931 году венгерским математиком Э. Эгервари был разработан достаточно
простой и удобный метод решения транспортных задач, получивший впоследствии
название "венгерский". Рассмотрим его
основные положения, для этого введем некоторые
новые понятия.
Две транспортные задачи называются
эквивалентными, если они имеют одно и то
же решение; матрицы таких задач тоже называют эквивалентными.
Доказана теорема, что
если к элементам одной строки (столбца) матрицы C
ij
или T
ij
добавить (или вычесть из них) одно и то же положительное число, не превосходящее в
случае вычитания каждого из элементов данной строки (столбца), то полученная матрица
будет эквивалентна исходной.
Идея венгерского метода решения транспортных задач заключается в том, что
исходная матрица задачи заменяется эквивалентной, в которой стоимости (времена)
перевозок по некоторым наиболее дешевым маршрутам сведены к нулю; перевозки
планируются именно по этим маршрутам; возможно улучшение плана путём
перераспределения нагрузок по выбранным маршрутам.
Укрупненная структурная схема алгоритма венгерского метода представлена на
рисунке 6.7.
Прежде всего, задача проверяется
на наличие баланса. Случай, когда общие запасы
материальных средств на базах равны суммарным запросам потребителей, называется
задачей с балансом.
Транспортная задача, в которой запасы превышают потребности, сводится к задаче с
балансом введением
фиктивного потребителя с запросами, равными избытку имущества
(материальных средств) на базах. Элементы столбца матрицы, соответствующего
фиктивному потребителю, принимаются равными нулю, поскольку на самом деле избыток
материальных средств остаётся на базах и никуда не перевозится.
Транспортная задача, в которой имеется недостаток имущества (материальных
средств) на базах в сравнении с запросами потребителей, приводится к
задаче с балансом
введением
фиктивной базы. Элементы строки, соответствующей фиктивной базе,
принимаются равными нулю.

Страницы