Задание 3. Имеются три пункта поставки однородного груза пять пунктов потребления этого груза

Имеются три пункта поставки однородного груза пять пунктов потребления этого груза. На пунктах находится груз соответственно в количестве 200, 350, 300 т. В пункты требуется доставить соответственно 270, 130, 190, 150, 110 т груза.

Расстояние между пунктами потребления приведено в следующей матрице таблице:

Найти план перевозок данной транспортной задачи методом северо-западного угла.

Решение.

Проверим задачу на сбалансированность.

.

Условие баланса соблюдается. Запасы груза в пунктах поставки равны потребностям в пунктах потребления этого груза, т.е. .

Следовательно, задача является сбалансированной (закрытой).

Отыщем начальное решение методом северо-западного угла.

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

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

	Пункты потребления
Пункты поставки

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

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

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

В таблице сама клетка и соответствующие ей остатки отображаются жирным шрифтом.

	Х

Шаг 1.

Заполним клетку . Сравним значения остатков для производителя и потребителя .

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

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

	Х

Шаг 2.

Заполним клетку . Сравним значения остатков для производителя и потребителя .

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

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

		Х

Шаг 3.

			Х

Шаг 4.

			Х

Шаг 5.

				Х

Шаг 6.

					Х

Шаг 7.

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

Проверим полученное решение на невырожденность.

Количество заполненных клеток N должно удовлетворять условию N=n+m-1.

В нашем случае, , что удовлетворяет условию невырожденности плана.

Далее вычислим общие затраты на перевозку всей продукции.

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

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

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

.