Контрольні завдання. Розв’язати задачу знаходження найкоротшого шляху від вершини A до вершини N у спрямованій ациклічній мережі

Розв’язати задачу знаходження найкоротшого шляху від вершини A до вершини N у спрямованій ациклічній мережі, зображеній на рис. 18. Довжини дуг наведені у табл. 3.

Рис. 18

Таблиця 3

Варі-ант

Довжина дуги

a1

a2

a3

b1

b2

c1

c2

c3

c4

d1

d2

e1

e2

f1

f2

Продовження таблиці 3

Варі-ант

Довжина дуги

g1

g2

h1

h2

i1

i2

i3

j1

j2

j3

k1

l1

m1

4. ЗАДАЧА ПРО ОПТИМАЛЬНЕ ВИКОРИСТАННЯ РЕСУРСУ

Розглянемо наступну задачу дискретного програмування:

,

при обмеженнях ,

,

де і додатні цілі числа, функції – невід’ємні і приймають цілі значення, причому ; – довільні функції, такі, що .

Дана задача називається задачею про оптимальне використання ресурсу (ЗОВР).