Page 87 - 6449

Найбільш простим способом розв’язання сформульованої задачі є

процедура повного перебору. Вказана задача має 4 * 5 * 4  80 можливих
розв’язків, причому деякі з них є недопустимими, оскільки вони
передбачають вкладення капіталів у сумі, більшій за 6 млн. Процедура
повного перебору має такі суттєві недоліки:
– кожна комбінація проектів визначає деякий розв’язок задачі в
цілому, звідки випливає той факт, що перебір всіх можливих комбінацій в
задачах середньої та великої розмірності може бути пов’язаний з
надзвичайно великим обсягом обчислень;
– відсутня апріорна інформація про розв’язки, які не є
допустимими, що знижує ефективність обчислювальної процедури
повного перебору;
– інформація, одержана в результаті аналізу деяких комбінацій
проектів, в подальшому не використовується для виявлення та виключення

неоптимальних комбінацій.

4.2 Сіткова модель
Вважатимемо, що вкладення капіталу на реалізацію кожного з
проектів виражається цілими числами – в даному випадку в кожне з
підприємств вкладати можна 0; 1; 2; 3; 4; 5; 6 млн. у.о. Кожному з
підприємств ставиться у відповідність деякий етап, етапи пов’язані між
собою обмеженням на сумарну величину капіталовкладень. Вводяться
наступні визначення для змінних:
– X – обсяг капіталовкладень, розподілений на етапі
1
X  0,1,2,3,4, 5,6 ;
1
– X – обсяг капіталовкладень, розподілений на етапах 1 та 2;
2
X  0,1,2,3,4, 5,6;
2
– X – обсяг капіталовкладень, розподілений на етапах 1, 2 та 3;
3
X  6.
3
Використовуючи вказані змінні, можна побудувати сіткову модель

(рис. 4.1). Зауважимо, що X  6 , оскільки після реалізації третього етапу
3
всі кошти повинні бути реалізовані. Для кожного етапу введемо
позначення:
– fj(xj) – оптимальне значення прибутку при певному значенні

змінної xjна етапі номер j ;
– Rj(xj - 1, xj) – вартість переходу від значення змінної x 1 - j на етапі

1 - j .
Враховуючи введені позначення, запишемо рівняння динамічного
програмування:

f (x )  max f (x )  R (x , x  ) . (4.1)
j j j 1 j 1  j j 1 j
x j 1 ,x j

87