Задачі транспортного типу

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

Класична ЗТТ формулюється таким чином. Нехай є m пунктів відправлення продукції: , у яких сконцентровано запаси певного однорідного товару (вантажу) в кількості відповідно одиниць. Крім того, є n пунктів призначення: , які подали замовлення відповідно на одиниць товару. Припустімо, що сума всіх замовлень дорівнює сумі запасів:

(10.1)

Будемо вважати, що задано вартість перевезень одиниці товару від кожного пункту відправлення до кожного пункту призначення . Матрицю (таблицю) перевезень задано у вигляді

Треба скласти такий план перевезень, щоб забезпечити виконання всіх замовлень і щоб сумарна вартість перевезень при цьому була мінімальна (найменша):

(10.2)

де – кількість товару, що перевозиться з пункту в пункт .

Побудуємо математичну модель цієї задачі.

Невід’ємні змінні (кількість яких ) повинні задовольняти такі умови:

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

або

(10.3)

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

або

(10.4)

3. Має виконуватись умова (10.2):

(10.5)

Функція – лінійна, обмеження рівності (10.3), (10.4) також лінійні. Перед нами типова ЗЛП з обмеженнями-рівностями.

Як і будь-яку ЗЛП, її можна було б розв’язати використовуючи симплекс-метод, але внутрішня специфіка задачі (обмеження-рівності, одиничні коефіцієнти в обмеженнях, невід’ємність коефіцієнтів в (10.5)) дозволяє значно спростити її розв’язання.

Неважко переконатися, що не всі n+m рівнянь (10.3), (10.4) незалежні. Дійсно, підсумовуючи всі рівняння (10.3) та (10.4) одержимо одне й теж саме число згідно з умовою (10.1). Отже, умови (10.3), (10.4) зв’язані однією лінійною залежністю, і фактично з цих рівнянь лише n+m-1, не n+m, лінійно незалежні. Це означає, що ранг системи рівнянь (10.3), (10.4) однаковий:

r = n+m-1,

а отже, можна розв’язати ці рівняння відносно n+m-1 базових змінних, виразивши їх через інші, вільні.

Підрахуємо кількість вільних змінних:

k = mn-(m+n-1) = mn – m - (n-1) = (m-1)(n-1).

Із розгляду ЗЛП відомо, що оптимальний розв’язок досягається в одній з вершин області допустимих розв’язків (ОДР), де хоча б k змінних перетворюється на нуль. У нашому випадку для оптимального плану перевезень хоча б (m-1)(n-1) значень повинні бути рівні нулю. Значення кількості одиниць ватажу, який направляється з пункту в пункт будемо називати перевезеннями.

Будь-яку сукупність будемо називати планом перевезень, або просто планом.

План будемо називати допустимим, якщо він задовольняє умови (10.3), (10.4) («балансові умови» – всі замовлення виконані, всі запаси вичерпані).

Допустимий план будемо називати опорним, якщо в ньому відмінні від нуля не більше r = n+m-1 базових перевезень , а всі інші дорівнюють нулю.

План будемо називати оптимальним, якщо він серед усіх допустимих планів приводить до найменшої сумарної вартості перевезень.

Розв’язок ЗТТ можна звести до деякої маніпуляції із симплекс-таблицями, які для цієї задачі будемо називати транспортними таблицями,

ПП ПВ	В1	В2	...	Вn	Запаси ai
А1	c11	c12	...	c1n	a1
А2	c21	c22	…	c2n	a2
…	…	…	…	…	…
Аm	cm1	cm2	…	cmn	am
Замовленняbj	b1	b2	…	bn

де ПП – пункт призначення вантажу; ПВ – пункт відправлення вантажу; усі інші позначення відповідають попереднім. Клітинки таблиці, у яких будемо записувати відмінні від нуля перевезення, називатимемо базовими, а
порожні – вільними.

Отже, розв’язок задачі зводиться до знаходження додатних чисел, які, будучи поставлені в базових клітинках транспортної таблиці, забезпечили б виконання таких умов:

­ сума перевезень у кожному рядку таблиці має дорівнювати запасу даного ПВ;

­ сума перевезень у кожному стовпчику таблиці має дорівнювати розміру замовлення певного ПП;

­ сумарна вартість перевезень – мінімальна.

Надалі всі дії щодо знаходженню розв’язків ЗТТ будуть пов’язані з перетвореннями транспортної табл. (10.6). Для опису цих перетворень скористаємося нумерацією клітинок таблиці, подібної до нумерації клітин шахової дошки. Клітинкою ( ), або , будемо називати клітинку, яка стоїть в i-му рядку і j-му стовпчику транспортної таблиці. Наприклад, верхня ліва клітинка позначатиметься як (1, 1), яка стоїть під нею – (1,2) і т.д.

