Складское хозяйство как элемент логистической системы

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

Матрицу перевозок начинаем заполнять с левого верхнего (северо-западного) угла, с клетки (1,1). Для этого сравниваем два значения а₁ = 30 и b₁= 20, т.е. попытаемся удовлетворить потребность первого пункта назначения за счет запасов первого пункта отправления. Запасы пункта А₁ больше потребности пункта В₁, следовательно, в качестве значения Х₁₁ выбираем меньшее число – b₁ и запишем это число в соответствующей клетке таблицы. Таким образом, потребность пункта В₁ в грузе удовлетворена, и поэтому все остальные числа этого столбца (Х₂₁, Х₃₁, Х₄₁) считаем равными нулю, а соответствующие им клетки оставляем свободными.

Получаем новую матрицу  из трех столбцов (В₂, В₃, В₄) и четырех строк (А₁, А₂, А₃, А₄) и новое значение запаса у первого пункта отправления ( = 30 – 20 = 10). Далее сравниваем значения = 10 и b₂ = 90 и повторяем алгоритм. Меньшее из этих значений, равное 10, выбираем в качестве Х₁₂ и записываем в клетку (1,2) таблицы. Тогда запас пункта А₁ будет полностью исчерпан, следовательно, остальные значения перевозок из первой строки (Х₁₃, Х₁₄) принимаем равными нулю, а соответствующие клетки остаются свободными. Продолжая заполнять таблицу, таким образом дойдем до клетки (4,4). Построенный план является опорным. В рассматриваемой задаче число пунктов отправления m = 4 и число пунктов назначения n = 4, следовательно, невырожденный план задачи определяется числами, стоящими в m+n–1 = 4 + 4 – 1 = 7 заполненных клетках.

Пункты  отправления	Пункты назначения				Предложение
	В1	В2	В3	В4
А1	20     5	10     4	2	5	30
А2	6	70     1	1	3	70
А3	2	10     3	40     1	8	50
А4	6	3	30     2	70     1	100
Спрос	20	90	70	70	-

Запишем первоначальный опорный план в виде матрицы Х:

Х = .

Согласно данному плану  перевозок функция цели – общая  стоимость перевозок всего груза - составляет

f(х) = 5 × 20 + 4 × 10 + 1 × 70 + 3 × 10 + 1 × 40 + 2 × 30 + 1 × 70 = 410.

Вырожденный план. При построении опорного плана нужно следить, чтобы сумма перевозок по каждой строке была равна соответствующим запасам, а сумма перевозок по каждому столбцу – потребности. Количество заполненных клеток равно m + n – 1. Если план вырожденный, т.е. если на очередном шаге запас а_i равен потребности b_j, в этом случае необходимо считать одну из клеток (либо справа, либо под последней заполненной клеткой) базисной со значением, равным нулю. Этот нуль вписывают, и соответствующая клетка считается занятой.

Пусть условия задачи заданы следующей таблицей:

Пункты  отправления	Пункты назначения				Предложение
	В1	В2	В3	В4
А1	20     5	10     4	2	5	30
А2	6	70     1	1	3	70
А3	2	0     3	30     1	20     8	50
А4	6	3	2	100     1	100
Спрос	20	80	30	120	S250

На первом шаге заполняем  северо-западный угол, полагая Х₁₁ = 20, клетки (2,1), (3,1) и (4,1) остаются свободными. На втором шаге полагаем Х₁₂ = 10. Этим мы используем полностью запас пункта А₁. Остальные клетки первой строки (1,3) и (1,4) остаются свободными. На третьем шаге рассматриваем перевозку Х₂₂. Поскольку в этом случае запас пункта А₂, равный 70, совпадает с оставшейся неудовлетворенной потребностью пункта В₂,  равной 70, то выбираем Х₂₂ = 70. Этим самым заполняется одновременно и вся вторая строка и весь второй столбец. В этом случае нужно считать одну из переменный Х₂₃ или Х₃₂ базисной со значением, равным нулю. Пусть Х₃₂ = 0. Проставив в соответствующей клетке базисный нуль, мы получаем при продолжении процесса заполнения таблицы m + n – 1 заполненную клетку. Если не проставить нулевую базисную переменную, окажется, что число занятых положительными перевозками клеток меньше, чем m + n – 1.

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

Этот метод позволяет найти первоначальный опорный план с меньшей стоимостью перевозок, чем план, полученный методом северо-западного угла:

Пункты  отправления	Пункты назначения				Предложение
	В1	В2	В3	В4
