Магистерская диссертация 2009 Журак И.К. 1 БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ФАКУЛЬТЕТ ПРИКЛАДНОЙ МАТЕМАТИКИ и ИНФОРМАТИКИ Кафедра информационного. - презентация

1 Магистерская диссертация 2009 Журак И.К. 1 БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ФАКУЛЬТЕТ ПРИКЛАДНОЙ МАТЕМАТИКИ и ИНФОРМАТИКИ Кафедра информационного и программно-математического обеспечения автоматизированных производств ОПТИМИЗАЦИЯ МУЛЬТИПОТОКОВ В ОБОБЩЕННОЙ СЕТИ ЖУРАК ИРИНА КОНСТАНТИНОВНА Руководитель работы Пилипчук Людмила Андреевна Доцент кафедры ИПМОАП

2 Магистерская диссертация 2009 Журак И.К. 2 Научная гипотеза ОПТИМИЗАЦИЯ МУЛЬТИПОТОКОВ В ОБОБЩЕННОЙ СЕТИ Если реализовать симплекс-метод с учетом специфики экстремальной неоднородной задачи с взаимосвязью потоков и свойств опоры, то получается метод, который намного эффективнее симплекс-метода.

3 Магистерская диссертация 2009 Журак И.К. 3 Поставленные цели и задачи ОПТИМИЗАЦИЯ МУЛЬТИПОТОКОВ В ОБОБЩЕННОЙ СЕТИ Разработать опорные методы решения неоднородных задач оптимизации потока в обобщенной сети, основанные на учете специфики опоры, ее сетевых свойств и использовании численных результатов предыдущих итераций. Запрограммировать двойственные опорные алгоритмы решения неоднородных экстремальных задач потокового программирования с взаимосвязью потоков различных видов (обобщенная сеть) с использованием современных технологий численного решения неоднородных задач указанного класса.

4 Магистерская диссертация 2009 Журак И.К. 4 Сгенерировать математические модели (прямые и двойственные неоднородные задачи) с взаимосвязью потоков различных видов с использованием форматов системы Tex. Построить решения сгенерированных задач в КТС Mathematica с использованием встроенных функций. Провести необходимые расчеты, установить параметры и размеры исследуемых неоднородных задач, которые можно решить с использованием встроенных функций в КТС Mathematica. Поставленные цели и задачи ОПТИМИЗАЦИЯ МУЛЬТИПОТОКОВ В ОБОБЩЕННОЙ СЕТИ

5 Магистерская диссертация 2009 Журак И.К. 5 Объект исследования. Методы исследования. Область применения ОПТИМИЗАЦИЯ МУЛЬТИПОТОКОВ В ОБОБЩЕННОЙ СЕТИ Объект исследования – алгоритмы решения экстремальных неоднородных задач потокового программирования в случае обобщенной сети. Методы исследования – методы линейной алгебры, теории алгоритмов, оптимизации, потокового программирования. Область применения – транспортные системы, электрические цепи, компьютерные сети.

6 Магистерская диссертация 2009 Журак И.К. 6 Актуальность ОПТИМИЗАЦИЯ МУЛЬТИПОТОКОВ В ОБОБЩЕННОЙ СЕТИ Успехи, достигнутые в решении больших задач, позволят с помощью современных ЭВМ решать специальные задачи линейного программирования, имеющие миллионы переменных и сотни тысяч основных ограничений, с минимальными затратами ресурсов (время, оперативная память).

7 Магистерская диссертация 2009 Журак И.К ОПТИМИЗАЦИЯ МУЛЬТИПОТОКОВ В ОБОБЩЕННОЙ СЕТИ Математическая модель (1)

8 Магистерская диссертация 2009 Журак И.К Общий вид двойственной задачи: (2) ОПТИМИЗАЦИЯ МУЛЬТИПОТОКОВ В ОБОБЩЕННОЙ СЕТИ

9 Магистерская диссертация 2009 Журак И.К Классификация методов решения экстремальных задач Альсевич, В. В. Оптимизация линейных экономических моделей: Статические задачи: Учеб. пособие/В. В. Альсевич, Р. Габасов, В. С. Глушенков. Мн.: БГУ, с.: ил. Стр Итеративные методы: конечные и неконечные; прямые и непрямые; (Прямые методы строят итерации для прямых (исходных) задач. Если решение прямой задачи получается из решения других (вспомогательных) задач, то метод называется непрямым.) точные и приближенные. ОПТИМИЗАЦИЯ МУЛЬТИПОТОКОВ В ОБОБЩЕННОЙ СЕТИ

10 Магистерская диссертация 2009 Журак И.К. 10 Опора сети есть множество дуг такое что система имеет только тривиальное решение при и имеет нетривиальное решение при для любой дуги Структура опоры (3) ОПТИМИЗАЦИЯ МУЛЬТИПОТОКОВ В ОБОБЩЕННОЙ СЕТИ

11 Магистерская диссертация 2009 Журак И.К. 11 Структура опоры ОПТИМИЗАЦИЯ МУЛЬТИПОТОКОВ В ОБОБЩЕННОЙ СЕТИ Опр. Опоры

12 Магистерская диссертация 2009 Журак И.К. 12 Строим псевдопоток из системы: Этапы решения двойственной задачи (4) ОПТИМИЗАЦИЯ МУЛЬТИПОТОКОВ В ОБОБЩЕННОЙ СЕТИ

13 Магистерская диссертация 2009 Журак И.К. 13 Строим направление изменения вектора оценок Этапы решения двойственной задачи (5) ОПТИМИЗАЦИЯ МУЛЬТИПОТОКОВ В ОБОБЩЕННОЙ СЕТИ

14 Магистерская диссертация 2009 Журак И.К. 14 Основные результаты Исследована неоднородная задача потокового программирования с взаимосвязью потоков различных типов на обобщенной сети. Построены правила перехода к двойственной задаче и условие согласования. Доказан критерий оптимальности, получена формула приращения целевой функции, построена итерация метода с симплекной нормировкой. ОПТИМИЗАЦИЯ МУЛЬТИПОТОКОВ В ОБОБЩЕННОЙ СЕТИ

15 Магистерская диссертация 2009 Журак И.К. 15 Двойственный алгоритм решения экстремальной неоднородной задачи потокового программирования реализован с помощью языка программирования С++. Разработаны структуры данных для построения численных решений разреженных систем вычисления вектора псевдопотоков и вектора приращения потенциалов. Основные результаты ОПТИМИЗАЦИЯ МУЛЬТИПОТОКОВ В ОБОБЩЕННОЙ СЕТИ Выпускная работа по ОИТ

16 Магистерская диссертация 2009 Журак И.К. 16 Спасибо за внимание