11. Знаходження опорного плану
задачі транспортного типу

Розв’язок ЗТТ, як і кожної ЗЛП починається із знаходження опорного (допустимого) розв’язку, або, як будемо говорити, опорного плану. На відміну від загального випадку ЗЛП розв’язок ЗТТ завжди існує, оскільки сумарна вартість перевезень – невід’ємна обмежена знизу функція.

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

Приклад.Розглянемо таблицю:

Треба знайти опорний (допустимий) план.

Розв’язування.Перепишемо табл. (11.1) і будемо поступово заповнювати її перевезеннями, починаючи з лівої верхньої клітинки (1,1) (північно-західного кута таблиці).

Міркуємо таким чином. Пункт В₁ подав замовлення на 18 одиниць вантажу. Задовольнимо це замовлення за рахунок запасу 48, який є в пункті А₁, і запишемо перевезення 18 в клітинці (1,1). Після цього замовлення з пункту В₁ виконане, а в пункті А₁ залишилося ще 48-18=30 одиниць продукції. Задовольняємо за їх рахунок замовлення з пункту В₂ (27 одиниць). Запишемо 27 в клітинку (1,2). Три одиниці продукції в пункті А₁ призначимо пункту В₃. У складі замовлення В₃ залишилися незабезпеченими 39 одиниць. З них 30 покриємо за рахунок пункту А₂, чим його запас буде вичерпано, а ще 9 візьмемо з пункту А₃. Із 18 одиниць пункту відправлення А₃ 12 виділимо на пункт В₄; 6 одиниць, що лишилися, призначимо пункту В₅ і разом з 20 одиницями пункту А₄ повністю покриємо його замовлення. Одержимо:

Як видно з табл. (11.2) розподіл запасів закінчено: кожен пункт призначення одержав вантаж згідно зі своїм замовленням. Це випливає з того, що сума перевезень у кожному рядку дорівнює відповідному запасу, а у стовпчику – замовленню.

Таким чином, складено план перевезень, що задовольняє балансові рівняння вигляду (10.3), (10.4). Одержаний розв’язок не тільки допустимим, а й опорний розв’язок ЗТТ.

Клітинки таблиці (11.2), в яких стоять ненульові перевезення – базові, їх кількість задовольняє умову r= n+m-1=8. Інші клітинки – вільні (порожні), їх кількість (m-1)(n-1)=12. Отже, план опорний і поставлене завдання побудови опорного плану виконане. Виникає запитання: а чи оптимальний за сумарною вартістю перевезень план отримано? Звичайно, ні. Адже під час побудови опорного плану зовсім не враховувалась вартість локальних перевезень . Природно, що цей план не зобов’язаний бути оптимальним. Дійсно, сумарна вартість цього плану складає:

.

Не важко переконатися, що коли перенесемо 18 одиниць з клітини (1,1) в клітину (2,1), а потім 18 одиниць з клітини (2,3) в (1,3), одержимо сумарну вартість перевезень:

Балансові співвідношення при цьому не були порушені. Отже, попередній план перевезень не був оптимальним.

12. Поліпшення плану перевезень

Візьмемо транспортну таблицю, яка складається із 5 рядків та 6 стовпчиків (кількість рядків і стовпчиків не суттєва).

ПП ПВ	В1	В2	В3	В4	В5	В6	Запаси ai
А1	c11	c12	с13	c14 +	с15	с16 –	a1
А2	c21 +	c22	с23 –	c24	с25	с26	a2
А3	с31	с32	с33	с34 +	с35 –	с36	а3
А4	с41 –	с42	с43 +	с44 –	с45	с46 +	а4
А5	с51	с52	с53	c54 –	с55 +	с56	а5
Замовлення bj	b1	b2	b3	b4	b5	b6

Циклом у транспортній таблиці будемо називати декілька клітинок, з’єднаних замкнутою ламаною лінією, яка в кожній з цих клітинок здійснює поворот на 90⁰. Наприклад, у табл.(12.1) зображено два цикли: перший з чотирма вершинами (2,1), (2,3), (4,3), (4,1) і другий з вісьмома вершинами (1,4), (1,6), (4,6), (4,4), (3,4), (3,5), (5,5), (5,4). Стрілками вказано напрямок проходження циклу. Не важко переконатися, що кожен цикл має парну кількість вершин, а отже, і парну кількість стрілок.

