Метод наименьшей стоимости
Данный метод находит лучшее начальное решение, чем метод северо-западного угла, поскольку выбирает переменные, которым соответствуют наименьшие стоимости. Сначала по всей транспортной таблице ведется поиск ячейки с наименьшей стоимостью. Затем переменной в этой ячейке присваивается наибольшее значение, допускаемое ограничениями на спрос и предложение. (Если таких пе¬ременных несколько, выбор произволен.) Далее вычеркивается соответствующий столбец или строка и соответствующим образом корректируются значения спроса и предложений. Если одновременно выполняются ограничения и по спросу, и по предложению, вычеркивается или строка, или столбец (точно так же, как в методе северо-западного угла). Затем просматриваются невычеркнутые ячейки, и выбирается новая ячейка с минимальной стоимостью. Описанный процесс продолжается до тех пор, пока не останется лишь одна невычеркнутая строка или столбец.
Алгоритм решения транспортной задачи
После определения начального решения применяется алгоритм, позволяющий найти оптимальное решение транспортной задачи.
Шаг 1
На основе симплексного условия оптимальности среди текущего мно¬жества небазисных переменных определяется вводимая в базис пере-менная, которая может улучшить значение целевой функции. Если усло¬вие оптимальности выполняется для всех небазисных переменных, вы¬числения заканчиваются, в противном случае необходимо перейти ко второму шагу.
Шаг 2
С помощью симплексного условия допустимости определяется исклю¬чаемая из базиса переменная. Происходит изменение базиса и возврат к первому шагу.
При изменении базиса в данном случае не используются вычисления, выполняемые при реализации симплекс-метода, — специальная структура транспортной таблицы позволяет значительно упростить вычисления.
Пример
1) Ячейка (1,2) имеет наименьшую в таблице стоимость (= $2). Наибольшее значение, которое можно присвоить переменной x12, равно 15. В этом случае удовлетворяются ограничения, соответствующие первой строке и вто¬рому столбцу. Вычеркиваем второй столбец, предложение первой строки и спрос второго столбца принимают нулевые значения.
2) Следующей ячейкой с наименьшей стоимостью в незачеркнутой части таблицы будет (3, 1). Присвоим переменной x31 значение 5 и вычеркнем первый столбец. Ограничение по предложению, соответствующее третьей строке, станет равным 10 - 5 = 5.
3) Продолжая процедуру, последовательно присваиваем переменной х23 значение 15, переменной х14 значение 0; далее находим х34 = 5 и х24 = 10.
Процесс поиска начального решения представлен в табл. 1. Стрелками по¬казана последовательность присвоения переменным значений. Итак, получили следующее начальное базисное решение (состоящее из 6 переменных):
x12 = 15, x14 = 0, x23 = 15, x24 = 10, x31 = 5, x34 = 5.
Соответствующее значение целевой функции равно:
z = 15*2 + 0*11 + 15*9 + 10*20 + 5*4 + 5*18 = $475.
Один из методов составления опорного плана перевозок в транспортной задаче является метод наименьшей стоимости. Отличаясь простотой данный метод все же эффективнее чем, к примеру, метод Северо-западного угла. Кроме того, метод минимального элемента (или, иначе "метод наименьшего элемента") понятен и логичен. Его суть в том, что в транспортной таблице сначала заполняются ячейки с наименьшими тарифами, а потом уже ячейки с большими тарифами. То есть мы выбираем перевозки с минимальной стоимостью доставки груза. Это очевидный и логичный ход. Алгоритм решения транспортной задачи повторяет основные шаги симплекс-метода. Только для представления данных, вместо обычных симплекс-таблиц, используются транспортные таблицы со специальной структурой. пример в приложенном файле.