Тема 5. Транспортна задача

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

Специфіка математичних моделей цих задач дала можливість розробити простіший метод розв’язування, ніж універсальний симплексній метод.

У процесі викладення матеріалу значною мірою спиратимемося на приведені раніше властивості задач лінійного програмування.

2.5.1. Постановка й математична модель транспортної задачі

Розглянемо традиційну постановку одноетапної задачі планування перевезень - транспортної задачі (ТЗ).

У деяких пунктах А₁, А₂, ..., а_і, ..., А_т, що називаються постачальниками, зосереджено товар у кількості відповідно а₁, а₂, ..., а_і, ..., а_т. Пункти В₁, В₂, ..., B_i, …, В_n, що називаються споживачами, мають потребу в цьому товарі в кількості відповідно b₁, b₂, ..., b_i, …, b_n. Числа a_i називатимемо потужностями (пропозиціями) постачальників, a b_j – попитами споживачів. Між пунктами A_i і B_j існують комунікації та відомо затрати на перевезення товарів від A_i до B_j. Треба скласти план перевезень, який забезпечує мінімум транспортних витрат.

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

1. Товар є однорідним і подільним, тобто споживачеві байдуже, з якого саме джерела він отримує товар, і перевезення можуть здійснюватися партіями будь-якого, розміру.

2. Вартість перевезень пропорційна обсягу товару, що перевозиться, тобто задано матрицю тарифів С = ||с_ij|| розмірності m ´ n, де с_ij – вартість перевезення одиниці товару від A_i до B_j.

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

Означення 2.13. ТЗ називається закритою, якщо сумарний попит дорівнює сумарній пропозиції:

= . (2.80)

У противному разі ТЗ називається відкритою.

Економічна постановка та математична модель закритої транспортної задачі

Скласти план перевезень, за якого вивозиться весь товар від постачальників, попит усіх споживачів задовольняється й транспортні витрати мінімальні.

Щоб скласти математичну модель, уведемо матрицю змінних Х = ||х_ij||, де х_ij - запланований обсяг перевезень від A_i до B_j. Очевидно, що розмірність цієї матриці m ´ n і матриця визначає шуканий план перевезень.

Знайдемо вираз кількості товарів, щo вивозиться від A_i. Першому споживачеві заплановано поставку х_і1, другому – х_і2 і т.д., п-му – х_1п. Сума цих величин х_і1 + х_і2 + ... + х_1п, або в скороченому запису визначає запланований вивіз товару від A_i. За умовою задачі весь товар треба вивезти, отже, має виконуватися умова

. (2.81)

Аналогічно запланована кількість товару, що надходить до B_j, складається з поставок від А₁ – х_1j, від А₂ – х_2j, від А_m – х_mj. Сума х_1j + х_2j + ...+ х_mj = – це кількість товару, що направляється до B_j. Оскільки всіх споживачів треба задовольнити, отримуємо таку систему обмежень:

. (2.82)

Розглянемо можливий знак невідoмих x_ij. Величина x_ij> 0 означає, що планується перевезення від А_і до B_j, якщо x_ij = 0, перевезення не планується. Випадку x_ij < 0 відповідає перевезення від B_j до А_і, що суперечить умові задачі. Отже,

x_ij ³ 0 . (2.83)

Найдемо математичний вираз цільової функції задачі – сумарної вартості перевезень. Тариф перевезень, тобто вартість перевезення одиниці товару за маршрутом А_іB_j становить с_ij. Якщо за цим маршрутом перевозиться x_ij одиниць товару, то затрати становитимуть с_ijx_ij. Вираз відображує вартість перевезень від А_і до всіх B_j. Підсумовуючи його за j, дістаємо вартість перевезень . Згідно з умовою задачі треба знайти план, який забезпечує мінімум транспортних витрат, отже, цільова функція задачі має вигляд

. (2.84)

Обмеження (2.81)-(2.82), умова невід’ємності (2.83) і цільова функція (2.84) є математичною моделлю закритої ТЗ. Оскільки основні обмеження (2.81) і (2.82) складаються з т + п рівнянь, то задача (2.81)-(2.84) є ЗЛП, заданою в канонічній формі.