Оценка свободных клеток

 

Построим опорный план методом минимальной стоимости(

1. загрузить в транспортную таблицу клетку с минимальным тарифом A2b2

2. исключить из рассматриваемых соответствующую поставку или потребность

3. в оставшиеся части транспортной таблицы загрузить клетку с минимальным тарифом

4. Повторить п. 2 и 3 до тех пор пока не будут исчерпаны запасы всех поставщиков, удовлетворен спрос всех потребителей

5. если в результате будет загружено m+n-1 клеток то опорный план построен. в противоположном случае все последующие клетки заполнить 0 чтобы число загруженных клеток стало (m+n+1)

 

проверим на опорность:

m+n-1=3+3-1=5→построенный план является опорным т.к. число загруженных клеток =5

вычислим транспортные расходы:

Z =90*2+300+100*5+50*3+60*3= 1610

4. найдем потенциалы поставщиков и потребителей u_i + v_j = c_ij примем u ₁=0

U₁+V₁=2 U₁=0 V₁=2

U₂+V₂=1 U₂=-2 V₂=3

U₂+V₃=5 U₂=-2 V₃=7

U₃+V₁=3 U₃=1 V₁=2

U₃+V₃=8 U₃=1 V₃=7

оценка свободных клеток

D _ij = u_i + v_j - c_ij.

Проверка решения на оптимальность.

Если все D _ij £0, то найденное решение оптимально.

Если среди оценок есть хотя бы одно положительное число, то найденное решение не оптимально и его надо улучшить.

D ₁₂ = u₁ + v₂ – c₁₂=0+3-5=-3

. D ₁₃ = u₁ + v₃ – c₁₃=0+7-5=4

т.к. есть положительный результат опорный план не оптимален

 

6. строим цикл

	Потребители	V1 b1	V2 b2	V3 b3
получатели
U1 A1		-90 2		+ 2
U2 A2			300 1	100 5
U3 A3		+50 3		- 60 -8

 

l=60

	Потребители	V1 b1	V2 b2	V3 b3
получатели
U1 A1		30 2		60 2
U2 A2			300 1	100 5
U3 A3		110 3		-8

 

вычислим транспортные расходы:

Z =30*2+60*2+300+100*5+11*3=1310

найдем потенциалы поставщиков и потребителей u_i + v_j = c_ij примем u ₁=0

U₁+V₁=2 U₁=0 V₁=2

U₁+V₃=2 U₁=0 V₃=2

U₂+V₂=1 U₂=3 V₂=-2

U₂+V₃=5 U₂=3 V₃=2

U₃+V₁=3 U₃=1 V₁=2