27. Постановка транспортної задачі.

Представляє собою ЗЛП. Це означає, що її можна досліджувати і розв’язувати, використовуючи теорію ЛП. Використовуючи специфіку ТЗ, для неї існують свої методи розв’язання, які є більш прості, ніж загальні.

Економічна постановка.

Деякий однорідний продукт перевозиться з m пунктів постачання з обсягами a_i, і=1, m в n пунктів споживання з потребами b_ij, j=1,n.

Із всіх пунктів постачання у всі пункти споживання представлені у вигляді матриці перевезення.

Необхідно знайти такий оптимальний план перевезень, щоб загальна вартість всіх перевезень була мінімальною.

Математична постановка.

Позначимо через x_ij – кількість однорідної продукції, яка перевозиться із і-го пункту постачання в b_j - пункт споживання.

Умову ТЗ зручно задавати у вигляді симплекс-таблиці для ТЗ.

Функція мети, яка економічно означає, що сумарна вартість перевезень повинна бути мінімальною, математично можна записати наступним чином:

Z = c₁₁x₁₁ + c₁₂x₁₂ + … + c_1nx_1n +

+ c₂₁x₂₁ + c₂₂x₂₂ + … + c_2nx_2n + (1)

+ c_m1x_m1 + c_m2x_m2 … + c_mnx_mn  min

Так, як вся продукція повинна бути вивезена із пункту постачання, то математично це можна записати наступним чином:

x₁₁ + x₁₂ + … + x_1n = a₁

x₂₁ + x22 + … + x2n = a₂ (2)

x_m1+ x_m2 + … + x_mn = a_m

Всі потреби пунктів споживання повинні бути виконані, то це можна записати наступним чином:

x₁₁ + x₁₂ + … + x_1n = b₁

x₂₁ + x22 + … + x2n = b₂ (3)

x_m1+ x_m2 + … + x_mn = b_m

(1)-(4) – математична постановка ТЗ.

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

Математична модель транспортної задачі має такий вигляд:

за обмежень

де x_ij – кількість продукції, що перевозиться від і-го постачальника до j-го споживача;

c_ij – вартість перевезення одиниці продукції від і-го постачальника до j-го споживача;

a_i – запаси продукції i-го постачальника; b_j – попит на продукцію j-го споживача.

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

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