приватного рішення системи одному з потенціалів (зазвичай того, якому відповідає більше число зайнятих клітин) задають довільно деяке значення (частіше нуль). Решта потенціали однозначно визначаються за формулами: В
якщо відомий потенціал, і
В
якщо відомий потенціал
4. Перевірити виконання умови оптимальності для вільних клітин таблиці. Для цього обчислюють оцінки для всіх вільних клітин за формулами
В
і ті з них, які більше нуля, записуються в ліві нижні кути клітин. Якщо для всіх вільних клітин, то обчислюють значення цільової функції і вирішення завдання закінчується, так як отримане рішення є оптимальним. Якщо ж є хоча б одна клітина з позитивною оцінкою, опорне рішення не є оптимальним.
5. Перейти до опорному рішенням, на якому значення цільової функції буде менше. Для цього знаходять клітку таблиці завдання, якій відповідає найбільша позитивна оцінка
В
Будують цикл, що включає в свій склад дану клітину і частина клітин, зайнятих опорним рішенням. У клітинах циклу розставляють по черзі знаки В«+В» і В«-В», починаючи з В«+В» в клітці з найбільшою позитивною оцінкою. Здійснюють зсув (Перерозподіл вантажу) по циклу на величину. Клітка зі знаком В«-В», в якій досягається залишається порожньою. Якщо мінімум досягається в декількох клітинах, то одна з них залишається порожньою, а в інших проставляють базисні нулі, щоб число зайнятих клітин залишалося рівним.
Далі перейти до пунктом 3 даного алгоритму.
1.2.4 МЕТОД північно-західного кута
Відповідно до даного методу запаси чергового постачальника використовуються для забезпечення запитів чергових споживачів до тих пір, поки не будуть вичерпані повністю, після чого використовується запаси наступного за номером постачальника.
Заповнення таблиці транспортної задачі починається з лівого верхнього кута і складається з ряду однотипних кроків. На кожному кроці, виходячи із запасів чергового постачальника і запитів чергового споживача, заповнюється тільки одна клітина і відповідно виключається з розгляду один постачальник або споживач. При цьому нульові перевезення прийнято заносити в таблицю тільки в тому випадку, коли вони потрапляють в клітку (i, j), що підлягає заповненню, тобто в таблицю заносяться тільки базисні нулі, решта клітини з нульовими перевезеннями залишаються порожніми.
Щоб уникнути помилок після побудови початкового опорного рішення необхідно перевірити, що число зайнятих клітин одно m + n-1 і вектори умов, відповідні цим клітинам, лінійно незалежні.
Необхідно мати на увазі, що метод північно-західного кута не враховує вартість перевезень, тому, опорне рішення, побудоване за цим методом, може бути далеким від оптимального.
Приклад 3:
Скласти опорне рішення методом північно-західного кута транспортної задачі, у якій 5 постачальників та 5 споживачів. дані записані в таблиці 6
Таблиця 6
