Дати означення поняттям «граф», «шлях», «дерево».

Дати означення поняттям «граф», «шлях», «дерево».

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

Шляхом, що з’єднує вершини A і B, називається сукупність ребер, початком першого з яких є вершина A, а кінцем останнього – вершина B  

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

Приклади задач, які можна подати у вигляді мережевих моделей.

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

Побудувати мінімальне кістякове дерево для графа, наведеного на

Рисунку (3 ітерації).

Побудувати мінімальне кістякове дерево для графа, наведеного на

Рисунку (3 ітерації).

Формалізація задачі пошуку найкоротшого шляху як задачі

Лінійного програмування.

Нехай мережа складається з n вузлів і потрібно знайти найкоротший шлях між двома вузлами s і t цієї мережі.

Припустимо, що у вузол s входить одиниця зовнішнього потоку, і цей потік виходить через вузол .t Позначимо

Xij– величина потоку, що проходить по дузі (i, j);

Cij – довжина дуги (i, j);

Оскільки лише одна одиниця потоку може пройти через будь-яку дугу в кожен момент часу, то змінні Xij можуть приймати значення 0 або 1. При цих позначеннях цільову функцію, яку потрібно мінімізувати:

Для кожного вузла визначається лише одне обмеження, що задає баланс потоку, який проходить через даний вузол:

загальний вхідний потік = загальний вихідний потік.

Варто відзначити, що одне обмеження завжди є зайвим, тобто будь-яке обмеження можна отримати з інших n-1 обмежень.

Використання задачі пошуку найкоротшого шляху для

Розв’язування задачі про заміну обладнання.

7. Розв’язування задачі про найбільш надійний маршрут (ваги дуг –

Визначити максимальний потік в мережі та пропускну здатність 4

Насосної станції для мережі, наведеної на рисунку (число біля дуги

– величина потоку по дузі).

Формалізація задачі про максимальний потік як задачі лінійного

Програмування.

 по наявних дугах з вузла S               

F  по наявних дугах з вузла Е

Обмеження:

z є 1..n

до вузла z     з вузла z

xij≤ dij — на пропускну здатність

xij>0

Припустимо, що потрібно знайти максимальний потік між початковим вузлом s та кінцевим вузлом t. Позначимо:

Xij– величина потоку, що проходить по дузі (i,j );

Cij– пропускна здатність цієї дуги.

Для кожного проміжного вузла записується обмеження, що задає баланс потоку, який проходить через даний вузол:

загальний вхідний потік = загальний вихідний потік.

Для кожної дуги записується обмеження, що потік не перевищує пропускної здатності дуги та є невід’ємним:

0 ≤ потік по дузі ≤ пропускна здатність дуги.

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

Найменшої вартості.

Дати означення поняттям «граф», «шлях», «дерево».

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

Шляхом, що з’єднує вершини A і B, називається сукупність ребер, початком першого з яких є вершина A, а кінцем останнього – вершина B  

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

12Следующая ⇒

Поделиться: