Разработка программы для нахождения максимального потока в cети
Букреев П.А., Стручинский А.А.,
студенты 4 курса Оршанского колледжа УО «ВГУ им. П.М. Машерова», г. Орша, Республика Беларусь
Научный руководитель – Юржиц С.Л., преподаватель
На сегодняшний день в математическом моделировании широкое распространение получили задачи линейного программирования. К ним относятся транспортные задачи для нахождения кратчайшего пути, максимального потока. Так, например, могут быть сформулированы задачи составления расписаний в исследовании операций, анализа сетей в электротехнике, установление структуры молекул в органической химии, сегментации программ в программировании [1, с. 288]. В сфере промышленности довольно часто стоит вопрос о том, как с минимальными потерями отправить какой-либо продукт из одной точки в другую. Для решения этого вопроса рациональным решением будет использование транспортных задач. Транспортная задача – задача об оптимальном плане перевозок товара со складов в пункты потребления на транспортных средствах.
Исходные данные такой задачи представляют собой сеть. Сетью называется связный граф, в котором заданы «пропускные способности» рёбер. Следует отметить, что сети имеют огромные приложения, в частности, «сети планирования» (имеется в виду планирование производства некоторых новых, достаточно сложных изделий), где «пропускные способности» рёбер – это время, за которое нужно из нескольких узлов изделия (вершин графа) получить другой более сложный узел.
|
|
|
Для решения такого типа задач была разработана программа, позволяющая выполнять определенные действия с графами.
При работе с программой сначала необходимо построить граф. Для этого необходимо установить вершины и дуги между ними. Затем ввести значения пропускных способностей дуг в матрицу смежности вершин. Вычисления проводятся по алгоритму Форда-Фалкерсона [2, с. 267]. В результате пользователю выводится итоговая матрица вычислений и значение максимального потока.
Преимущество этой программы заключается в том, что помимо ввода пропускных способностей в матрицу, вначале строится граф для удобного визуального представления сети. Также данная программа является полезной для работы с транспортными задачами в математическом моделировании, а конкретнее для вычисления максимального количества ресурсов, которое идёт по сети. Сетевое планирование здесь не исследуется, так как гораздо больший интерес представляет сеть связи, где пропускные способности ребёр – это обычно «количество одновременных разговоров», которые могут происходить между телефонными узлами (вершинами графа).
Таким образом, данная работа будет востребована в сферах управления и осуществления контроля в транспортной отрасли, является основополагающей в вопросах градостроительства, а также в вопросах включения отдельных узлов в единую систему транспортных сетей.
|
|
|
Литература:
1. Костюкова, Н.И. Графы и их применение. Комбинаторные алгоритмы для программистов. / Н.И. Костюкова– М.: Издательство БИНОМ, 2007. – 311 с.: ил.
2. Костевич, Л.С. Математическое программирование / Л.С. Костевич – Мн.: Издательство ООО «новое знание», 2003. – 424 с.: ил.
Использование логистических моделей межвидовой конкуренции при подготовке биологов-экологов
Булах А.В.,
студент 3 курса УО «ВГУ им. П.М. Машерова», г. Витебск, Республика Беларусь
Целью нашей работы является создание имитационной учебной экологической модели как продукта проекта, для изучения жизни двух популяций, находящихся в отношениях «хищник-жертва», и исследования процессов (исследовательская часть проекта), происходящих в этой системе, а также использование созданной экологической модели на уроках экологии, биологии и информатики.
Для реализации данной цели были сформулированы следующие задачи:
· Выбор реальной экологической системы для моделирования и определения популяционных видов, взаимодействующих в этой системе.
|
|
|
· Определение существенных факторов, влияющих на жизнь популяции, которые необходимо учитывать в модели.
· Определение связей между факторами и элементами популяций.
· Определение начальных параметров системы.
Одновременно с этими задачами необходимо было решить задачи из области компьютерного моделирования.
· Выбор среды программирования.
· Определение «границ» программирования (изменяемые параметры).
· Выбор интерфейса.
Реализация поставленных задач.
Для исследования была выбрана экологическая система, состоящая из популяций рысей и кроликов, которая представляет собой систему взаимоотношений «хищник-жертва». Такой выбор обусловлен тем, что подобные модели описаны в учебной литературе, а полученный в ходе проектной работы продукт по своим целям предназначен для использования в обучающем процессе.
Уравнения баланса между численностью рожденных и гибнущих особей описываются дифференциальными уравнениями второго порядка.
Программа позволяет изменяя популяционные параметры оценить периоды колебаний численностей хищников и жертв.
В ходе выполнения работы студентам предлагается выполнить следующие задания:
|
|
|
1. Проанализируйте поведение системы при различных параметрах ε, Г, s.
2. Запишите закон изменения x(t) для заданных параметров ε, Г, s.
3. Постройте графики x(t). Кривые для каждого вида параметров должны быть представлены на одном рисунке
4. Оцените характерные величины процесса:
a. стационарное значение Xст сравните с расчетными данными Хст = ε/Г
5. Постройте графики Хст(ε), Хст(Г)
6. Проанализируйте поведение системы при изменении начальной численности особей Х0
7. Сделайте вывод.
Рис. 1. Интерфейс программы «Модель Вольтерра»
Дата добавления: 2018-05-09; просмотров: 236; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!