Зміст
Вступ
. Постановка задачі максімізації кількості призначеня у завданнях розподілу
. Необхідні Поняття Теорії графів
. Завдання для найбільш Потік
.1 Постановка задачі
.2 Алгоритм Форда знаходження максимального потоку
. Завдання максімізації кількості призначеня у завданнях розподілу як завдання для найбільш Потік
.1 Зведення задачі до задачі про Максимальний Потік
.2 Модифікація алгоритму Форда розвязання задачі максімізації кількості призначеня у завданнях розподілу
. Результати числового ЕКСПЕРИМЕНТ
Висновки
Список використаної літератури
Додатки
Текст програми
ІНСТРУКЦІЯ користувача
Вступ
Останнім годиною однозначно зросла зацікавленість учених та практіків Мережна и потокового моделями. Це пов язано Із Впровадження та активним РОЗВИТКУ різноманітніх територіально розподіленіх систем: трубопровідніх, транспортних, телекомунікаційніх та ін. Основою таких систем є Певна мережа (мережа трубопроводів, доріг, каналів зв язку ТОЩО), в якій ціркулюють певні потоки (потоки Речовини, транспорту, Даних ТОЩО), тому задачі, Які доводитися розв язувати при проектуванні та ЕКСПЛУАТАЦІЇ систем з Мережна структурою, часто зводяться до розробки математичних моделей розподілу потоків та постановки и розв язання відповідніх оптимізаційних завдань.
відомі МОДЕЛІ розподілу потоків у МЕРЕЖА базуються на Поняття Теорії графів. Це пов язано з тим, что граф Дає можлівість наочно відобразіті структуру мережі, а параметри его вузлів и дуг - представіті Основними числовими характеристиками ее ЕЛЕМЕНТІВ. Набір характеристик покладів від природи модельованої системи, а такоже характером розв язування задач, однак у потокових моделях їх, як правило, представляються такими параметрами, як зовнішній Потік у вузлі, Потік по дузі, пропускна здатність дуги, ВАРТІСТЬ передавання одініці потоку по дузі ТОЩО.
Потокові задачі, як правило, зводяться до поиска такого розподілу потоків у мережі, при якому б забезпечувався екстремум Деяк крітерію. При цьом мают враховуватіся обмеження, что накладаються умів Збереження потоків у Вузли и неперевіщення потоками пропускної здатності дуг. Типового потокового завданнями є задача про Потік мінімальної вартості, для найбільш Потік, транспортна задача, задача про призначення та Інші.
У даній работе розглядається задача максімізації кількості призначеня у задачі розподілу. Дана задача такоже зводіться до задачі про Максимальний Потік и ее розв язок находится з використаних модіфікації алгоритмом Форда.
Робота Складається з теоретичної и практичної частин. У теоретічній частіні розглядаються основні Поняття Теорії графів, задача про Максимальний Потік, алгоритм Форда та йо Модифікація для розв язання задачі максімізації кількості призначеня у завданнях розподілу. У практічній частіні наведено ряд завдань, розв язок якіх знаходится з використаних програмної реалізації алгорірітму Форда. У додатках приводитися текст програми та інструкція користувача.
1. Постановка задачі максімізації кількості призначеня у завданнях розподілу
Однією Із прикладних постановок задачі максімізації кількості призначеня у завданнях розподілу є задача призн...
