Warning: session_start() [function.session-start]: Cannot send session cookie - headers already sent by (output started at /var/www/nelvin/data/www/ebooktime.net/index.php:6) in /var/www/nelvin/data/www/ebooktime.net/index.php on line 7

Warning: session_start() [function.session-start]: Cannot send session cache limiter - headers already sent (output started at /var/www/nelvin/data/www/ebooktime.net/index.php:6) in /var/www/nelvin/data/www/ebooktime.net/index.php on line 7
3.9. Задача про призначення та метод її розв'язування : Дослідження операцій : Бібліотека для студентів

3.9. Задача про призначення та метод її розв'язування


Повернутися на початок книги
1 2 3 4 5 6 7 8 9 10 11 12 13 14 
15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 
30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 
45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 
60 61 62 63 64 65 66 67 

магниевый скраб beletage

Окремим випадком транспортної задачі є задача про призна-чення: керівництву підприємства необхідно призначити на п по-сад виробників так, щоб забезпечити виконання всіх робіт за мі-

німальну вартість. При цьому відомі числа Ctj — ціна, яку бажає отримати   /-ий   працівник   за   виконання   j -і  роботи   (і = 1, п,

j = \,п). Для розв'язування цієї задачі був побудований окремий алгоритм, який розглядається в цьому розділі.

Для побудови математичної моделі задачі введемо змінні xtJ,

і = l,n,   j = 1, п '.

 

^

1, якщо г-ий працівник призначається на j -ту посаду;

Хіі

 ■   -    •          (3.55)

0, якщо г-ии пращвник не призначається на j -ту посаду.

Слід відзначити, що в цій задачі кількість працівників збіга-ється з кількістю посад, тому план призначення повинен врахо-вувати такі умови:

 

п                    

 

(3.56)

 

тобто кожний працівник може бути призначений лише на одну посаду:

 

п                    

Yjxtj =і5  j = hn

 

(3.57)

 

тобто на кожну посаду може призначатися лише один працівник. Загальна вартість виконання робіт визначається функцією

 

F(x) = X X СуХу —> min

 

(3.58)

 

Особливості задачі (3.55)—(3.58) дозволяють розв'язувати її за допомогою більш простих методів, ніж методи розв'язування транспортної задачі. Сутність одного з них наступна.

Відповідно до постановки задачі про призначення необхідно з матриці

 

С

 

 

'с         с          ...         С   )

с

і           с

і           •■.       с2п

с          СМ1    ...         nm J

 

вибрати п елементів по одному з кожного рядка (працівники) і кожного стовпчика (посади) так, щоб сума цих елементів (вар-тість виконання всіх робіт) була мінімальною.

Цю задачу можна звести до вибору п нульових елементів з де-якої матриці з невід’ємними елементами, яка має нулі в кожному рядку і кожному стовпчику.

Визначення. Дві матриці C = \cij], і = \,т, j = \,п та Z) = {<^.}, і = 1,т, j = \,п називаються екеіеалентними, якщо dtj = ctj -ut--Vj, i = \,n, j = \,n,   ut, Vj —деякі числа.

Еквівалентність матриць означає, що якщо від елементів кож-ного рядка або кожного стовпчика однієї матриці відняти або до-дати одне і те ж саме число (можливо, різні для різних рядків і стовпчиків), то отримаємо еквівалентну матрицю. Оптимальні розв 'язки задач з еквівалентними матрицями співпадають.

Для розв'язування задачі про призначення застосовують угор-ський метод, який вперше запропонував угорський математик Егерварі у 1931 р. Протягом тривалого часу його робота залиша-лась маловідомою. У 1953 р. математик Т. Кун переклав цю ро-боту англійською мовою, заново відкрив її для фахівців, розви-нув ідеї Егерварі та вдосконалив метод, який на честь першого

""^Z^^^^ify складається з підготовчого ета-пу і не більше ніж (п- 2) -х ітерацій. Підготовчий етап:

