Одной из самых распространённых и востребованных задач в логистике является транспортная задача. В классическом виде она предполагает нахождение плана грузоперевозок с минимальными денежными или временными затратами. Например, сети розничных магазинов требуется определённое количество товаров. Имеется ряд складов поставщиков, где требуемые товары хранятся. При этом на каждом складе различный объём запасов этих товаров. Кроме этого известны тарифы – затраты на перевозку единицы товара от каждого склада к каждому магазину. Необходимо разработать такой план перевозок, чтобы магазины получили требуемое количество товаров с наименьшими затратами на транспортировку. В таких случаях приходится решать транспортную задачу.
Один из наиболее подходящих методов решения транспортной задачи – итерационное улучшение плана перевозок. Суть его в следующем: находим некий опорный (первоначальный) план и проверяем его на оптимальность. Если план оптимален – решение найдено. Если нет – улучшаем план столько раз, сколько потребуется, пока не будет найден оптимальный план. Наиболее простым методом составления опорного плана является метод северо-западного угла, который состоит в последовательном переборе строк и столбцов транспортной таблицы, начиная с левого верхнего угла. Количество перевозимого груза соответствует максимально возможной отгрузке в ячейки таблицы так, чтобы заявленные в задаче запасы поставщиков или потребности потребителей не были превышены. На стоимость доставки в этом случае не обращают внимания, т.к. предполагается только составлений первоначального плана перевозок, а затем последующая оптимизация отгрузок методом потенциалов.
Прежде чем начать составление первоначального плана перевозок, необходимо проверить данные задачи на сбалансированность, т.е. суммарные запасы поставщиков должны соответствовать суммарным запросам потребителей. В противном случае необходимо введение «фиктивных» строк или столбцов с нулевыми стоимостями перевозок.
Пусть условие транспортной задачи представлено в виде табл. 1. Здесь суммарные мощности поставщиков составляют 4 + 6 + 8 + 7 = 25 и суммарные мощности потребителей 3 + 5 + 4 + 7 + 9 = 28 не совпадают. Значит, необходимо ввести «фиктивного» поставщика с запасом товара 28 – 25 = 3 и нулевыми стоимостями перевозок (табл. 2).
Программная реализация метода северо-западного угла в программном модуле Mathcad 15 представлена на рис. 1.
Таблица 1
|
Потребители Поставщики |
3 |
5 |
4 |
7 |
9 |
|
4 |
6 |
3 |
7 |
10 |
6 |
|
6 |
2 |
7 |
6 |
9 |
3 |
|
8 |
3 |
4 |
2 |
3 |
5 |
|
7 |
3 |
4 |
5 |
4 |
2 |
Таблица 2
|
Потребители Поставщики |
3 |
5 |
4 |
7 |
9 |
|
4 |
6 |
3 |
7 |
10 |
6 |
|
6 |
2 |
7 |
6 |
9 |
3 |
|
8 |
3 |
4 |
2 |
3 |
5 |
|
7 |
3 |
4 |
5 |
4 |
2 |
|
3 |
0 |
0 |
0 |
0 |
0 |
В результате будет получена первоначальная матрица перевозок
,
которую можно использовать как основу для поиска оптимального решения.