Прийняття управлінських рішень - Петруня Ю.Є. - Розділ 5. Математичні методи розробки рішень у логістичній діяльності

5.1. Транспортна задача за загальним критерієм вартості

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

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

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

Складемо математичну модель задачі. Нехай аі - кількість одиниць товару, що міститься в 7-му пункті постачання Аі: Ьу - кількість одиниць товару, що потребує у-й пункт споживання Ву: су - вартість перевезення одиниці товару з 7-го пункту постачання Аі в у-й пункт споживання Ву: ху - кількість одиниць товару, що планується перевезти з 7-го пункту постачання Аі в у-й пункт споживання Ву (шукані величини).

Згідно з критерієм оптимальності загальні транспортні витрати

тп

і = ' уху мають бути мінімальними, тобто

і=1у=1

m n

z = 'E'Ecijxij -"min

1=1 j=1

за умов:

2 xtj < ai, i = 1, m;

m -

- Z xij ^ bj, j =1 n; 1=1 _

Xij ^ 0, i = 1, m, j = 1, n, де m - кількість пунктів постачання, n - кількість пунктів споживання.

m n

Якщо виконується умова балансу 2 ai = 2 bj (сумарні запаси до-

г=1 j=1

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

mn

Коли 2 at > 2 bj (сумарні запаси перевищують сумарні потреби),

г=1 j=1

вводять фіктивний (n + 1)-й пункт споживання i?n+1 з потребою

m n -

bn+1 =2 ai - 2 bj одиниць вантажу і береться, що ci n+1 = 0 (i = 1, m).

i=1 j=1

mn

Якщо 2 ai < 2 bj (сумарні потреби перевищують сумарні запаси),

і=1 j=1

вводять фіктивний (m +1) -й пункт постачання Am+1 з обсягом

n m -

am+1 = 2 bj - Z ai одиниць вантажу і береться, що cm+1 j = 0 (j = 1,n).

j'=1

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

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

На практиці виникають різного роду ускладнення в постановці ло-гістичних задач. Розглянемо деякі з них і методику зведення таких задач до класичної транспортної задачі.

1. У деяких реальних умовах перевезення вантажу з пункту постачання At в пункт призначення Bj не можуть бути виконані, наприклад порушується умова наявності інфраструктури (доріг) або умови контракту між організацією, котра подана як z'-й пункт постачання, та організацією, що показана як j-й пункт споживання. Заборону перевезення з пункту At в пункт Bj роблять за допомогою введення дуже великого тарифу замість існуючого у відповідну клітинку таблиці, за рахунок чого вона блокується.

2. Інколи в транспортній задачі додатковою умовою є забезпечення перевезень за відповідними маршрутами певної кількості вантажу. Наприклад, з пункту відправлення At в пункт постачання Bj треба обов'язково перевезти Oy одиниць вантажу. Тоді в клітинку таблиці транспортної задачі, яка міститься на перетині 7-го рядка та j-ro стовпця, записують число ац і в подальшому цю клітинку вважають вільною з яким завгодно великим тарифом перевезень, який блокує дану клітинку.

3. У деяких випадках треба знайти розв'язок транспортної задачі, для якої з пункту відправлення At в пункт призначення Bj має бути завезено не менше заданої кількості вантажу, тобто Хц > $j. Для визначення оптимального плану такої транспортної задачі вважаємо, що запаси пункту At та потреби пункту Bj менші фактичних на Яj одиниць. Після цього знаходимо оптимальний план нової транспортної задачі та, збільшуючи обсяги перевезень Xj на Яj, визначаємо розв'язок початкової транспортної задачі.

4. У деяких транспортних задачах треба знайти оптимальний план перевезень за умови, що з пункту відправлення At в пункт призначення Bj необхідно перевезти не більше ніж jj одиниць вантажу, тобто Xj > jj (транспортна задача з обмеженнями на пропускну здатність). Тоді в таблиці вхідних даних передбачають додатковий стовпець, тобто вводять додатковий пункт призначення Bn + 1. У цьому стовпці записують ті самі тарифи, що і в стовпці Bj, за винятком тарифу, який міститься в 7-му рядку. У додатковому стовпці в цьому рядку вважається, що тариф дорівнює деякому скільки завгодно великому числу M. При цьому вважають, що потреби пункту Bj дорівнюють y,j, а потреби введеного пункту призначення Bn + 1: bj - y,j. Після одержання оптимального розв'язку величини вантажу, що перевозиться до (n + 1)-го споживача, додаються до величин перевезень j-ro споживача. Оскільки n + 1 = M

- найбільший тариф перевезень, то в оптимальному розв'язку клітинка з номером (і, n + 1) залишається порожньою: x, n + 1 = 0, а обсяг перевезення Ху не буде більшим уд.

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

1. Трьохіндексна транспортна задача. Нехай у постачальників A1, A2, Am є напівфабрикат, який треба спочатку переробити, отримати з нього продукцію в деяких проміжних пунктах і перевезти її споживачам B1, B2, Bn. Припустімо, що сумарні запаси дорівнюють сумарним по-

mn

требам: 2аі = 2zbj. Задано проміжні пункти переробки С1, С2, С/,

г=і j=1

причому k-й пункт переробки не може обробити вантажу більше, ніж dk:

m n /

2 аі = Zl by ^ 2 dk. Відомі також елементи двох матриць С1 = (%)т/1

і=1 j=1 k=1

- вартості перевезення одиниці вантажу від і-го постачальника в k-й пункт переробки та С2 = (c'kj )/xn - вартості перевезення одиниці вантажу від k-ro пункту переробки в j-й пункт споживання. Потрібно визначити оптимальну схему перевезень продукції з мінімальними сумарними витратами. Для математичної моделі вводяться змінні xiky

(і = 1, m; j = 1, n; k = 1, /) - кількість вантажу, що перевозиться від і-го постачальника j-му споживачеві через k-й пункт переробки. Тоді

т n / /

z = ZZZ{c'ik + ckj)xikj -> min;

і=1 j=1k=1

]C lLxikj = аі, і =1, m;

k=1 j=1

/ m -

HlLxuj = bj, j =1 n;

k=1і=1

m n -

ZTxuj < dk, k = 1,/;

і=1 j=1__ _ _

Xikj >■ 0, і = 1,m; j = 1,n; k = 1,/.

2. Трьохіндексна транспортна задача з різними видами вантажу. У класичній транспортній задачі розглядалося перевезення однорідного виду вантажу. Однак на практиці часто потрібно визначити оптимальний план перевезень неоднорідної продукції. Позначимо через a k ( і = 1, m; k = 1, p) - кількість вантажу k-ro виду, що належить і-му постачальнику, а через bjk (j = 1, n; k = 1, p) - потреби j-ro споживача у k-му виді вантажу. Для спрощення припустімо, що задача

m n

збалансована £ ak = £ bjk, тобто для кожного k-ro виду вантажу сумарні запаси постачальників дорівнюють сумарним потребам споживачів. Матриця вартості перевезень одиниці k-ro виду вантажу від i-ro постачальника j-му споживачеві має вигляд C = (c yk)mxnx . Вводяться

змінні Xjk - кількість вантажу k-ro виду, що перевозиться від i-ro постачальника j-му споживачеві. Тоді математична модель має такий вигляд:

m n p

z = zzzCijkXijk ->min;

2 Xjk = aik, i =1, m; k =1, p;

j=1

- 2 Xijk = bjk, j =1, n; k =1, p;

Xjk ^ 0, i = 1, m; j = 1, n; k = 1, p.

3. Чотирьохіндексна транспортна задача. Вартість перевезення в цій задачі залежить також від /-го виду транспорту, яким перевозиться вантаж. Задані C = (CjM )mxnxpxq - вартості перевезень одиниці вантажу.

Вводячи змінні Xjki - кількість k-ro виду вантажу, що перевозиться /-м видом транспорту від i-ro постачальника j-му споживачеві, маємо

m n / q

z = zzzzCjkiXjki min;

i=1 j=1k=1/=1

zzXijk/ = aik, i =1 m; k =1, p;

j=1/=1

- zzXik/ = bjk, j =1 n; k =1, p;

Xjki ^ 0, i = 1, m; j = 1, n; k = 1, p; / = 1, q.

Існують транспортні задачі і з більшою кількістю індексів, наприклад з урахуванням країни-походження товару тощо. Багатоіндексні задачі, починаючи з трьохіндексних, можна розв'язувати тільки симплекс-методом.

Транспортна задача часто використовується для виконання таких управлінських завдань, які за умовою не мають нічого спільного з транспортуванням вантажів, і величини Cj залежно від конкретної задачі можуть означати відстань, час, продуктивність тощо.