1.         У кожному рядку матриці С знаходимо мінімальний еле-мент та віднімаємо його від елементів відповідного рядка. В ре-зультаті отримуємо матрицю, Сх, в кожному рядку якої є хоча б один нуль.

2.         У кожному стовпчику матриці С1 знаходимо мінімальний елемент та віднімаємо його від елементів відповідного стовпчика. В результаті отримаємо матрицю D, в кожному рядку і стовпчи-

Основний етап:

1. Відмічаємо знаком «*» нулі в стовпчиках матриці D так, щоб в кожному рядку був тільки один такий знак. Якщо кількість нулів із «*» дорівнює п, то знайдено оптимальний розв'язок: міс-ця нулів із «*» відповідають х* = 1, всі інші х* = 0.

Якщо кількість нулів із «*» менше п, то позначаємо знаком «+» стовпчики матриці, в яких є 0* і вважаємо ці стовпчики за-йнятими. У процесі розв'язування задачі будуть з'являтися за-

ІТТТЯТІ Т)Я7ТКРТ   T^JTGIVTGTTTPT lVTJiTDPTTTI    ЯК1  СТОЯТІ-i ТТЯ. TTGDGXDGCTI ТТЄ^ЇІТТТТЯ-

2.         Переглядаємо рядки матриці зліва направо: якщо незайня-

тих нулів немає, то переходимо до п. 4.

Якщо незайнятий нуль є, то відмічаємо його «'«. Якщо в цьому ж рядку немає 0*, то переходимо до п. 3. Якщо ж в цьому рядку є 0*, то знімаємо позначку «+» зі стовпчика з 0* і позначаємо «+» рядок з 0', після чого повертаємось на початок п. 2, поки не пере-глянемо всі рядки матриці.

3.         Будуємо ланцюг: від 0' по стовпчику до 0*, від нього по ря-дку до 0' і т. д., доки це можливо. Ланцюг може складатися навіть з одного 0'. Знімаємо знаки «*» і знімаємо «'« на «*» у нулів з ла-нцюга. Таким чином, кількість 0* зростає принаймні на один. Повертаємось до п. 1, знявши всі позначки з матриці, і залишив-ши тільки 0*.

4.         Знаходимо мінімальний елемент матриці серед незайнятих. Віднімаємо цей елемент від всіх незайнятих рядків та додаємо до всіх зайнятих стовпчиків.

Позначки нулів та всіх зайнятих стовпчиків і рядків залишає-мо без змін. Таким чином, отримаємо нові незайняті нулі і повер-таємось до п. 2.

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

Приклад 3.8. Естафета на Олімпійських іграх складається з чотирьох дистанцій, довжина яких 100 м, 20 м, 500 м та 800 м. У команді чотири спортсмени, результати кожного з яких на ко-жній дистанції наведено у табл. 3.14.

Таблщя 3.14

 

Спортсмени  Результати спортсменів (сек.)

 

            100 м  200 м  500 м  800 м

Іванов 10        21        54        86

Петров           10        20        55        88

Коваленко     9          22        55        87

Шевченко      9          21        56        89

Один спортсмен може бути призначеним тільки на одну дис-танцію і на кожну дистанцію має бути призначений тільки один

спортсмен. Як розподілити спортсменів по дистанціях, щоб зага-льний результат естафети був найкращим?

Побудуємо модель задачі. Змінні xtJ означають результат при-

значення /'-го спортсмена нау'-ту дистанцію, тобто:

xtJ = 1, якщо /-ий спортсмен призначається нау'-ту дистанцію;

xtJ = 0, якщо /-ий спортсмен не призначається на у'-ту дис-

танцію.

Час, за який команда пробіжить естафету, буде визначатися як

f(x) = 10хп + 21х12 + 54х13 + 86х14 + 10х21 + 20х22 + 55х23 + 88х24 + + 9х31 + 22х32 + 33х33 + 87х34 + 9х41 + 21х42 + 56х43 + 89х44.

Кожний спортсмен може бути призначений тільки на одну ди-станцію, що виражається як

