У n-вимірному узагальненні задачі обмеження (16.5) замінюється на систему обмежень

Отже отримуємо математичну модель у вигляді

F = с_і x_i ® max, (16.4)

а_і x_i £ а, (16.5)

x_i ³ 0, - ціла, і = 1, n. (16.6)

а_іj x_i £ а_j, j = 1, m,

коли врахувуються обмеження не тільки на сумарну вагу, а наприклад, ще на сумарний об’єм та деякі інші параметри.

Задачу (16.4) - (16.6) можна розв’язати методом цілочисельного програмування, але більш ефективним виявляється застосування методу динамічного програмування.

Як і у випадку застосування методу гілок та меж не існує універсального засобу переходу від практичної задачі до моделі динамічного програмування. Ефективність застосування залежить від того, наскільки вдало визначені стани системи та організований перехід від значень цільової функції на простих траекторіях до значень на більш складних.

Уведемо функцію Y_k(m), що дорівнює значенню цільової функції для оптимального завантаження рюкзака при використанні перших k типів предметів і при умові, що сумарна вага предметів у рюкзаку не перебільшує m. Якщо m = 0, то Y_k(m) = 0, k = 0, n, оскільки нульове обмеження на сумарну вагу предметів не дозволяє покласти у рюкзак жодний предмет. Аналогічно, при k = 0 Y_k(m) = 0, m = 0, а. Отже Y_k(0) = 0, " k і Y₀(m) = 0, " m, що відповідає відомим значенням F(i) у (16.3).

Рівняння динамічного програмування для поданої задачі можна записати у вигляді

Y_k(m) = max {Y_k-1(m), c_k + Y_k(m - a_k)}, якщо m ³ a_k, (16.7)

Y_k(m) = Y_k-1(m), якщо m < a_k. (16.8)

Дійсно, при оптимальному завантаженні рюкзаку предметами перших k типів при обмеженні сумарної ваги величиною m може бути два випадки: 1) предмет k-го типу не вибирався жодного разу; 2) предмет k-го типу вибирався хоча б один раз. У першому випадку, очевидно, Y_k(m) = Y_k-1(m). У другому випадку, коли вилучити з рюкзаку один предмет k-го типу, якому відповідає цінність c_k, то сумарна вага залишених у рюкзаку предметів обмежується величиною y - a_k. Очевидно, що залишені у рюкзаку предмети повинні утворювати оптимальне завантаження при вказанному обмеженні на сумарну вагу. Тому Y_k(m) = c_k + Y_k(m - a_k). Вибір кращого з перелічених двох варіантів і відображає формула (16.7). Формула (16.8) відповідає першому випадку.

Отримані рівняння (16.7), (16.8) показують, що починаючи із значень Y_k(0) та Y₀(m) і поступово збільшуючи значення k та m, можна отримати значення Y_n(a) = F_max. При обчисленні значень Y_k(m) будемо заповнювати таблицю A _{n x a}, кожний рядок якої відповідає певному значенню k, а стовпчик – m. На перетинанні k–го рядка та m–го стовпчика будемо записувати обчислене значення Y_k(m) (A(k, m) = Y_k(m)). Шукане значення Y_n(a) визначимо за порядком Y₁(1), Y₁(2), …, Y₁(a), Y₂(1), Y₂(2), …, Y₂(a), …, Y _n (1), Y _n(2), …, Y _n(a).

Після того, як величина Y _n(a) обчислена, необхідно знайти значення x_i, які визначають цю величину. Для того, щоб забезпечити можливість визначення x_i, одночасно з заповненням таблиці A будемо заповнювати ще одну таблицю B _{n x a}. Елементам цієї таблиці будемо присвоювати значення максимального типу предметів, що використані для отримання Y_k(m): B(k, m) = max{i | x_i > 0 }.

В результаті B(n, a) дорівнює типу предмету, що присутній у рюкзаку при оптимальному завантаженні. Якщо вилучити з рюкзаку предмет цього типу, сумарна вага залишених предметів не буде перебільшувати a – a_{B(n, a)} , і тому максимальний тип предмету, що залишився у рюкзаку дорівнює B(n, a – a_{B(n, a)}). Продовжуючи аналогічно доки не буде визначено, що максимальний тип залишених предметів дорівнює нулю або сумарна вага залишених предметів дорівнює нулю, можна визначити типи усіх предметів, покладених у рюкзак при оптимальному завантаженні. Кількість предметів кожного типу і визначає розв’язок задачі.

Значення B(k, m) обчислюються за правилом

B(k-1, m), якщо Y_k-1(m) > c_k + Y_k(m - a_k);

B(k, m) =

k, якщо Y_k-1(m) £ c_k + Y_k(m - a_k).

Важливою особливостю застосування методу динамічного програмування для розв’язування задачі про рюкзак є той факт, що для обчислення Y_k(m) (1£ m £ a) серед Y_l(m) (l < k) використовується тільки Y_k-1(m) (1£ m £ a), і це значення не використовується при обчисленні Y_p(m) (p > k). Отже, як тільки значення Y_k(m) обчислене, величина Y_k-1(m) для подальших обчислень не потрібна. Аналогічна ситуація має місце і при обчисленні елементів B(k, m). Після обчислення B(k, m) величина B(k-1, m) для подальших обчислень не потрібна. Вказана особливість при програмуванні методу дозволяє не зберігати одночасно у оперативній пам’яті усі елементи таблиць A та B.

Розглянемо приклад розв’язування задачі про рюкзак методом динамічного програмування. Нехай у рюкзак відбираються предмети чотирьох типів, і сумарна вага предметів у рюкзаку не повинна перебільшувати 10. Значення ваги предмету кожного типу і цінності показані у табл.16.1.

Таблиця 16.1

Тип предмету	Вага	Цінність

Математична модель для поданого прикладу має вигляд

F = 1x₁ + 3x₂ + 5x₃ + 9x₄ max,

2x₁ + 3x₂ + 4x₃ + 7x₄ £ 10.

Послідовність обчислень елементів таблиць А та В має такий вигляд.

А(1, 1) = Y₁ (1) = 0; В(1, 1) = 0;

А(1, 2) = Y₁ (2) = max{Y₀(2), с₁ + Y₁ (2-2)} = max{0, 1 + 0} = 1; В(1, 2) = 1;

А(1, 3) = Y₁ (3) = max{Y₀(3), с₁ + Y₁ (1)} = max{0, 1 + 0} = 1; В(1, 3) = 1;

А(1, 4) = Y₁ (4) = max{Y₀(4), с₁ + Y₁ (2)} = max{0, 1 + 1} = 2; В(1, 4) = 1;

А(1, 5) = Y₁ (4) = max{Y₀(5), с₁ + Y₁ (3)} = max{0, 1 + 1} = 2; В(1, 5) = 1;

А(1, 6) = Y₁ (4) = max{Y₀(6), с₁ + Y₁ (4)} = max{0, 1 + 2} = 3; В(1, 6) = 1;

А(1, 7) = Y₁ (4) = max{Y₀(7), с₁ + Y₁ (5)} = max{0, 1 + 2} = 3; В(1, 7) = 1;

А(1, 8) = Y₁ (4) = max{Y₀(8), с₁ + Y₁ (6)} = max{0, 1 + 3} = 4; В(1, 8) = 1;

А(1, 9) = Y₁ (4) = max{Y₀(9), с₁ + Y₁ (7)} = max{0, 1 + 3} = 4; В(1, 9) = 1;

А(1, 10) = Y₁ (4) = max{Y₀(10), с₁ + Y₁ (8)} = max{0, 1 + 1} = 5; В(1, 10) = 1;

А(2, 1) = Y₂ (1) = 0; В(2, 1) = 0;

А(2, 2) = Y₂ (2) = Y₁ (2) = 1; В(2, 2) = В(1, 2) = 1;

А(2, 3) = Y₂ (3) = max{Y₁(3), с₂ + Y₂(0)} = max{1, 3 + 0} = 3; В(2, 3) = 2;

А(2, 4) = Y₂ (4) = max{Y₁(4), с₂ + Y₂(1)} = max{2, 3 + 0} = 3; В(2, 4) = 2;

А(2, 5) = Y₂ (5) = max{Y₁(5), с₂ + Y₂(2)} = max{2, 3 + 1} = 4; В(2, 5) = 2;

А(2, 6) = Y₂ (6) = max{Y₁(6), с₂ + Y₂(3)} = max{3, 3 + 3} = 6; В(2, 6) = 2

А(2, 7) = Y₂ (7) = max{Y₁(7), с₂ + Y₂(4)} = max{3, 3 + 3} = 6; В(2, 7) = 2;

А(2, 8) = Y₂ (8) = max{Y₁(8), с₂ + Y₂(5)} = max{4, 3 + 4} = 7; В(2, 8) = 2;

А(2, 9) = Y₂ (9) = max{Y₁(9), с₂ + Y₂(6)} = max{4, 3 + 6} = 9; В(2, 9) = 2;

А(2, 10) = Y₂ (10) = max{Y₁(10), с₁ + Y₂(7)} = max{5, 3 + 6} = 9; В(2, 10) = 2;

А(3, 1) = Y₃ (1) = 0; В(3, 1) = 0;

