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

Шарапов М.М.

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

В найпростішому варіанті транспортна задача формулюється наступним чином: є n постачальників із запасами однорідного штучного товару a₁,a₂,…,a_n та m споживачів із потребами цього товару b₁,b₂,…,b_m. Не порушуючи загальності, можна вважати транспортну задачу закритою, тобто, що сума всіх запасів дорівнює сумі всіх потреб, в противному разі задача є відкритою і простими відомими методами (введенням фіктивного постачальника чи фіктивного споживача) зводиться до закритої. Нехай матриця С розмірності m ´ n є матрицею цін перевезень, тобто кожен її елемент c_ij є ціною за перевезення одиниці продукції від i–го постачальника j–му споживачу, а матриця Х такої ж розмірності є планом перевезень, тобто кожне х_ij є цілим невід’ємним числом, що дорівнює кількості товару, що перевозиться від i–го постачальника j–му споживачу. Метою розв’язку транспортної задачі є пошук такого плану перевезень Х, при якому загальна вартість перевезень

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

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

max(0, a₁-b₂-b₃-b₄)=max(0,50-25-35-20)=max(0,-30)=0

до

min(a₁, b₁)=min(30, 50)=30.

Дійсно, х₁₁ не може бути меншим від 0 (очевидно) і не може бути меншим від a₁-b₂-b₃-b₄ (бо інакше у першого постачальника залишиться невивезена продукція), отже

х₁₁ ³ max(0, a₁-b₂-b₃-b₄).

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

х₁₁ £ min(a₁, b₁).

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

max(0, a₁-х₁₁-b₃-b₄)

до

min(a₁- х₁₁, b₂)

і аналогічно

max(0, a₁-х₁₁-х₁₂-b₄) £ х₁₃£ min(a₁-х₁₁-х₁₂, b₃).

При фіксованих значеннях перевезень величин х₁₁, х₁₂ та х₁₃ величина х₁₄ може прийняти лише одне значення

х₁₄=a₁-х₁₁-х₁₂-х₁₃.

При фіксованих значеннях х₁₁, х₁₂, х₁₃ та х₁₄, розглянемо, в яких межах можуть змінюватись елементи х₂₁, х₂₂, х₂₃ та х₂₄. Використовуючи ті ж міркування, маємо наступні обмеження:

max(0, a₂-(b₂-х₁₂)-(b₃-х₁₃)-(b₄-х₁₄))£ х₂₁£ min(a₂,b₁-х₁₁),

max(0, (a₂-х₂₁)-(b₃-х₁₃)-(b₄-х₁₄)) £ х₂₂ £ min(a₂-х₂₁, b₂-х₁₂),

max(0, (a₂-х₂₁-х₂₂)-(b₄-х₁₄)) £ х₂₃ £ min(a₂-х₂₁-х₂₂, b₃-х₁₃),

х₂₄= a₂-х₂₁-х₂₂-х₂₃,

х₃₁= b₁-х₁₁-х₂₁,

х₃₂=b₂-х₁₂-х₂₂,

х₃₃= b₃-х₁₂-х₂₂,

х₃₃=b₃-х₁₃-х₂₃,

х₃₄=b₄-х₁₄-х₂₄=a₃-х₃₁-х₃₂-х₃₃.

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

´´

´1 = 11265721,

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

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

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

ЛІТЕРАТУРА

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