Домовимося відмічати знаком «+» ті вершини циклу, перевезення в яких збільшуються, а знаком «–» – вершини, в яких вони зменшуються. Цикл з вершинами, відміченими знаками «+» або «–», будемо називати орієнтованим. Знаки «+» та «–» у циклі будемо розставляти почергово, це означає, що у вершини зі знаком «+» дві сусідні мають знаки «–» і навпаки.

Перенести якусь кількість одиниць вантажу орієнтованим циклом означає збільшити перевезення у вершинах зі знаком «+», і зменшити перевезення на ту саму кількість вантажу у вершинах зі знаком «–».

Очевидно, що з перенесенням будь-якої кількості одиниць вантажу по циклу рівновага між запасами і замовленнями зберігається: сума перевезень у кожному рядку дорівнює запасам цього рядка, а сума перевезень у кожному стовпчику дорівнює замовленню по цьому стовпчику. Отже, за будь-якого циклічного перенесення, що залишає перевезення невід’ємними, допустимий (опорний) план залишається допустимим (опорним). Сумарна вартість усього плану перевезень може змінюватися – збільшуватися або зменшуватися.

Назвемо ціною циклу збільшення вартості перевезень із переміщенням одиниці вантажу означеним циклом. Очевидно, ціна циклу дорівнює алгебраїчній сумі вартостей, що стоять у вершинах циклу. Вартості, що стоять у вершинах циклу зі знаком «+» беруться із знаком «+», а ті, що стоять у вершинах із знаком «–», беруться зі знаком «–».

Наприклад, для циклів зображених в табл. (12.1), ціна циклів відповідно дорівнює:

с₂₁ – с_{2 3}+ с₄₃ – с₄₁ і с₁₄ – с₁₆ + с₄₆ – с₄₄ + с₃₄ – с₃₅ + с₅₅ – с₅₄.

Позначимо ціну циклу через r. Із переміщенням одиниці вантажу по циклу вартість перевезення збільшиться на величину r; із переміщенням по ньому k одиниць вантажу вартість перевезень збільшиться на kr. Звідси випливає: щоб поліпшити план перевезень, треба здійснювати перевезення тими циклами, ціна яких від’ємна. Якщо кожного разу вдасться здійснити таке переміщення, то вартість плану зменшиться на величину kr.

Оскільки перевезення не можуть бути від’ємними, будемо користуватися лише тими циклами, «від’ємні» вершини яких лежать у базових клітинках таблиці. Якщо циклів з від’ємними числом r у таблиці не залишилося, це означає, що подальше поліпшення плану не можливе, тобто задачі (10.3), (10.4), (10.5) розв’язані.

Відшукати цикли з від’ємними вартостями можна використовуючи метод потенціалів.

Будемо вважати, що кожен із пунктів відправлення А_і вносить на перевезення одиниці вантажу (все одно куди) якусь суму , у свою чергу кожен із пунктів призначення також вносить за перевезення одиниці вантажу суму . Ці суми передаються третій особі («перевізнику»). Позначимо

будемо називати псевдовартістю перевезення одиниці вантажу із пункту в пункт . Помітимо, що платежі , не обов’язково мають бути додатними: не виключено, що «перевізник» сам платить тому чи іншому пункту якусь премію за перевезення.

Позначимо всю сукупність платежів , через . Не уточнюючи, у який спосіб вони призначаються сформулюємо «теорему про платежі».

Теорема 1.Для заданої сукупності платежів сумарна псевдовартість перевезень

за будь-якого допустимого плану перевезень ( ) зберігає одне й те саме значення:

У цій формулі величина С залежить лише від сукупності платежів і не залежить від того, який допустимим планом ( ) використовується.

Доведемо це твердження. Маємо

Перетворимо першу з двох останніх сум

відповідно до рівностей (10.3).

Аналогічно

в силу рівностей (10.4).

Таким чином,

Останній вираз для від ( ) не залежить для будь-якого допустимого плану. Теорему 1 доведено.

Спробуємо встановити зв’язок між вартостями та псевдовартостями. Припустимо, що план ( ) допустимий і не вироджений (кількість базових клітинок у таблиці дорівнює n+m-1). Для всіх цих клітинок . Визначимо платежі так, щоб в усіх базових клітинках псевдовартості дорівнювали вартостям:

при .

Для довільних клітин ( ) співвідношення між та може бути будь-яким:

або при .

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

Теорема 2.Якщо в усіх базових клітинках ( )

(12.2)

а для всіх вільних клітинок ( )

(12.3)

то план перевезень оптимальний і ніяким способом не може бути здешевлений.

Доведення. Позначимо через – план перевезень із системою платежів , що задовольняє умови теореми 2. Визначимо його сумарну вартість: (12.4)

