Главная Прочие дисциплины Книги Математичне програмування - Наконечний С.І.

Математичне програмування - Наконечний С.І.

5.9. Розв’язування транспортної задачі на мережі

Серед сучасних методів оптимізації і керування виробничими процесами значна роль належить мережевим методам. Широке коло задач математичного програмування можна подати в мережевому вигляді. Особливо це стосується транспортних задач, які мають цілком природну інтерпретацію як мережеві задачі, бо вони пов’язані з певною мережею транспортних маршрутів (доріг, залізничних, водяних шляхів, маршрутів повітряних трас, трубопроводів тощо). У цьому параграфі буде розглянуто кілька типових мережевих задач математичного програмування.

Назвемо графом будь-яку систему відрізків (прямолінійних чи криволінійних), у певний спосіб з’єднаних між собою (рис. 5.2).

Названі відрізки, якщо їм приписано напрям, називаються дугами графа; надалі позначатимемо їх , наприклад: — відрізок, що з’єднує точку 1 з точкою 2 (рис. 5.2).

Точки, що є кінцями або початками дуг графів, в яких можуть з’єднуватись дві дуги або більше, називаються вершинами графа: кожна з вершин позначається певним номером (натуральним числом: 1, 2, 3, 4, ...), наприклад, точки 1, 2, 3, — вершини (рис. 5.2).

Отже, кожній дузі відповідає впорядкована пара вершин , де перший індекс і означає початок дуги (вхід), другий індекс j — кінець дуги (вихід); тим самим задано орієнтацію (напрям) дуги, що геометрично зображається стрілкою в напрямі від початку до кінця дуги.

Дуги та називаються симетричними, або взаємними, наприклад: (2, 4) і (4, 2).

Ребром (або ланкою) графа називається ненапрямлений відрізок, що зображає дугу. Позначимо ребра символами , наприклад [5, 7] — ребро; тоді як для відповідних дуг ця рівність не справджується: .

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

Такими параметрами можуть бути, наприклад, пропускні здатності шляхів, величини запасів чи потреб у певних пунктах — вершинах графа тощо.

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

Шлях зручно позначати послідовністю вершин, через які він проходить, тобто . Прикладом шляху є послідовність таких дуг (1, 2), (2, 3), (3, 5) або (1,2, 3, 5).

Контуром називається шлях, початкова вершина якого збігається з кінцевою, наприклад (1, 2), (2, 3), (3, 5), (5, 1) = (1, 2, 3, 5, 1).

Граф називається сильно (чи міцно) зв’язаним, якщо будь-які його вершини і і j можна з’єднати шляхом, що йде з і в j.

Якщо в означеннях шляху, контуру і сильної зв’язаності графа поняття дуги замінити поняттям ребра, то дістанемо означення ланцюга, циклу і зв’язаності графа.

Легко збагнути, що ребра дуг, які утворюють шлях і контур, завжди утворюють відповідно ланцюг і цикл, проте зворотне твердження не справджується. Це саме стосується і зв’язаності: зв’язаний граф не обов’язково буде міцно зв’язаним.

Ланцюг і цикл позначають аналогічно до шляху і контуру, проте замість круглих використовують квадратні дужки, наприклад, ланцюг [1, 2], [2, 3], [3, 4], [4, 6], або [1, 2, 3, 4, 6]; цикл [1, 2], [2, 3], [3, 4], [4, 6], [6, 1], або [1, 2, 3, 4, 6, 1]; відповідні послідовності дуг не завжди є шляхами чи контурами.

Деревом називається граф, який не має циклів і в якому кожна вершина зв’язана з будь-якою іншою деяким ланцюгом ребер.