Получается, что можно убрать все те строки, которые содержат только одну занятую клетку, затем нужно избавиться от всех столбов, которые содержат одну занятую клетку. Далее нужно вернуться к строкам и продолжить реализацию алгоритма. Алгоритм прекращает своё действие, когда из оставшихся клеток нельзя образовать цикл. Только в этом случае система становится линейно независимой, а решение опорным. В случае обратной ситуации, система векторов уже линейно зависима и тогда решение не является опорным. [9, c.67-70]
Метод минимальной стоимости.
Следующим методом является метод минимальной стоимости, который позволяет получить решение, которое очень близко к оптимальному, благодаря использования матрицы стоимостей транспортной задачи , i=1,2,…,m; j=1,2…,n.
Метод заключается в проделывании одинаковых действий на каждом из которых нужно заполнять только ту клетку таблицы, в которой присутствует значение минимальной стоимости , и исключается из рассмотрения только одна строка(поставщик) или один столбец(потребитель). Очередную клетку, соответствующую , заполняют также. Поставщик считается исключенным из рассмотрения в случае, когда его запасы исчерпываются. Потребитель исключается только в том случае, когда все его запросы удовлетворены целиком и полностью.
При последующих шагах перестают рассматривать либо одного поставщика, либо одного потребителя. При этом если поставщик не исключен, но его запасы равны нулю, то на том шаге, когда от него требуется поставить груз, в соответствующую клетку таблицы заносится базисный нуль и лишь затем поставщик исключается из рассмотрения. Аналогично поступают с потребителем. [12, c.110-112]
Пример 2:
Используя метод минимальной стоимости, построить начальное опорное решение транспортной задачи, доставки лекарств из трех складов в четыре аптеки.
Таблица 3
80 120 160 120
120 1 3 4 2
160 4 5 8 3
200 2 3 6 7