У сумі (12.4) відмінні від нуля лише доданки, які відповідають базовим клітинкам, але в них вартості дорівнюють псевдовартостям (згідно з (12.2)). Тому

Згідно з теоремою 1 . Тепер замінимо план ( ) іншим планом ( ). Новий план має сумарну вартість :

(12.5)

де – нові кількості перевезень, відмінні від нуля, в інших клітинах. Деякі з них збігаються з попередніми клітинками попереднього плану, а інші – з вільними. У першому випадку вартості співпадають з , а в іншому

згідно (12.3). Тому сума (12.5)

Звідси випливає, що в умовах теореми 2 ніякими змінами плану перевезень ( ) його вартість змінити не можна. Це означає, що план перевезень, який задовольняє умови теореми 2 – оптимальний. Теорему доведено.

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

Таким чином, доведено, що ознакою оптимальності плану ( ) є виконання умов:

для всіх базових клітинок; для всіх вільних клітинок.

(12.6)

План, для якого виконуються ці умови називається потенціальним, а відповідні платежі – потенціалами пунктів . Теорему 2 можна переформулювати так: будь-який потенціальний план оптимальний.

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

Для поліпшення плану перевезень використаємо властивість платежів і псевдовартостей: яка б не була система платежів , що задовольняє першу з умов (12.6), для кожної вільної клітинки вартість циклу перерахунку дорівнює:

(12.7)

Приклад. Розглянемо таблицю:

ПП ПВ	В1	В2	В3	В4	В5	В6
А1	c11	c12 –	с13	c14	с15 +	с16
А2	c21	c22 +	с23 –	c24	с25	с26
А3	с31	с32	с33 +	с34	с35 –	с36
А4	с41	с42	с43	с44	с45	с46
А5	с51	с52	с53	с54	с55	с56

Не будемо проставляти в табл. (12.8) ні запаси ні замовлення, ні перевезення (вони нам не потрібні), просто помітимо (обведемо жирною лінією) базові клітинки.

Візьмемо будь-яку вільну клітинку, наприклад (1,5), і побудуємо її цикл перерахунку, додатна вершина якого лежить у вільній клітинці, а всі інші – в базових. Визначимо вартість циклу:

Відповідно до умов (12.6) для всіх базових клітинок вартість дорівнює псевдовартостям, тому

Очевидно, що ця властивість справедлива для будь-якої довільної клітинки. Крім того, вона спрощує пошук циклів з від’ємною вартістю.

Процедура побудови потенціального плану така: як перше наближення до оптимального плану береться будь-який допустимий план. Платежі можна визначити так, щоб виконувалась умова

(12.9)

Рівнянь у (12.9) m+n-1, а кількість невідомих m+n, отже, одну з невідомих можна взяти довільною (наприклад, нульовою), а інші визначимо із системи: для всіх вільних клітин. Якщо виконується умова то ЗТТ розв’язана, оскільки план перевезень оптимальний. Якщо ж хоча б в одній вільній клітинці псевдовартість більша за вартість:

(12.10)

то план перевезень не оптимальний і може бути поліпшений перенесенням перевезень по циклу, який відповідає вільній клітинці. Вартість циклу встановлюється за формулою (12.7).

Алгоритм розв’язання ЗТТ методом потенціалів (на підставі теореми 2) такий:

1. Беремо будь-який опорний план перевезень, у якому відмічено m+n-1 базових клітинок (інші клітинки – вільні).

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

один з платежів можна призначити довільно, наприклад, покласти рівним нулю.

3. Перераховуємо псевдовартість для всіх вільних клітинок. Якщо всі вони не перевищують вартостей, то план перевезень оптимальний.

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

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

Приклад. Розв’язати ЗТТ методом потенціалів, якщо опорний план побудовано за допомогою методу північно-західного кута.

ПП ПВ	В1	В2	В3	В4	В5	Запасиai	Платежіαі
А1	10 10 – 17	8 8 + 8	6 9	5 6	4 5
А2	8 5 +	6 6 – 13	4 4	3 3	2 8		-2
А3	9 9	7 7	5 5	4 4 14	3 3		-1
А4	6 14	4 10	2 8	1 8	8 8
Замов-лення bj
Платежі βj

У табл. (12.11) з’явився один стовпчик для платежів α_і та один рядок для платежів β_j.

Псевдовартості будемо записувати в лівій частині кожної клітинки, а вартості – у правій. Один з платежів, наприклад, α_і покладемо рівним нулю ( ). Для кожної базової клітинки покладемо . Випишемо клітинки, де виконується ця рівність:

