лькість програмних модулів. Поточне значення i відповідає ситуації розподілу наявних процесорів між першим, другим,., I-му програмними модулями.
Зокрема:
i=1 - відповідає ситуації розподілу всіх процесорів для реалізації тільки перших програмного модуля;
i=2 - передбачає розподіл процесорів між R 1 -м і R 2 -м програмними модулями;
i=3 - припускає розподіл процесорів між R 1 -м, R 2 -м і R 3 -м програмними модулями;
i=m - відповідає розподілу процесорів між усіма програмними модулями;
- стан - як стану вибирається поточна кількість процесорів D, що розподіляються між програмними модулями min {dij} DD0;
- управління - задає кількість процесорів, яке виділяється на i-му етапі для реалізації Ri-го програмного модуля. Таким чином, мінімум береться по dij, а максимум вибирається із значень t (dij) і Ti - 1 (D-dij);
- оператор переходу - представляється у вигляді виразу D-dij. Цей параметр задає кількість процесорів, яке повинно розподілятися між першим, другим,., I - 1-м програмними модулями за умови, що поточна кількість розподіляються процесорів дорівнює D і прийнято управління, відповідне виділенню dij процесорів для реалізації Ri-го програмного модуля;
- локальний дохід на i-му етапі - цієї компоненті відповідає час виконання i-го програмного модуля за умови виділення його для реалізації dij процесорів. Очевидно, що цей час одно t (dij);
- умовний оптимальний дохід T i (D) визначає час закінчення реалізації першого, другого,., i-го програмних модулів за умови, що розподіляється D процесорів.
2.3 Конструювання алгоритму розв'язання задачі
В основі методу динамічного програмування лежить принцип оптимальності Беллмана т. е оптимальне управління будується поступово. На кожному кроці оптимізується управління тільки цього кроку. Разом з тим на кожному кроці управління вибирається з урахуванням наслідків, так як управління, оптимизирующее цільову функцію тільки для даного кроку, може призвести до неоптимальному ефекту всього процесу. Управління на кожному кроці має бути оптимальним з погляду процесу в цілому. Це основне правило динамічного програмування, сформульоване Беллманом, називається принципом оптимальності. З цього випливає, що для того щоб знайти оптимальне рішення на останньому кроці треба спочатку знайти оптимальне рішення для першого, потім для другого і так далі поки не пройдемо всі етапи до останнього.
На підприємстві необхідно виконати розвантажувально-навантажувальні роботи на M складах підприємства. Час виконання роботи на кожному складі залежить від кількості вантажників - де n кількість вантажників, зайнятих на j-му складі при i-му варіанті розподілу вантажників. На підприємстві є вантажники в кількості N чоловік. Потрібно сформувати бригади на кожен склад таким чином, щоб виконати всі роботи за мінімальний час.
Етап 1. Поточне кількість процесорів D розподіляється тільки для виконання першого програмного модуля R1:
T 1 (D)=max (t (d 1, j), T 0 (Dd 1, j))=t (d 1, j),
так як вираження T 0 (Dd 1, j) невизначено. Результати виконання першого кроку представляються в таблиці 1.
Результати виконання першого кроку
Стан DУправленіе U 1 Оптимальний дохід T 1 (D) D 1,1=d 1,1 D 1,2=d 1,2 ... D 1, j=d 1, j D 1, N (1)=d 1, N (1) U 1=d 1,1 U 1=d 1,2 ... U 1=d 1, j U 1=d 1, N (1) Т 1 (D)=t (d 1,1) Т 1 (D)=t (d 1,2) ..... Т 1 (D)=t (d 1, j) Т 1 (D)=t ( d 1, N (1))
Решта таблиці формуються за таким же алгоритмом, але з урахуванням обчислених даних.
Етап 2. Поточне кількість процесорів D розподіляється між двома програмними модулями R 1 і R 2. Тоді i=2 і рівняння Беллмана має наступний вигляд:
T 2 (D)=max (t (d 2, j), T 1 (Dd 2, j)).
Результати виконання другого кроку представлені в таблиці:
Результати виконання другого кроку
Управління U 2 Стан другого етапу D 1,1 D 1,2 ... D 1, j D 1, N (1) U 2= d 2,1 ... D 2,1= d 2,1 + D 1,1 D 2,2= d 2,1 + D 1,2... D 2, j = d 2,1 + D
