Технологии программирования задач сетевой оптимизации

Министерство образования Республики беларусь

 

БЕЛОРУССКИЙ  ГОСУДАРСТВЕННЫЙ  УНИВЕРСИТЕТ

 

Факультет прикладной математики и информатики

 

 

Кафедра компьютерных технологий и систем

 

Кафедра методов оптимального управления

 

КРИВОРОТ МАРГАРИТА ИВАНОВНА

 

ТЕХНОЛОГИЯ ПРОГРАММИРОВАНИЯ ЗАДАЧ СЕТЕВОЙ ОПТИМИЗАЦИИ

 

Курсовой проект

студентки 3 курса 10 группы

 

 

“Допустить к защите“ Руководитель проекта Пилипчук Людмила Андреевна доцент кафедры КТС канд. физ.-мат. наук ________________ “___”  ___________ 2012 г

 

 

 

 

Минск 2012

 

Белорусский  государственный  университет

Факультет  прикладной  математики и информатики

 

“Утверждаю”

Заведующий кафедрой

_______________В.Б. Таранчук

“___”  _______________  2012 г.

 

ЗАДАНИЕ

ПО  ПОДГОТОВКЕ  КУРСОВОГО  ПРОЕКТА 

Студентке 3 курса  Криворот Маргарите Ивановне (группа 10)

 

1. Тема работы  ТЕХНОЛОГИЯ ПРОГРАММИРОВНИЯ ЗАДАЧ СЕТЕВОЙ ОПТИМИЗАЦИИ. (PLA-1-03)

 

2. Срок сдачи студентом законченной работы  26 декабря 2012 г.

 

3. Исходные данные к работе

• Примеры решения систем линейных алгебраических уравнений (СЛАУ).
• Образцы технических заданий и проектов.
• Технические требования к электронным версиям отчетных документов, рекомендации составителям

Библиографические описания источников, рекомендуемых студентам к ознакомлению при выполнении работы:

1. Пилипчук Л.А.: Линейные неоднородные задачи потокового программирования:  Учебное пособие. Минск, БГУ, 2009. - 222 с.
2. Ravindra K. Ahuja, Thomas L. Magnanti, James B. Orlin. Network Flows: Theory, Algorithms, and Applications - Prentice Hall, Englewood Cliffs, New Jersey, 1993. - 840 p.
3. East West Journal of Mathematics / L.A. Pilipchuk, Y. V. Malakhouskaya, David R. Kincaid, Minghorng Lai - Vol. 4, No 2 (2002) pp. 191-201 - Algorithms of Solving Large Sparse Underdeterminated Linear Systems with Embedded Network Structure.
4. Таранчук В.Б. Графический сервис вычислительного эксперимента. [Электрон. ресурс] БГУ, факультет прикладной математики и информатики, \\Serv314\subfaculty\Каф. КТС\TarVB\ БылоДо2011\1_ZapuskUst-ki_v0609.nb, 3_Grafika_v0609.nb
5. L. Bianco, G. Confessore, M. Gentili Combinatorial Aspects of the Sensor Location Problem. Annals of Operation Research - 144, 1, 201-234 (2006).
6. Pilipchuk L. A: Network optimization problems. Applications of Mathematics in Engineering and Economics '27 , eds. D. Ivanchev and M.D.Todorov, Heron Press, Sofia, 2002.

 

4. Перечень вопросов подлежащих разработке или краткое содержание работы

• Ознакомиться со спецификой построения решений недоопределенных СЛАУ.
• Проанализировать неоднородные задачи потокового программирования со взаимосвязью потоков различного типа.
• Реализовать средствами пакета MATHEMATICA и объектно-ориентированного языка программирования Java алгоритмы решения СЛАУ с использованием точных методов.
• Реализовать средствами пакета MATHEMATICA графическую визуализацию алгоритма решения СЛАУ
• Освоить приемы подготовки скриншотов и включения их в отчеты doc, компьютерные презентации ppt.

 

 

5. Перечень графического материала

• Логотип БГУ для включения на слайды презентации.
• Иллюстрации сравнительного анализа изучаемых задач.
• Скриншоты интерфейса для включения в презентацию.

 

6. Дата выдачи задания  __ сентября 2012 г.

 

7. Календарный график работы на весь период (с указанием этапов работы и  
сроков их выполнения)

