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

1. Берется самая верхняя левая клетка (, туда проставляется груз: . То есть либо вывезен весь первый ПО, либо полностью удовлетворен первый ПН.

а) Если полностью вывезен ПО, то вычеркиваем а₁, вместо b₁ пишем число . Из первого ПО больше ничего нельзя вывезти, а в первый ПН осталось привезти . Оставшиеся клетки в строке будут пустыми (не занятыми).

б) Если полностью удовлетворен ПН, то вычеркиваем b₁, вместо а₁ пишем число . В первый ПН ничего больше нельзя ввезти. Оставшиеся клетки в столбце будут пустыми (незанятыми).

Находим следующую самую северо-западную клетку.

В случае а) – это будет – вторая строка, первый столбец.

В случае б) – это будет – первый столбец, вторая строка.

Снова заполняем ее аналогичным образом.

На каждом этапе либо какой-то ПО вывозится полностью, либо какой-то ПН удовлетворяется полностью.

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

На последнем этапе все ПО вывезены и все ПН удовлетворены.

Date: 2015-08-15; view: 429; Нарушение авторских прав