та на кожну дистанцію має бути призначений тільки один спорт-смен:

Xj - + х2 - + х3 - + х4 - =1,    j = 1,4.

Математична модель задачі має вигляд:

f(x) —> min

в області, що визначається умовами:

хп +х12 +х13 +х14 =1, х21 + х22 + х23 + х24 = 1, х31 + х32 + х33 + х34 = 1, х41 + х42 + х43 + хи =1, хп +х21 +х31 +х41 =1, х12 + х22 + х32 + х42 = 1, х13 + х23 + х33 + х43 = 1, х14 + х24 + х34 + х44 = 1,

х.- = <       і, j = 1,4.

0

Для розв’язування цієї задачі застосуємо угорський ме-тод. Етапи розв'язування задачі подамо у вигляді табл. (3.15— 3.20).

Підготовчий етап. Виявимо мінімальний елемент у рядках (табл. 3.15).

Таблщя 3.15

 

№        Спортсмен     Результати спортсменів (сек)          Мінімальний елемент рядка

 

           

            100 м  200 м  500 м  800 м 

 

1          Іванов 10        21        54        86        10

2          Петров           10        20        55        88        10

3          Коваленко     9          22        55        87        9

4          Шевченко      9          21        56        89        9

Віднімаємо мінімальний елемент від елементів відповідного рядка та знаходимо мінімальний елемент у кожному стоепчи-ку ноеоїтабл. 3.16.

Таблщя 3.16

 

№        Спортсмени  Результати спортсменів (сек.)

 

           

            100 м  200 м  500 м  800 м

1          Іванов 0          11        44        76

2          Петров           0          10        45        78

3          Коваленко     0          13        46        78

4          Шевченко      0          12        47        80

5          Мінімальний елемент стовпчика    0          10        44        76

Віднімаємо мінімальний елемент від елементів відповідного стовпчика і отримуємо табл. 3.17.

Таблщя 3.17

 

№        Спортсмени  Результати спортсменів (сек.)        

 

           

            100 м  200 м  500 м  800 м 

 

1          Іванов 0          1          0*        0"         +

2          Петров           0          0*        1          2         

3          Коваленко     0          3          2          2         

4          Шевченко      0*        2          3          4         

5                      +          +          +                    

Основний етап. Згідно з п. 1 основного етапу алгоритму спробуємо зробити призначення з даними табл. 3.17.

На даному етапі можемо зробити тільки три призначення, a необхідно чотири. Згідно п. 1 позначаємо у табл. 3.17 знаком «+» зайняті стовпчики. Переходимо до п. 2. У першому рядку табл. 3.17 є один незайнятий нуль (c14 = 0), який позначаємо «х» і 0* (c13 = 0*), тому знімаємо позначку «+» з третього стовпчика (позначки, які знімаємо, обводимо квадратом) та позначаємо пе-рший рядок таблиці знаком «+». Більш незайнятих нулів у табли-ці немає, тому переходимо до п. 4.

Серед незайнятих елементів таблиці знаходимо мінімальний

тт(c23,c24,c33,c34,c43,c44) = min(l, 2,2,2,3,4) = 1.

Віднімаємо це число від усіх незайнятих рядків (табл. 3.17) та додаємо до всіх зайнятих стовпчиків, отримуємо табл. 3.18.

Таблщя 3.18

 

№ з/п  Спортсмени  Результати спортсменів (сек.)        

 

           

            100 м  200 м  500 м  800 м 

 

1          Іванов 1          2          0+        0'         +

2          Петров           0          о*        0'         1          +

3          Коваленко     0          3          1          1         

4          Шевченко      о*        2          2          3         

5                      +          +                                

Повертаємося до п. 2. Незайнятий нуль відповідає елементу C23. Позначимо його «'», другий рядок робимо зайнятим та знімаємо по-значку «+» з другого стовпчика. Незайнятих нулів у табл. 3.18 бі-льше немає. Переходимо до п. 4. та заповнюємо табл. 3.19.

