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

Этот метод позволяет построить опорное решение, которое достаточно близко к оптимальному решению, так как использует матрицу стоимостей транспортной задачи.

На каждом шаге метода заполняется только одна клетка таблицы, соответствующая минимальной стоимости и исключается из рассмотрения только одна строка или один столбец. Очередную клетку, соответствующую минимальной стоимости заполняют по тем же правилам, что и в методе северо-западного угла. Если поставщик еще не исключен, но его запасы равны нулю, то на том шаге, когда от него требуется поставить груз, в соответствующую клетку таблицы заносится базисный нуль и только потом поставщик исключается из рассмотрения. Аналогично поступают с потребителем.

Пример. Составить начальное опорное решение транспортной задачи, используя метод минимальной стоимости

Решение:

1) Среди элементов матрицы стоимости минимальной является стоимость . В клетку записываем максимально возможную перевозку . Исключаем из рассмотрения первого потребителя. Запасы третьего поставщика уменьшаем . Вычеркиваем первый столбец.

2) Среди элементов оставшейся матрицы стоимости минимальной является стоимость . В клетку записываем максимально возможную перевозку . Исключаем из рассмотрения первого поставщика. Запросы второго потребителя уменьшаем . Вычеркиваем первую строку.

3) Среди элементов оставшейся матрицы стоимости минимальной является стоимость . В одну из этих клеток, например, записываем максимально возможную перевозку . Исключаем из рассмотрения второго потребителя. Запасы второго поставщика уменьшаем . Вычеркиваем второй столбец.

4) Среди элементов оставшейся матрицы стоимости минимальной является стоимость . В клетку записываем максимально возможную перевозку . Исключаем из рассмотрения третьего поставщика. Запросы третьего потребителя уменьшаем . Вычеркиваем третью строку.

5) Среди элементов оставшейся матрицы стоимости минимальной является стоимость . В клетку записываем максимально возможную перевозку . Исключаем из рассмотрения третьего потребителя. Запасы второго поставщика уменьшаем . Вычеркиваем третий столбец.

6) В оставшейся матрице осталась незаполненной одна клетка со стоимостью . Записываем в нее число .

7) Применяя метод вычеркивания, проверяем линейную зависимость векторов условий

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

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

Для удобства вычислений вершины циклов нумеруют и отмечают нечетные знаком плюс, а четные знаком минус. Такой цикл называется означенным.

Сдвигом по циклу на величину называется увеличение объемов перевозок во всех нечетных клетках цикла, отмеченных знаком плюс, и уменьшение объемов перевозок на ту же величину во всех четных клетках, отмеченных знаком минус.