Метод минимального элемента

Метод северо-западного элемента.

Построение начального решения

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

Специальная структура транспортной модели позволяет использовать специальные методы построения начального решения (в общем случае метод Фогеля дает лучшее начальное решение).

1. В транспортной матрице определяется ячейка с наименьшей стоимостью перевозки (если таких ячеек несколько, выбор среди них произволен).

2. Переменной, соответствующей ячейки определенной выше, присваивается максимально возможное значение перевозки, допускаемое ограничениями на спрос и предложение.

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

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

Дата добавления: 2014-12-29