Транспортная задача Основные понятия

Общая постановка транспортной задачи состоит в определении оптимального плана перевозок некоторого груза из m пунктов отправления

в n пунктов назначения .

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

Рассмотрим транспортную задачу, в качестве критерия оптимальности которой взята минимальная стоимость перевозок всего груза. Обозначим через c_ij тарифы перевозки единицы груза из i-го пункта отправления в j-й пункт назначения, через a_i - запасы груза в i-м пункте отправления, через b_j потребности в грузе в j-м пункте назначения, а через x_ij - количество единицы груза, перевозимого из i-го пункта отправления в j-й пункт назначения. Тогда математическая постановка задачи состоит в определении минимального значения функции:

при условиях:

; ;

План X , , при котором функция принимает свое минимальное значение, называется оптимальным планом.

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

.

Исходные данные заносятся в таблицу следующего вида:

Таблица 1.

ai\bj	b1	b2	…	bk	…	bn
a1	c11 x11	c12 x12	…	c1k x1k	…	c1n x1n
a2	c21 x21	c22 x22	…	c2k x2k	…	c2n x2n
…	…	…	…	…	…	…
Ai	ci1 xi1	ci2 xi2	…	cik xik	…	cin xin
…	…	…	…	…	…	…
Am	cm1 xm1	cm2 xm2	…	cmk xmk	…	cmn xmn

Алгоритм решения задачи

1. Составление первоначального (исходного) плана перевозок.

Для определения опорного плана существует несколько методов (метод северо-западного угла, метод минимального элемента, метод аппроксимации Фогеля).

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

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

Заполнение клеток таблицы условий начинается с левой верхней клетки для неизвестного x₁₁(''северо-западный угол'') и заканчивается клеткой для неизвестного x_mn.

Пример

В двух пунктах отправления А1 и А2 находятся соответственно 150 и 90 т горючего. Пункты №1, 2, 3 требуют соответственно 60, 70, 110 т горючего. Стоимость перевозки одной тонны горючего из пункта А1 в пункты № 1, 2, 3 соответственно 6,10 и 4 руб. за тонну горючего, а из А2 – 12, 2 и 8 руб. Составить оптимальный план перевозок горючего так, чтобы общая сумма транспортных расходов была наименьшей.

Запишем исходные данные в таблицу 1. Заполнение начнем с клетки (1,1): x₁₁=min{150, 60}=60, первый столбец закрыт. Переходим к клетке (1,2): x₁₂=min{150- 60,70}=70, второй столбец закрыт; далее клетка (1,3): x₁₃=min{150- 60-70,110}=20. Так как в третьем столбце остаток, равный 90, то переходим к заполнению клетки (2,3), куда заносим x₂₃=min{90, 90}=90. Поскольку остатки по строке и столбцу равны нулю, опорное решение построено таблица 2.

Этому плану соответствуют затраты

F = 6•60 + 10•70 + 4•20 + 8•90 = 1860 руб.

Таблица 2.

№1 №2 №3

А1 А2 ai\bj	60	70	110
150	6 60	10 70	4 20
90	12	2	8 90

Метод минимального элемента

Заполнение клеток транспортной таблицы начинается с клетки, в которой значение стоимости минимальное. Например клетки АiBj. В эту клетку записываем минимально возможное значение перевозки x_ij, которое может быть равно либо запасу а_i соответствующего пункта отправления А_i, либо заявке b_j – пункта назначения Bj. Если заявка b_j пункта назначения Bj выполнена полностью, то j-й столбец исключается из дальнейшего рассмотрения. Если в пункте отправления А_i остается не вывезенный груз, то он вывозится в следующий пункт назначения с минимальной стоимостью и т.д. до тех пор, пока не будут исчерпаны запасы а_i пункта А_{i .} Далее, из рассмотрения исключают либо строку, соответствующую поставщику, запасы которого полностью израсходованы, либо столбец, соответствующий потребителю, заявка, которого выполнена. Затем из оставшихся клеток таблицы снова выбираем клетку с наименьшей стоимостью, и все рассуждения повторяются до тех пор, пока не будет найдено допустимое решение.

Пример

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

Решение начнем с клетки (2,2), где с₂₂=2. В эту клетку заносим x₂₂=min{90, 70}=70. Остатки по строке и по столбцу записываем в соответствующие клетки строки и столбца остатков. Столбец b₂ закрыт. Теперь переходим к клетке (1,3), так как после с₂₂ =2 наименьшим является с₁₃ =4. В эту клетку (1,3) заносим x₁₃=min{150- 60,110}=90. Затем переходим к клетке (1,1) : x₁₁=min{150, 60}=60. И, наконец, переходим к клетке (2,3), в которую заносим x₂₃=min{90-70, 110}=20 (таблица 3).

При этом варианте затраты

F = 6•60 + 4•90 + 2•70 + 8•20 = 1020 руб.

Таблица 3

№1 №2 №3

А1 А2 ai\bj	60	70	110
150	6 60	10	4 90
90	12	2 70	8 20