Нахождение опорного решения методом «северо-западного угла»

Сущность метода поясним на примере решения (табл. 8.2.1).

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

Z₁ = 1130

Процесс распределения ресурсов начинается с клетки, расположенной на «северо-западе», то есть в левом верхнем углу. Ей соответствует ресурс а₁ = 20 и

потребность b₁ = 10. Удовлетворяем потребность полностью, остаётся ресурс, равный 10. Теперь, по правилу, “дораспределяем» остаток ресурса, передав его следующей потребности b₂ которая его забирает, но с нехваткой относительно её потребности. Нехватка ресурса для потребности b₂ восполняется уже за счёт ресурса a₂, расположенного, уже, во второй строчке таблицы. Действия повторяются таким же образом и далее, с образованием ряда ступенек, ведущих в правый нижний угол, где и заканчивается процесс начального распределения.

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

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

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