Метод минимальной стоимости нахождения начального решения транспортной задачи

В соответствии с методом минимальной стоимости грузы распределяются в первую очередь в те клетки, которым соответствует минимальный тариф перевозок с _ij. При этом объем поставки, вносимый в клетку, определяется как минимальное значение среди значений запаса и потребности:

x_ij = min(a_i, b_j).

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

В случае нескольких клеток с одинаковыми значениями тарифов в первую очередь поставки распределяются в клетку с максимально возможной поставкой.

Процесс распределения продолжают до тех пор, пока все грузы от поставщиков не будут вывезены, а потребители не будут удовлетворены.

 

Минимальное значение имеет тариф перевозки от четвертого поставщика к четвертому потребителю с₄₄ = 4, т.е. клетка (4, 4). В данную клетку вносится значение поставки, представляющее собой минимальное значение из значений запаса у четвертого поставщика и потребности у четвертого потребителя, т.е. min (21, 20) = 20. Это первая из искомых поставок х₄₄ = 20.

Поскольку потребность четвертого поставщика поставкой х₄₄ = 20 полностью удовлетворена, то потребность обнуляется, а в остальных клетках четвертого столбца проставляется прочерк – в эти клетки другое поставки вноситься не будут.

У четвертого поставщика остается еще одна единица груза (21 – 20 = 1), которая подлежит дальнейшему распределению:

bj ai		1	2	3	4
		15/	16/	15/	20/0
1	14/	6	10		5 -
2	11/	10	7		9 -
3	20/5/	13	14		7 -
4	21/1/	5	10 -	6 -	4 20

 

Следующими клетками с минимальным значением тарифа являются клетки (4, 1) и (3, 3), в которых с₄₁ = с₃₃ = 5. В клетку (4, 1) можно разместить поставку min (1, 14) = 1, в клетку (3, 3) – поставку min (20, 15) = 15. Максимальным среди них является значение 15. Следовательно, х₃₃ = 15. Потребность третьего поставщика обнуляется, а в остальных клетках третьего столбца проставляется прочерк. У третьего поставщика остается еще пять единиц груза (20 – 15 = 5), которые подлежат дальнейшему распределению. Поскольку клетка (4, 1) не занята, то в нее можно разместить оставшуюся единицу груза, следовательно, х₄₁ = 1. При этом запас четвертого поставщика обнуляется, а в оставшуюся незанятой клетку четвертой строки (4, 2) вносится прочерк. Потребность первого потребителя сокращается до 14 (14 = 15 – 1):

 

bj ai		1	2	3	4
		15/14	16/	15/0	20/0
1	14/	6	10	7 -	5 -
2	11/	10	7	6 -	9 -
3	20/5/	13	14	5 15	7 -
4	21/1/0	5 1	10 -	6 -	4 20

 

Среди незанятых клеток минимальный тариф имеет клетка (1, 1): с₁₁ = 6. Объем возможной поставки определяется как min (14, 14) = 14. Следовательно, х₁₁ = 14. При этом обнуляется запас первого поставщика и потребность первого потребителя, а в свободных клетках первого столбца и первой строки ставится прочерк:

 

bj ai		1	2	3	4
		15/14/0	16/	15/0	20/0
1	14/0	6 14	10 -	7 -	5 -
2	11/	10 -	7	6 -	9 -
3	20/5/	13 -	14	5 15	7 -
4	21/1/0	5 1	10 -	6 -	4 20

 

Следующая клетка с минимальным тарифом – клетка (2, 2): с₂₂ = 7. Объем возможной поставки определяется как min (11, 16) = 11. Следовательно, х₂₂ = 11. При этом обнуляется запас второго поставщика. В последнюю свободную клетку (3, 2) вносится последняя поставка х₃₂ = 5:

 

 

bj ai		1	2	3	4
		15/14/0	16/5/0	15/0	20/0
1	14/0	6 14	10 -	7 -	5 -
2	11/0	10 -	7 11	6 -	9 -
3	20/5/0	13 -	14 5	5 15	7 -
4	21/1/0	5 1	10 -	6 -	4 20

 

Таким образом, все поставки распределены, получено начальное решение транспортной задачи:

.

Значение целевой функции:

.

 

⇐ Предыдущая567891011121314Следующая ⇒

Поделиться: