ня між псевдостоімость і вартостями може бути , яке завгодно. Виявляється співвідношення між псевдостоімость і вартостями у вільних клітинах показує, чи є план оптимальним або ж він може бути поліпшений. Існує спеціальна теорема: Якщо для всіх базисних клітин плану
x ij > 0, a i + b j = і ij = з ij,
а для всіх вільних клітин
ij = 0, a i + b j = і ij ? з ij,
то план є оптимальним і ніякими способами поліпшений бути не може. Неважко показати, що це теорема справедлива також для виродженого плану, і деякі з базисних змінних дорівнюють нулю. План, що володіє властивістю:
Г? і ij = з < span align = "justify"> ij (для всіх базисних клітин) (1)
Г? і ij ? з ij (для всіх вільних клітин) (2)
називається потенційним планом, а відповідні йому платежі (a i і b j ) - потенціалами пунктів A i і B j (i = 1,., m; j = 1,., n).
Користуючись цією термінологією вищезгадану теорему можна сформулювати так: В«всякий потенційний план є оптимальнимВ».
Отже, для вирішення транспортної задачі нам потрібно одне - побудувати потенційний план. Виявляється його можна побудувати методом послідовних наближень, задаючись спочатку якийсь довільній системою платежів, що задовольняє умові (1). При цьому в кожній базисної клітці вийти сума платежів, рівна вартості перевезень у даній клітині; потім, поліпшуючи план, слід одночасно змінювати систему платежів. Так, що вони наближаються до потенціалом. При поліпшенні плану нам допомагає таке властивість платежів і псевдостоімость: яка б не була система платежів (a i і b j ) задовольняє умові (1), для кожної вільної к...
