Транспортна задача з проміжними пунктами
Одне практично важливе узагальнення класичної транспортної задачі з урахуванням можливості доставки продукту (товару, вантажів, матеріалів тощо) від і-го джерела до j- го стану за маршрутом, якій проходить через деякий проміжний пункт (склад). Так, наприклад, проміжні пункти є складовою частиною розподільної системи будь-якої великої компанії, яка має мережу універсальних магазинів у багатьох містах. Така компанія звичайно має зональні оптові бази (джерела), які постачають товари більш дрібним регіональним складам (проміжним пунктам), звідки ці товари надходять у роздрібну торговельну мережу (стани). При цьому товар для кожного фіксованого стока у загальному випадку може бути доставлений не з будь-якого джерела та за маршрутами, які не обов’язково проходять через усі проміжні пункти. Крім цього, проміжні пункти можуть мати визначену специфіку. Так, наприклад, при транспортуванні товару від джерела до стока за маршрутом, який проходить через склад, частина товару може бути використана для створення недоторканого запасу на складі.
Задачу вибору плану перевезення товарів від джерел до стоків з урахуванням проміжних пунктів, що забезпечує мінімальні транспортні затрати і потреби стоків, в досліджені операцій називають транспортною задачею з проміжними пунктами.
Розглянемо приклад.
Приклад 7.1. Торговельна фірма має 8 складів, на яких зосередженні усі наявні запаси товару. Перед початком рекламної компанії було вирішено перерозподілити частину запасів товару між складами у відповідності з прогнозами збуту у районах їх розташування. Необхідно розробити план перевезення товару між складами, який дозволить при мінімальних транспортних затратах створити на кожному складі необхідній запас товару.
На рис.7.1. подана схема розміщення складів на якій вказані: а) номери складів (цифри 1-8 у полі); б) надлишок товару на складі (якщо він є)який може бути розроблені в системі складів (він вказаний під колом з номером складу позитивним числом у одиницях виміру товару); в) нестача товару на складі (якщо вона є), яка повинна бути усунена за рахунок його постачання з інших складів системи (вона вказана під колом з номером складу негативним числом в одиницях виміру товару); г) можливість перевезення товару зі складу і на склад j (орієнтована дуга від кола з номером і до кола з номером j); д) затрати пов’язані з перевезенням одиниці товару зі складу і на склад j (величина сij над відповідною орієнтованою дугою), яка виражена в умовних грошових одиницях).
Рис.7.1. Схема розміщення складів
З рис. 7.1. видно, що сумарний надлишок товара, який є на складах № 1 і № 4, дорівнює сумарній нестачі товару на сткладах № 3, № 6 і № 8 цієї системи. Перерозподіл товару може бути здійсненим через склади. Перерозподіл товару може бути здійсненим через склади № 2, № 4 - № 7, які у цій системі є проміжними пунктами. Джерелом є лише склад № 1 на якому є надлишок товару і з якого товар і з якого товар можна лише вивозити, а стоками є склади № 3 та № 8, де є нестача товару, й на ці склади товар можна тільки завозити.
Відмітити також, що між складами з № 4 і № 5 можливі перевезення в обох напрямках, але в загальному випадку С45 ¹С54.
На рис. 7.1. фактично подана мережа транспортної задачі з проміжними пунктами, що розглядаються . Формальний опис цієї мережі зручно надати у вигляді табл.7.1.
Формальний опис мережі складів
Табл. 7.1.
| Номер складу | Об’єми перевезень xij | Надлишок (+) або нестача (-) товару | |||||
| х12 | х23 х25 | х43 х45 х47 | х54 х56 | х67 | х78 | ||
| -1 | 1 1 | ||||||
| -1 | -1 | -3 | |||||
| 1 1 1 | -1 | ||||||
| -1 | 1 1 | ||||||
| -1 | -1 | ||||||
| -1 | -1 | ||||||
| -1 | -8 | ||||||
| с12 | с23 с25 | с43 с45 с47 | с54 с56 | с67 | с78 |
В табл. 7.1. кожному вузлу мережі (складу) відповідає одна стрічка і кожній орієнтований дузі мережі відповідає одне змінне моделі xij, яке являє собою кількість товару (в одиницях його виміру). Кожному змінному моделі xij, відповідає один стовбець, в якому 1 стоїть і і-й у j-й стрічці. В табл. 7.1. на перехресті і-тої стрічки та останнього стовбця знаходиться число, яке дорівнює надлишку (якщо воно позитивне) або нестачі (якщо воно негативне) товару на і-тому складі ( в одиницях виміру товару).
Розглянемо транспортну таблицю (табл. 7.2) для нашого приклада з метою доведення можливості перетворення такої задачі у класичну транспортну задачу.
На першому етапі в табл. 7.1 необхідно виділити стрічку для кожного джерела і вказати його потужність (надлишок товару на складі). У даному прикладі джерелом є склад № 1 (в нього не входять стрілки) з потужністю S1=10. В табл. 7.2. об’єм поставок для складу № 1 S1=10.
Табл. 7.2
Транспортна таблиця для мережі складів
| Пункт виробни-цтва | Пункт споживання | Поставки (S) | ||||||
| х12 с12 | ||||||||
| х22 0 | х23 с23 | х25 с25 | ||||||
| х43 с43 | х44 0 | х45 с45 | х47 с47 | |||||
| х54 с54 | х55 0 | х56 с56 | ||||||
| х66 0 | х67 с67 | |||||||
| х77 0 | х78 с78 | |||||||
| Попит (Д) |
На другому етапі в табл.7.1 необхідно виділити стовбець для кожного етапу і вказати його потужність (нестачу товару на складі). В нашому прикладі стоками є склади № 3 та № 8 (стрілки не виходять). Д3 = 3, Д8 = 8 в табл. 7.2. відповідь значенням попиту для цих пунктів попиту.
На третьому етапі необхідно зробити наступне.
3.1. В табл. 7.2. виділити стрічку і стовбець для кожного проміжного пункту. В даному випадку проміжними складами є склади № 2, ;4 - № 7, які у табл. 7.2. фігурують як пункти виробництва і пункти попиту (стрілки входять і виходять.
3.2. Для кожного К-го проміжного пункту визначити величину чистого запасу товару Тк, який дорівнює об’єму надлишка зі знаком плюс, або об’єму нестачі зі знаком мінус. Тобто Т2 = 0, Т4 = 2, Т5 = 0, Т6 = 1, Т7 = 0.
3.3. Визначити сумарний об’єм надлишку В на усіх складах системи, використовуючи для цього останній стовбець табл.7.1. В=10+2=12. Надлишок є на складах № 1 і № 4.
3.4. Вважати, що маршрут транспортування усього сумарного об’єму надлишку товару може проходити через будь-який проміжний пункт. Це означає, що будь-який склад з номером К, що розглядається як проміжний пункт, може прийняти увесь сумарний об’єм надлишку товару і потужність “його стоку” дорівнює В, тобто Дк = В. Тому, у нашому випадку Д2 = Д4 = Д5 = Д6 = =Д7 = 12, в табл. 7.2. ці значення фігурують як попит.
3.5. Для кожного К-го проміжного пункту визначити “потужність його джерела” Sk, тобто об’єм товару, який може бути вивезений зі складу з номером К величина чистого запасу товару дорівнює Тк, а максимально можливий обєм поставок визначається величиною В, то Sk = B + T. У даному випадку S2= 12 + 0 = 12, S4 = 12 + 2 = 14, S5 = 12 + 0 = 12, S6 = 12 – 1 = 11, S7 = 12 + 0 = 12. В табл. 7.2. ці значення фігурують як постачання.
На четвертому етапі необхідно для кожного К-го проміжного пункту ввести змінну хкк при скк = 0. У нашому випадку К є {2,4,5,6,7}, а інтерпретувати змінну хкк можна як об’єм товару, який осідає на складі з номером к.
При побудові транспортної табл. 7.2. введена величина В, яка має смисл “буферного запасу” в кожному проміжному пункті. Для кожного К-го проміжного пункта величина В входить як в Sк, так в Дк. Тому сума попиту дорівнює сумі поставок. Значення Sk повинно бути настільки великим, щоб воно змогло відповідати будь-якій кількості товару, що проходить через К-й проміжний пункт при любому припустимому розв’язанні вихідної задачі.
Тому значення В приймають таким, що дорівнює сумарному об’єму надлишку товару в системі. У цьому випадку значення різниці (В-хкк) являє собою об’єм товару (в одиницях його виміру), який перевезений через К-й проміжний пункт, то В-максимально можливий об’єм поставок товару на склад Nk, а хкк – об’єм товару, який осів на складі.
В табл. 7.2. заповнені лише ті клієнти, які містять зміни хij, що відповідають орієнтованим дугам мережі, а також змінні хкк, що відповідають проміжним пунктам. Це і є відміною табл. 7.2 від таблиці стандартної транспортної задачі.
Необхідно відмітити, що в табл. 7.1. задані вісім обмежень та 10 змінних, а в транспортній табл. 7.2. вже 13 обмежень (по стрічкам та стовбцям) та 15 змінних. Збільшення розмірності на 5 одиниць пояснюється наявністю 5 проміжних пунктів.
Залишилося довести еквівалентність (у смислі спів падіння оптимальних рішень) вихідної транспортної задачі з проміжними пунктами, яка подана в табл. 7.1. з, відповідною їй класичною транспортною задачею. (табл. 7.2).
Не важко впевнитися в тому, що в табл. 7.2. стрічка, яка відповідає першому складу (джерело) й стовбці, що відповідають складам № 3 і № 8 (стоки), задають ті ж обмеження, що й відповідні стрічки в табл. 7.1.
Розглянемо К-й проміжний склад, тобто К є {2,4,5,6,7}.
Нехай I* - множина складів, на які товар може бути доставлений з К-го складу, а I** - множина номерів складів, з яких товар може бути доставлений на К-й склад. Тоді обмеження для К-го складу, що задані в табл. 7.1, має вигляд
де Тк – величина чистого запасу, яка введена на 3-му етапі побудови транспортної табл. 7.2. А так як відповідні обмеження, які задані в табл. 7.2. (по стрічці та по стовбцю), можуть бути подані наступним чином:
то віднімаючи (7.3) з (7.2) обмеженням (1).
Доведення того, що транспортна задача з проміжними пунктами еквівалентна класичній транспортній задачі, можна вважати закінченим.
Зокрема, для складу № 4, який є проміжним пунктом, обмеження (7.1) має вигляд х43 + х45 + х47 – х54 = 2, а відповідні йому обмеження (7.2) і (7.3) можуть подані так:
х43 + х44 + х45 + х47 = 14, х44 + х54 = 12.
Це витікає з рівенств Т4 = 2 і В = 12 (див 3-й етап побудови табл. 7.2)