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

Постановка задачі

  1. I. ЗАВДАННЯ АРТИЛЕРІЇ
  2. I. Мета і завдання дисципліни
  3. II. Основні завдання та їх реалізація
  4. VII. Шматки ТА ЗАВДАННЯ
  5. А. Умова завдання
  6. А. Умова завдання.
  7. А. Умова завдання.

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

Формулювання завдання має наступний вигляд:

задана мережа - G = {N, A}; для всіх дуг з A визначена узагальнена вартість cij проходження одиниці потоку по дузі, яка в реальних задачах залежно від обраного критерію оптимальності може бути або часом виконання будь-яких процесів в моделюється об'єкті, або відстанню, або величиною, що має грошовий вираз і пов'язаної з вартістю. Для фіктивних дуг, які задають тільки послідовність вузлів, cij = 0, для пари вузлів i и j, Не поєднаних дугою, cij = .

Інтенсивності витоку і стоку: ds = 1, dr = -1; для інших вузлів мережі

d = 0.

Потрібно знайти ланцюг [s, ..., r] З оптимальною (мінімальної або максимальної) сумарною узагальненої вартістю csr усіх, хто входив в неї дуг.

Це завдання може бути представлена, як завдання дискретного програмування:

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



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

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

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