Записать правила построения первого базисного решения замкнутой транспортной задачи по методу северо-западного угла

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

если остаток продукта у i-го поставщика после предыдущих шагов меньше, чем неудовлетв. запрос j-го потребителя, то исключается из рассмотрения i-й поставщик, и в клетку (i, j) заносится поставка x_ij, равная остатку продукта у i-го поставщика после предыдущих шагов;

если остаток продукта у i-го поставщика после предыдущих шагов больше, чем неудовлетворенный запрос j-го потребителя, то исключается из рассмотрения j-й потребитель, и в клетку (i, j) заносится поставка x_ij, равная неудовлетворенному запросу j-го потребителя;

если остаток продукта у i-го поставщика после предыдущих шагов равен неудовлетворенному запросу j-го потребителя, то исключается из рассмотрения или i-й поставщик, или j-й потребитель, и в клетку (i, j) заносится поставка x_ij=0 равная остатку продукта у i-го поставщика после предыдущих шагов.

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

Каждому поставщику ставится в соответствие потенциал p_i, а каждому потребителю — потенциал q_i. При этом каждой клетке соответствует некоторая оценка: .

Один из потенциалов можно выбрать произвольно, так как в системе одно уравнение линейно зависит от остальных. Обычно полагают p₁=0. Остальные потенциалы вычисляются из условия, что для базисных клеток ∆_ij=0.

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

Для выбранной свободной клетки строится цикл пересчета — замкнутая ломаная, одна из вершин которой находится в данной свободной клетке, а все остальные — в занятых клетках, соседние звенья взаимно перпендикулярны, сами звенья параллельны строкам и столбцам таблицы.

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