Умова оптимальності опорного плану ТЗ
Матеріал з Вікі ЦДУ
Версія від 18:15, 10 травня 2012; Ghaiklor (обговорення • внесок)
Умова оптимальності опорного плану транспортної задачі
Опорний план перевіряють на оптимальність за допомогою потенціалів Неможливо розібрати вираз (невідома помилка): u_i
та Неможливо розібрати вираз (невідома помилка): v_j відповідно постачальників та споживачів.
Якщо для деякого опорного плану Неможливо розібрати вираз (невідома помилка): X^* = (x_{ij}^*)
існують числа Неможливо розібрати вираз (невідома помилка): u_i та Неможливо розібрати вираз (невідома помилка): v_j
, для яких виконується умова:
Неможливо розібрати вираз (невідома помилка): u_i + v_j = c_{ij}, x_{ij} > 0,
Неможливо розібрати вираз (невідома помилка): u_i + v_j \leq c_{ij}, x_{ij} = 0
для всіх Неможливо розібрати вираз (невідома помилка): i = \bar{1,m}
та Неможливо розібрати вираз (невідома помилка): j = \bar{1,n}
, то він є оптимальним планом транспортної задачі.
Потенціали опорного плану визначаються із системи рівнянь Неможливо розібрати вираз (невідома помилка): u_i + v_j = c_{ij} , які записують для всіх заповнених клітинок транспортної таблиці.
Приклад перевірки транспортної задачі на оптимальний план
Нехай дана транспортна таблиця:
