дставляються працівніків. Ця вершина Виступає в якості стоку. Для кожної з дуг Вважаємо, что ее Пропускна здатність дорівнює 1. Отже, дана задача может буті представлена ??у вігляді графа
Очевидно, пропускна здатність даної мережі буде тім більшою, чім більшою буде кількість використаних дуг (призначеня). Таким чином задача максімізації кількості призначеня у завданнях розподілу зводіться до задачі про Максимальний Потік.
4.2 Модифікація алгоритму Форда розв язання задачі максімізації кількості призначеня у завданнях розподілу
У алгорітмі Форда знаходження максимального потоку в мережі на основному етапі доводитися знаходіті пропускну здатність знайдення шляху. Для задачі максімізації кількості призначеня у завданнях розподілу цею крок є надлишково, оскількі Пропускна здатність кожної Із дуг дорівнює 1. На третьому кроці основного етапу шкірному Елемент матріці, что входять до шляху ставімие у відповідність значення 0 а симетрично Елемент ставімие у відповідність значення 1. Дані Особливості прізводять до Спрощення обчіслювальної складності алгоритму и Зменшення годині роботи.
5. Результати числового ЕКСПЕРИМЕНТ
Приклад 1. На підпріємстві є 5 Вакансій і 4 працівники. Можлівість Прийняття працівніків на вакансії подано таблицею
Працівник 1Працівнік 2Працівнік 3Працівнік 4Вакансія 1 + + Вакансія 2 + + Вакансія 3 + + + Вакансія 4 + + Вакансія 5 + +
На Основі ціх Даних побудуємо граф
На Основі даного графу пріходімо задачі про Максимальний Потік. Знайдемо результат з використаних програмної реалізації модіфікованого алгоритмом Форда. Пріведемо покроковий процес розв язання
Приклад 2. На підпріємстві є 8 Вакансій и 6 працівніків. Можлівість Прийняття працівніків на вакансії подано таблицею
прац. 1Прац. 2Прац. 3Прац. 4Прац. 5Прац. 6Вакансія 1 + + + Вакансія 2 + + + Вакансія 3 + + + Вакансія 4 + + + Вакансія 5 + + + Вакансія 6 + + + Вакансія 7 + + Вакансія 8 + + +
Знайдемо розв язок з використаних програмної реалізації модіфікованого алгоритмом Форда
теорія граф числовий максімізація
Приклад 3. На підпріємстві є 6 Вакансій и 6 працівніків. Можлівість Прийняття працівніків на вакансії подано таблицею
прац. 1Прац. 2Прац. 3Прац. 4Прац. 5Прац. 6Прац. 7Прац. 8Вакансія 1 + + Вакансія 2 + + + + Вакансія 3 + Вакансія 4 + + + Вакансія 5 + + + + Знайдемо розв язок з використаних програмної реалізації модіфікованого алгоритмом Форда
Висновки
У работе Розглянуто задачу максімізації кількості призначеня в задачі розподілу. Для розв язання цієї задачі застосовано підхід, что Полягає у зведенні цієї задачі до задачі про Максимальний Потік.
ПЕРЕВАГА такого підходу є ті, что ВІН дозволяє застосуваті відомі методи розв язання задачі про Максимальний Потік. Цею факт однозначно спрощує процес розв язання поставленої задачі.
Недоліком такого підходу є ті, что при побудові графа и его представленні помощью матріці суміжності ми одержуємо матрицю Великої розмірно...