А(3, 2) = Y₃(2) = Y₂(2) = 1; В(3, 2) = 1;

А(3, 3) = Y₃(3) = Y₂(3) = 3; В(3, 3) = 2;

А(3, 4) = Y₃(4) = max{Y₂(4), с₃ + Y₃(0)} = max{3, 5 + 0} = 5; В(3, 4) = 3;

А(3, 5) = Y₃(5) = max{Y₂(5), с₃ + Y₃(1)} = max{4, 5 + 0} = 5; В(3, 5) = 3;

А(3, 6) = Y₃(6) = max{Y₂(6), с₃ + Y₃(2)} = max{6, 5 + 1} = 6; В(3, 6) = 3;

А(3, 7) = Y₃(7) = max{Y₂(7), с₃ + Y₃(3)} = max{6, 5 + 3} = 8; В(3, 7) = 3;

А(3, 8) = Y₃(8) = max{Y₂(8), с₃ + Y₃(4)} = max{7, 5 + 5} = 10; В(3, 8) = 3;

А(3, 9) = Y₃(9) = max{Y₂(9), с₃ + Y₃(5)} = max{9, 5 + 5} = 10; В(3, 9) = 3;

А(3, 10) = Y₃(10) = max{Y₂(10), с₃ + Y₃(6)} = max{9, 5 + 6} = 11; В(3, 10) = 3;

А(4, 1) = Y₄(1) = 0; В(4, 1) = 0;

А(4, 2) = Y₄(2) = Y₁ (2) = 1; В(4, 2) = В(3, 2) = 1;

А(4, 3) = Y₄(3) = Y₃(3) = 3; В(4, 3) = 2;

А(4, 4) = Y₄(4) = Y₃(4) = 5; В(4, 4) = 3;

А(4, 5) = Y₄(5) = Y₃(5) = 5; В(4, 5) = 3;

А(4, 6) = Y₄(6) = Y₃(6) = 6; В(4, 6) = 3

А(4, 7) = Y₄(7) = max{Y₃(7), с₄ + Y₄(0)} = max{8, 9 + 0} = 9; В(4, 7) = 4;

А(4, 8) = Y₄(8) = max{Y₃(8), с₄ + Y₄(1)} = max{10, 9 + 0} = 10; В(4, 8) = 3;

А(4, 9) = Y₄(9) = max{Y₃(9), с₄ + Y₄(2)} = max{10, 9 + 1} = 10; В(4, 9) = 4;

А(4, 10) = Y₄(10) = max{Y₃(10), с₄ + Y₄(3)} = max{11, 9 + 3} = 12; В(4, 10) = 4;

В результаті отримуємо таблиці у вигляді

Таблиця А

k m

Таблиця B

k m

Оскільки В(4, 10) = 4, у оптимальному завантаженні рюкзака є предмет типу 4. Вилучивши цей предмет, отримуєму обмеження на сумарну вагу залишених предметів 10 – 7 = 3. Тому переходимо до елементу В(4, 3), який дорівнює 2. Це означає, що у рюкзаку є предмет типу 2. Після вилучення цього предмету отримуємо, що сумарна вага залишених предметів не перебільшує 3 – 3 = 0, і процес визначення розв’язку припиняється. Таким чином, отримуємо розв’язок x₁ = 0, x₂ = 1, x₃ = 0, x₄ = 1, і максимальне значення цільової функції F_max = 0 + 3 x 1 + 5 x 0 + 9 x 1 = 12.

У розглянутому прикладі при побудові таблиць А та В розглядалися усі цілі значення від 1 до 10. У тому разі, коли значення ваги типів предметів мають найбільший спільний дільник d > 1, достатньо обчислювати Y_k(m) лише для m кратних d. Наприклад, якщо кожне значення ваги – парне число, таблиці А та В повинні містити лише стовпці, що відповідають парним числам.

Метод динамічного програмування, як і метод гілок та меж, належить до групи методів послідовного аналізу варіантів. Можна вважати, що ці методи реалізують дві протилежні стратегії пошуку розв’язку. У методі гілок та меж від вихідної задачі шляхом розбиття допустимої області відбувається перехід до більш простих підзадач, доки не буде отримано підзадачу з тривіальним розв’язком. Таку стратегію можна віднести до групи стратегій “зверху униз”.

У методі динамічного програмування, навпаки, процес пошуку розв’язку починається з розглядання підзадач з тривіальним розв’язком. Підзадачі з відомим розв’язком поступово ускладнюються, доки не буде отримано розв’язок вихідної задачі. Такий підхід можна розглядати як стратегію “знизу угору”.

Дата добавления: 2014-01-13