- •Конспект лекцій
- •Вінниця - 2010 вступ
- •1. Логістика в ринковій економіці
- •1.1. Еволюція концепції логістики
- •1.2. Логістика як науковий напрямок
- •1.3. Розвиток логістики
- •Класифікація форм логістичних утворень
- •2.1. Поняття терміна «логістика»
- •2.2. Види логістики
- •3. Характеристика основних елементів логістики
- •3.1. Цілі логістики
- •3.2. Задачі логістики
- •3.3. Вимоги і функції логістичного управління
- •3.4. Основні підходи і методи, що застосовуються в логістиці
- •4. Технологічні процеси та управління матеріальними потоками
- •4.1. Матеріальний потік і його характеристики
- •4.2. Інформаційні потоки в логістиці
- •4.3. Логістичні операції і інші поняття в логістиці
- •5. Фпктори Формування логістичних систем
- •5.1. Сутність логістичних систем
- •5.2. Типи і види логістичних систем
- •5.3. Розробка логістичних систем
- •5.4. Логістичні ланцюга і логістичні ланки
- •6. Види логістики
- •6.1. Заготівельна логістика
- •6.2. Розподільча логістика
- •6.3. Внутрішньовиробнича логістика
- •6.4. Логістика посередництва
- •6.5. Логістика складування
- •7. Управління иатеріальними потоками в логістичних системах
- •1. Математичні методи побудови макрологістичних моделей
- •1.1. Загальні відомості про потокові моделі
- •1.1.1. Задачі, які розв’язуються методами теорії потоків
- •1.1.2. Основні поняття та означення теорії потоків
- •1.1.3. Теорема про максимальний потік (теорема Форда-Фалкерсона)
- •Стверджується, що кінцева вершина
- •1.1.4. Задачі теорії потоків і лінійного програмування
- •Причому змінні мають довільні знаки, а змінні
- •1.2. Основні алгоритми теорії потоків
- •1.2.1. Алгоритми визначення максимального потоку
- •1.2.2. Угорський алгоритм
- •2. Математичні моделі оптимізації пропускних спроможностей і потоків на мережах
- •2.1. Загальні положення
- •2.2. Задача вибору пропускних спроможностей
- •2.3. Зворотня задача вибору пропускних спроможностей
- •2.4. Задача розподілу потоків
- •Додаток 2
- •Розв’язком задачі пошуку екстремуму (д. 1) буде розв’язок системи
- •8.Прикладні задачі галузевої логістики
- •1. Керування виробничими і торгівельними запасами
- •1.1. Модель економічного розміру партії поставки
- •1.2. Знаходження оптимального розміру партії поставки з урахуванням можливого дефіциту запасів
- •1.3. Випадковий попит. Збитки із-за надлишку або нестачі запасів
- •1.4. Визначення груп запасів по методу авс і xyz
- •Ідентифікація об'єктів керування, що аналізуються методом авс
- •Оцінка об'єктів керування по виділеній класифікаційній ознаці
- •Визначення коефіцієнтів варіації
- •Побудови кривої xyz Поділ сукупності об'єктів керування
- •2. Практичні задачі логістики складування
- •2.1. Управління матеріальними потоками на основі поопераційного обліку логістичних витрат
- •Зона зберігання – головне приміщення складу з єдиною матеріальною відповідальністю
- •Ділянка приймання
- •2.2. Визначення розмірів технологічних зон складу
- •3. Площі ділянок приймання і комплектування (Sпр і Sком)
- •4. Площа робочих місць (Sрм )
- •5. Площа приймальної експедиції (Sпе)
- •6. Площа відправної експедиції (Sев)
- •2.3. Розрахунок точки беззбитковості діяльності складу
- •2.4. Ухвалення рішення про користування послугами найманого складу
- •2.5. Визначення місця розташування розподільчого складу на території, що обслуговується
1.2. Основні алгоритми теорії потоків
1.2.1. Алгоритми визначення максимального потоку
На підставі властивостей двоїстості задач лінійного програмування, як це показано в попередніх розділах, можливо визначити максимальний потік в мережі. Однак більш простішим є алгоритм Форда-Фалкерсона.
Розглянемо алгоритм отримання максимального потоку з любого початкового потоку. Ця процедура складається з двох операцій: операції А – процесу розташування поміток в вершинах мережі (графу) і операції В – зміни потоку. В наявності є кілька модифікацій методу поміток, в які закладена одна і та ж ідея: шляхом певної системи поміток визначаються ланцюги (шляхи), які не містять насичених дуг. Помітка починається з джерела (початку) х0, яка помічається індексом 0, тобто . Нехай задана вже помічена вершина хі (рис. 6). Якщо для деякої поміченої вершини хі є суміжна вершина хj, яка з’єднується з нею насиченою дугою, то остання вершина не помічається (рис. 6, а). Якщо слідуючи вершина з’єднана з поміченою хі дугою зі значенням потоку , то вершина хj помічається знаком +і, тобто (рис. 6, б).
Якщо вершина хj пов’язана з хі з позитивним нульовим потоком , то вона позначається знаком -і, тобто (рис. 6, в). Таким чином, не помічаються такі вершини, які з’єднані з поміченою суміжною вершиною хі виходячи з неї насиченою дугою, або дугою з нульовим потоком, що входить в неї (рис. 6, г).
Ясно, що потік в мережі можна збільшити за рахунок збільшення потоків в дугах, що закінчуються вершинами, поміченими знаком "+" і зменшення потоків дугах, що закінчуються в вершинах, помічених знаком "–". На рис. 7 наведено приклад поміченого шляху.
Рис. 7. Приклад поміченого шляху
Припустимо, що процедурі помічення вершин, вдалося знайти такий шлях (всі вершини його помічені), що в нього попала кінцева вершина. Тоді така ситуація називається прорив (по одному із шляхів прорвалися до кінця). В протилежному випадку кажуть про не прорив. Це означає, що між початком х0 і кінцем хz є шлях , вершини якого помічені індексами попередніх вершин. Тоді можливо збільшити потік в мережі. Справді, так як знайдений шлях не містить в собі жодної прямої насиченої дуги, то можна змінити значення потоків на всіх дугах цього шляху на величину
,
причому потік на дузі збільшується на h, якщо орієнтація дуги співпадає з напрямком від х0 до хz і зменшується на в протилежному випадку. Після цього отримуємо новий потік, збільшений на величину h. Далі всі помітки на вершинах графу зтираються і процедура повторюється спочатку. Цей процес повторюють до тих пір, доки неможливо знайти жодного шляху , тобто до не прориву. На цьому останньому кроці ми отримуємо максимальний потік. Слід зауважити, що існують і інші форми запису алгоритму, наприклад [28]. Початкова вершина помічається . Суміжна наступна вершина хj помічається , якщо
,
де . (2.1)
або ця вершина помічається , якщо , де
. (2.2)
Процедуру отримання максимального потоку рекомендується починати з нульового значення потоку.
Приклад. Визначимо максимальний потік в мережі, яка наведена на рис... Біля кожної дуги проставлена її пропускна спроможність. Послідовний процес розв’язку наводиться в таблиці.
В цьому простому прикладі без особливої праці можна знайти шлях від х0 до z, який не містить насичених дуг. Таким є шлях . У відповідності з формулою (2.1) збільшуємо значення потоку на дугах цього шляху на 2 тоді дуга стає насиченою (в табл. це відмічено рискою зверху). Відповідні значення потоку наведені в третьому стовпчику табл. На другій ітерації вибираємо другий шлях , вільний від насичених дуг.
Таблиця
Дуги |
|
|
|
|
|
0 |
2 |
|
|
|
0 |
0 |
0 |
2 |
|
0 |
2 |
2 |
2 |
|
0 |
0 |
3 |
3 |
|
0 |
0 |
0 |
2 |
|
0 |
0 |
0 |
0 |
|
0 |
2 |
2 |
2 |
|
0 |
0 |
3 |
5 |
Рис. 8 Пояснення до прикладу
Змінюємо (збільшуємо) значення потоку на . Сумарний потік наведений в четвертому стовпчику. На третій ітерації вибирається шлях , потік збільшується на 2. результати наведені в п’ятому стовпчику. Прорив з точки z більше ніяким чином здійснити неможливо. Отриманий потік є максимальним зі значенням Ф=7.
Приклад. Проілюструємо метод поміток вершин на прикладі мережі, що наведена на рис. 9, а. Джерелу х0 надаємо мітку . Далі, вершині х2 надаємо мітку . Це єдина вершина, яку можна помітити, починаючи з х0, тому що дуга (х0, х1) є насиченою. Продовжуючи процес з х2 можемо помітити вершину х1 двома способами: або . Настав прорив, рис. 9, б. Вздовж розглянутого шляху значення . Змінюємо на це значення потоки на дугах. Отримуємо новий потік зі значенням сумарного потоку на кінцевих дугах 2 (замість початкового, який дорівнював 1), який представлений на рис. 9, в. Далі знов проходить прорив вздовж шляху . Після зміни потоків на маємо потік, який наведений на рис. 9, г, з максимальним значенням потоку на кінцевих дугах 3. мінімальний розріз складається з дуг .
Рис. 9 Пояснення до прикладу.