span>
Дані таблиці (1.7 і 1.8) відповідає оптимальному призначенням (1,2), (2,3), (3,1), (4,5) і (5,4) або (1 , 3), (2,4), (3,1), (4,5) і (5,2). Відповідні сумарні витрати:
z = + + = 12 +3 +1 = 16 од. часу.
У таблиці 1.1.7 і 1.1.8 знаходимо сумарні витрати часу по клітках (1,2), (2,3), (3,1), (4,5) і (5,4) і (1 , 3), (2,4), (3,1), (4,5) і (5,2)
z = 2 +5 +4 +2 +3 = 16 = 5 +3 +4 +2 +2,
тобто результати збіглися.
Відповідь: мінімальні витрати часу будуть становити 16 од. часу.
1.2 Оптимальний розподіл робітників по захваткам
Нехай є n видів робіт і кілька спеціалізованих бригад робітників. Необхідно розподілити робітників між окремими видами робіт таким шляхом, щоб у будівельний потік включити максимальну кількість робітників. Таке завдання близька до транспортної. У науковій літературі вона відома як задача про максимальний потік в матричної постановці або завдання призначення (вибору). Розглянемо постановку задачі в загальному вигляді. Нехай задані кількості одиниць ресурсу а:,,, направляються в пункти призначення, у яких потреби b:,, в цьому ресурсі. Відмінною особливістю цього завдання є закріплення кожного пункту відправлення за деякими пунктами призначення. Отже, мається матриця, в якій
, якщо не можна перевозити ресурс з i-го пункт відправлення в j-пункт призначення, 0, якщо перевезення можлива.
Задача складається у складанні плану перевезень максимальної кількості ресурсу.
Такий план визначається числами (i = 1, m, j = 1, n);.
Якщо = 0, то = 0, тобто не можна перевозити ресурс з i-го пункту відправлення в j-ий пункт призначення.
При цьому повинні дотримуватися умови:
1, i = 1, m, тобто з i-го пункту відправлення вивозиться ресурс не більш ніж.
2, j = 1, n, тобто в j-ий пункт призначення можна ввести не більше потреби-го ресурсу.
При цьому кількість перевезеного ресурсу
Ф = max.
Вихідні дані:
На будівельному об'єкті є 4 види робіт та 4 груп робітників. Робочі кожної групи виконують одні й ті ж роботи. Необхідно, щоб роботи виконувало максимальну кількість робітників. Умови завдання наведені в таблиці 1.2.1, в шпальтах якій зазначено необхідну кількість робітників для виконання відповідної роботи, а рядки окремі види робочих. У клітинах таблиці наведені нулі, якщо робітник i-ої групи може виконувати j-ю роботу, і одиниці, якщо робочі i-ої групи не можуть виконувати j-ю роботу. br/>
Таблиця 1.2.1
12341 4537 2 6285 3 4796 4 2354
помножается кожен елемент матриці на -1 і ...
