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

Теорема.

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

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

Транспортна задача є задачею лінійного програмування, яку можна розв'язати симплекс-методом. Але специфічна структура транспортної задачі дає змогу використовувати для її розв'язування ефективніший метод, який повторює, по суті, кроки симплекс-алгоритму. Таким є метод потенціалів.

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

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

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

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

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

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

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

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

6.3.2. Методи побудови опорного плану тз

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

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

Таблиця заповнюється починаючи з лівого верхнього кута (північно-західного кута), рухаючись далі по стрічці вправо, або по стовпчику вниз. У клітинку (1.1) заноситься менше з чисел а₁ і b₁, тобто х₁₁ =min(а₁,b₁).

Якщо а₁ >= b₁, то х₁₁= b₁ і перший стовпчик закритий для заповнення інших його клітинок, тобто х_ij. =0 для і = 2,3,...m (потреби першого споживача задоволені повністю). Далі рухаються по першій стрічці в клітинку (1.2). У ній записується менше з а₁–b₁ i b₂, тобто х₁₂ = min(а₁–b₁,b₂).

Якщо а₁<b₁, то аналогічно закривається перша стрічка, тобто х_ij. =0 для j = 2,3,...n . Далі заповнюється клітинка (2.1), в яку заноситься х₂₁ =min(а₂, b₁–a₁).

Заповнивши клітинку (1.2), або (2.1), переходять до заповнення третьої клітинки або по другій стрічці, або по другому стовпчику. Цей процес продовжують до повного вичерпування продукції у пунктах, або повного задоволення потреб споживачів. Остання заповнена клітинка (min) виявиться в останній m-тій стрічці та n-му стовпчику.

План, отриманий методом північно-західного кута, буде опорним планом системи обмежень транспортної задачі.