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

Метод СЗУ

Метод северо-западного угла работает по следующему принципу: доставка единиц продукции начинается с левой верхней ячейки матрицы, т.е заполнение таблицы транспортной задачи начинается с ячейки a1 и b1, и постепенно переходя к другим ячейкам таблицы. На каждом шаге исходя из запасов поставщика и запросов потребителя заполняется одна клетка и исключается из дальнейшего рассмотрения либо поставщик, либо потребитель. И так до тех пор, пока поставщики и потребители не исчерпают свои запасы и запросы. Из представленного объяснения мы понимаем что метод СЗУ не учитывает стоимость перевозок, и поэтому опорное решение будет не совсем, оптимальным.

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

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

Переход от одного опорного решения к другому.

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

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

При построении цикла его составляющие ячейки нумеруют и отмечают нечетные знаком «+», а четные знаком «-». Это делается с целью удобного и безошибочного вычисления опорного решения. Пример означенного цикла:

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