min(c32,c33,c34,c42, c43, c^) = min(3,1,1, 2, 2,3) = 1.

Таблщя 3.19

 

№ з/п  Спортсмени  Результати спортсменів (сек.)        

 

           

            100 м  200 м  500 м  800 м 

 

1          Іванов 2          2          о*        0'         +

2          Петров           1          о*        0'         1          +

3          Коваленко     0          2          0'         0         

4          Шевченко      о*        1          1          2         

5                      +                                            

Повертаємося до п. 2. У третьому рядку є два незайнятих нулі (сзз та С34). Виберемо, наприклад, с33 та позначимо його «'» (та3л. 3.19). Оскільки у третьому рядку немає 0*, тоді переходи-мо до п. 3.

Побудуємо цикл с.3 —> с13 —> с14. Знімемо «*» з с13 та замінимо «'» на «*» у С14 та сзз- Таким чином, новий набір нулів з «*» має на один більше, ніж попередній. Повертаємося до п. 1 та спробу-ємо зробити призначення. Оскільки кількість 0* дорівнює чоти-рьом, знайдемо оптимальний варіант призначень (табл. 3.20).

Таблщя 3.20

 

№ з/п  Спортсмени  Результати спортсменів (сек.)

 

           

            100 м  200 м  500 м  800 м

1          Іванов                                    *

2          Петров                       *                     

3          Коваленко                             *         

4          Шевченко      *                                

Мінімальний час, за який команда може пробігти естафету, дорівнює 170 секундам. У табл. 3.20 позначка «*» означає при-значення спортсмена на відповідну дистанцію.

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

Підготовчий етап виконується аналогічно розглянутому в ал-горитмі.

Основний етап: Зазначимо, що розв’язок задачі про призна-чення є допустимим, якщо з кожного рядка та кожного стовпчика матриці С вибрано тільки один елемент. Ви’рані нульові елемен-ти матриці відповідають оптимальному розвязку задачі.

1.         Знайти рядок матриці D, який містить тільки один нульовий елемент, та позначити цей елемент «*». Якщо такі рядки відсутні, а є рядки з більшою кількістю нульових елементів, тоді вибрати будь-який з них і також позначити його «*». Перейти до п. 2.

2.         Якщо у відповідному стовпчику та рядку є інші нульові елементи, тоді їх закреслити. Пункти 1 та 2 повторювати доти, доки продовження цієї процедури можливе.

Якщо кількість позначених нульових елементів дорівнює п, тоді знайдемо оптимальний розв’язок задачі.

Якщо кількість таких елементів матриці менше за п, тоді п. 3.

3.         Провести мінімальне число горизонтальних та вертикаль-них ліній через рядки та стовпчики матриці так, щоб всі нульові елементи стали викресленими.

4.         Знайти мінімальний елемент серед невикреслених.

5.         Відняти його від усіх невикреслених елементів матриці та додати до всіх елементів матриці, які лежать на перехресті прямих.

Всі елементи матриці, через які проходять тільки одна пряма, залишаються без змін.

аЛГо3рГд=І^ГГоТоУіНаВмЄу^„^

Характерною рисою економічних систем або економічних процесів є їх розвиток та функціонування у часі. Оптимальна стратегія управління такими системами та процесами може сут-тєво залежати від тривалості планового періоду. Аналіз такого зв’язку можна реалізувати за допомогою методів динамічного програмування.

В основі методу лежить ідея апарату рекурентних співвідно-шень. Запропонований Р. Беллманом метод дозволяє звести про-цес оптимізації функції п змінних до и-крокового процесу опти-мізації функцій однієї змінної. [2], [3], [25].

Задачі, для розв’язування яких можливе застосування методу динамічного програмування, повинні задовольняти такі власти-вості:

•          можливості фактичного або умовного розподілу початкової задачі на окремі підзадачі, кожна з яких містить меншу кількість змінних (навіть до однієї);

•          однотипності підзадач;

•          можливості вимірювання однаковими одиницями ефекту від прийнятого рішення в результаті розв’язування кожної підзадачі;

