(сумма предложений равна сумме спроса), одно из этих равенств должно быть избыточным. Таким образом, транспортная модель имеет т + п - 1 независимых ограничений, отсюда следует, что начальное базисное решение состоит из т + п - 1 базисных переменных. Например, начальное решение в примере 5.3.1 содержит 3 + 4-1 = 6 базисных переменных.

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

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

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

3. Метод Фогеля.

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

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

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

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

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

Пример 5.3.2

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

Получено следующее начальное базисное решение: х = 5,х12=10, х.п = 5, х.а - 15, х24 = 5, хм=10.

Соответствующая суммарная стоимость перевозок равна Z = 5xl0+10x2 + 5x7+15x9 + 5x20+10xl8 = 520 долл-

Спрос 5 15 15 15

Метод наименьшей стоимости. Данный метод находит лучшее начальное решение, чем метод северо-западного угла, поскольку выбирает переменные, которым соответствуют наименьшие стоимости. Сначала по всей транспортной таблице ведется поиск ячейки с наименьшей стоимостью. Затем переменной в этой ячейке присваивается наибольшее значение, допускаемое ограничениями на спрос и предложение. (Если таких переменных несколько, выбор произволен.) Далее вычеркивается соответствующий столбец или строка, и соответствующим образом корректируются значения спроса и предложений. Если одновременно выполняются ограничения и по спросу, и по предложению, вычеркивается или строка, или столбец (точно так же, как в методе северо-западного угла). Затем просматриваются невычеркнутые ячейки, и выбирается новая ячейка с минимальной стоимостью. Описанный процесс продолжается до тех пор, пока не останется лишь одна невычеркнутая строка или столбец.

Пример 5.3.3

Применим метод наименьшей стоимости к задаче из примера 5.3.1.

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

2. Следующей ячейкой с наименьшей стоимостью в незачеркнутой части таблицы будет (3, 1). Присвоим переменной x3i значение 5 и вычеркнем первый столбец. Ограничение по предложению, соответствующее третьей строке, станет равным 10 - 5 = 5.

3. Продолжая процедуру, последовательно присваиваем переменной x2i значение 15, переменной хи - значение 0; далее находим х34 = 5 их,4 = 10 (проверьте!).

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

Этот метод в русской математической литературе часто называют методом минимального элемента. - Прим. ред.

Таблица 5.17

1 2 3 4 Предложение

.г12= 15,х14 = 0, .г23=15,х24 = 10, Аз1 = >> *34 = 5.

Соответствующее значение целевой функции равно

z=15x2 + 0xll + 15x9 + 10x 20 + 5x4 + 5x 18 = 475 долл. Отсюда следует, что полученное методом наименьшей стоимости начальное решение лучше, чем начальное решение, представленное методом северо-западного угла (сравните данное значение целевой функции с аналогичным значением из примера 5.3.2).

Таблица 5.18

1 2 3 4 Предложение

Спрос 5 15 15 15

Метод Фогеля. Данный метод является вариацией метода наименьшей стоимости и в общем случае находит лучшее начальное решение. Алгоритм этого метода состоит из следующих шагов.

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

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