• сентябрь – ознакомление с предлагаемыми темами, выбор и согласование темы с руководителем;
• сентябрь – ознакомление с техническими требованиями к электронным отчетным документам (doc, ppt, pdf) и освоение правил, как их реализовать;
• сентябрь-октябрь – изучение постановки задачи, основных теоретических вопросов; изучение основ программирования в КТС Mathematica;
• октябрь-ноябрь – информационный поиск, работа с электронными ресурсами, программирование секций вычислений и визуализации;
• ноябрь – практическая реализация задач проекта;
• декабрь – оформление результатов работы (отчета DOC, презентации PPT, NB), подготовка доклада и отладка презентации на защиту;
• : защита, зачет.

 

Руководитель ______________ / Л.А. Пилипчук / …. сентября 2012 г.

 

Задание принял к исполнению __________________ .… сентября 2012г.

(подпись студента)

 

 

 

 

 

Аннотация

Криворот М.И. Технология программирования задач сетевой оптимизации. Курсовой проект / Минск: БГУ, 2012 – 49 с.

Изложены методы решения разреженных недоопределенных систем линейных алгебраических уравнений с помощью эффективных алгоритмов, основанных на декомпозиции линейных систем и учете их сетевых свойств, рассмотрены примеры решения таких задач и продемонстрировано использование встроенных методов пакета Mathematica и объектно-ориентированного языка программирования JAVA.

 

Annotation

Krivorot M.I. Technology of programming network optimization problems Course project / Minsk. BSU, 2012 – 49 p.

The methods of solving systems of linear underdetermined algebraic equations using effective algorithms, based on decomposition of linear system and using systems’ network properties, are explored in this project. Also there are examples, which display solving such kinds of systems using embedded methods of system packet Mathematica and object oriented programming language JAVA.

Анатацыя

Крыварот М.І. Тэхналогія праграмавання задач сеткавай аптымізацыі. Курсавы праект / Мiнск: БДУ, 2012 – 49 с.

Выкладзены метады рашэння разрэджаных недавызначаных сiстэм лiнейных алгебраiчных раўнанняў з дапамогай эфектыўных алгарытмаў, заснаваных на дэкампазіцыі лiнейных сістэм і ўліку сеткавых уласцівасцяў , разгледжаны прыклады рашэння такiх задач i прадэманстравана выкарыстанне для гэтага ўбудаваных метадаў пакета Mathematica i аб'ектна арыентаванай мовы праграмавання JAVA.

 

 

РЕФЕРАТ

 

Курсовой проект, 49 с., 20 рис., 5 табл., 6 источников.

 

Ключевые слова: ЛИНЕЙНАЯ СИСТЕМА, НЕДООПРЕДЕЛЁННАЯ СИСТЕМА, НЕДООПРЕДЕЛЕННЫЕ СИСТЕМЫ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ, КОНЕЧНАЯ ОРИЕНТИРОВАННАЯ СВЯЗНАЯ СЕТЬ, ОПОРА СЕТИ, ХАРАКТЕРИСТИЧЕСКИЕ ВЕКТОРЫ, ЦИКЛ, ДЕТЕРМИНАНТ ЦИКЛА, ДЕКОМПОЗИЦИЯ СИСТЕМЫ.

Объект исследования – разреженные недоопределенные системы линейных алгебраических уравнений, методы решения системы алгебраических уравнений специального вида для оценки потоков в конечных ориентированных связных сетях.

Цель работы – изучить компьютерную техническую систему Mathematica и объектно-ориентированный язык программирования Java на примере нахождения решения разреженных недоопределенных систем линейных алгебраических уравнений.

Методы  исследования – методы матричного анализа, вычислительные методы алгебры и методы  линейного программирования.

Результатом является вычисленный по входным данным вектор-столбец, наиболее удовлетворяющий системе (по возможности, являющийся решением системы).

Область применения – логистика, решение транспортных задач и задач мониторинга перемещения трафика любого типа.

 

 

Оглавление

 

 

 

 

 

 

Введение

Задачей данного проекта является рассмотрение технологии программирования задач сетевой оптимизации. Для этого необходимо решение разреженных недоопределенных систем линейных алгебраических уравнений, выделение из бесконечного множества решений одного, оправданного с математической   точки   зрения,   и   предложение   алгоритма   его поиска.   Для построения решения в данном проекте используются такой пакет прикладных программ, как КТС Mathematica, и средства объектно-ориентированного языка программирования JAVA. Также анализируются неоднородные задачи потокового программирования с взаимосвязью потоков различных типов и учетом ограничений на пропускные способности дуг.

Пакеты прикладных программ (аббр. ППП, англ. Software package) — комплекс взаимосвязанных программ, предназначенных для решения задач определенного класса конкретной предметной области. Служат программным инструментарием решения функциональных задач и являются самым многочисленным классом программных продуктов.

