Умова існування розв’язку транспортної задачі

Теорема. Для того щоб існував розв’язок ТЗ необхідно і достатньо, щоб вона була збалансованою, тобто, щоб = .

Для розв’язування транспортної задачі застосовують метод потенціалів.

Алгоритм методу потенціалів складається з таких етапів.

1. Визначення типу транспортної задачі (відкрита чи закрита).

2. Побудова першого опорного плану транспортної задачі.

3. Визначення потенціалів плану ТЗ.

4. Перевірка плану ТЗ на оптимальність. Констатація оптимального плану, якщо умова оптимальності виконується. Перехід до наступного опорного плану за умови, якщо план не є оптимальним.

5. Повторення дій, починаючи з п.3.

Розглянемо кожний з етапів.

Етап 1. Якщо під час перевірки умови збалансованості (8.5) виявилося, що транспортна задача є відкритою, то її необхідно звести до закритого типу. Це виконується введенням фіктивного умовного постачальника Аm+1 у випадку перевищення загального попиту над запасами ( ) із запасом . Якщо запаси постачальників перевищують попит споживачів , то до закритого типу задача зводиться введенням фіктивного умовного споживача Вn+1 з потребою .

Вартість перевезення одиниці продукції для фіктивного постачальника Аm+1, або фіктивного споживача Вn+1 вважається рівною нулю.

Етап 2. Для побудови початкового опорного плану ТЗ існує декілька методів: північно-західного кута; мінімальної вартості, подвійної переваги та інші. Побудову опорного плану зручно надавати у вигляді т таблиці, в якій постачальники продукції визначаються рядками, а споживачі – стовпчиками.