8.4. Вибір шляхів переміщення вантажопотоків

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

Маршрут руху — шлях переміщення рухомого складу при ви-конанні перевезення.

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

Постановка транспортного завдання

Маємо m постачальників визначеного виду продукції. Максима-льні об'єми можливих поставок продукції задані і дорівнюють від-повідно a,i = 1,2,...,m. Ця продукція використовується n споживача-ми. Об'єми потреби задані та дорівнюють відповідно bj, j = 1,2,..., n.Вартість перевезення одиниці продукції від i-го постачальника до j-го споживача відома для всіх i = 1,2,...,m та всіх j = 1,2,...,n та дорів-нює с^ . Потрібно встановити такі об'єми перевезення xtj від кож-ного постачальника до кожного споживача, щоби сумарні витратина перевезення були мінімальними і потреби всіх споживачів булиб задоволені (якщо тільки загальний об'єм можливих поставок по-криває загальний об'єм потреб).

Математична модель цього завдання наступна:

mn

XX j,- ^ min;    (8.22)

i=1 j=1

n

Xxij < ai,i = 1,2,...,m;

j=1

m

Xxj > bj, j = 1,2,..vn;

i=1

x,, > 0,i = 1,2,...,m; j = 1,2,...,n.

у

Вирішення транспортного завданняметодом північно-західного кута

При використанні методу «північно-західного кута» насампереданалізують транспортну проблему визначаючи потужність кожногопостачальника і потреби кожного споживача, а також витрати наперевезення від кожного відправника до кожного споживача. До-тримуються наступних вимог:

витратити всю потужність джерела постачання;

задовольнити всі потреби кожного споживача;

перевірити, чи всі потреби задоволені.

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

Таблиця 8.4

ТРАНСПОРТНА МАТРИЦЯ

c11

x11

c12

x12

...

c1n

x1n

a1

С21

x21

c22

x22

...

c2n

x2n

a2

 

 

 

 

 

Cm1

xm1

cm2

xm2

...

c

mn

xmn

am

b

b2

...

bn

d

Кожна клітина транспортної матриці відповідає визначеній паріпостачальник — споживач. Наприклад, клітина, що розташована вг-му горизонтальному рядку та j-му вертикальному стовпчику, від-повідає парі г-й постачальник — j-й споживач. В клітинки будемозаносити дані про об'єми перевезень за відповідним маршрутом.Почнемо вирішення завдання, починаючи з встановлення об'ємуперевезень за маршрутом (1,1), тобто з заповнення верхньої лівої(«північно-західної») клітини матриці. Приймемо його максималь-но можливим за умовою завдання, тобто таким, що дорівнює

x11 - min(a1,b1).         (8.23)

Якщо a1 < b1, то постачальник 1 повністю використав свої мож-ливості, і при встановленні інших перевезень його можна не врахо-вувати, а потреба споживача 1 тепер буде дорівнювати (bl - a1).Якщо a1 > b1, то споживач 1 повністю задовольнив свою потребу впродукції, і його можна в подальшому не враховувати, а постача-льник 1 тепер розпоряджається лишеЦ - bl) одиницями продукції.Якщо a1 = b1, то можна в подальшому не враховувати ні споживача,ні постачальника. Однак умовимось вважати, що в цьому випадку«вибуває з гри» тільки один з них (хай для визначеності — поста-чальник), а можливі постачання (і відповідно потреба) споживачадорівнює нулю (фіктивне постачання або потреба).

З цих міркувань виходить, що після встановлення об'єму пере-везень за маршрутом (1,1) ми маємо справу з новим завданням, вкотрому сумарне число постачальників і споживачів на одиницюменше, ніж у вихідному завданні. В північно-західну клітину мат-риці, яка одержана уявним викреслюванням першого рядка абостовпчика зі «старої» матриці, знову розміщуємо максимально мо-жливий об'єм перевезень (він може бути і нульовим). Цей процеспродовжується до розподілення всієї кількості вантажу. Як прави-ло, число всіх заповнених клітин є (m +n - 1), де m — число поста-чальників, n — число споживачів. Продовжуючи цей процес, ми,очевидно, одержимо допустиме вирішення завдання, тому, що

mn

X a, =X bj = d.            (8.24)

i=1 j=1

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

Метод послідовного покращення рішення

Це ітеративний метод, що дозволяє послідовно переходити відпочаткового допустимого рішення до оптимального рішення. З ці-єю метою ми перевіряємо кожну невикористану клітину транспор-тної матриці, задаючи собі наступне питання: «що скоїться з сума-рними витратами, якщо одну одиницю продукції умовно перевезтишляхом, який невикористаний нами?».

Проведемо цю перевірку наступним чином:

Виберемо будь-яку невикористану клітину матриці для оцінки.

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

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

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

Потрібно повторити кроки 1—4 для всіх невикористаних клі-тин. Якщо значення всіх індексів зросло або дорівнює нулю, то цеозначає, що досягнуте оптимальне рішення. Якщо ні, то існує мож-ливість покращити це рішення та знизити сумарні витрати переве-зень. Кожний від'ємний індекс показує величину, на котру можназменшити сумарні витрати, якщо перевезення будемо здійснюватишляхом, що характеризується від'ємним індексом. Тому, наступ-ний крок полягає у виборі для перевезень такого шляху, котромувідповідає максимальний від'ємний індекс (якщо їх декілька). Та-ким чином ми досягаємо максимальної економії сумарних витрат ізнаходимо оптимальний план перевезень.

МОДІ — метод (модифікований розподільчий)

МОДІ — метод дозволяє розрахувати індекси, для кожної неви-користаної клітини, не прокладаючи пов'язані з цим шляхи, як церекомендується в попередньому методі. Це зберігає час при вирі-шенні транспортного завдання.

Використання МОДІ — методу починається з початкового рі-шення, яке знаходиться за допомогою методу «північно-західногокута». Далі визначають значущість кожного рядка і кожної колон-ки. Оцінки значущості рядків і стовпчиків позначимо наступнимчином:

R — оцінка значущості рядка і (і = 1, 2,..., m);

Kj — оцінка значущості стовпчика j (j = 1, 2,..., n);

Су — вартість перевезення продукції від i-го постачальника доj-го споживача.

МОДІ — метод складається з п'яти кроків:

Розраховується оцінка для кожного рядка і стовпчика у ви-гляді R + Kj = Cj, але тільки для тих клітин, котрі послідовно вико-ристовуються або зайняті. Наприклад, якщо клітина знаходиться наперетині рядка 3 ті стовпчика 2, вона формує оціночний набір

R3 + K2 = C32.

Після того, як виписані всі рівняння, приймають, що R1 = 0.

Вирішуються всі рівняння для всіх R та K оцінок.

Розраховується індекс покращення для кожної невикориста-ної клітини за формулою: Індекс = Cj - R - Kj.

Відбирається найбільший за абсолютним значеннямвід'ємний індекс і рішення задачі продовжується відповідно до ме-тоду послідовного покращення рішення (пункт 5).

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

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