Объектно-ориентированный язык программирования (ОО-язык) — язык, построенный на принципах объектно-ориентированного программирования. В основе концепции объектно-ориентированного программирования лежит понятие объекта — некой субстанции, которая объединяет в себе поля (данные) и методы (выполняемые объектом действия).

Mathematica — система компьютерной алгебры компании Wolfram Research. Содержит множество функций как для аналитических преобразований, так и для численных расчётов. Кроме того, программа поддерживает работу с графикой и звуком, включая построение дву- и трёхмерных графиков функций, рисование произвольных геометрических фигур, импорт и экспорт изображений и звука.

Java — объектно-ориентированный язык программирования, разработанный компанией Sun Microsystems (в последующем приобретённой компанией Oracle). Приложения Java обычно компилируются в специальный байт-код, поэтому они могут работать на любой виртуальной Java-машине (JVM) вне зависимости от компьютерной архитектуры. Достоинство подобного способа выполнения программ — в полной независимости байт-кода от операционной системы и оборудования, что позволяет выполнять Java-приложения на любом устройстве, для которого существует соответствующая виртуальная машина. Другой важной особенностью технологии Java является гибкая система безопасности благодаря тому, что исполнение программы полностью контролируется виртуальной машиной.

 

 

Часть 1

 

1. Разреженные недоопределенные системы

1.1 Общий вид системы

Рассмотрим конечную ориентированную связную сеть без кратных дуг и петель, где множество узлов, – множество дуг, определенных на , . Пусть – множество различных продуктов (типов потока), транспортируемых в сети (). Для определенности введем множество Обозначим связную сеть, соответствующую типу потока через   , – множество дуг сети . Определим множества и типов потока, транспортируемых через каждый узел и каждую дугу соответственно.

Введем подмножество множества и подмножества  , для каждого из которых выполняется условие: . Таким образом, начальная сеть   может быть представлена в виде объединения сетей , .

Рассмотрим линейную недоопределенную систему вида:

 

 

 

где ,,; – вектор неизвестных.

Рассмотрим построения системы (1)  – (3) на рисунке 1.

 

 

Рисунок 1. – Пример системы (1) – (3)

 

Матрица системы (1) – (3) имеет следующую блочную структуру:

(4)

Здесь М – разреженная матрица блочно-диагонального вида размера , каждый блок которой представлен матрицей инцидентности сети , т.е где - блоки матрицы М; - подматрица (в общем случае плотная ) с элементами ; одматрица, состоящая из нулей и единиц, где все ненулевые элементы столбцов соответствуют дугам . Предположим, что

 

1.2 Сетевая часть  системы

Построение решения системы (1) – (3) начнем с рассмотрения сетевой части системы.

Определение 1.2.1. Система называется сетевой частью системы – . Системы называются дополнительной частью системы –

Прежде чем начать построение решения системы , укажем необходимые и достаточные условия существования решения (теорема Кронекера – Капелли):

 

Теорема 1.2.1. Ранг матрицы системы   равен

Доказательство. Поскольку матрица M системы   имеет вид , где – диагональный блок матрицы M, , и то = 

 

Замечание 1.2.1. Предположим, без ограничения общности, что ранг системы равен , где – число  уравнений дополнительной части

Поскольку матрица системы имеет блочно-диагональную структуру, разбиваем систему на независимых систем, каждая из которых соответствует отдельному блоку для фиксированного и имеет следующий вид:

 

1.2.1 Критерий  опорности

Определим опору сети  для системы

Определение 1.2.2. Опора сети   для системы есть множество дуг , такое, что система

 

имеет только тривиально решение для , но нетривиальное решение для   , 

 

Сформулируем сетевой критерий опорности.

Теорема 1.2.2.  Множество является опорой сети   для системы тогда и только тогда, когда для каждого множество дуг является покрывающим (остовным) деревом сети .

Доказательство. Следует непосредственно из [5] для случая и блочно-диагональной структуры матрицы системы  

 

1.2.2.  Характеристические векторы

Прежде чем вводить определение характеристического вектора, проанализируем структуру сети, полученную в результате добавления произвольной дуги , где фиксировано, к опоре сети S для системы

Для фиксированного рассмотрим сеть где – множество дуг покрывающего (остовного) дерева  сети. Добавление дуги к дереву порождает единственный цикл, который обозначим . Множество есть множество фундаментальных циклов относительно выбранного покрывающего дерева сети .