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

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

Существующий алгоритм решения транспортных задач (метод потенциалов) предполагает, что ЦФ стремится к минимуму. Однако существуют ситуации, когда в рамках транспортной модели требуется максимизировать ЦФ, например, общий доход, объем продаж, прибыль, качество выполняемых работ и т.д. В этом случае в модель вместо искомой целевой функции 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 ед. продукции, тарифы перевозки в рублях за единицу продукции следующие: