Теорема. Транспортна задача закритого типу завжди має розв’язання

Транспортна задача закритого типу завжди має розв’язання.

Доказ

план Т.З. є набір , , якийзадовольняє обмеженням (1.3).

За умовою теореми . Покажемо,що , , , є планом Т.З.,тобто задовольняє обмеженням (1.3).

,

,

- задовольняє обмеженням (1.3), значить, це план транспортної задачі.

3.2 Опорні плани транспортних задач

У транспортній задачі число змінних х _ij® m х n, число обмежень m+n

- задача закритого типу.

У силу закритості задачі серед m+n обмежень одне буде виражатися через всі інші,тому що

.

Тому лінійно незалежних обмежень буде m+n-1.

Це означає, що базисних векторів буде m+n-1. Тоді х_ij>0 не може бути більше ніж m+n-1. Опорним планом транспортної задачі називається план задачі , в якому ненегативним змінним х_ij відповідають лінійно незалежні вектори A_ij, що є стовпцями матриці обмежень Т.З.

Якщо в опорному плані транспортної задачі число х_ij> 0 дорівнює m+n-1, то опорний план не выроджений. Якщо число х_ij>0 менше m+n-1,то опорний план выроджений.

Усі обчислення при розв’язанны транспортної задачі роблять в таблицях. Хоча транспортна задача – задача лінійного програмування, для ії розв’язання застосовуються свої спеціальні методи.

Розглянемо ці методи на прикладі. Дані Т.З. та ії план наведені в таблиці 1.

Таблиця 1.

Аi\ Bj	B1	B2	B3	B4	aj
А1	20 2	0 4	0 3	0 1
А2	0 2	15 2	15 7	Х 6
А3	0 3	Х 4	15 2	15 3
bj

=80 - задача закритого типу чи збалансована.

У правому верхньому кутку кожної клітини стоять тарифи перевезень c _ij (вартість) одиниці вантажу з пункту A_i до пункту B_j, від виробника до споживача.

Посередины клітини ставиться кількість перевезеного товару. Клітин вважається заповненой, якщо в ней стоїть кількість перевезеного товару x _ij>0, не заповненою – якщо товар не перевозиться з пункту A_i до пункту B_j.

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

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

х ₁₁=20, х ₂₂=15, х ₂₃=15, х ₃₂=15, х ₃₃=15,усі останні х_ij=0.

Обчислимо сумарну вартість при такому плані перевезень:

(ден.ед.)

Цей план опорний, тому що із заповнених клітинок не можна скласти ланцюг. Він вирождений,тому що кількість заповнених клітинок 5 менше m+n-1 = 3+4-1=6.

Щоб одержати з цього опорного плану невироджений план,необхідно одну незаповнену клітин зайняти нулем. Причому вона не повина скласти ланцюг с заповненими клітинами. Такою клітиною може бути в таблиці кожна клітина, яка зайнята нулем. Хрестиком позначені клітинки, які не можна займати.

3.3 Методи визначення початкових опорних планів

Метод північно- західного кута

Суть методу:

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

х _ij=min(a_i,b_j).

Попередній приклад заповнювався за методом північно-західного кута.

Якщо a_i >b_j,х _ij= b_j, і заповнюється сусідня клітинка по рядку з урахуванням того, що залишок продукту у пункті A_i дорівнює a_i –b_j.

Якщо a_i<b_j,х _ij= a_i, і заповнюється сусідня нижня клітинка по стовпцю з урахуванням того,що потреба продукту в пункті B_j дорівнює b_j - a_i.

Якщо a_i=b_j,х _ij= a_i=b_j, і заповнюється нижня клітинка по діагоналі з урахуванням того, що потреба продукту в пункті B_j+1 дорівнює b_j+1,а виробництво продукту в пункті A_i+1 дорівнює a_i+1.