Контрольні завдання. Розв’язати задачу знаходження найкоротшого шляху від вершини 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. ЗАДАЧА ПРО ОПТИМАЛЬНЕ ВИКОРИСТАННЯ РЕСУРСУ

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

,

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

,

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

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

4.1 Змістовна інтерпретація задачі про оптимальне використання ресурсу

4.1.1 Нехай маємо деяке підприємство, що випускає n видів продуктів і використовує для цього один ресурс.

Нехай - об’єм виробництва продукту . При виробництві одиниць j- го продукту ресурс споживається в кількості , а прибуток становить одиниць. Об'єми випуску продукції обмежені величинами . Визначити ассортимент випуску продукції, при якому сумарний прибуток максимальний і витрачається не більше одиниць ресурсу.

Відзначимо, що класична задача про рюкзак (ранець) є частковим випадком ЗОВР.

4.1.2 На початку фінансового року керівництво фірми ухвалює рішення щодо модернізації n підприємств, на що виділяється одиниць вартості. Кожне підприємство подає на розгляд проекти модернізації , які характеризуються величинами необхідних інвестицій () і прибутками від них (). Нульові проекти відповідають рішенню не проводити модернізацію підприємств. Мета фірми полягає в одержанні максимального прибутку від інвестицій.

Дата добавления: 2014-11-29