6. Транспортная задача

Математическая постановка транспортной задачи состоит в определении оптимального плана перевозок некоторого однородного груза из т пунктов отправления А₁, А₂, …, А_т в п пунктов назначения В₁, В₂, …, В_п. При этом в качестве критерия оптимальности обычно берется либо минимальная стоимость перевозок всего груза, либо минимальное время его доставки. Рассмотрим транспортную задачу, в качестве критерия оптимальности которой взята минимальная стоимость перевозок всего груза.

Обозначим:

c_ij – тарифы перевозки единицы груза из i-го пункта отправления в j-й пункт назначения,

a_i – запасы груза в i-м пункте отправления,

b_j – потребности в грузе в j–м пункте назначения,

x_ij – количество единиц груза, перевозимого из i-го пункта отправления в j-й пункт назначения.

Тогда математическая постановка задачи состоит в определении минимального значения функции: (6.1)

при условиях (6.2)

(6.3)

Всякое неотрицательное решение систем линейных уравнений (6.2) и (6.3), определяемое матрицей Х=(х_ij), называется планом транспортной задачи.

План Х*=(х*ij), при котором функция (6.1) принимает свое минимальное значение, называется оптимальным планом транспортной задачи.

Обычно исходные данные транспортной задачи записывают в виде таблицы.

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

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

В самую северо-западную клетку таблицы заносится максимально допустимая перевозка, при этом либо вывозится весь груз со станции А₁ и все остальные клетки первой строки вычеркиваются, либо потребности первого потребителя В₁ полностью удовлетворяются, тогда все клетки первого столбца вычеркиваются. После этого самой северо-западной клеткой становится клетка А₁В₂ или В₂А₁. Алгоритм продолжается до заполнения таблицы. Недостатки – не учитывается стоимость перевозки, и получается план далекий от оптимального.

Метод наименьшей стоимости

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

Метод аппроксимации Фогеля

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

Широкораспространенным методом решения транспортных задач является метод потенциалов.

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

Теорема 1. Если опорный план Х=(х_ij) является оптимальным, существует система из (т+п) чисел, называемых потенциалами, U_i, V_j, такая, что:

• U_i+ V_j=С_ij ,для х_ij>0 (базисные переменные);

• U_i+ V_j=С_ij ,для х_ij=0 (свободные переменные).

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

• для каждой занятой клетки сумма потенциалов равна стоимости перевозки единицы груза, стоящей в этой клетке:

U_i+ V_j=С_ij

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

U_i+ V_j£ С_ij

Теорема 2. Любая закрытая транспортная задача имеет решение, которое достигается за конечное число шагов метода потенциалов.

Построение цикла и определение величины перераспределения груза.

Циклом в таблице перевозок называется ломаная с вершинами в клетках и ребрами, расположенными вдоль строк или столбцов матрицы, удовлетворяющая двум требованиям:

• ломаная должна быть связной, т.е. из любой ее вершины можно попасть в другую вершину, двигаясь по ребрам;

• в каждой вершине цикла сходятся ровно два ребра – одно по строке, другое по столбцу.

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

Приведем примеры некоторых циклов.

Теорема 3. В таблице перевозок для каждой свободной клетки существует один цикл пересчета.

Алгоритм метода потенциалов

1. Поставим в соответствие каждой станции А_i потенциал и_i, а каждой станции В_j потенциал v_j. Для этого для каждой заполненной клетки х_ij≠0 составим уравнение и_i +v_j=с_ij . Придадим и₁ =1 (можно любое другое значение) и найдем все остальные потенциалы.

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

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

4. Для новых потенциалов проверяем условие оптимальности. Если условия оптимальности выполняются, то получено оптимальное решение, если нет, то продолжаем поиск оптимального решения по методу потенциалов.

Пример 7.1. Четыре предприятия данного экономического района для производства продукции использует три вида сырья. Потребности в сырье каждого из предприятий соответственно равны 120, 50, 190 и 110 ед. Сырье сосредоточено в трех местах его получения, а запасы соответственно равны 160, 140, 170 ед. На каждое из предприятий сырье может завозиться из любого пункта его получения. Тарифы перевозок являются известными величинами и задаются матрицей .

Составить такой план перевозок, при котором общая себестоимость перевозок является минимальной.

Решение:

	B1	B2	B3	B4
A1	7	8	1	2	160
A2	4	5	9	8	140
A3	9	2	3	6	170
	120	50	190	110	470

задача закрытого типа.

Составим первый план транспортной задачи методом северо-западного угла. Заполнение клеток таблицы начнем с левой верхней клетки.

	B1	B2	B3	B4
A1	7 120	8 40	1	2	160
A2	4	5 10	9 130	8	140
A3	9	2	3 60	6 110	170
	120	50	190	110	470

S₁=120·7+40·8+10·5+130·9+60·3+110·6=3120

Составим первый план методом минимальной стоимости. Будем заполнять клетки с минимальными тарифами.

	B1	B2	B3	B4
A1	7	8	1 160	2	160
A2	4 120	5	9	8 20	140
A3	9	2 50	3 30	6 90	170
	120	50	190	110	470

S₂=160·1+120·4+20·8+50·2+30·3+90·6=1530

Стоимость при таком плане перевозок почти в два раза меньше. Начнем решение задачи с этого плана. Проверим его на оптимальность. Введем потенциалы α_i – соответственно отправления, β_j – соответственно назначения. По занятым клеткам составляем систему уравнений α_i + β_j=c_ij:

Для свободных клеток таблицы проверяем критерий оптимальности

Будем составлять разности

План не оптимальный т. к. имеется положительная оценка Построим из неё цикл пересчета. Это ломаная линия звеньев которые расположены строго по вертикали или горизонтали, а вершины находятся в занятых клетках. В плохой клетке поставим знак (+). В остальных вершинах знаки чередуются. Из отрицательных вершин выбираем наименьшее число и сдвигаем его по циклу. Перешли к новому опорному плану.

	B1	B2	B3	B4
A1	7	8	1 160	2	160
A2	4 120	5	9	8 20	140
A3	9	2 50	3 30	6 90	170
	120	50	190	110	470

	B1	B2	B3	B4
A1	7	8	1 70	2 90	160
A2	4 120	5	9	8 20	140
A3	9	2 50	3 120	6	170
	120	50	190	110	470

S₃=70·1+90·2+120·4+20·8+50·2+120·3=1350

Стоимость перевозок меньше, т.е. план улучшили. Проверяем теперь новый план на оптимальность. По занятым клеткам:

По свободным клеткам:

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

	B1	B2	B3	B4
A1	7	8	1 50	2 110	160
A2	4 120	5 20	9	8	140
A3	9	2 30	3 140	6	170
	120	50	190	110	470

S₄=50·1+110·2+120·4+20·5+30·2+140·3=1330

Проверяем новый план на оптимальность.

По занятым клеткам:

По свободным клеткам:

Критерий оптимальности выполнен, т. е. последний план оптимальный.

Ответ:

S_min =1330.