Транспортные задачи. Теоретические основы

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

Таблица перевозок имеет те же размеры ( ) и содержит переменные решения.

Необходимо также задать запасы поставщиков, готовые к вывозу

и величины заказов потребителей

В транспортной задаче предполагается, что необходимо вывести запасы каждого i-го поставщика и удовлетворить заказ каждого j-го потребителя. Это возможно только если сумма запасов всех поставщиков равна сумме заказов всех потребителей.

Это важнейшее условие применимости эффективных алгоритмов.

Ограничения транспортной задачи имеют очень простой вид: сумма переменных решения вдоль каждой i-ой строки должна быть равна запасу поставщика S_i, а сумма переменных решения вдоль каждого j-го столбца должна быть равна заказу соответствующего потребителя D_j, переменные x_ij – не отрицательны.

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

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

Несбалансированность в транспортной задаче

Если сумма запасов превышает сумму заказов (излишек запасов) или, наоборот сумма запасов меньше, чем сумма заказов (дефицит запасов) необходимо сбалансировать задачу. В первом случае,

нужно добавить в таблицу транспортных издержек и в таблицу перевозок по одному лишнему столбцу.

Это можно трактовать так, как если бы появился еще один «фиктивный» потребитель. Если потребовать, чтобы заказ этого «потребителя» в точности равнялся бы разности между суммой всех запасов и суммой всех заказов

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

Во втором случае, когда

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

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

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

Еще одно возможное осложнение транспортной задачи – это запрещение определенной перевозки от i-го поставщика к j-му потребителю для составляемого плана перевозок (ремонт дороги, неплатеж и пр.). В этом случае, естественно, можно просто ввести ограничение x_ij =0. Однако, это вновь означает невозможность использования эффективных «транспортных» алгоритмов решения.

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

Подробнее о постановке и методах решения транспортной задачи можно узнать в [1, 3, 4].