Лекція 4. Транспортна задача: алгоритм вирішення.

Приклад.

На території міста є три телефонні станції: А, В, С. Є три нових райони забудови, що мають потребу в телефонізації. Незадіяна ємність:

станціяА– 5 тис.

станціяВ– 3 тис.

станціяС– 4 тис.

Потреби нових районів у телефонних номерах:

1-й – 3 тис.

2-й – 4 тис.

3-й – 5 тис.

Відома вартість прокладки і будівництва лінійних споруджень від діючих АТС до нових районів.

Потрібно знайти такий розподіл ємності АТС міжновими районами, щоб сумарні витрати на прокладку лінійних споруджень були мінімальними.

.

Рішення розбивається на 2 етапи.

1-й етап: здійснюється пошук припустимого рішення (первинного базисного рішення, опорного рішення, опорного плану);

2-й етап: знаходиться оптимальне рішення (якщо воно існує).

1-й етап. Пошук первинного базисного рішення.

Існує два методи знаходження припустимого рішення (первинного базисного рішення).

1. Метод «північно-західного кута».

Пошук рішення починається з визначення змінної х_А1лівого стовпця верхнього рядка («північно-західний кут»), якій надається максимально можливе значення, чи іншими словами, максимально можливе постачання в клітку (А, 1):х_А1= min{5тис;3тис}=3тис. Після цього попит 1-го споживача (району) буде цілком задоволений, у результаті чого перший стовпець таблиці постачань випаде з наступного розгляду.

У таблиці постачань знайдемо новий «північно-західний кут» - клітку (А, 2) і надамо їй максимально можливого значення. З огляду на те, щоА-й постачальник (АТС) вже віддав3тисномерів, то в нього залишилося тільки2тис=5тис-3тис. Одержуємох_А2= min{5тис; 3тис}=2тис. Після цього потужність першого постачальника (АТС) цілком реалізована і з розгляду випадає перший рядок таблиці постачань.

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

А	4 3т	7 2т	6 0	5т
В	12 0	15 2т	11 1т	3т
С	13 0	7 0	10 4т	4т
n	1	2	3	Qj
q	3т	4т	5т

Істотним недоліком методу «північно-західного кута» є те, що він не враховує значень коефіцієнтів витрат.

W = 3т*4 + 2т*7 + 2т*15 + 1т*11 + 4т*10 = 107 т.

2. Метод «найменшого елемента» (найменших витрат).

Цей метод є модифікацією методу «північно-західного кута» і дозволяє враховувати витрати (коефіцієнт витрат) на постачання при відшуканні опорного рішення.

Це дає можливість одержати рішення, як правило, більш близьке до оптимального.

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

Розподілимо ємність АТСАміж районами з найменшими витратами відповідно до потреб цих районів, починаючи з найменших витрат. Це (А,1) і (А,3). Повторюємо пошук і заповнення кліток, що залишилися, аналогічним чином. Одержимо:

А	4 3т	7 0	6 2т	5т
В	12 0	15 0	11 3т	3т
С	13 0	7 4т	10 0	4т
n	1	2	3	Qj
q	3т	4т	5т

W = 3т*4 + 2т*6 + 3т*11 + 4т*7 = 85.

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

2-й етап. Пошук оптимального рішення (поліпшення планів перевезень).

Цикл перерахунку.

На другому етапі перевіряється - чи є базисне рішення оптимальним.

Для цього спочатку потрібно виразити цільову функцію W(3.1) задачі через неосновні (вільні) змінні. Мінімум цільової функції, тобто рішення транспортної задачі, отримується тоді, коли всі коефіцієнти при вільних (неосновних) змінних у виразі для цільової функціїW(3.1) через вільні перемінні невід’ємні.

У транспортній задачі змінна х_ijототожнюється з вмістом відповідної клітки(i, j)таблиці постачань. Позначимоb_ijкоефіцієнт біля вільної змінноїх_ijу виразі для лінійної функції ціліW(3.1) через вільні змінні;b_ijназиваєтьсяоцінкою вільної клітки(i, j).

При даному базисному розподілі постачань клітка (i, j) - вільна (змінна х_ij - вільна),b_ij- оцінка клітки(i, j) чи коефіцієнт у виразі лінійної функції W(3.1) через вільні змінні:

W = W₀ + b_ij х_ij + … (3.4)

де трикрапкоюпозначені доданки, що відповідають вільним змінним, відмінним від х_ij,W₀– сумарні витрати на даний розподіл постачань.

Тоді з (3.4) випливає, що оцінка b_ijвільної(i, j)клітки дорівнює зміні сумарних витратΔWна постачання при переведенні в клітку(i, j)одиничного постачання (збільшеннязмінної х_ijвід 0 до 1), тобто:b_ij = ΔW = W_п – W_н, де W_н -первиннівитрати на постачання;W_п -витрати на постачання після перерозподілу. Передбачається, що у всіх вільних клітках відмінних від клітки(i, j), постачання залишиться нульовим. Очевидно, щоΔW > 0якщоb_ij> 0;ΔW < 0якщоb_ij< 0. Останнє непряме визначення оцінки вільної клітки називаютьекономічним змістом оцінки вільної клітки.

Знайдемо оцінку вільної клітки А3. Для цього дамо в кліткуА3одиничне постачання. При цьому буде потрібно змінити постачання в заповнених клітках так, щоб зберігся баланс по рядках і стовпцям (передбачається, що у всіх вільних клітках відмінних від кліткиА3, постачання залишиться нульовим). Так, щоб 3-й район як і раніше одержав 5 тис. номерів, постачання в клітціВ3варто зменшити на 1тис. Для того, щобАТСВяк і раніше поставила 3тис. номерів, постачання в клітціВ2збільшуємо на 1тис. 2-му району необхідно тільки 4тис. номерів, тому постачання в клітціА2варто зменшити на 1тис. З'єднавши один по одному зазначені кліткиA3 à B3 à B2 à A2 à A3одержимо замкнутий контур (цикл).

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

