Зміст

Вступ

.Постановка задачі максимізації кількості призначень у задачах розподілу

. Необхідні поняття теорії графів

. Задача про максимальний потік

.1 Постановка задачі

.2 Алгоритм Форда знаходження максимального потоку

. Задача максимізації кількості призначень у задачах розподілу як задача про максимальний потік

.1 Зведення задачі до задачі про максимальний потік

.2 Модифікація алгоритму Форда розвязання задачі максимізації кількості призначень у задачах розподілу

. Результати числового експерименту

Висновки

Список використаної літератури

Додатки

Текст програми

Інструкція користувача

Вступ

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

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

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

У даній роботі розглядається задача максимізації кількості призначень у задачі розподілу. Дана задача також зводиться до задачі про максимальний потік і її розвязок знаходиться з використанням модифікації алгоритму Форда.

Робота складається з теоретичної і практичної частин. У теоретичній частині розглядаються основні поняття теорії графів, задача про максимальний потік, алгоритм Форда та його модифікація для розвязання задачі максимізації кількості призначень у задачах розподілу. У практичній частині наведено ряд задач, розвязок яких знаходиться з використанням програмної реалізації алгориритму Форда. У додатках приводиться текст програми та інструкція користувача.

1. Постановка задачі максимізації кількості призначень у задачах розподілу

Однією із прикладних постановок задачі максимізації кількості призначень у задачах розподілу є задача призначення працівників на робочі міста. На деякому підприємстві є вакансій на які претендують працівників. Для кожної вакансії з урахування її особливостей та кваліфікації працівників вказано перелік працівників, які можуть бути призначені на цю вакансію. Задача полягає у визначенні таких призначень працівників на вакансії, при якому кількість призначень буде максимальною.

2. Необхідні поняття теорії графів

Теорія графів виникла понад 240 років тому. Основи її розробив математик Леонард Ейлер, розв'язавши в 1736 р. відому задачу про 7 мостів. Проте лише протягом останніх часів ця теорія була докладно розроблена й почала широко використовуватися у фізиці, хімії, біології, соціології, економіці, картографіі тощо. Отримання дальших суттєвих результатів у цій галузі датують серединою ХIХ століття. Однак початок проведення активних систематичних досліджень та становлення теорії графів як окремішного авторитетного розділу сучасної математики відбулося ще майже 100 років по тому, тобто в середині ХХ століття. Саме з цього часу граф стає однією з найпоширеніших і найпопулярніших математичних моделей у багатьох сферах науки і техніки. Картинка у вигляді набору точок на площині та ліній, проведених між деякими з них, стала зручною і наочною формою зображення найрізноманітніших обєктів, процесів та явищ.

Великою мірою це повязано з виникненням, бурхливим розвитком та поширенням електронних обчислювальних машин і, як наслідок, значним зростанням ролі задач дискретного характеру. Математика від "обслуговування" переважно фізики переходить до проникнення своїх методів у інші сфери людської діяльності. Із суто формальної точки зору граф можна розглядати як один з різновидів алгебраїчної системи (а саме, як модель), а отже, і всю теорію графів - як розділ сучасної алгебри. Справді, результати та методи алгебри широко використовуються в теорії графів. Однак за останні півстоліття активного інтенсивного та екстенсивного розвитку теорія графів виробила свою достатньо специфічну власну проблематику і методологію. На сьогодні теорія графів є однією зі складових математичного апарату кібернетики, важливим розділом дискретної математики. Тому теорія графів включається до навчальних програм університетів і технічних вузів як окрема дисципліна, або як розділ курсу "Дискретна математика".