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

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

Построение допустимого первоначального плана методом северо-западного угла начинается с заполнения левой верхней клетки матрицы и заканчивается в ее правой нижней клетке. Груз, имеющийся у первого поставщика, распределяется так, чтобы сначала по возможности полностью удовлетворить потребности первого потребителя, потом второго и т. д. Затем переходят к распределению груза, имеющегося у второго поставщика, и так до полного распределения груза у всех поставщиков. Если спрос какого-либо потребителя превышает наличие груза у поставщика, то недостающий спрос удовлетворяют за счет следующего поставщика.

Для проверкиоптимальности полученного распределенияперевозок используют вспомогательные показатели для строк u и столбцов v, называемые потенциалами. Для каждой загруженной клетки сумма соответствующих этой клетке потенциалов должна быть равна расстоянию между пунктами, указанному в этой клетке. В соответствии с этим потенциалы можно определить по следующему правилу. Одному из столбцов или строк присваивается потенциал, равный нулю. Это может быть любой столбец или строка, но целесообразно приравнять к нулю потенциал того столбца (или строки), в котором содержится загруженная клетка с наибольшим расстоянием между пунктами.

Затем определяем потенциалы остальных столбцов и строк, исходя из того, что и_i + v_j = с_ij,при этом определяем потенциалы только строк и столбцов, содержащих загруженные клетки. Для того чтобы определить потенциалы всех столбцов и строк в матрице, необходимо, чтобы матрица содержала не менее (п + т – 1) загруженных клеток. Если количество загруженных клеток меньше, чем (п + т – 1), необходимо искусственно загрузить недостающее количество клеток матрицы, для чего в эти клетки записывается нулевая загрузка. Ноль следует приписывать той клетке, которая лежит на пересечении строки или столбца, не имеющих потенциала, со строкой или столбцом, потенциал которых уже определен. В этом случае будет возможно определить еще неопределенный потенциал строки или столбца.

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

Следующим этапом в построении оптимального плана распределения загрузок является этап улучшения полученного распределения.

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

Контуром называется замкнутая ломаная линия, образованная прямыми отрезками, углы соединений между которыми равны 90°. Строится контур так, чтобы все углы, кроме одного, располагались
в загруженных клетках, а один угол находился в незагруженной, наиболее потенциальной клетке. От выбранной незагруженной клетки проводят прямую линию по строке или столбцу до загруженной клетки, которой в свою очередь должна соответствовать еще одна загруженная клетка, расположенная под прямым углом, и так до тех пор, пока контур не замкнется в исходной клетке. Такой контур может быть только один!

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

Рис. 3.2. Возможные виды контуров для определения

оптимального плана перевозок

После того как контур построен, всем вершинам контура присваиваются попеременно знаки «+» и «–». Начинать надо с клетки, выбранной для начала построения контура (это незагруженная клетка), ей присваивается знак «–».

Затем из всех клеток, обозначенных знаком «+», выбирают наименьшую загрузку. Величину этой загрузки вычитают из величины загрузки во всех клетках, помеченных знаком «+», и прибавляют к величине загрузки в клетках со знаком «–». В результате этих действий наиболее потенциальная клетка становится загруженной, а одна (или несколько) загруженных клеток становятся свободными.

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

Т е м а 4

Автомобильные грузовые транспортные

Средства (2 ч)