Позначимо знаком «+» ті вершини, у яких постачання (перевезення) збільшуються, а знаком « - » ті, у яких вони зменшуються.

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

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

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

Так, якщо після перерозподілу маємо b_ij=ΔWз від’ємною оцінкою, то вихідний базовий розподіл – не оптимальний і його можна поліпшити.

Якщо ціна циклу додатнявеличина, то поліпшити рішення за рахунок цього циклу перерахунку не вдасться. З іншого боку вартість перевезень зросте, якщо інакше перерозподілити ресурси по цьому циклу.

Якщо ціна дорівнює 0, то вартість постачань по цьому циклу не змінюється при переміщенні.

В отриманій базовій транспортній таблиці необхідно побудувати зазначені цикли перерахунку для усіх вільних кліток. У вихідній вільній клітці розміщаємо одну з вершин і приписуємо «+». Всі інші вершини перерахунку повинні спиратися на зайняті клітки.

А	4 3т	7 2т	6 0	5т
В	12 0	15 2т	11 1т	3т
С	13 0	7 0	10 4т	4т
n	1	2	3	Qj
q	3т	4т	5т

А3: A3 àB3àB2àA2àA3b_A3= 6-11+15-7 = 3

B1: В1 àА1àА2àВ2àВ1b_В1 = 12-4+7-15 = 0

C1: С1 àС3àВ3àВ2àА2àA1àC1b_С1 = 13-10+11-15+7-4 = 2

C2: С2 àВ2àВ3àC3àC2b_С2 = 7-15+11-10 = -7

Для поліпшення рішення в розглянутій задачі можна виконати єдиний цикл перерахунку з від’ємною ціною b_С2:

А	4 3т	7 2т	6 0	5т
В	12 0	15- 2т	11 + 1т	3т
С	13 0	7 + 0	10 - 4т	4т
n	1	2	3	Qj
q	3т	4т	5т

Оптимізація рішення транспортної задачі (оптимізація розподілу постачань).

При переміщенні по циклу k одиниць ресурсу зміна вартості складе ΔW=k´b_ij. При цьому значення ресурсу вклітках зізнаком «+» збільшиться наk, а в кліткахзізнаком «-» - зменшиться наk.

Значення k вибирається серед кліток циклу,що мають знак «-». Крім того, воно має мінімальне значення серед цих кліток, отже k = min{2,4} = 2, тобто це буде клітка B2. Для обнулення постачання в цій клітці по циклу слід передати 2 одиниці ресурсу. Постачання, передане по циклу, визначається як мінімум серед постачань у клітках циклу зі знаком «-». Після цього клітка В3 вважається заповненою, а клітка В2 - вільною. Одержали новий базисний розподіл постачань:

А	4 3т	7 - 2т	6 + 0	5т
В	12 0	15 0	11 3т	3т
С	13 0	7 + 2т	10 - 2т	4т
n	1	2	3	Qj
q	3т	4т	5т

Зміна витрат на новому розподілі складе ΔW⁽¹⁾ = -7 ´ 2 = -14. Загальний обсяг витрат при новому базисному розподілі складе: W⁽¹⁾ = W⁽⁰⁾ + ΔW⁽¹⁾ = 107-14 = 93.

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

A3: b_A3 = 6-10+7-7 = - 4 по циклу A3àC3àC2à А2 à A3.

B1: b_B1 = 12-4+7-7+10-11 = 7 пo циклу B1àA1àA2àC2àC3àВ3àВ1.

В2: b_B2 = 15-7+10-11 = 7 по циклу B2àC2àC3àB3àB2.

C1: b_C1 = 13-4+7-7 = 9 по циклу C1àA1àA2àC2àC1.

Оскільки є вільні клітки з від’ємною оцінкою (b₃ = - 4), то оптимальне рішення ще не знайдене. Для одержання чергового базисного розподілу використовуємо цикл перерахунку по A3. При цьому k = min{2,2} = 2; ΔW⁽²⁾ = b₃ x k⁽²⁾ = - 4 x 2 = - 8; W⁽²⁾= W⁽¹⁾ + ΔW⁽²⁾ = 93 - 8 = 85.

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

Як видно, при виконанні кожного чергового циклу перерахунку вільна клітка стає заповненою, а одна з заповнених – вільною.

А	4 3т	7 0	6 2т	5т
В	12 0	15 0	11 3т	3т
С	13 0	7 4т	10 0	4т
n	1	2	3	Qj
q	3т	4т	5т

Загальний алгоритм рішення транспортної задачі може бути сформульований у такому вигляді:

1. Для даного базисного розподілу постачань підбираються потенціалирядків і стовпців таблиці постачань так, щоб коефіцієнти витрат заповнених кліток стали рівні 0. Складається матриця оцінок.

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

3. Для обраної вільної клітки будується зазначений цикл перерахунку. Постачанняk, переданепо циклу, визначається як мінімум серед постачань у клітках зі знаком «-». Знайдене постачання пересувається по циклу. При цьому постачання в клітках зі знаком «+» збільшується наk, а в клітках зі знаком «-» зменшується наk. Клітка, постачання в який при цьому стане рівним0, буде вважатися вільною, інші клітки циклу – заповненими. Таким чином, отриманобазисний розподіл постачань.

4. Переходимо до п. 1 алгоритму.

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

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