Определение начального решения

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

Специальная структура транспортной модели для построения начального решения позволяет применить следующие методы (вместо использования искусственных переменных, как это делается в симплекс-методе):

– метод северо-западного угла;

– метод наименьшей стоимости;

– метод Фогеля.

Различие этих методов заключается в «качестве» начального решения, т.е. насколько начальное решение ближе к оптимальному. В общем случае метод Фогеля дает наилучшее решение, а метод северо-западного угла — наихудшее. Однако метод северо-западного угла требует меньшего объема вычислений.

2.1.1 Метод северо-западного угла

Выполнение начинается с верхней левой ячейки (северо-западного угла) транспортной таблицы, т.е. с переменной . Шаг 1. Переменной присваивается максимальное значение, допускаемое ограничениями на спрос и предложение.

Шаг 2. Вычеркивается строка (или столбец) с полностью реализованным предложением (с удовлетворенным спросом). Это означает, что в вычеркнутой строке (столбце) мы не будем присваивать значения остальным переменным (кроме переменной, определенной на первом шаге). Если одновременно удовлетворяются спрос и предложение, вычеркивается только строка или только столбец.

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

Таблица 2.2. Метод северо-западного угла

Соответствующая суммарная стоимость перевозок равна

,