•          можливості обчислення загального ефекту як суми ефектів в окремих підзадачах.

Продемонструємо змістовну та обчислювальну сторони мето-ду динамічного програмування на прикладі задачі розподілу ре-сурсів.

Постановка задачі. Припустимо, що існує певна кількість де-якого ресурсу. Це може бути запас сировини, енергетичні ресур-си, фінансові, трудові тощо. Існують альтернативні варіанти ви-користання цього ресурсу.

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

Математична модель задачі. Для побудови математичної мо-делі задачі введемо такі позначення:

п — кількість різних технологічних процесів;

j — номер технологічного процесу, j = 1,п; Xj — кількість ресурсу, яка виділяється у'-му технологічному

процесу j = 1,п;

fj(xj) — прибуток віду'-го технологічного процесу, одержаний у

результаті використання ресурсу в кількості х- одиниць, j = 1, п;

Ь — загальна кількість ресурсу.

Необхідно знайти такі значення змінних х;, j = 1,п, щоб мак-симізувати загальний прибуток.

п

(3.59)

F(x) = Х//(х/) за обмежень по витратах ресурсу

п

(3.60)

та невід’ємності змінних

х- > 0,     j = 1,п .       (3.61)

Процес розподілу ресурсу між п технологічними процесами можна розбити на п етапів, на кожному з яких будуть прийматись рішення по окремому технологічному процесу в залежності від стану запасу ресурсу. Постановка задачі дає можливість оцінити загальний прибуток як суму прибутків від кожного технологічно-го процесу. Врахування цих особливостей дає можливість вико-ристати методу динамічного програмування для розв’язування задачі (3.58)—(3.61).

Зрозуміло, що оптимальне значення загального прибутку за-лежить від кількості ресурсу Ь, а також від кількості різних тех-нологічних процесів, серед яких розподіляється ресурс. Відобра-зимо цю залежність функцією

п

gn(b) = max Х//(х/)

7=1

на множині, яка описується умовами (3.60), (3.61).

Функція g„(b) виражає максимальний прибуток, одержаний від розподілу Ь одиниць ресурсу між п технологічними проце-сами.

Побудуємо рекурентні співвідношення між величинами при-бутку від п технологічних процесів gn та від (п -1) -го технологі-чного процесу -gn_x. Для цього виберемо значення змінної хп, 0 < хп < Ь . Ресурси, які залишилися (Ь-хп), повинні бути викори-стані оптимально, тобто необхідно знайти

и-1

Sn-І Ф ~ ХП )  =  ШаХ Tj fi (Хі )  ■>

j=\

за умов

п-\

Y,xi -b~xn>

х. > 0,   j = 1, n -1.

Ефективність цих двох кроків визначається сумою прибутків від и-го технологічного процесу та всіх інших:

/n(xn) + gn_j(fc-xn).

Вимога максимальної ефективності від реалізації цих кроків еквівалентна запису:

g„(b)= max (fn(хп) + gn_l(b-xn)),

0<x„<b

причому п-му технологічному процесу може бути виділена будь-яка кількість ресурсів у межах величини Ь.

3 аналогічних міркувань максимальний прибуток від розподі-лу залишку ресурсу (Ь-хп) визначається формулою:

Sn-\ (У) =    ШаХ   ifn-І (Хи-1) + Sn-2 (У ~ Хп-\)) 1 0<хп_і <у

ДЄ

у = Ь - хп.

Максимальний прибуток від розподілу ресурсу на проміжно-му кроці к визначається наступною формулою:

gk(y) = max (ft(xk) +§к-і(У~хк))>   к = 2,п ,  (3.62)

0<хк<у

ДЄ

п

у = b - YJ ХГ

j=k+\

Враховуючи, що на останньому кроці

у - Xj = 0 ,

природно вважати g0(0) = 0 .

Таким чином, максимальний прибуток від розподілу ресурсу на и-му кроці дорівнює:

gx(y) = max yj(xj).       (3.63)

0<y<b

