ij матриці тарифів з набору клітин, в яких розташовані x ij > 0, будемо називати Х -відзначеними.
Якщо ж число позитивних компонент плану N < k + l - l, то до клітин, зайнятим позитивними x ij додаємо відсутні до ( k + l -1) з нульових клітин, аби приєднані клітини разом з уже взятими не допускали циклів. Тарифи a ij всіх узятих клітин, так само як і самі клітини, включаються до числа Х -відзначених.
Більше ( k + l - 1) число компонент ациклического плану не може бути:, так як вже при N = k + l по доведеною вище теоремі завжди з обраних клітин можна побудувати цикл.
Теорема 2 (основна теорема). Якщо для деякого плану Х = (x ij ) k пѓ— l транспортної завдання можна підібрати систему з k + l чисел u 1 , u 2 , ..., u i, ..., u k ; v l , v 2 , ..., v j , ..., v l , що задовольняє таким умовам: v j - u i ВЈ a ij для всіх i = 1, 2,., k ; j = 1, 2,., l , а для x ij > 0 ( X ij (- X )) v j - u i = a ij , то план Х буде оптимальним.
Числа u i , v j називаються потенціалами пунктів відправлення і пунктів призначення; умови v j - u i ВЈ a ij і v j - u i = a ij називають умовами потенційності плану Х .
До кожної клітині ( i , j ) відносяться два потенціалу: i -ro пункту відправлення u i і j -ro пункту призначення v j . Умови потенційності словесно можна сформулювати так: різниця потенціалів для всіх без винятку клітин повинна бути менше або дорівнює тарифом, а для зайнятих ( Х -відмічених) клітин вона повинна бути точно дорівнює тарифом. План, що задовольняє цим умовам, називається потенційним.
З урахуванням такої термінології основну теорему можна викласти коротше: якщо деякий план транспортної задачі потенціалів, то він оптимальний.
Доказ. Припустимо, що для деякого плану Х ( x ij ) умови потенційності виконані, тобто існує така система чисел u i і v j , яка задовольняє умовам v j - u i = a ij і v j - u i ВЈ a ij (табл.8).
В
Іншими словами, нехай план Х потенціалом. Доведемо, що цей план буде оптимальним. План Х дає з...
