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

Warning: file_get_contents(files/survey) [function.file-get-contents]: failed to open stream: No such file or directory in /var/www/nelvin/data/www/ebooktime.net/index.php on line 82
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 

Загрузка...

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

німальну вартість. При цьому відомі числа 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

 

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

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

Визначення. Дві матриц