Транспортная задача. 
Экономический анализ

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

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

Конкретные особенности постановки и решения такой задачи рассмотрим на примере.

Пример 2.26.

В пределах одного населенного пункта имеется три склада (А, Б, В), где хранится один и тог же товар, который необходимо перевезти в три магазина (1,2, 3). При этом емкость каждого склада и потребность в товаре у каждого магазина неодинаковая. Известны все расстояния между магазинами и складами. Требуется составить такой план перевозок товара, чтобы обеспечить наименьший общий пробег грузов (в т-км). Представим исходные данные в виде таблицы. В каждой клетке на пересечении соответствующего склада и магазина в правом верхнем углу проставим расстояние между ними.

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

Рассмотрим основные этапы решения транспортной задачи.

1-й этап. Составляется первоначальное распределение перевозок. Чаще всего для этого применяется правило «северо-западного угла». Этот прием предполагает, что максимально допустимое количество груза помещается в верхнюю левую («северо-западную) клетку таблицы. Затем заполняется соседняя клетка (в строке или столбце), в зависимости от того, где имеются еще не использованные возможности перевозок. При заполнении одной из клеток, следующая должна загружаться одной из примыкающих к ней клеток: либо в гой же строке, либо в том же столбце. Если ни в ту ни в другую из них нечего поставить (т.е. возможности соответствующих строк и столбцов уже исчерпаны), то в любой из них проставляется ноль и от нее продолжается процесс последовательного распределения. Этот прием гарантирует получение в исходном варианте необходимого количества занятых клеток равного т + п — 1, где т — количество строк; п — количество столбцов. В процессе вычислений клетка с нулем считается несвободной, а загруженной.

После исходного распределения просчитываем грузопоток. Грузопоток = 6* 1 + 6- 3 + 3- 5 + 5- 3 + 5- 10=104 (т-км).

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

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

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

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

— для свободной клетки АЗ он равен + 3 (-3 + 4−3 + 5).

— для свободной клетки Б1 он равен -1 (+2 — 1 + 3 — 5) — лучший вариант.

— для свободной клетки В2 он равен 0 (+3 -5 + 7−5).

— для свободной клетки В1 он равен +1 (-1+3−5 + 3- 5 + 6).

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

3-й этап. Далее осуществляется переход к новому варианту. Для этого производится перемещение грузов в пределах клеток данного многоугольника. В свободную клетку записывается наименьший из грузов, стоящий в клетках с отрицательными характеристиками. Одновременно этот же груз прибавляется к перевозкам всех плюсовых клеток и вычитается из всех минусовых клеток. Если в пределах данного многоугольника одинаковый минимальный груз имеют две и более клеток, то освобождаться может лишь одна из них, остальные будут загружены нулевыми поставками, так как на следующем этапе нельзя построить многоугольник для всех свободных клеток. Число занятых клеток должно быть равно т + п- 1.

Просчитываем грузопоток:

Грузопоток = 3- 1+3−2 + 3- 9 + 5- 3 + 5- 10= 101 (т-км).

4-й этап. Полученный результат проверяется на оптимальность (аналогично этапу 2V

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

Решение больших и средних по размеру матриц распределительным методом — это трудоемкий процесс. Недостаток распределительного метода преодолен в алгоритме модифицированного распределительного метода.

Суть его состоит в том, что первоначальное распределение составляется обычным порядком (по правилу «северо-западного угла»), затем для каждой строки и столбца определяются коэффициенты так, чтобы для любой загруженной клетки показатель критерия оптимальности был бы равен сумме коэффициентов строки и столбца, на пересечении которых находится эта клетка. Для каждой свободной клетки определяется разность между ее показателем критерия оптимальности и суммой коэффициентов соответствующей строки и столбца:

• 4 — (0 + 1) = 3 > 0: АЗ — не оптимальна;
• 2 — (1 + 2) = -1 <0:Б1 — оптимальна;
• 6-(1+4)=1 >0:В1 — не оптимальна;
• 7 — (3 + 4) = 0: В2 — ни оптимальна, ни нс оптимальна.

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