Повна версія

Головна arrow Логістика arrow Інтегроване планування ланцюгів поставок

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


<<   ЗМІСТ   >>

Метод знаходження максимального потоку

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

Розглянемо мережу розподілу (рис. 4.21), в якій виділені пункти 0 (вхід, наприклад, склад готової продукції виробника) і п (вихід, розподільні центри, склади оптових і роздрібних організацій, споживач) і кожній дузі (відрізку), що зв'язує пункти i і j, співставлено число dij> 0, зване пропускною здатністю дуги. Величина пропускної здатності характеризує максимальне допустиму кількість матеріального потоку, яке може проходити за відповідною дузі в одиницю часу.

Приклад мережі розподілу

Мал. 4.21. Приклад мережі розподілу

Кількість продукції, що проходить по дузі від i до j, називатимемо потоком по дузі (i, j) і позначати через. Очевидно, що

Якщо врахувати, що весь матеріальний потік, який увійшов в проміжний пункт мережі, повинен повністю вийти з нього, отримаємо

З природного вимоги рівності потоків на вході і на виході маємо

Величину Z назвемо величиною потоку в мережі і поставимо завдання максимізації Z при дотриманні зазначених вище умов.

Пошук максимального потоку зводиться до пошуку пропускної здатності мінімального розрізу.

Розглянемо універсальний алгоритм пошуку в матричної формі.

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

Основні кроки алгоритму полягають в пошуку деякого шляху і корекції потоку на цьому шляху.

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

і переносимо мітки стовпців на рядки. Потім беремо ί-ю відзначену рядок, шукаємо в ній Непомічені стовпець з, якому зіставляємо мітки-індекси

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

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

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

Максимальний потік може бути знайдений вирахуванням з вихідної матриці D 0, одержуваної після наведеної вище коректури матриці пропускних спроможностей:

Приклад 4.4

Виробництво розміщено в Москві. Для розподілу продукції підприємство залучає посередників, які працюють з підприємством через розподільні центри різних рівнів. У європейській частині Росії працює оптове підприємство 1, обслуживаемое центральним розподільчим центром. Оптове підприємство 2 працює в найближчому зарубіжжі (Україна, Білорусія) і обслуговується регіональним розподільчим центром. Є у підприємства на місцевому ринку (Москва і Московська область) свої клієнти - рітейлери, які отримують продукцію з міського розподільного центру. Запаси регіонального та міського розподільних центрів поповнюються з центрального розподільного центру.

Виділимо фрагмент розподільчої мережі:

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

Мережа розподілу виробничого підприємства

Мал. 4.22. Мережа розподілу виробничого підприємства

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

Граф мережі розподілу продукції представлений на рис. 4.23. Побудуємо матрицю D 0, в яку занесемо значення пропускних спроможностей ланок розподільної мережі (рис. 4.24).

Граф мережі розподілу виробничого підприємства

Мал. 4.23. Граф мережі розподілу виробничого підприємства

Пошук оптимального рішення: ітерація 1

Мал. 4.24. Пошук оптимального рішення: ітерація 1

З нульовою рядки відзначимо вершини (рядки-стовпці) 1, 2 і 3 індексами μ = 0 і V, рівними 30,10 і 10.

З поміченої рядка 1 відзначимо вершини 4 і 5 індексами μ = 1 і V4 = min (30,15) = 15, V5 = min (30,10) = 10.

З рядка 3 відзначимо вершину 6 і, нарешті, з рядка 4 - вершину 7 (рис. 4.25).

Пошук оптимального рішення: ітерація 2

Мал. 4.25. Пошук оптимального рішення: ітерація 2

Зворотним ходом по μ виявляємо шлях: до вершини 7 від 4, до вершини 4 від 1, до вершини 1 від 0; коригуємо елементи D 0 на величину потоку V7 = 15.

Черговий крок дає шлях [0-1-5-7] з потоком 5 (рис. 4.26).

Пошук оптимального рішення: ітерація 3

Мал. 4.26. Пошук оптимального рішення: ітерація 3

Наступний крок дає результат, представлений на рис. 4.27.

Пошук оптимального рішення: ітерації 4, 5 і 6

Мал. 4.27. Пошук оптимального рішення: ітерації 4, 5 і 6

Подальше відзначення неможливо. Звідси отримуємо матрицю максимального потоку (рис. 4.28).

Матриця максимального потоку

Мал. 4.28. Матриця максимального потоку

В результаті застосування алгоритму знаходження максимального потоку в мережі отримані результати, представлені на рис. 4.29. Пари чисел в дужках, показані на дугах графа, означають максимальну пропускну здатність дуги і рекомендований об'єм поставки товарів в мережу.

Результат розрахунку максимального потоку при розподілі продукції виробничого підприємства

Мал. 4.29. Результат розрахунку максимального потоку при розподілі продукції виробничого підприємства

 
<<   ЗМІСТ   >>