3.2.1. Метод северо-западного угла
Алгоритм этого метода следующий:
1.
Рассматривается левая верхняя клетка
распределительной таблицы. Сравниваются
.ресурсы -
и
потребности
.
2.
Если
,
то в клетку записывается
.
Клетка объявляется базисной (коэффициент
транспортных затрат
обводим кружком). Подсчитывается новый
ресурс:
,
столбец с номером j
исключается из рассмотрения. Далее
необходимо перейти к пункту 1
для новой таблицы с исключенным столбцом.
3 Если
,
то в клетку записывается
,
клетка объявляется базисной. Подсчитывается
новая потребность
и строка с номером i
исключается
из дальнейшего рассмотрения. Далее
также необходимо перейти к пункту 1
для
новой таблицы с исключенной строкой.
4 Может
представиться случай, когда
.
В этом случае строка или столбец
исключаются произвольно, а новая
потребность или новый ресурс равны
нулю. Например, в клетку записывается
,
новая потребность
,
строка исключается
из рассмотрения. Далее - переход к пункту
1
для новой таблицы с исключенной строкой.
5. При заполнении последней клетки таблицы, когда оставшиеся потребность и ресурс равны, исключаются одновременно и строка, и столбец.
Пример
В распределительной таблице записаны условия транспортной задачи:
Таблица 1
Потребности
Ресурсы |
3 |
4 |
3 |
5 |
3 |
5 |
3 |
2 |
2 |
1 |
1 |
3 |
1 |
3 |
4 |
1.
Возьмем верхнюю левую клетку:
(п.
2 алгоритма), следовательно, в клетку
надо записать потребность
,
новый ресурс
,
а 1-й столбец исключается из дальнейшего
рассмотрения, клетка объявляется
базисной (коэффициент
транспортных
затрат обводится
кружком) (таблица 2).
2. Переходим к рассмотрению новой таблицы.
Таблица 2
Потребности
Ресурсы |
3 |
0 2 4 |
3 |
2 5 |
3 3 |
5 2 |
3 |
2 |
2 |
1 2 |
1 |
3 |
1 |
3 0 |
4 3 |
Здесь
также выбирается верхняя левая клетка:
(п. 3 алгоритм), следовательно
в клетку надо записать ресурс
,
новая потребность
,
первую строку исключить из рассмотрения.
Клетка объявляется базисной.
3.
Опять переходим к рассмотрению новой
таблицы, где верхняя левая клетка:
(п. 4 алгоритма). Тогда
и
.
Исключаем из рассмотрения строку.
4.
Рассматриваем новую таблицу, где верхняя
левая клетка:
(п. 2 алгоритма). Тогда
,
а новый ресурс:
.
Столбец исключается из рассмотрения.
5.
Для последней клетки таблицы:
,
тогда исключаем и столбец и строку,
клетку объявляем базисной и
.
Рекомендуется на начальной стадии для большей наглядности алгоритма производить вычисления в разных таблицах (в примере 4 таблицы).
Подсчитаем значение целевой функции (по базисным клеткам):
В таблице получено исходное опорное решение. Рассматривая алгоритм записи исходного опорного решения методом северо-западного угла, можно установить следующее:
В таблицу всегда заносятся неотрицательные числа.
Из таблицы исключаются строка или столбец лишь тогда, когда соответствующее ограничение превращается в тождество. Следовательно, после заполнения таблицы все ограничения - тождества.
Так как при записи базисной переменной исключается или строка, или столбец, и лишь при записи последней базисной переменной исключаются одновременно и строка, и столбец, то всего в таблицу вносится (m+n-1) базисных переменных, что соответствует рангу системы ограничений транспортной задачи.
Указанным требованиям подчиняются и алгоритмы других методов записи исходного опорного решения. После записи опорного решения рекомендуется всегда проверять выполняются ли условия 1, 2 и 3.