загрузка...
загрузка...
На головну

визначення

  1. III. Метод визначення платоспроможності фізичних осіб, розроблена Ощадбанком Росії.
  2. Quot; Коли проблема стає проблемою "або особистісні кореляти труднощів юнацького самовизначення
  3. Актуальний соціальний контекст проблеми юнацького самовизначення
  4. Алгоритм визначення кращою організаційної структури управління диверсифікованої фірми
  5. Алгоритм побудови дерева і визначення ймовірностей
  6. Алгоритм проведення біопроби (реакція нейтралізації на мишах) при діагностиці газової гангрени. Мета постановки цієї реакції для визначення виду збудника.
  7. Аналіз документів СМЯ аудиту проводять для визначення відповідності документів системи вимогам ГОСТ Р ІСО 9001.

 
 

 Мережею (графом) G може бути названий будь-який об'єкт, який можна представити як сукупність безлічі вузлів N і безлічі дуг A, Що з'єднують їх. G = {N, A}. Кожен елемент безлічі A є пара (i, j) Елементів безлічі N. Приклади графічного представлення мереж і задають їх множин см. Рис. 1.

Вузли також називають вершинами або точками, а дуги - ребрами, ланками, лініями або гілками. Граф G кінцевий, якщо кінцеві обидва задають його безлічі N и A.

Мережа (граф) G1, Що складається з вузлів і дуг, що входять в мережу G, Називають подграфом мережі G; тобто G1 = {N1, A1} - підграф G = {N, A}, якщо N1 N и A1 A. Найбільш просте уявлення мережі виходить, якщо використовувати в якості елементів {N} Натуральні числа - номери вузлів. Тоді кожна дуга характеризується парою чисел - номерами вузлів, які вона пов'язує.

Однак кожен вузол і дуга мережі характеризуються ще однією числовою величиною, сенс якої визначається в конкретних завданнях. У загальному випадку таке поставлене у відповідність вузла число називають його інтенсивністю d. Вузли називають джерелами (якщо d> 0), стоками (якщо d < 0) і нейтральними вузлами (якщо d = 0). Таким чином: N = {N+}  {N-}  {No}; N+ = {N: dn > 0}, N- = {N: dn < 0}, No = {N: dn = 0}.

Аналогічно, поставлене у відповідність дузі (i, j) Число тієї ж природи, що і інтенсивність вузла, називають пропускною спроможністю дуги rij.

потоком F = {fij : (I, j)  A} в мережі G називають сукупність величин fij - Потоків в дугах, що задовольняють співвідношенням:

fij - fji = di, i  N; 0 ? fij ? rij. (1)

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

cij fij ® opt (2)

при одночасному виконанні умов (1). В результаті ця задача набуває вигляду стандартної задачі лінійного (якщо cij = const), або нелінійного (якщо cij = F (fkl), (K, l) A) Програмування.

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

Метод - шлях, спосіб отримання рішення; сукупність прийомів, операцій, спрямованих на досягнення певної мети.

Алгоритм - послідовність чітко визначених правил (команд) для отримання рішення за кінцеве число кроків.

Будь алгоритм - метод; але не будь-який метод є алгоритмом.



Попередня   1   2   3   4   5   6   7   8   9   10   11   12   13   14   15   Наступна

Вступ | Теорема про максимальний потік і мінімальному розрізі | Ізоморфізм і гомеоморфизм графів. | Дерева і деревовидних | Матричні уявлення мереж | Постановка задачі | Алгоритм рішення (алгоритм Дейкстри) | приклад рішення | Приклади економічних задач, що зводяться до задачі про найкоротшою ланцюга | Алгоритм рішення (алгоритм Літтла) |

загрузка...
© um.co.ua - учбові матеріали та реферати