на ряд можливих кроків, на кожному з яких вартість будівництва відома. Кожен крок будівництва є прокладкою шляху між двома поруч розташованими вузлами. Всі вузли пронумеровані, і у відповідності з номером варіанту дана вартість спорудження елемента шляху між вузлами.
Вихідні дані - ( варіант 67 ). p> Рішення:
Задачу вирішуємо методом динамічного програмування, послідовно рухаючись від кінця траси до її початку, при цьому на кожному кроці процесу вибираючи той напрямок траси, яке дає меншу вартість її будівництва від розглянутого пункту до пункту В (Рис. 2). <В
Рис. 2
Відповідь: Мінімальні витрати на спорудження ділянки А - В складуть W = 131 ден.ед.
Задача № 5
Задача оптимального розподілу ресурсів.
Завдання ( варіант 67 ):
Підприємство має вільних До млрд. руб. коштів, які воно може вкласти в п'ять різних виробничих програм. При цьому прибуток від кожної з програм залежить від обсягу інвестицій. Ці залежності f i відомі і мають наступний вигляд:
f (х) = bx - ax 2
і конкретно:
f 1 (х 1 ) = 0,18 x 1 - 0,05 x 1 2 ;
f 2 (х 2 ) = 0,16 x 2 - 0,04 x 2 2 ;
f 3 (х 3 ) = 0,14 x 3 - 0,02 x 3 2 ;
f 4 (х 4 ) = 0,12 x 4 - 0,02 x 4 2 ;
f +5 (х +5 ) = 0,1 x +5 - 0,01 x +5 2 млрд.руб.
де х 1 , х 2 , х 3 , х 4 , х 5 - інвестиції в програми, млрд.руб. Їх загальний обсяг дорівнює К = 8,5 млрд.руб. p> Потрібно знайти невід'ємні обсяги інвестицій х 1 , х 2 , х 3 , х 4 , х 5 відповідні найбільшою загального прибутку
П = f 1 (х 1 ) + f 2 (х 2 ) + f 3 (х 3 ) + F 4 (х 4 ) + f 5 (х 5 ). br/>
Рішення:
Можливі наступні варіанти:
1) Всі кошти передаються першій програмі;
2) Засоби розподіляються між першою і другою програмами;
3) Засоби розподіляються між першою, другою та третьою програмами;
4) Засоби розподіляються між першою, другою, третьою і четвертою програмами;
5) Засоби розподіляються між першою, другою, третьою, четвертою та п'ятою програмами.
Розглянемо всі 5 варіантів.
1) До 1 = х 1 = 8,5
П 1 = f 1 (х 1 ) = 0,18 8,5 - 0,05 8,5 2 = - 2,08 млрд.руб. <0, слідів-але збиток. p> 2) До 2 = х 1 + Х 2
П 2 = f 1 (х 1 ) + f 2 (х 2 )
0,18 - 2 0,05 х 1 = 0,16 - 2 0,04 х 2
х 1 + х 2 = 8,5
0,1 х 1 - 0,08 х 2 = 0,02
х 1 = 8,5 - х 2 p> 0,1 (8,5 - х 2 ) - 0,08 х 2 = 0,02
0,85 - 0,1 х 2 - 0,08 х 2 = 0,02
0,85 - 0,18 х 2 = 0,02
0,18 х 2 = 0,83
х 2 = 4,61
х 1 = 8,5 - 4,61 = 3,89
П 2 = 0,18 В· 3,89 - +0,05 3,89 2 + 0,16 4,61 - 0,04 4,61 2 = 0,7 - 0,757 + 0,738 - 0,85 = - 0,169 млрд.руб. <0, слідів-але збиток. br/>
3) До 3 = х 1 + Х 2 + х 3
П 3 = f 1 (х 1 ) + f 2 (х 2 ) + f 3 (х 3 )
0,18 - 0,1 х 1 = 0,16 - 0,08 х 2
0,16 - 0,08 х 2 = 0,14 - 2 В· 0,02 х 3
х 1 + х 2 + Х 3 = 8,5
0,18 - 0,1 х 1 = 0,16 - 0,08 х 2
0,16 - 0,08 х 2 = 0,14 - 0,04 х 3
х 1 + х 2 + Х 3 = 8,5
0,1 х 1 - 0,08 х 2 = 0,18 - 0,16 В· 50
0,08 х 2 - 0,04 х 3 = 0,16 - 0,14
х 1 + х 2 + Х 3 = 8,5
5х 1 - 4х 2 = 1 (1)
4х 2 - 2х 3 = 1 (2)
х 1 + х 2 + Х 3 = 8,5 (3)
З 2 - го ур - ия: х 3 = 2х 2 - 0,5
<...
