Исходная транспортная матрица

В табл. 2.2 по строкам матрицы представлены пункты (станции) отправления от А₁ до А₄ и объемы погрузки в тоннах – 100, 150, 90, 30 т, а по столбцам – пункты (станции) назначения от В₁ до В₅ и объемы выгрузки – 40, 80, 110, 50, 90 т. Данная транспортная задача является сбалансированной (a_i = b_j = 370 т), поэтому добавлять фиктивного потребителя ФВ или фиктивного поставщика ФА не требуется. На пересечении строк и столбцов в клетках матрицы в маленьких квадратиках записаны показатели критерия оптимальности транспортной задачи, например, затраты на перевозку единицы груза или кратчайшие расстояния между соответствующими пунктами (станциями) погрузки и выгрузки. Расстояние между станцией погрузки А₁ и станцией выгрузки В₁, как следует из матрицы, равно 10 (или 100, 1000 и т. д.) км, потом – 9, 8, 5 км и т. д. Тогда целью, решения задачи явится отыскание совокупности объемов перевозок между всеми пунктами (станциями) погрузки и выгрузки (корреспонденций), обеспечивающей минимальный объем перевозочной работы (грузооборота) в тонно-километрах. Любую совокупность корреспонденций, обеспечивающую весь объем перевозок, будем называть планом, а совокупность, обеспечивающую минимум грузооборота, – оптимальным планом перевозок.

Алгоритм решения транспортной задачи линейного программирования будем описывать по операциям с присвоением номера и названия.

Операция 1. Построение опорного плана.

Опорным, называется любой допустимый, как правило, не оптимальный план, который является исходным для последующего решения. Для построения опорного плана существует ряд методов. Самый простой из них – метод северо-западного угла (табл. 2.3).

Таблица 2.3

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

Берем «северо-западную» клетку матрицы – это клетка А₁В₁ и записываем в нее максимально возможную поставку – 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