Задание 5

Имеются три пункта поставки однородного груза А₁, А₂, А₃ и четыре пункта В₁, В₂, В₃, В₄ потребления этого груза. На пунктах А₁, А₂ и А₃ находится груз соответственно в количестве a₁, a₂ и a₃ т. В пункты В₁, В₂, В₃ и В₄ требуется доставить соответственно b₁ , b₂ , b₃ и b₄ т груза. Расстояние между пунктами поставки и пунктами потребления приведено в следующей матрице-таблице:

Пункты поставки	Пункты потребления
	В1	В2	В3	В4
А1
А2
А3

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

а₁ = 230 , a₂ = 280, a₃ = 120, b₁ = 200, b₂ = 160, b₃ = 180, b₄ = 100.

Решение.

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

Получим первоначальный опорный план. Он является невырожденным, т.к. занято m+n-1=3+4-1=6 клеток.

Его стоимость Z=200*13+30*6+100*11+180*7+60*10+70*5=6090

Матрица планирования		Пункты потребления												Запасы
		В1			В2			В3			В4
Поставщики	vj ui	v1=13			v2=11			v3=7			v4=6
А1	u1=0			13			15			9			6	230
		200									30
А2	u2=0			19			11			7			14	280
					100			180
А3	u3=-1			17			10			23			5	120
					60						70
Потребности		200			160			180			100

Для проверки плана на оптимальность построим систему потенциалов. Потенциалы найдем из условия u_i+v_j=c_ij для занятих клеток.

Пусть u₂=0, тогда

u ₂+v₂=11 v₂=11

u ₂+v₃=7 v₃=7

u ₃+v₂=10 u₃=-1

u ₃+v₄=5 v₄=6

u ₁+v₄=6 u₁=0

u ₁+v₁=13 v₁=13

Систему потенциалов составили. Теперь проверим найденный опорный план на оптимальность для незанятых клеток: u_i+v_j-c_ij<0

Для строки А₁: u₁+v₂-c₁₂ =0+11-15=-4<0

u₁+v₃-c₁₃ =0+7-9=-2<0

Для строки А₂: u₂+v₁-c₂₁ =0+13-19=-6<0

u₂+v₄-c₂₄ =0+6-14=-8<0

Для строки А₃: u₃+v₁-c₃₁ =-1+13-17=-5<0

u₃+v₃-c₃₃ =-1+7-23=-17<0

Для всех клеток условие оптимальности выполнено, значит получен оптимальный план.