Рівняння типу (3.62) називається осноеним рекурентним співвідношенням, яке є математичним відображенням так звано-го принципу оптимальності. оптимальна поведінка має таку властивість, що в якому б стані не знаходилася система і які б рішення не приймалися у попередні моменти, наступні рішення повинні бути оптимальними відносно стану, в якому опинилася система.

Алгоритм розв'язування задачі (3.59)—(3.61) методом дина-мічного програмування складається з двох етапів. Перший етап — розв'язування рекурентних рівнянь вигляду (3.24), тобто визначення сукупності gk(y) для >>є[0,й] та оптимальних хк для

кожного к = \,п. Другий— формування оптимального розв'язку задачі.

Розглянемо обчислювальну процедуру знаходження опти-мального розв'язку задачі (3.59)—(3.61). Оскільки в процесі розв’язування задачі методом динамічного програмування не-обхідно мати інформацію про величини прибутків від кожного технологічного процесу при різних варіантах розподілу ресур-

cy, TO для виконання першого етапу зручно користуватися таблицею:

Таблщя 3.21

 

у          S1(y)   х1        g2(y)    х2        ...         8п(У)  х„

0 1

; ь                                                                              

В табл. (3.21) зміст величини у стовпчиках такий: у — наявна кількість ресурсу; gk(y) — ефективність використання к техно-логічних способів, к = 1,п; хк — інтенсивність використання к-

го технологічного способу, к = 1, п.

Зрозуміло, що неможливо протабулювати всі значення функ-цій gk(у), к = 1,п при будь-яких значеннях у, 0<у<Ь. Тому до-

цільно скористатися значенням функцій gk(y), к = 1,п, у скінче-ній кількості точок, скажімо,

у = 0, A, 2А, ..., /A = b,

