Метод потенціалів

5.3.1. Критерій оптимальності опорного плану за методом потенціалів

Ми вже знаємо методи знаходження початкових опорних планів транспортної задачі, але чи ці опорні плани є оптимальними, тобто такими, що дають найменшу загальну вартість перевезення всього вантажу від постачальників до споживачів, ми не знаємо. Опорний план перевіряють на оптимальність за допомогою потенціалів. Відповідно до кожного постачальника A_і ставимо потенціал u_і aкожному споживачу .

Критерій оптимальності опорного плану транспортної задачі

якщо для деякого опорного плану (х_іj) транспортної задачі існують такі числа-потенціали u_і та v_j що для базисних клітинок виконуються рівності , а для небазисних клітинок виконуються нерівність для всіх , то такий опорний план є оптимальним.

Потенціали опорного плану визначаються із рівнянь системи , які записують для всіх заповнених клітинок таблиці транспортної задачі. За допомогою розрахованих потенціалів перевіряють умову оптимальності - для незаповнених клітинок таблиці. Якщо хоча б для однієї небазисної клітинки ця умова не виконується, тобто , то поточний план не є оптимальним і потрібно перейти до нового опорного плану.