2 Основні теореми транспортної задачі.

Означення 1. Якщо у транспортної задачі виконується умова балансу

∑b_j = ∑a_i (5)

То задача називається закритою або збалансованою.

Означення 2. Планом транспортної задачі називається сукупність величин x_ji (i=1,2…..m; j=1,2…..n), який задовольняє умови обмеження (2) – (4).

Означення 3. Опорний план транспортної задачі називається не виродженим, якщо він містить N=m+n-1 додатних елементів x_ji

Означення 4. Якщо опорний план містить менше N<m+n-1 додатних елементів, то він називається виродженим.

Означення 5. Оптимальним планом транспортної задачі називають матрицю Х^* , яка задовольняє умови задачі (2) – (4) і для якої цільова функція F набуває мінімального значення.

Теорема 1. (Необхідна і достатня умова існування розв’язку задачі ТЗ).

Транспортна задача має розв’язок тоді і тільки тоді, коли вона збалансована, тобто виконується умова (5).

Теорема 2. Для того щоб деякий план Х транспортної задачі був оптимальним необхідно і достатньо, щоб йому відповідала така система із m+n чисел u_i (i=1,2…..m) v_j ( j=1,2…..n) для якої виконуються умови

v_j - u_i = с_ji для x_ji>0

v_j - u_i ≤ с_ji для x_ji=0.

Означення 6. Числа v_j та u_i називаються потенціалами строк та стовпців.