Метод северо-западного угла

Берем «северо-западную» клетку матрицы – это клетка А₁В₁ и записываем в нее максимально возможную поставку – 40 т (объем выгрузки 40 т, ресурсы станции погрузки 100 т). Поскольку ресурсы станции погрузки А₁ не исчерпаны, следуем по первой строке вправо и записываем в клетку А₁В₂ корреспонденцию равную максимально возможной величине – 60 т. Таким образом получается, что ресурсы станции А₁ полностью использованы, однако спрос станции выгрузки В₂ не удовлетворен. Тогда от клетки А₁В₂ опускаемся вниз до клетки А₂В₂ и записываем в нее поставку равную 20 т. Описанным способом следуем далее до последней «юго-западной» клетки матрицы. В результате получаем допустимый план перевозок груза. Грузооборот или функционал транспортной задачи (сумма произведений корреспонденций на расстояние, рассчитанная по табл. 2.3) составит:

F_{сев-зап.} = 40 ∙ 10 + 60 ∙ 9 + 20 ∙ 7 + 110 ∙ 13 + 20 ∙ 6 + 30 ∙ 7 + 60 ∙ 1 + + 30 ∙ 2 = 2960 ткм [см. формулу (2.4)].

После расстановки корреспонденции матрица проверяется на вырождение, т. е. должно выполняться условие

, (2.5)

где m – количество строк, n – количество столбцов, N_баз – количество базисных клеток.

Другими словами, количество клеток матрицы, содержащих корреспонденции, должно быть равно сумме строк и столбцов без единицы. В нашем случае это условие соблюдается: 8 = 4 + 5 – 1. План транспортной задачи, отвечающий условию (n + m – 1) называют базисным. Базисными также называются клетки матрицы, содержащие поставки. Клетки, в которых поставки отсутствуют, называются небазисными.

Метод северо-западного угла имеет существенный недостаток. При его использовании не учитываются значения показателей критерия оптимальности в клетках матрицы. Поэтому поставки могут попасть в «дорогие» клетки с заведомо высокой ценой или большим расстоянием. Опорный план, полученный с использованием данного метода, как правило, далек от оптимального, что обусловливает большой объем последующих расчетов для доведения его до оптимального. Описанный метод обычно не применяется.

Наиболее предпочтительным при ручном решении транспортных задач считается метод минимальной стоимости или, как его еще называют, метод наименьшего элемента в матрице. Суть его в следующем. В транспортной матрице выбирается клетка с минимальной стоимостью (расстоянием). В нашем случае это клетка А₃В₅. В нее записывается максимально возможная поставка – это 90 т (табл. 2.4).

Таблица 2.4