Отримаємо вісім рівнянь і дев’ять невідомих, тому маємо право одну з невідомих покласти рівною нулю ( ):

(12.12)

Оскільки не всі псевдовартості у вільних клітинках табл. (12.11) задовольняють умову (12.6), план наведений в таблиці не оптимальний. Спробуємо його поліпшити, переводячи в базову одну з вільних клітинок, для якої , наприклад, клітинку (2,1). Будуємо відповідний цій клітинці цикл (див. табл. (12.11)). Вартість циклу 5 – 8 = –3. Перенесемо по ньому 13 одиниць вантажу(найменше число, що стоїть у вершинах циклу з від’ємними вершинами). Сумарна вартість перевезень зменшилася на .

Знову повторимо перетворення в таблиці, перерахувавши псевдовартості після заміни в (12.12) рівняння на , перерозв’язавши систему рівнянь.

Послідовне перетворення табл. (12.11) в (12.13), (12.4), (12.15). Табл. (12.15) містить оптимальні розміри перевезень оптимальними маршрутами. ПП   ПВ	В1	В2	В3	В4	В5	Запасиai	Платежіαі
А1	10 10 4 –	8 8	9 9	8 6 +	7 5
А2	5 5 +	3 6	4 4 19 –	3 3	2 8		-5
А3	6 9	4 7	5 5 +	4 4 –	3 3		-4
А4	11 14	9 10	10 8	9 8	8 8
Замов-лення bj
Платежі βj

ПП   ПВ	В1	В2	В3	В4	В5	Запаси ai	Платежі αі
А1	8 10	8 8	7 9	6 6	5 5
А2	5 5	5 6	4 4	3 3	2 8		-3
А3	6 9	6 7	5 5 26 –	4 4	3 3 + 4		-2
А4	11 14	11 10	10 8 +	9 8	8 8 – 20
Замов-лення bj
Платежіβj

Відповідь:

Поняттям «платежі» та «псевдовартості» можна дати наочну економічну інтерпретацію.

Будемо вважати, що – реальні платежі, які пункти та платять за перевезення одиниці вантажу третій особі «перевізнику». Будемо також вважати, що інтереси А і В не антагоністичні. Нехай вони діють як єдина економічна система. Перевезення одиниці вантажу з пункту в пункт об’єктивно дорівнює , а сторони А та В разом платять за це перевезення «перевізнику» суму . Оптимальним буде такий план перевезень, за якого пункти та не платять «перевізнику» понад об’єктивну вартість перевезень. Тобто такий план, будь-яке відхилення від якого не буде вигідне системі АВ, оскільки примусить платити за перевезення більше, ніж якби пункти самі перевозили вантаж.

Розв’яжемо методом потенціалів ЗТТ у виродженому випадку.

Приклад.Розв’язати ЗТТ, транспортна таблиця якої має вигляд (12.16). Будемо вважати, що опорний план методом північно-західного кута побудували.

Для розв’язання цієї виродженої ЗТТ використовуємо такий прийом. Будемо вважати, що в пункті А₁ знаходиться не 20 одиниць вантажу, а трохи більше: 20+ε (ε – мала кількість). У пункті А₂ не 25 одиниць вантажу, а 25+ε; у пункті А₃: 30-2ε.

Після застосування методу північно-західного кута до нової таблиці, отримаємо табл. (12.17).

ПП ПВ	В1	В2	В3	Запаси ai	Платежі αі
А1	6 6 20 –	4 4 + ε	3 2	20+ ε
А2	7 3	5 – 5 25- ε	4 4 + 2ε	25+ ε
А3	6 3 +	4 6	3 – 3 30-2ε	30-2ε
Замов-лення bj
Платежі βj

Далі, використовуючи метод потенціалів, одержуємо послідовно табл. (12.18)-(12.20).

ПП   ПВ	В1	В2	В3	Запаси ai	Платежі αі
А1	3 6	4 4 20+ε –	3 2 +	20+ ε
А2	4 3	5 5 5–ε +	4 – 4 20+2ε	25+ ε
А3	3 3	4 6	3 3 10-2ε	30-2ε
Замовлення bj
Платежі βj

ПП   ПВ	В1	В2	В3	Запаси ai	Платежі αі
А1	2 6	3 4	2 2 20+ ε	20+ ε
А2	4 3 –	5 5	4 4 + ε	25+ ε
А3	3 3 20 +	4 6	3 – 3 10-2ε	30-2ε
Замовлення bj
Платежі βj

Після побудови потенціального плану в табл. (12.20) покладемо ε =0.

Відповідь: