Імовірність беззупинкового проїзду).

На рис. 9.2 наведено схему мережі вулиць, якими пан Петренко щоденно їздить автомобілем з дому на роботу. Дана ділянка вулично- дорожньої мережі посилено контролюється нарядами ДАІ, і автомобіль Петренка часто зупиняють за перевищення швидкості. Тому пан Петренко планує розробити маршрут, на якому він би мав найбільшу ймовірність не бути зупиненим інспекторами ДАІ. Імовірність проїзду без зупинки для кожної вулиці наведено на схемі (рис. 9.2).

Імовірність не бути зупиненим на маршруті 1 — 2—…— m дорівнює добутку ймовірностей не бути зупиненим на кожній ділянці мережі, тобто

p_1,m= p_{12 *} p_{2j *} …_* p_jm

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

lnp_1m= lnp_{12 *} lnp_{2j *} …_*lnp_jm

Задача ймовірності p_1,m еквівалентна формулі максимізації задачі величини lnp_1m оскільки p_1,m ≤1 відповідно lnp_1m ≤ 0

 Таким чином задача максимізації логарифму lnp_1m еквівалентна задачі мінімізації величини (- lnp_1m). Замінивши імовірності p_ij на величини (- lnp_ij) отримаємо мережу до якої можна застосувати алгоритм пошуку найкоротшого шляху.

Для цієї нової мережі найкоротшим шляхом є шлях 1→3→5→7 з довжиною - lnp_{1 ,7} =1,1707 Тоді максимальна ймовірність не бути зупиненим становить p_{1 ,7} =0,0675.

Задача про максимальний потік.

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

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

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

Обмеження:

z є 1..n

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

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

xij>0

 Нехай мережа комунікацій задана у вигляді графа з одним джерелом G={N;A}; S є N (джерело) та одним виходом t є N. Множина вершин N складається з множини постачальників та транзитних вершин. Множина дуг А містить всі можливі комунікації (з’єднання) (i,j) є A, які мають обмежену пропускну здатність. Задача про пошук максимального потоку, полягає в пошуку таких потоків, по дугах (i,j) є A, щоб результуючий потік з джерела S до стоку t був максимальним. В такому випадку будемо вважати, що до джерела може надійти не обмежений потік (вантаж, ресурси) і для кожного проміжного вузла мережі буде виконуватися умова збереження потоку, а пропускна спроможність Cij кожної дуги являє собою скінченну верхню межу потоку fij по цій дузі

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

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

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

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

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

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

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

Обмеження:

z є 1..n

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

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

xij>0

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

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

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

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

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

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

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

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

⇐ Предыдущая12

Поделиться: