Перевірка на оптимальність невиродженого опорного плану методом потенціалів (другий пункт алгоритму)
1 Кожному постачальнику поставимо у відповідність потенціал, а кожному споживачеві потенціал.
Тоді кожної зайнятої клітці буде відповідати рівняння
Так як всіх зайнятих клітин має бути m + n - 1, тобто на одиницю менше числа потенціалів, то для знаходження необхідно вирішити систему з m + n - 1 рівнянь з m + n невідомими. Система є лінійно-залежною і, щоб знайти приватне рішення, одному з потенціалів потрібно надати довільне числове значення, тоді інші потенціали визначаються однозначно. Наприклад, потенціали рядків і стовпців для початкового опорного плану, знайденого в останньому прикладі методом мінімального елемента визначимо з рішення системи
Система є лінійно-залежною, для знаходження одного з приватних рішень додамо одному з потенціалів числове значення, наприклад, тоді
Для розробки проекту на оптимальність для кожної вільної клітини вважаємо оцінки за формулою
;
а) якщо всі оцінки є позитивними, то знайдений опорний план оптимальний і единственен;
б) якщо поряд з позитивними оцінками зустрічаються і нульові оцінки, то знайдений опорний план оптимальний, але не единственен;
в) якщо оцінка хоча б однієї вільної клітини негативна, то опорний план не є оптимальним, його можна поліпшити за рахунок завантаження цієї клітини. Якщо таких клітин кілька, то найбільш перспективною для завантаження є клітина з найменшою оцінкою. Наприклад, для клітин маємо оцінки. Тут найбільш потенційної (перспективної для завантаження) є клітина.
Перехід до нехудшему опорному плану (третій пункт алгоритму)
Покращимо план перевезень за рахунок завантаження вільної клітини з негативною оцінкою, для цього для найбільш перспективною вільної клітини будується замкнутий цикл з вершинами в завантажених клітинах. Вершин цього циклу умовно присвоюються знаки: вільної клітці - плюс, наступної, за годинниковою або проти годинникової стрілки, зайнятої клітці - мінус, наступного - знову плюс і т.д. З поставок в клітинах циклу з «негативними» вершинами вибирається найменша кількість вантажу, яке і переміщається по клітинам цього циклу: додається до поставок в «позитивних» вершинах і віднімається з поставок в «негативних» вершинах, в результаті чого баланс циклу не порушиться.
цикл перерахунку
У загальному випадку цикл перерахунку являє собою замкнуту ламану лінію, що складається з ланок, що перетинаються під прямим кутом. Кожна ланка з'єднує дві клітки рядка (стовпчика). Цикл включає одну вільну клітину, інші клітини циклу зайняті. У циклі завжди парне число клітин. Для вільної клітини завжди можна побудувати єдиний цикл.
Якщо з зайнятих клітин утворюється цикл, то план перевезень не є опорним. Цикл будується лише для вільної клітини.
Наприклад, знайдемо оцінки вільних клітин початкового опорного плану, побудованого в останньому прикладі методом мінімального елемента. Використовуючи знайдені вище потенціали рядків і стовпців, розрахуємо оцінки вільних клітин:
Так як оцінка, то знайдений план не оптимальний. Його можна поліпшити шляхом завантаження цієї клітини.
Складемо цикл перерахунку щодо клітини () (див. Таблицю 19).