Головна Логістика
Проектування логістичних систем
|
|
|||||
Завдання про максимальний потік (в мережевий постановці)Аналіз транспортних мереж призводить і до ряду інших спеціальних завдань, що укладаються в рамки лінійного програмування. Ці завдання, з одного боку, мають великий самостійний практичний інтерес, що буде видно при їх розгляді; з іншого боку, використання методів їх вирішення виявляється корисним при розробці методів вирішення транспортної задачі на мережі. Розглянемо транспортну мережу, що має один пункт виробництва Величину р назвемо величиною потоку. Ця величина показує, скільки продукту вивозиться з пункту Складемо останню рівність з усіма равенствами (4.25) і (4.26). Неважко бачити, що ліва частина отриманого рівності звертається в нуль, так як для будь-якого числа Отже, з пункту Пункт P N носить назву "стік". Завданням про максимальний потік називається задача відшукання потоку найбільшої величини з пункту Назвемо спрямованим маршрутом з пункту Завдання про максимальний потік має сенс розглядати тільки в тому випадку, якщо існує хоча б один спрямований маршрут з пункту Іншою умовою, необхідною для існування максимального потоку, є наявність обмежених пропускних спроможностей у досить великого числа комунікацій. В іншому випадку потік може бути зроблений як завгодно великим. Завдання про максимальний потік легко узагальнюється на випадок, коли на транспортній мережі задається кілька пунктів В цьому випадку під потоком розуміється система перевезень, що задовольняє наступним умовам: Тут I - безліч номерів всіх пунктів транспортної мережі, за винятком пунктів Метод рішення задачі про максимальний потік розроблений американськими математиками Фордом і Фулкерсоном [11, 36, 38, 39]. |
<< | ЗМІСТ | >> |
---|