III. Построение сбалансированной транспортной матрицы.

Общий вид транспортной матрицы

Пункты отправления, A i	Пункты назначения Bj	Запасы продукции, в пунктах отправления
B1	B2	…	B m
A1					…			a 1
	c 11		c 12		c 1 m
A2					…			a 2
	c 21		c 22		c 2 m
…	…	…	…	…	…
A n					…			an
	cn 1		cn 2		cnm
Потребности в продукции, в пунктах назначения	b 1	b 2	…	bm

Существующий алгоритм решения транспортных задач (метод потенциалов) предполагает, что ЦФ стремится к минимуму. Однако существуют ситуации, когда в рамках транспортной модели требуется максимизировать ЦФ, например, общий доход, объем продаж, прибыль, качество выполняемых работ и т.д. В этом случае в модель вместо искомой целевой функции L (X) вводится ЦФ L ₁(X) = - L (X), в которой тарифы умножаются на (-1). Таким образом, максимизация L (X) будет соответствовать минимизации L ₁(X).

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

Рассмотрим три основных метода нахождения опорных планов: метод северо-западного угла, метод минимального элемента и метод Фогеля. «Качество» опорных планов, полученных этими методами, различается: в общем случае метод Фогеля дает наилучшее решение (зачастую оптимальное), а метод северо-западного угла – наихудшее приближение.

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

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

На каждом шаге метода северо-западного угла из всех не вычеркнутых клеток выбирается самая левая и верхняя (северо-западная) клетка. Другими словами, на каждом шаге выбирается первая из оставшихся не вычеркнутых строк и первый из оставшихся не вычеркнутых столбцов. Для того, чтобы заполнить клетку (i, j), необходимо сравнить текущий запас товара в рассматриваемой i -й строке a_i ^тек с текущей потребностью в рассматриваемом j -м столбце b_j ^тек.

Если существующий запас позволяет перевезти всю потребность, то:

• в клетку (i,j) в качестве перевозки вписывается значение потребности b_j ^тек;

• j -й столбец вычеркивается, поскольку его потребность уже исчерпана;

• от существующего запаса в i -й строке отнимается величина сделанной перевозки, прежний запас зачеркивается, а вместо него записывается остаток, т.е. (a_i ^тек - b_j ^тек).

Если существующий запас не позволяет перевезти всю потребность, то:

• в клетку (i,j) в качестве перевозки вписывается значение запаса a_i ^тек;

• i-я строка вычеркивается, поскольку ее запас уже исчерпан;

• от существующей потребности в j -ом столбце отнимается величина сделанной перевозки, прежняя потребность зачеркивается, а вместо нее записывается остаток, т.е. (b_j ^тек - a_i ^тек)

Нахождение опорного плана продолжается до тех пор, пока не будут вычеркнуты все строки и столбцы.

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

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

Метод Фогеля

На каждом шаге метода Фогеля для каждой i -й строки вычисляются штрафы d_i как разность между двумя наименьшими тарифами строки. Таким же образом вычисляются штрафы d_j для каждого j -го столбца. После чего выбирается максимальный штраф из всех штрафов строк и столбцов. В строке или столбце, соответствующем выбранному штрафу, для заполнения выбирается не вычеркнутая клетка с минимальным тарифом min с_ij.

Если существует несколько одинаковых по величине максимальных штрафов в матрице, то в соответствующих строках или столбцах выбирается одна не вычеркнутая клетка с минимальным тарифом min с_ij.

Если клеток с минимальным тарифом также несколько, то из них выбирается клетка (i, j) с максимальным суммарным штрафом, т.е. суммой штрафов по i -й строке и j -му столбцу.

Задача

Найти тремя методами опорный план транспортной задачи, в которой запасы на трех складах равны 210, 170, 65 ед. продукции, потребности четырех магазинов равны 110, 90, 130, 100 ед. продукции, тарифы перевозки в рублях за единицу продукции следующие:

Решение

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

Результаты нахождения опорного плана различными методами представлены в следующих таблицах.

Транспортная таблица с опорным планом, найденным методом северо-западного угла.

Затраты на транспортировку при перемещении товара согласно полученному опорному плану равны:

.

Транспортная таблица с опорным планом, найденным методом минимального элемента.

Затраты на транспортировку при перемещении товара согласно полученному опорному плану равны:

.

Транспортная таблица с опорным планом, найденным методом Фогеля.

Затраты на транспортировку при перемещении товара согласно полученному опорному плану равны:

.

Отметим, что хотя введенные фиктивные строки или столбцы и считаются равноправными, но в случае задания в них нулевых тарифов эти тарифы не считаются как минимальные при построении опорных планов.

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

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

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

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

Потенциал удобно воспринимать как себестоимость продукции.