Пример 4.4

Определим начальное решение по методу Фогеля для транспортной задачи из примера 4.1 (табл.4.4).

Решение.

Разности по строкам будем записывать в правой части табл. 4.4, разности по столбцам — внизу табл.4.4. Максимальную разность будем отмечать кружком. Наименьший тариф в первой строке равен 1. Ближайший к нему равен 3. Разность равна 1. Наименьший тариф во второй строке 4. Ближайшее к нему значение 5. В третьей строке 2 и 3, соответственно. Разности по всем строкам равны 1.

Таблица 4.4

№					Предложение	Разность по столбцам
	^1	^8	^1	^2				-	-
	^1	^5	^9	^8
	^9	^2	^3	^6
Спрос
Разность по строкам
			-
			-
		-	-

В первом столбце наименьший тариф c ₂₁= 4. Ближайшее значение с ₁₁ = 7, с ₁₁ – c ₂₁ = 7 – 4 = 3. Во втором столбце наименьшее значение c₃₂ = 3. Ближайшее значение с ₂₂ = 5, с ₂₂ – c₃₂ = 5 – 2 = 3.

Третий столбец: с ₁₃ = 1, с ₃₃ = 3, с ₃₃ – с ₁₃ = 3 -1 = 3.

Четвертый столбец: с ₁₄= 2, с ₃₄ = 6, с ₃₄ – с ₁₄ = 6 – 2 = 4.

Максимальная из всех разностей 4 находится в четвертом столбце.
В этом столбце клетка с наименьшим тарифом с ₁₄ = 2 находится в первой строке. В эту клетку помещаем максимально возможное значение: х₁₄ = min(110,160) = 110. Четвертый потребитель полностью удовлетворил свой спрос, и четвертый столбец вычеркиваем.

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

Первая строка: минимальный тариф с₁₃ = 1. Ближайшее значение
с ₁₁ =7, с ₁₁ – с ₁₃ =7-1 = 6.

Вторая строка: минимальный тариф c₂₁ = 4. Ближайшее значение
с ₂₂ = 5. с ₂₂- с ₂₁ = 5 – 4 = 1.

Третья строка: с₃₂ = 2, с₃₃ = 3, с₃₃ – с₃₂ = 3 – 2 = 1.

Первый столбец: минимальный тариф c₂₁ = 4. Ближайшее значение с₁₁ =7,

с₁₁ – c₂₁=7-4 = 3.

Второй столбец: с₃₂ = 2, с₂₂ = 5, с₂₂ – с₃₂ = 5 – 2 = 3.

Третий столбец: с₁₃ = 1. с₃₃ ⁼ 3, с₃₃ — с₁₃ =3 -1 = 3.

Максимальная разность равна 6 и стоит в первой строке. Минимальный тариф в первой строке с₁₃ = 1. В эту клетку помещаем х₁₃ = min(160 -110,190) = 50.

Вычеркиваем первую строку.

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

Вторая строка: с₂₁ = 4, с₂₂ = 5, с₂₂ – c₂₁ = 5 – 4 = 1.

Третья строка: с₃₂ = 2, с₃₃ = 3, с₃₃ – с₃₂ = 3 – 2 = 1.

Первый столбец: c₂₁ = 4, с₃₁ = 9, с₃₁ – c₂₁ = 9 – 4 = 5.

Второй столбец: с₃₂ = 2, с₂₂ = 5, с₂₂ – с₃₂= 5 – 2 = 3.

Третий столбец: с₃₃ = 3, с₂₃ = 9, с₂₃ – с₃₃ = 9 – 3 = 6.

Максимальная разность равна 6 и стоит в третьем столбце. Минимальный из оставшихся тарифов в этом столбце с ₃₃ = 3, х ₃₃ =
= min(170, 90 – 50) = 140. Спрос третьего потребителя удовлетворен, третий столбец вычеркиваем.

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

Вторая строка: с₂₁ = 4, с₂₂ = 5, с₂₂ – с₂₁=5 – 4 = 1.

Третья строка: с₃₂ = 2, с₃₁ = 9, с₃₁– с₃₂ = 9 – 2 = 7.

Первый столбец: c₂₁ = 4, с₃₁ =9, с₃₁ – c₂₁ = 9 – 4 = 5.

Второй столбец: с₃₂ = 2, с₂₂ = 5, с₂₂ – с₃₂ = 5 – 2 = 3.

Максимальная разность стоит в третьей строке. Минимальный тариф в этой строке с₃₂ = 2, х ₃₂ = min(170 -140,50) = 30.

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

Осталась одна строка транспортной таблицы. Это вторая строка.
В этой строке сначала заполняем клетку с наименьшим тарифом c₂₁=4, х₃₁ =min(140,120) = 120. Оставшееся предложение второго поставщика записываем в единственную свободную клетку х₂₂ = min(140 -120,50 –
– 30) = 20.

Полученный по методу Фогеля план перевозок имеет вид

Затраты на перевозку по этому плану составляют

S ₃ = 50*1 + 110*2+120*4+20*5+30*2+140*3=1430.

S _3< S _2< S ₁.

Таким образом, для одной и той же транспортной задачи получены различные начальные планы перевозок, построенные с использованием разных методов. При этом затраты на перевозки уставляют соответственно: S ₁ =3220, S ₂ = 1530, S ₃ = 1430. Метод Фогеля наиболее трудоемкий, однако начальный план перевозок, построенный с его использованием, обычно бывает близок к оптимальному плану, а в некоторых случаях является оптимальным планом.

Изложенные методы нахождения начального решения не единственные. В качестве начального решения может быть взят любой набор чисел, удовлетворяющих ограничениям (4.9)–(4.12) (например, полученный по методу "юго-восточного" угла). Читатель может придумать свой собственный метод получения начального решения.

Дата добавления: 2015-08-20