Максимізація кількості призначень в задачі розподілу

курсовая работа

Вступ

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

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

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

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

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

Делись добром ;)