КОМБІНАТОРНИЙ РОЗВ’ЯЗОК ТРАНСПОРТНОЇ ЗАДАЧІ

Шарапов М.М.

В цій нотатці йдеться про комбінаторний розв’язок транспортної задачі як альтернативу іншим відомим методам (в першу чергу методу потенціалів) та суттєві переваги комбінаторного розв’язку.

В найпростішому варіанті транспортна задача формулюється наступним чином: є n постачальників із запасами однорідного штучного товару a1,a2,…,an та m споживачів із потребами цього товару b1,b2,…,bm. Не порушуючи загальності, можна вважати транспортну задачу закритою, тобто, що сума всіх запасів дорівнює сумі всіх потреб, в противному разі задача є відкритою і простими відомими методами (введенням фіктивного постачальника чи фіктивного споживача) зводиться до закритої. Нехай матриця С розмірності m ´ n є матрицею цін перевезень, тобто кожен її елемент cij є ціною за перевезення одиниці продукції від i–го постачальника j–му споживачу, а матриця Х такої ж розмірності є планом перевезень, тобто кожне х ij є цілим невід’ємним числом, що дорівнює кількості товару, що перевозиться від i–го постачальника j–му споживачу. Метою розв’язку транспортної задачі є пошук такого плану перевезень Х, при якому загальна вартість перевезень

була б найменшою з можливих за умови, що весь товар від постачальників перевозиться до споживачів. Транспортна задача є задачею цілочислового лінійного програмування. З основами лінійного програмування можна ознайомитись, наприклад в [1], з науковим обґрунтуванням алгоритмів розв’язку задач лінійного програмування, зокрема транспортної задачі, можна ознайомитись в [2], а з науково-популярним викладенням самого алгоритму розв’язку транспортної та інших оптимізацій них задач – в [3]. Відзначимо лише, що по-перше, жоден з відомих алгоритмів не є досконалим, а по-друге, зажди пропонується шукати один оптимальний план перевезень, а решта оптимальних планів залишається або без уваги, або в кращому випадку залишається на розгляд методами післяоптимізаційного аналізу. Досі було важко запропонувати достойну альтернативу цим методам через відсутність потужної обчислювальної техніки, але тепер це можливо.

Суть комбінаторного методу розглянемо для простоти на конкретному прикладі, але наведені міркування можна легко застосувати для розв’язку довільної транспортної задачі, навіть з додатковими обмеженнями на плани перевезень. Нехай запаси трьох постачальників складають (50, 40, 20), а потреби чотирьох споживачів складають (30, 25, 35, 20). Значення цін перевезень нас поки що не цікавлять. Наша мета – перебрати всі можливі плани перевезень, відібравши ті, на яких досягається мінімум загальної вартості. Скільки ж є таких можливих планів? Застосуємо основне правило комбінаторики (правило добутку). Величина х11 може приймати довільне (ціле) значення від

max(0, a1-b2-b3-b4)=max(0,50-25-35-20)=max(0,-30)=0

до

min(a1, b1)=min(30, 50)=30.

Дійсно, х11 не може бути меншим від 0 (очевидно) і не може бути меншим від a1-b2-b3-b4 (бо інакше у першого постачальника залишиться невивезена продукція), отже

х11 ³ max(0, a1-b2-b3-b4).

З іншого боку, х11 не може перевищити ні a1 (не можемо вивезти від першого постачальника більше, ніж у нього є), ні b1 (першому споживачу не повинні везти більше, ніж йому треба), тобто,

х11 £ min(a1, b1).

Продовжуючи аналогічні міркування, доходимо висновку, що для кожного фіксованого х11 величина перевезень х12 може змінюватись лише від

max(0, a1-х11-b3-b4)

до

min(a1- х11, b2)

і аналогічно

max(0, a1-х11-х12-b4) £ х13 £ min(a1-х11-х12, b3).

При фіксованих значеннях перевезень величин х11, х12 та х13 величина х14 може прийняти лише одне значення

х14=a1-х11-х12-х13.

При фіксованих значеннях х11, х12, х13 та х14, розглянемо, в яких межах можуть змінюватись елементи х21, х22, х23 та х24. Використовуючи ті ж міркування, маємо наступні обмеження:

max(0, a2-(b2-х12)-(b3-х13)-(b4-х14))£ х21£ min(a2,b1-х11),

max(0, (a2-х21)-(b3-х13)-(b4-х14)) £ х22 £ min(a2-х21, b2-х12),

max(0, (a2-х21-х22)-(b4-х14)) £ х23 £ min(a2-х21-х22, b3-х13),

х24= a2-х21-х22-х23,

х31= b1-х11-х21,

х32=b2-х12-х22,

х33= b3-х12-х22,

х33=b3-х13-х23,

х34=b4-х14-х24=a3-х31-х32-х33.

Отже, всього маємо перебрати таку кількість варіантів:

´

´´

´1 = 11265721,

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

Другою перевагою цього методу є те, що в ході перебору легко отримати не один, а всі оптимальні плани перевезень Х, для яких досягається спільне мінімальне значення вартості перевезень, які в свою чергу, для зручності аналізу можна згрупувати по кількості відмінних елементів (до речі, ця кількість може бути лише парним числом, починаючи з 4).

Третьою суттєвою перевагою цього методу є його прозорість (порівняно з іншими методами) та можливість легкого програмування. Єдиним недоліком цього методу є те, що при великих розмірностях матриці Х та великих значеннях обсягів потреб та запасів час роботи програми може складати кілька годин, хоча і такий час може бути виправданий, коли мова йде про конкретну практичну задачу. На розв’язок наведеної вище задачі, тобто на виконання відповідної програми, написаної на мові Turbo Pascal 7.0, ЕОМ класу Pentium-II з тактовою частотою 350 МГц та об’ємом оперативної пам’яті 128 Мб витрачає всього 95с секунд, причому якщо додаткові обмеження на перевезення ускладнюють розв’язок транспортної задачі звичайними методами, то запропонований метод перебору лише покращиться, бо зменшиться кількість варіантів.

# ЛІТЕРАТУРА

1. Карманов В.Г. Ма тематическое программирование. М., Наука, 1986.
2. Кігель В.Р. Елементи лінійного, цілочислового лінійного, нелінійного програмування. Київ, 1995.
3. Грешилов А.А. Как принять наилучшее решение в реальных условиях. Москва, Радио и связь, 1991.