Методы решения транспортной задачи

Транспортная задача решается в два этапа. На начальной стадии находят любое допустимое ответ, удовлетворяющее совокупностям (1.1)-(1.3). Такое ответ именуется начальным базовым распределением поставок. После этого, посредством способа потенциалов, делают такие преобразования с начальным распределением поставок, для получения оптимального распределения поставок. Разглядим сначала нахождение начального базового распределения поставок.

Нахождение начального базового распределения поставок

Начальное базовое распределение поставок возможно обнаружить разными способами. Разглядим главные из них.

Способ северо-западного угла.

В этом способе груз распределяем от верхней левой клетки (1, 1), именуемой северо-западной, двигаясь после этого от нее по строчку вправо либо по столбцу вниз. Полагаем . В случае если , то полагают и первый потребитель будет всецело удовлетворен. Тогда, в будущем первый столбец выпадает и полагаем . В случае если в клетку мы дали поставку, то вычисляем ее заполненной, и перечеркиваем ее, для удобства, целой линией. Выпавшие из предстоящего рассмотрения клетки, вычисляем свободными, и перечеркиваем их пунктирной линией.

После этого двигаемся по первой строке таблицы и заносим в клетку (1,2) . В случае если , то запасы первого поставщика исчерпаны и из предстоящего рассмотрения выпадает первая строка.

Потом переходим ко второму поставщику. В случае если , то , значит запас первого поставщика исчерпан, т.е. и первая строка выпадает. Переходим в клетку (2, 1) наряду с этим . По окончании заполнения клетки (1, 2) либо (2, 1) переходим ко второй строке либо ко второму столбцу и т.д., пока не исчерпаются все ресурсы.

Способ мельчайших затрат

Сначала находится клетка с мельчайшим коэффициентом затрат . После этого в нее записывается максимальная поставка и из рассмотрения исключают либо выпавшую наряду с этим строчок, либо столбец.

После этого выбираем мельчайший из оставшихся клеток , пока мощность всех поставщиков не будет реализована, а спрос всех потребителей не будет удовлетворен.

В этом способе в ходе заполнения таблицы смогут в один момент выпасть столбец и строка, т.е. количество клеток будет меньше (m+n-1). В этом случае в некую свободную клетку поставляют фиктивную нулевую поставку. Эта клетка будет принимать во внимание заполненной, и в будущем с ней трудятся равно как и с другими заполненными клетками. Эту фиктивную нулевую поставку возможно ставить лишь в ту свободную клетку, дабы не образовывался квадрат либо прямоугольник с вершинами из заполненных клеток.

Способ Фогеля

Сначала определяют разность между двумя мельчайшими по столбцам и строкам. Находят громаднейшую отличие. В строке (в столбце) с громаднейшей разностью заполняется клетка с минимальным . Потом повторяем те же действия с не выпавшими клетками.

Продемонстрируем на примере, как находится начальное базовое распределение поставок способом мельчайших затрат.

Лекция 3: Транспортная задача


Также читать:

Понравилась статья? Поделиться с друзьями: