Методы составления начального

опорного плана перевозок

Рассмотрим три метода составления начального распределения (начального плана перевозок): метод „северо-западного угла”, метод учета наименьших затрат и метод аппроксимаций Фогеля.

При каждом из этих методов при заполнении некоторой клетки, кроме последней, вычеркивается или только строка, или только столбец; лишь при заполнении последней клетки вычеркивается и строка и столбец. Такой подход будет гарантировать, что после заполнения таблицы в ней будет ровно базисных (заполненных) клеток, и, следовательно, задача будет разрешима. Если при заполнении некоторой (не последней) клетки одновременно удовлетворяется запрос потребителя и исчерпывается запас поставщика, то в любую клетку из вычеркиваемых строки и столбца следует поставить ноль и считать эту клетку заполненной – клеткой с „нулевой поставкой”. Транспортные задачи, в базисном плане перевозок которых имеют место занятые клетки с „нулевой поставкой”, называются вырожденными.

Метод „северо-западного угла”. В данном методе в первую очередь всегда заполняется клетка, стоящая в верхнем левом (северо-западном) углу транспортной таблицы. Если при этом полностью исчерпывается запас поставщика, то вычеркивается строка, если удовлетворен запрос потребителя, то вычеркивается столбец. Далее снова заполняется верхняя левая клетка среди невычеркнутых и так далее.

Пример составления начального плана методом „северо-западного угла” показан в таблице 3.

Таблица 3

		—	—	—
			—	—
	—		—	—
	—

Суммарные затраты на реализацию данного плана перевозок составят:

.

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

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

Таблица 4

	—	—		—
				—
	—	—		—
	—		—

Суммарные затраты на реализацию данного плана перевозок составят:

.

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

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

· вычисляем разности в каждой строке и каждом столбце транспортной таблицы между наименьшей стоимостью и ближайшей к ней по величине.

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

Пример составления начального плана методом аппроксимаций Фогеля показан в таблице 5.

Таблица 5

						Столбцы разностей
	—	—		—				—	—	—
				—
	—	—		—					—	—
	—		—							—
Строки разностей
			—
			—
			—
—	—	—	—

Суммарные затраты на реализацию данного плана перевозок:

.

Суммарная стоимость перевозок, соответствующая начальному распределению, построенному в соответствии с методами учета наименьших затрат и аппроксимаций Фогеля меньше, чем стоимость перевозок, соответствующая распределению, полученному по методу "северо-западного угла", следовательно последнее распределение ближе к оптимальному и целесообразно продолжить решение задачи с последнего распределения.

Метод потенциалов решения транспортной задачи. В 1940 г. советским ученым Л. В. Канторовичем был разработан метод решения транспортной задачи, и в первой публикации (1942 г.) содержались основные идеи метода. Впоследствии (в 1949 г.) в совместной статье Л. В. Канторовичем и М. К. Гавуриным был изложен сам метод (в сетевой постановке), названный методом потенциалов. Позднее (в 1951 г.) американским ученым Дж. Б. Данцигом был разработан аналогичный метод, получивший название модифицированного распределительного метода, который в иностранной и некоторой советской литературе сокращенно именуют методом МОДИ. Поскольку разница между этими способами чрезвычайно незначительна, в дальнейшем не будем их разграничивать и станем именовать общим названием – методом потенциалов.

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

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

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

Проверим опорный план перевозок, построенный методом аппроксимаций Фогеля на оптимальность методом потенциалов.

Добавим в транспортную таблицу ещё одну строку и столбец для потенциалов.

Таблица 6

	—	—		—
				—
	—	—		—		– 3
	—		—			– 3

· Для занятых клеток транспортной таблицы вычислим потенциалы по формуле :

пусть , тогда ,

,

,

,

,

,

.

· Для свободных клеток таблицы вычислим оценки (косвенные тарифы) по формуле .

,

,

,

,

,

,

,

,

.

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