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 називаються потенціалами строк та стовпців.

3. Метод північно-західного кута (діагональний.)

Побудова опорного плану задачі починають із заповнення верхньої клітинки таблиці x₁₁ , в яку записують менше з двох чисел a₁ та b₁.

Далі переходять до наступної клітинки в рядку або стовпчику і заповнюють ії і т.д. Закінчують заповнювати таблицю у правій нижній клітинці.

Зауважемо, що користуючись методом північно-західного кута початковий опорний план залежить від величин a_i та b_j і зовсім не залежить від вартостей перевезення с_ji, а тому він буде далекий від оптимального.

4. Метод найменшої вартості.

Сутність цього методу полягає у тому, що на кожному кроці заповнюють клітинки таблиці, яка має найменшу вартість перевезеня одиниці продукції між постачальниками та споживачами.

5. Метод потенціалів.

Після перевірки транспортної задачі на сбалансованість та визначення початкового плану транспортної задачі приступаємо до розрахунку потенціалів строк і стовпців для заповнених кліток:

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

Оскільки заповнених клітинок є m+n-1, то система рівнянь (6) із m+n невідомих містить m+n-1 рівнянь. Прийнявши одне невідоме за нуль, наприклад, u₁=0, решту знаходимо.

Для побудованого опрного плану і знайдених потенціалів обчислюємо оцінки вільних клітинок:

Δ_ji =v_j - u_i - с_ji

Якщо, Δ_ji ≤0, то побудований опрний план є оптимальним.

Якщо, хоча б для однієї клітинки ця умова не виконується, то опорний план не є оптимальним і треба від нього переходити до нового опорного плану.

Перехід від одного опорного плану до іншого здійснюється заповненням клітинки, для якої порушено умови оптимальності. Якщо таких клітинрк кілька, то для заповнення вибіраютьтаку, що має найбільшє порушенняі з неї будують цикл перерозподілу.

Означення 7. Циклом у транспортної задачі називають замкнену ламану лінію, вершини якої розміщуються в заповнених клітинках таблиці, а сторонни проходять уздовж рядків і стовпчиків таблиці.

Для вибраної вільної клітинки і клітинок, що пов’язані з нею циклом, здійснюють перерозподіл продукції в межах цього циклу за такими правилами:

• Кожній вершині циклу приписують певний знак, причому вільній клітинці – знак «+», а всім іншим по черзі- знаки «-» та «+»;

• У поржню клітинку переносять менше з чисел x_ji , що стоять у клітинках зі знком «-». Одночасно це число додають до відповідних чисел, які розміщені в клітинках зі знаком «+».

Приклад. Розв’язати транспортну задачу.

	27		53		21		42		30		ui
65		3		1		3		4		2
68		2		3		1		2		3
40		3		5		2		2		4
vj