Повна версія

Головна arrow Логістика arrow Проектування логістичних систем

  • Увеличить шрифт
  • Уменьшить шрифт


<<   ЗМІСТ   >>

Завдання оптимізації потоків в мережевий постановці

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

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

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

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

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

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

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

Пункти - пункти виробництва з обсягами виробництва відповідно 30, 70, 50 одиниць; пункти - пункти споживання з обсягами споживання, що дорівнюють відповідно 60, 40, 50 одиниць; пункти , - перевалочні пункти (відсутність у відповідних колах, обсягів виробництва означає, що вони дорівнюють нулю).

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

Приклад транспортної мережі

Мал. 4.7. Приклад транспортної мережі

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

(4.21)

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

не узгоджується з обсягами виробництва і споживання пунктів мережі.

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

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

Звідси приходимо до наступного визначення плану транспортної задачі на мережі: планом називається будь-яка сукупність чисел , що задовольняє умовам

(4.22)

Легко підрахувати загальну вартість перевезень, визначених планом :

(4.23)

де підсумовування ведеться по всіх комунікацій транспортної мережі.

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

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

 
<<   ЗМІСТ   >>