де A — крок збільшення ресурсу, / — кількість дискретних ін-тервалів, на які розбивається відрізок [0,b\ (у табл. 3.7 A = 1, l = b).

Використаємо формулу (3.63), знайдені значення функції g1( ) ПРИ 0<>><й і відповідне значення змінної х1 заносяться до табл. 3.21, після чого переходимо до обчислення g2(y) згідно з (3.62).

Для зручності обчислень введемо допоміжну функцію ц>(у), де у — кількість ресурсу,  0 < у < Ь.

Нехай у = 3 , тоді х2 може приймати значення х2 = 0; х2 = 1; х2 =2; х2 =3. Кожне з цих значень надає <р(3) відповідні (3.62) значення, а саме:

ф(3) ^

 

х2 = 0 ^ /2 (0) + g1 (3), ^=1=>/2(1) + Й(2),

х2 = 2 ^ /2 (2) + g1 (1), х2 = 3 => f2 (3) + g1 (0).

 

У рядок y = 3 заноситься x2, якому відповідає найбільше із знайдених значень /2(x2) + g1(3-x2), а в стовпчик g2(3) відповід-не значення /2 (х2) + g1 (3 - х2).

Аналогічно заповнюються всі інші стовпчики табл. 3.21, крім g„(y) . У стовпчику g„(y) заповнюється лише останній рядок, тобто g„(b), а в останньому стовпчику хп записується значення змінної хп лише при у = Ь. Знайдене значення gn (b) відповідає оптимуму задачі (3.58)—(3.61), хп визначає оптимальне значення відповідної змінної (х*).

Тепер перейдемо до другого етапу методу динамічного про-грамування, тобто до процедури формування оптимального розв’язку задачі.

Для визначення вектора х = (х*      ) застосуємо наступний

алгоритм:

Крок 1. Обчислимо кількість ресурсів, які залишилися після фіксації х*:у(г) =b-x*n, і = 0 .

Якщо у(г) = Ь-х*_. дорівнює нулю, то всі інші координати век-

тора х  є нулі. Якщо у(г) > 0, то здійснити крок 3.

3. У першому стовпчику (у(г)) знайти рядок, що має значення у(г) =Ь-хп; вибрати йому відповідне значення хп_м. Після цього і = і + 1. Перейти до кроку 2.

Якщо   після   виконання   т(т < п)   кроків   залишок   ресурсу

у(г) = 0, то автоматично решті змінних х*   j = 1,n-m надаються нульові значення.

Приклад 3.9. Розглянемо задачу знаходження максимально-го прибутку від розподілу 6 одиниць ресурсу на виробництво 3 видів продукції А, В і С. Норми витрат ресурсу та прибуток з кожної одиниці продукції всіх видів наведено в табл. 3.22.

Таблиця 3.22

 

Види продукції          A         В         С

Норми витрат ресурсу (ум. од.)      4          5          2

Прибуток з одиниці продукції кожного виду (грн)           9          7          4

Прибуток підприємства можна підрахувати тоді, коли визна-чено план виробництва.

Введемо позначення: х- — кількість продукції виду j, j = 1,3 .

Припустимо, що кількість продукції може вимірюватися лише у цілих одиницях.

Математична модель задачі: максимізувати загальний прибуток

F(x) = 9xj + 7х2 + 4х3

за обмежень на використання ресурсу

4xj + 5х2 + 2х3 < 6

і на вибір змінних

х > 0, х  — ЦІлі, j = 1,3 .

Розв'яжемо задачу методом динамічного програмування. Від-повідно до принципу оптимальності побудуємо рекурентні спів-відношення типу (3.62) для даної задачі. В результаті розподілу ресурсу максимальний прибуток від виробництва продукції виду С в кількості х3 одиниць і оптимального використання залишку ресурсу (6-2х3) на виробництво інших видів продукції визнача-тиметься формулою:

2,(6) =   max (4х, + 2"т(6 -2х,)).         (3.64)

3          Гбі      3       z  3

0<х3<

Оскільки норма витрат ресурсу на одиницю продукції виду С дорівнює 2, то можлива кількість продукції виду С коливається

■    п       Г61  Г 1

від U до   — , де \а\ — щла частина числа а.

Величина максимального прибутку від розподілу залишку ре-сурсу у = 6 - 2х3 на виробництво продукції видів А і В визнача-ється формулою:

g2(y)=   max (7х2 + gi(y-5x2)).           (3.65)

Г vl [_ 5 _

Максимальний прибуток від розподілу залишку ресурсу у = 6 - 2х3 - 5х2 на виробництво продукції виду А дорівнює:

g1(y)=  max  9xj.         (3.66)

Г vl и<хг <

\_4 _

Використаємо (3.64)—(3.66) для заповнювання табл. 3.23. Бу-демо вважати, що кількість ресурсу у - - дискретна величина, яка набуває всіх цілих значень від 0 до 6.

Таблщя 3.23

 

у          Si(y)     хі         g2(y)    х2        g3(y)    х3

0          0          0          0          0                     

1          0          0          0          0                     

2          0          0          0          0                     

3          0          0          0          0                     

4          9          1          9          0                     

5          9          1          9          0                     

6          9          1          9          0          13        1

Заповнювати таблицю починаємо зі стовпчиків gx (у) та хх. Якщо величина ресурсу у дорівнює нулю, то на виробництво продукції виду A ресурс не може бути виділений. Відповідно gx (0) = 0 та Xj = 0 . Якщо залишилася 1 одиниця ресурсу, то вра-ховуючи норму витрат на продукцію виду А, яка дорівнює 4, ви-робництво цієї продукції неможливе. Тому g!(0) = 0 та х:=0. 3 аналогічних міркувань gx (2) = 0 та хх = 0 , gx (3) = 0 та хх = 0 . При у = 4, враховуючи (3.64), gj(4) = 9 та хх=1, при у = 5, gx (5) = 9 та Xj = 1 і т. д.

Для визначення g2 (у) скористаємося функцією ц>(у).

ф(0) = 0, отже g2 (0) = 0 , х2 = 0,

ср(1) = 7 • 0 + gx (1) = 0,

отже х2 = 0 для у < 5 . Але при у = 4  х2 = 0, проте gx (4) = 9, тому при у = 4  х2 = 0 , але g2 (у) = 9.

Розглянемо наступне значення у = 5, тоді

х2 = 0  =>    7.0 + gj(5) = 9 ср(5)

х2=1  =>    7.1 + gj(0) = 7.

0, тому при

Найбільше значення   ф(5) = 9   і відповідає   х2 = у = 5 маємо g2 (у) = 9; х2 = 0.

Наступне значення у = 6, тому

 

ф(6)

 

х2 = 0  => 7-0 + gj(6) = 9. х2=1 => 7-l + gj(l) = 7.

 

тобто х2 = 0, g2 (6) = 9. Прорахуємо g3(6).

 

 

ф(6)

х3 = 0 => 4.0 + g2 (6) = 9. х3 = 1=>4.1 + g2(7) = 4 + 9 = 13. х3 = 2 => 4.2 + +g2 (2) = 8. х3 = 3 => 4.3 + g2 (0) = 12.

Максимальному значенню g3(y), яке дорівнює 13, відповідає значення змінної х3=1. Ці результати вносимо до табл. 3.23 у стовпчики g3 (у) та х3.

Оскільки g3(6) відповідає оптимальному значенню цільової функції F*(x), то перший етап алгоритму закінчено.

Перейдемо до другого етапу — формування оптимального розв'язку х =(х*,х2,х3). Цей етап виконується за допомогою табл. 3.23.

Якщо х3 = 1, то на виробництво решти видів продукції зали-шиться 4 одиниці ресурсу. При у = 4 х2 = 0. На виробництво продукції А залишиться 4 одиниці ресурсу. При у = 4 х* = 1.

Оптимальним розв'язком задачі є х = (1,0,1), F(x*) = 13 , тобто продукції А та С треба виробляти по одній одиниці, продукт В не виробляється, а максимальний прибуток складає 13 грн.

Для програмної реалізації методу динамічного програмування можливо запропонувати наступну схему.

Позначимо    к -     кількість   способів,   що   вже   розглянуті,

к = \,п. Схема алгоритму буде такою:

1.         к = \.

2.         Розіб’ємо інтервал ресурсів від 0 до Ь одиниць на т інтер-валів довжиною A.

3.         Для кожного з т інтервалів визначимо можливі значення

інтенсивності технологічного способу к, тобто

0<хк <—,1 = \,т ,

ак

де: / —кількість точок поділу відрізку [0,b\ на т частин;

^' — проміжні значення ресурсів, I = 0,т;

ак — нормативи витрат ресурсів наА; -й технологічний спосіб.

Нехай змінна хк може набувати значень х'к,1 = 0,т .

4.         Визначимо величини невитрачених ресурсів для кожного

інтервалу /:

Д/ -акх[, 1 = 0,т .

5.         Ефективність використання Л/, 1 = 0,т ресурсів технологі-

чним способом к з інтенсивністю х[ буде визначатися як

Л4) + ^-і(л/-«л)-

6.         Найкращий варіант використання ресурсу Л/, 1 = 0,т тех-

нологічним способом к з інтенсивністю х[ буде визначатися як

gk (Л/) = max(fk (х[) + gk_1 (Л/ - акх[)). 4

Для кожного значення / зафіксуємо значення gk (Л/), а також відповідне значення змінної х[.

7.         Якщо к<п, тоді к = к +1 таповернутися до пункту 3.

Якщо к = п, тоді перейти до пункту 8.

8.         Оскільки на п технологічних способів виділяється Ь ре-

сурсів, то на цьому етапі доцільно розглянути розподіл саме Ь

одиниць ресурсу, тобто / = т, тоді Л/ = Ь. Повернутися до пункту

3. Пункти 3—6 виконати тільки для ї = т. На цьому закінчити

перший етап алгоритму. В результаті виконаних обчислень ви-

значено максимальний прибуток від розподілу можливої кількос-

ті ресурсу, а також оптимальний спосіб досягнення цього прибу-

тку при фіксованій кількості технологічних способів.