Метод минимальной стоимости.

Данный метод позволяет построить решение, которое достаточно близко к оптимальному, так как при его применении используются стоимости транспортной задачи , . Он состоит из ряда однотипных шагов, на каждом из которых заполняется только одна клетка, соответствующая (в отличие от метода северо- западного угла). Сам процесс заполнения клетки такой же, как и в методе северо-западного угла. Также на каждом шаге исключается из рассмотрения только одна строка (поставщик, если его запасы заканчиваются) или только один столбец (потребитель, если его запросы выполнены).

Затем переходят к клетке, соответствующей из неисключённых клеток и т.д. При этом, если поставщик ещё не исключён, но его запасы равны нулю, то на том шаге, когда от него требуется поставить груз, в соответствующую клетку таблицы заносится базисный нуль и лишь потом поставщик исключается из рассмотрения. Аналогично поступают и с потребителем.

Рассмотрим метод минимальной стоимости на примере табл. 7.2.

Наименьшую стоимость имеет клетка . Запасы 1-го поставщика, как и запросы 4-го потребителя равны 100 единицам, поэтому заносим в эту клетку 100 и исключаем, например, 4-го потребителя. Затем переходим к следующей клетке, содержащей минимальную стоимость, например, к . Запасы 2-го поставщика равны 200 единицам, а запросы 1-го потребителя – 250 единиц, поэтому в клетку заносим и исключаем 1-го потребителя. У 2-го поставщика остаётся ещё 50 единиц. Следующая клетка из неисключённых, соответствующая минимальной стоимости, находится на пересечении 3-й строки и 5-го столбца. Согласно тому же правилу, заносим в неё и исключаем 3-го поставщика и т.д. В результате получим табл. 3.

Таблица 3

Поставщики	Потребители	Запасы
Запросы

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

.

Естественно возникает вопрос, является ли это решение оптимальным. Ответ на него будет дан в следующем пункте.

Не нашли, что искали? Воспользуйтесь поиском: