Практическое занятие №2 2 страница

Издержки на перевозку единицы продукции со склада i потребителю j

	Потребители
Склад №
	1.1		2.05			0.5
		2.15	4.8		11.07	2.2
	0.8		0.75	2.12	0.1	2.8
	0.7	0.3	1.1	3.7		0.2

Шаг 1. Проверка на сбалансированность

Общее число запасов на складах - 60.

Общая потребность – 61.

Общая потребность превышает общее число запасов на 1.

Задача является открытой (несбалансированной), для приведения ее к закрытой введем фиктивного производителя №5 c запасом продукции равному 1.

Все издержки по доставке продукции с данного производителя (склада) любому потребителю принимаем равными нулю.

Шаг 2. Отыскание начального решения. Метод северо-западного угла

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

b1=

b2=

b3=

b4=

b5=

b6=

a1=

a2=

a3=

a4=

a5=

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

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

b1=

b2=

b3=

b4=

b5=

b6=

a1=

Х

a2=

a3=

a4=

a5=

Итерация 1. Заполним клетку a1,b1.

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

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

b1=

b2=

b3=

b4=

b5=

b6=

a1=

Х

a2=

a3=

a4=

a5=

Итерация 2. Заполним клетку a1,b2.

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

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

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

b1=

b2=

b3=

b4=

b5=

b6=

a1=

a2=

Х

a3=

a4=

a5=

Итерация 3

b1=

b2=

b3=

b4=

b5=

b6=

a1=

a2=

X

a3=

a4=

a5=

Итерация 4

b1=

b2=

b3=

b4=

b5=

b6=

a1=

a2=

a3=

X

a4=

a5=

Итерация 5

b1=

b2=

b3=

b4=

b5=

b6=

a1=

a2=

a3=

X

a4=

a5=

Итерация 6

b1=

b2=

b3=

b4=

b5=

b6=

a1=

a2=

a3=

X

a4=

a5=

Итерация 7

b1=

b2=

b3=

b4=

b5=

b6=

a1=

a2=

a3=

X

a4=

a5=

Итерация 8

b1=

b2=

b3=

b4=

b5=

b6=

a1=

a2=

a3=

a4=

X

a5=

Итерация 9

b1=

b2=

b3=

b4=

b5=

b5=

a1=

a2=

a3=

a4=

a5=

X

Итерация 10

b1=

b2=

b3=

b4=

b5=

b6=

a1=

a2=

a3=

a4=

a5=

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

b1=

b2=

b3=

b4=

b5=

b6=

a1=

a2=

a3=

a4=

a5=

Шаг 3. Проверим полученный опорный план на невырожденность. Количество заполненных клеток N должно удовлетворять условию N=n+m-1. В нашем случае N=10, n+m=6+5=11, что удовлетворяет условию невырожденности плана.

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

Дата добавления: 2017-02-01