А1	10     5	4	20     2	5	30
А2	6	70     1	1	3	70
А3	2	3	50     1	8	50
А4	10     6	20     3	2	70     1	100
Спрос	20	90	70	70	-

Порядок заполнения таблицы: находим клетки с наименьшим значением стоимости перевозки и рассмотрим величину потребности и запаса для соответствующих пунктов. Заполним клетки (2,2), (3,3), (4,4) и подсчитаем остатки неизрасходованных запасов и величины неудовлетворенной потребности. Так, запасы пункта А₂ полностью расходуются на удовлетворение потребности пункта В₂, поэтому при нахождении первоначального опорного плана клетки второй строки, кроме (2,2), должны остаться свободными. Потребности пункта В₂ остаются неудовлетворенными на 20 единиц груза, поэтому клетки второго столбца, кроме (2,2), могут быть заполнены перевозками. Аналогично рассматриваем заполнение клеток (3,3) и (4,4). Найдем свободные клетки с наименьшими стоимостями перевозок, которые могут быть заполнены, это, например, клетка (1,3) или (4,3). Заполним клетку (1,3) и подсчитаем остаток. Затем заполним клетку (4,2), на следующем шаге клетку (1,1) и, наконец, (4,1).

Значение функции цели для первоначального опорного плана

f(х) = 10 × 5 + 20 × 2 + 70 × 1 + 50 × 1 + 10 × 6 + 20 × 3 + 70 × 1 = 400.

Открытая транспортная задача

Если не соблюдается  баланс предложения и спроса, то есть

¹ ,

такая задача называется открытой. Для решения такой задачи, если общее предложение превышает общий спрос, то есть

> ,

необходимо ввести в  модель фиктивный пункт потребления (В_n+1) в n + 1-м столбце матрицы транспортной задачи. При этом стоимости перевозки для фиктивного пункта потребления равны нулю:

C_i,n+1 = 0;  i =

.

Потребность в грузе  фиктивного пункта назначения равна  разности предложения и спроса:

Пункты  отправления	Пункты назначения						Запасы (предложение)
	В1	…	Вj	…	Вn	(Вn+1)
А1	С11		C1j		C1n	0	а1
…		…		…
Аi	Сi1		Сij		Сin	0	аi
…		…		…
Аm	Сm1		Сmj		Сmn	0	аm
Потребности (спрос)	b1	…	bj	…	bm	(bn+1 = Sаi - Sbj)

 

Если величина суммарного спроса превышает суммарное предложение, то есть

< ,

необходимо ввести в модель фиктивный пункт отправления грузов (А_m+1) в m + 1-ю строку матрицы транспортной задачи. При этом стоимости перевозки от фиктивного пункта отправления равны нулю:

C_m+1,j = 0;  j =

.

Предложение фиктивного пункта отправления равно разности суммы потребностей и запасов грузов:

Пункты  отправления	Пункты назначения					Запасы  (предложение)
	В1	…	Вj	…	Вn
А1	С11		C1j		C1n	а1
…		…		…
Аi	Сi1		Сij		Сin	аi
…		…		…
Аm	Сm1		Сmj		Сmn	аm
(Аm+1)	0		0		0	(Аm+1 = Sbj - Sаi)
Потребности (спрос)	b1	…	bj	…	bm	__

 

Метод потенциалов

Для решения транспортной задачи можно использовать метод  потенциалов. Пусть задан опорный план задачи, тогда каждому пункту отправления А_i приписывается некоторое число U_i, а каждому пункту назначения В_j – число V_j. Эти числа называют потенциалами, они подбираются так, чтобы для каждой базисной клетки (i, j) выполнялось равенство U_i + V_j = C_ij.

Таким образом, получаем m + n – 1 простых уравнений с m + n неизвестными U_i  и V_j. В таком случае, когда система состоит из числа уравнений, меньшего, чем число неизвестных, появляется свободная неизвестная величина, которой мы можем придать любое значение. Все остальные неизвестные можно найти из системы уравнений.

После того, как будут  найдены все потенциалы U_i и V_j, для каждой свободной клетки (i, j) определяют числа D_ij = C_ij -(U_i + V_j). Далее поступаем так же, как и в распределительном методе: находим наибольшее по модулю отрицательное число (т.е. самое малое из отрицательных) и делаем сдвиг по соответствующему циклу пересчета. Таким образом, в методе потенциалов для нахождения чисел D_ij не нужно искать циклы пересчета для всех свободных клеток. Надо найти только один цикл пересчета, соответствующий наименьшему отрицательному .