Начальное решение транспортной задачи

Найдем исходное опорное решение по методу минимальной стоимости. Для этого заполним распределительную таблицу:

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

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

x_ij = min(a_i, b_j).

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

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

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

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

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

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

Следующими клетками с минимальным значением тарифа являются клетки (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):

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

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

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

.

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

.