овуючи (1.1) за, а (1.2) за, отримаємо:
. я
Звідси, що і доводить необхідність умови балансу Т-завдання.
Нехай справедливо умова (1.6). Позначимо, де. p> Неважко довести, що х ij складає план завдання. Дійсно
В
Таким чином, доведена достатність умови балансу для рішення Т-задачі.
2. Ранг системи обмежень (1.1), (1.2) дорівнює
Доказ. Оскільки кількість рівнянь (1.1), (1.2) одно, то ранг цієї системи. Нехай, набір задовольняє всім рівнянням, крім перших. Покажемо, що він задовольняє також і першому рівнянню.
Очевидно
В
Так як
, то
, звідси
,
Враховуючи умову балансу (1.6), отримаємо
,
тобто перше рівняння системи (1.1) теж задовольняється.
Таким чином, ранг системи рівнянь (1.1), (1.2).
Доведемо, що ранг системи рівнянь (1.1), (1.2) дорівнює точно. Для цього складемо матрицю з перших () компонентів векторів
В В
Очевидно, що ця матриця не вироджена. Тому вектори {} утворюють базис. Так як базис системи складається з () векторів, то й ранг системи (1.1), (1.2).
Двоїста транспортна задача (- завдання). Для Т-задачі, як і для будь-якої задачі ЛП, існує двоїста задача до неї-завдання.
Змінні-завдання позначимо v 1 , v 2 ., v n , - u 1 , - u 2 ., - u m ...
Теорема 1. -задача має рішення і якщо X опт =, p> - оптимальні рішення T і-завдання відповідно, то
. (1.7)
Якщо врахувати, що u i - вартість одиниці продукції у пункті А І, а v j - вартість після перевезення в пункт B j , то сенс теореми буде такою:
Сумарні транспортні витрати при оптимальному плані перевезень дорівнюють приросту сумарної вартості продукції після її перевезення до пункти споживання.
Змінні u i і v j називають потенціалами пунктів A i і B j для Т-завдання. p> Таким чином, теорема 1. стверджує, що за оптимальних рішеннях значення цільової функції прямої та двоїстої Т-задач рівні між собою.
Справедливість теореми 1. випливає з основної теореми двоїстої ЛП (теорема 2.5).
Сформулюємо необхідні і достатні умови оптимальності плану Т-завдання.
Теорема 2. Для оптимальності плану Х 0 Т-задачі необхідно і достатньо існування таких чисел v 1 , v 2 ., v n , - u 1 , - u 2 ., - u m , що
v j - u i c ij , i = 1., m; j = 1., n ... (1.8)
При цьому, якщо
це v j - u i = c ij . br/>
Cправедлівость цієї теореми випливає із загальних ідей теорії подвійності лінійного програмування (зокрема, теореми 2.5, 2.7).
Дамо економічну інтерпретацію умов теореми 2.
Різниця між потенціалами пунктів B j і A i , тобто величину v j - u i , можна розглядати як прирощення цінності одиниці продукції при перевезенні з пункту A i у пункт B j . Тому, якщо v j - u i ij , то перевезення по комунікації A i B j нерентабельна, і. Якщо v j - u i = c ij , то таке перевезення рентабельна, і (див. Теорему 2.7). p> Транспортна задача з обмеженими пропускними здібностями.
Важливою у практичному відношенні є Т d - завдання, в якою існують обмеження на пропускні здатності комунікацій.
Нехай - пропускна здатність комунікації A i B j .
Тоді (1.9)
Т-завдання полягає в мінімізації Ц.Ф. (1.3) за умов (1.1), (1.2), (1.9). Навіть у випадку розв'язання Т-задачі, Т d - завдання може виявитися нерозв'язною, оскільки величини пропускних здібностей будуть недостатні для повного вивезення продукту з п. А и , і повного ввезення продукту в п. У j . Тому для Т d - завдання вводять ще два условия:
(1.10)
(1.11)
Але і при додаткових умов (1.10), (1.11) Т d - завдання не завжди можна вирішити. Для встановлення сумісності всіх умов роблять спробу побудувати будь-який план Т-завдання. Якщо вдається, то система рівнянь (1.1), (1.2), (1.9) - (1.11) совместна. В іншому випадку Т d - завдання нерозв'язна.
Теорема 3. Для оптимальності плану Х 0 Т d - Завдання необхідно і достатньо існування таких чисел v 1 , v 2 ...
