Транспортна модель з проміжними пунктами
У стандартній транспортній моделі передбачається, що прямий маршрут між пунктом виробництва і пунктом споживання є маршрутом мінімальної вартості. Так із таблиці відстаней між трьома автомобільними заводами і двома центрами розподілу утворюються найкоротші маршрути між пунктами виробництва і пунктами споживання. Це означає, що визначенню вартостей перевезень одиниці продукції в стандартній транспортній моделі повинна передувати попередня робота, пов'язана з виявленням найкоротших маршрутів.
У задачах невеликої розмірності визначення найкоротшого маршруту не складає труднощів. Коли ж число пунктів виробництва і пунктів споживання є велике, для визначення мінімальної вартості прямого перевезення одиниці продукції по конкретному маршруту варто звернутися до алгоритму знаходження найкоротшого шляху.
Інший метод визначення мінімальної вартості прямого перевезення пов'язаний із постановкою задачі як задачі з проміжними пунктами. При цьому допускається «перевезення» вантажу (частково або цілком) через інші вихідні пункти або використання пунктів призначення транзитом, перед тим, як вантаж досягне встановленого пункту призначення. У задачі з проміжними пунктами автоматично шукається маршрут мінімальної вартості між пунктом виробництва і пунктом призначення без попереднього визначення найкоротшого маршруту.
Введення проміжних пунктів дає можливість перевозити весь объем продукції з вихідних пунктів через будь-який інший вихідний пункт або пункт призначення, перед тим, як продукція буде розподілена серед споживачів. Це означає, що будь-яку вершину транспортної мережі (як вихідний пункт, так і пункт призначенні) можна розглядати як транзитний пункт. Оскільки апріорі не відомо, які вершини будуть мати цю властивість, можна сформулювати задачу таким чином, щоб кожну вершину можна було розглядати і як вихідний пункт, і як пункт призначення. Іншими словами, число вихідних пунктів (пунктів призначення) у задачі з проміжними пунктами дорівнює сумі вихідних пунктів і пунктів призначення в стандартній задачі.
Для пояснення цього зауваження розглянемо наступну задачу.
Приклад.
Є три заводи і два центри розподілу. У моделі з проміжними пунктами буде п'ять вихідних пунктів і п'ять пунктів призначення.
Для того щоб врахувати транзитні перевезення, у кожному вихідному пункті призначення передбачений додатковий буфер ємністю В. За визначенням ємність буфера повинна бути не менше сумарного обсягу виробництва (або попиту) стандартної (збалансованої) транспортної задачі, тобто .
Вартості в розрахунку на одиницю вантажу оцінюються на підставі даних про маршрути, що з'єднують вихідні пункти з пунктами призначення в моделі з проміжними пунктами. Очевидно, що коефіцієнти вартості перевезення між спочатку заданими вихідними пунктами і пунктами призначення залишаються такими ж, як і в попередньому прикладі. Зауважимо також, що вартість перевезення з деякого пункту в нього ж (скажемо, із Денвера в Денвер) дорівнює нулю, і вартість перевезення може змінюватися в залежності від напрямку (наприклад, маршрут Детройт - Денвер може відрізнятися по вартості від маршруту Денвер - Детройт, якщо використовуються різноманітні режими перевезень).
Таблиця 2
У табл. наведений оптимальний розв’язок розглянутої вище задачі з проміжними пунктами, у якій місткість буфера Вдорівнює 3700 автомобілів. Зауважимо, що коефіцієнти вартості перевезень між спочатку заданими вихідними пунктами (Лос-Анжелес, Детройт і Новий Орлеан) і пунктами призначення (Денвер і Майамі) ті ж, що й у прикладі. Передбачається, що інші коефіцієнти оцінюються в залежності від відстані і режиму перевезень.
Діагональні елементи отримані в результаті використання буфера. Вони не дають ніякої інформації про остаточний розв’язок. Позадіагональні елементи забезпечують одержання розв’язку, поданого на рис нижче. З Детройта до Майамі перевезення відбувається через проміжний пункт у Новому Орлеані, куди надходить 200 автомобілів. Всі інші перевезення здійснюються безпосередньо з заводів у центри розподілу.
Крім розглянутої вище можливі ситуації, при яких має місце транзитне перевезення продукції. Наприклад, у прикладі остаточні пункти призначення, куди надходять автомобілі, можуть представляти окремих продавців, а не крупні центри розподілу. З метою спрощення припустимо, що є лише п'ять продавців, що одержують свої замовлення з центрів розподілу в Денвері і Майамі. На рис. центри розподілу зображені у виді тимчасових складів, із
яких автомобілі потрапляють у остаточні пункти призначення. Відповідні розміри, що характеризують попит п'ятьох продавців, складають 800, 500, 750, 1000 і 650 автомобілів. Припустимо, що продавець може одержувати товар із будь-якого центру розподілу. (З прикладу очевидно, що розміри попиту в центрах розподілу
не використовуються в якості вихідної інформації. ) У даному випадку, як показано на рис., проміжними пунктами можуть бути тільки центри розподілу.
Оскільки центри розподілу (вершини 4 і 5 на рис 3.) є єдиними проміжними пунктами, кожний із них може розглядатися і як пункт призначення, і як вихідний пункт. З іншого боку, заводи грають лише роль вихідних пунктів, а продавці – пунктів призначення. Побудована з урахуванням цього модель із проміжними пунктами наведена в табл.3.
Зауважимо, що в центрах розподілу (вершини 4 і 5) ємність буфера В, рівна 3700 автомобілів, додається до відповідних розмірів обсягу виробництва і попиту. Очевидно, що ніякої буферної ємності не потрібно додавати до розміру об'єму виробництва
| X | X | X | X | X | ||||
| X | X | X | X | X | ||||
| X | X | X | X | X | ||||
того або іншого заводу або величині, що характеризує попит продавців. Нагадаємо, що буфер уводиться лише в тих пунктах, що можуть розглядатися і як вихідні пункти, і як пункти призначення, тобто в ситуації, коли перевезення здійснюється через ці пункти транзитом. З рис. зрозуміло, що прямі перевезення з заводу продавцю не дозволені. У табл. 3 це обмеження подане забороненими (заштрихованими) комірками. При розв’язанні задачі забороненому маршруту відповідає дуже велика вартість , записана у відповідній комірці.
| X | X | X | X | X | |||||||
| X | X | X | X | X | |||||||
| X | X | X | X | X | |||||||
Припустимо, що дозволені маршрути з проміжними пунктами між заводами і центрами розподілу. Пряме перевезення допускається лише з центру розподілу продавцям. У табл. вище подана така модель. Зауважимо, що кожний завод і центр розподілу може тепер розглядатися і як вихідний пункт, і як пункт призначення.
Метод диференційних рент.
Для уникнення незручностей, які виникають в методі потенціалів і пов’язані з виродженістю, застосовується метод диференційних рент.
Алгоритм методу диференційних рент складається з двох кроків:
· початковий розподіл частини продукту між пунктами призначення найкращим чином (побудова умовно оптимального розподілу);
· зменшення на наступних кроках величини нерозподілених поставок, щоб прийти до оптимального плану перевезень.
Алґоритм методу диференційних рент.
Крок 1. В кожному стовпчику транспортної таблиці знаходимо мінімальний тариф. Знайдені тарифи позначаємо колами, що їх оточують, і заповнюємо відповідні клітинки — записуємо максимально можливі перевезення. Таким чином отримуємо розподіл, що в загальному може не задовільняти обмеженням транспортної задачі. Якщо розподіл задовольняє обмеженням задачі, то він оптимальний — стоп.
Крок 2. Скорочуємо нерозподілені поставки продукту так, щоб при цьому загальна вартість перевезень залишалась мінімальною:
визначаємо надлишкові та недостатні рядки — рядок є недостатнім (від’ємним), якщо запаси відповідного пункту зберігання розподілені повністю, а потреби не задоволені; рядок є надлишковим (додатнім), якщо потреби задоволені, і залишився продукт у відповідному пункті зберігання; Для уникнення неоднозначностей у визначенні знаку рядка, в якого нерозподілений залишок рівний 0, необхідно користатися наступним правилом: рядок вважається додатнім за умови, що друга заповнена клітинка, яка знаходиться в стовпчику, що зв’язаний з таким рядком однією заповненою клітинкою, розташована в додатньому рядку.
· для кожного стовпчика знаходимо різницю між тарифом у колі та найближчим до нього тарифом, який записаний в надлишковому рядку. Якщо тариф в колі знаходиться в позитивному (надлишковому) рядку, то різницю не визначаємо; серед різниць знаходимо найменшу — проміжну ренту;
· переходимо до нової таблиці — додаємо до відповідних тарифів, які знаходяться у від’ємних (недостатніх) рядках, проміжну ренту. Інші елементи не змінюємо.
Всі клітинки нової таблиці вважаємо вільними. Заповнюємо клітинки нової таблиці — до заповнення тепер буде на одну клітинку більше. Ця додаткова клітинка знаходиться в стовпчику, в якому записана проміжна рента. Всі інші клітинки знаходяться по одній в кожному зі стовпчиків і в них записані найменші числа в колах для кожного стовпчика. Так само в колах є два однакові числа, що знаходяться в стовпчику, в якому в попередній таблиці була записана проміжна рента.
Оскільки в новій таблиці число клітинок, що заповнюються, є більшим, ніж число стовпчиків, при заповненні клітинок користуємося наступним правилом. Обираємо деякий стовпчик (рядок), в якому наявна одна клітинка з колом. Цю клітинку заповнюємо і виключаємо з розгляду даний стовпчик (рядок). Продовжуючи цю процедуру, заповнюємо всі клітинки з колами. Якщо план допустимий, то він оптимальний — стоп , в іншому випадку переходимо до кроку 2.
Оскільки метод диференційних рент має простішу логічну структуру, ніж метод потенціалів, він і використовується частіше для програмних реалізацій.
Приклад.
| B1 | B2 | B3 | B4 | |||||||
| A1 | | |||||||||
| +40 | ||||||||||
| A2 | | | ||||||||
| -5 | ||||||||||
| A3 | | |||||||||
| -35 | ||||||||||
| — |
4 є проміжною рентою.
| | | ||||||||
| +5 | |||||||||
| | | ||||||||
| -5 | |||||||||
| | |||||||||
| +0 | |||||||||
| — | — |
| | | | | ||||||
| | | ||||||||
| | |||||||||
Задача про призначення
Задача про призначення змістовно формулюється наступним чином. Необхідно розподілити робіт серед виконавців таким чином, щоб сумарні витрати на виконання робіт були мінімальні. Відомі витрати — на виконання i-ї роботи j-м виконавцем для всіх робіт та виконавців. Окрім того, відомо, що кожен з виконавців може виконувати не більш, ніж одну роботу, і кожна робота може виконуватись не більш, ніж одним виконавцем.
Ця задача є не чим іншим, як специфіцним випадком транспортної — роботи можна розглядати, як пункти зберігання, виконавців — як пункти споживання, запаси в кожному з пунктів зберігання та потреби в пунктах споживання рівні одиниці, тариф на перевезення — .
В залежності від початкових умов для приведення задачі до задачі закритого типу додаємо фіктивні роботи або фіктивних виконавців, і отримуємо задачу з роботами та виконавцями. Формальна постановка задачі виглядатиме наступним чином.
,
, якщо і-та робота не виконується j-м виконавцем, та 1 — якщо виконується. Слід зауважити, що розв’язок задачі про призначення завжди буде виродженим, оскільки для невиродженого розв’язку ранґ матриці коефіцієнтів С повинен становити , в той час як призначеними можуть бути робіт. Таким чином, задачу про призначення можна розв’язати за допомогою методів розв’язування транспортних задач, але при цьому необхідно буде заповнення в транспортній таблиці пустих клітинок безмежно малими перевезеннями .
В той же час виявилося можливим з врахуванням специфічних особливостей задачі про призначення побудувати ефективні алгоритми її розв’язування, одним з яких є так званий угорський алгоритм. Для обґрунтування редукції в цьому алгоритмі покажемо, що оптимальний розв’язок задачі не зміниться, якщо до будь-якого рядка чи будь-якого стовпчика додати чи відняти постійну величину. Віднімемо від кожного i-го стовпчика та кожного j-го рядка постійні для відповідного рядка чи стовпчика значення та : , = .
Таким чином ця процедура зменшує значення функції мети на постійну величину, що не приводить до зміни положення оптимального розв’язку.
Угорський алґоритм для задачі про призначення складається з наступних кроків.
Крок 1. Редукція рядків та стовпчиків матриці С.
Послідовно в кожному з рядків матриці визначаємо мінімальний елемент та зменшуємо на це значення всі інші елементи відповідного рядка. В отриманій чином матриці таку ж процедуру виконуємо з кожним стовпчиком. Метою цього кроку є отримання максимальної кількості нульових елементів в редукованій матриці.
Крок 2. Реалізація призначень.
a). Послідовно переглядаючи рядки, визначаємо ті з них, в яких знаходиться рівно по одному невикресленому нульовому елементу. В кожному з таких рядків виконуємо призначення, яке відповідає цьому невикресленому нульовому елементу (призначені нулі відзначаємо кружечками). При виконанні призначення в кожному стовпчику, який відповідає призначеному нулеві, викреслюємо всі невикреслені раніше елементи.
b). Послідовно переглядаємо стовпчики, визначаємо ті з них, в яких знаходиться рівно по одному нульовому елементу. В кожному з таких стовпчиків виконуємо призначення, що відповідає невикресленому нульовому елементу. При виконанні призначення в кожному рядкові, який відповідає призначеному нулеві, викреслюємо всі невикреслені раніше елементи.
c). Перевірка: Якщо знайдене таким чином призначення повне (тобто призначено нульових елементів), то воно й буде оптимальним розв’язком задачі — стоп. Якщо деякі з нулів не викреслені (тобто залишилися рядки та стовпчики з кількістю нулів, більшою ніж 1), то обираємо рядок чи стовпчик з мінімальною кількістю нулів, довільно призначаємо один з них, викреслюємо всі нулі в в цьому рядку (стовпчику) та відповідному стовпчикові (рядку) і далі виконуємо крок 2. Якщо викреслені та призначені всі нулі в матриці, і знайдене призначення неповне, то переходимо до кроку 3.