WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!

Pages:     |
|

На правах рукописи

Афраймович Лев Григорьевич

РАСПРЕДЕЛЕНИЕ ограниченных ресурсов в иерархических системах транспортного типа

Специальность 05.13.18

Математическое моделирование, численные методы

и комплексы программ

(физико-математические науки)

АВТОРЕФЕРАТ

диссертации на соискание ученой степени
кандидата физико-математических наук

Нижний Новгород
2006

Работа выполнена на кафедре информатики и автоматизации научных исследований Нижегородского государственного университета им. Н.И. Лобачевского

Научный руководитель: доктор технических наук, профессор

Прилуцкий Михаил Хаимович

Официальные оппоненты:

доктор физико-математических наук, профессор

Иорданский Михаил Анатольевич

кандидат физико-математических наук, доцент

Баркалов Александр Валентинович

Ведущая организация: Институт проблем управления РАН (Москва)

Защита диссертации состоится « 23 » ноября 2006г.
в аудитории 229 корпуса 2 Нижегородского государственного университета им. Н.И. Лобачевского в 1430 часов на заседании Диссертационного совета Д 212.166.13.

Заверенные отзывы просим направлять по адресу: 603600, Н. Новгород, проспект Гагарина, 23, Нижегородский государственный университет им. Н.И. Лобачевского, Диссертационный совет Д 212.166.13.

С диссертацией можно ознакомиться в фундаментальной библиотеке университета.

Автореферат разослан « 12 » октября 2006г.

Ученый секретарь диссертационного совета,

кандидат физико-математических наук, доцент Савельев В.П.

Актуальность темы исследования

В середине XX века появился особый интерес к исследованиям многоиндексных задач линейного программирования транспортного типа. Это было обусловлено широким многообразием прикладных задач, формализуемых в виде данного частного класса задач линейного программирования. Особое место среди подобных прикладных задач занимают задачи распределения ресурсов в сложных системах, моделируемых сетевыми структурами, к которым в частности относятся и рассматриваемые в диссертационной работе задачи распределения ресурсов в иерархических системах транспортного типа.

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

Рассматриваемые в диссертационной работе задачи возникают, например, при распределении энергоресурсов между поставщиками и потребителями, базового сырья при производстве строительных материалов, мощностей каналов передачи данных провайдерами сети ИНТЕРНЕТ, нагрузки распределенной вычислительной сети, объема работ производства и так далее.

Из отечественных ученых существенный вклад в развитие рассматриваемого в диссертационной работе класса задач внесли Гольштейн Е.Г., Канторович Л.В., Карзанов А.В., Подчасова Т.П., Юдин Д.Б., Шкурба В.В. и другие. Среди зарубежных ученых развитием этой области занимались Danzig G.L., Hitchcock F.L., Hu T.C., Koopmans T.C. и другие. Следует также отметить школу Нижегородского университета и ученых  Батищева Д.И., Прилуцкого М.Х., Когана Д.И., Федосенко Ю.С., которые рассматривали подобные проблемы.

Цель работы

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

Методы исследования

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

Научная новизна

1. Построены общие математические модели распределения ресурсов в одноресурсной, многоресурсной и многоиндексной иерархических системах транспортного типа.

2. Проведено исследование построенных математических моделей распределения ресурсов в иерархических системах транспортного типа, построены алгоритмы проверки совместности и поиска допустимого варианта распределения ресурсов.

3. Поставлена общая многокритериальная задача распределения ресурсов в иерархических системах транспортного типа, применены схемы компромисса решения поставленной многокритериальной задачи.

4. Построены эффективные алгоритмы решения поставленных оптимизационных задач распределения ресурсов в иерархических системах транспортного типа.

5. Сформулирована концепция сводимости, применяемая при построении алгоритмов решения поставленных задач, основанных на сводимости к потоковым задачам.

Теоретическая и практическая значимость

В рамках построенных математических моделей описываются многие реальные прикладные задачи, связанные с проблемой распределения ресурсов. В качестве примеров можно отметить задачу распределения мощностей каналов передачи данных провайдерами сети ИНТЕРНЕТ, транспортную задачу с промежуточными пунктами, задачу объемно-календарного планирования и другие. Для решения данных задач могут применяться разработанные и программно реализованные в ходе выполнения исследования алгоритмы, позволяющие сократить объем вычислений, обеспечивая возможность решения прикладных задач достаточно большой размерности.

Апробация полученных результатов

Полученные в диссертационной работе результаты обсуждались на Всероссийской конференции «КоГраф 2002» (Нижний Новгород, 2002 г.), Международных научно-практических семинарах «Высокопроизводительные параллельные вычисления на кластерных системах» (Нижний Новгород, 2002 и 2003 г.), Нижегородских сессиях молодых ученых (Саров, 2003 и 2004 г., Нижний Новгород, 2004 г.), Научно-технической конференции ООО ТЕКОМ «Технические, программные и математические аспекты управления сложными распределенными системами» (Нижний Новгород, 2003 г.), Юбилейной научно-технической конференции ВМК ННГУ и НИИ ПМК, «Математика и кибернетика 2003» (Нижний Новгород, 2003 г.), VI международном конгрессе по математическому моделированию (Нижний Новгород, 2004 г.), Конференциях «Технологии Microsoft в теории и практике программирования» (Москва, 2005 г., Нижний Новгород, 2006 г.), Международной научной конференции, приуроченной к 200-летию со дня рождения Карла Густава Якоби (Калининград, 2005 г.), XIV международной конференции «Проблемы теоретической кибернетики» (Пенза, 2005 г.), научном семинаре отделения информатики университета г. Падерборна (Германия, г. Падерборн, 2005 г.), а также на научном семинаре кафедры информатики и автоматизации научных исследований факультета ВМК ННГУ (2006 г.).

Результаты диссертационной работы используются в учебном процессе Нижегородского государственного университета им. Н.И. Лобачевского на факультете ВМК при преподавании курса «Моделирование сложных систем» 1.

Разработанная программная система, составляющая прикладную часть диссертационной работы прошла апробацию при составлении план - графиков деятельности отделов ГУП ОКБМ им. Н.И. Африкантова (Нижний Новгород). Полученные результаты позволяют говорить об адекватности математических моделей, заложенных в основу созданного программного продукта, условиям реального производства.

Структура и объем работы

Работа состоит из введения, трех глав, заключения, списка литературы и приложения. Общий объем работы составляет 132 страницы. Список литературы включает 118 наименований.

Публикации

Основные полученные в диссертации результаты отражены в 19 публикациях (в том числе 7 статьях, 2 из которых опубликованы в ведущих рецензируемых научных журналах). Список публикаций приведен в конце автореферата.

Краткое содержание работы

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

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

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

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

Среди множества элементов системы выделяется подмножество контролируемых элементов, с которыми связаны функции предпочтения, определяющие условия эффективного функционирования системы.

Задача заключается в распределении ресурсов таким образом, чтобы были выполнены все ограничения иерархической системы, и распределение удовлетворяло эффективной схеме функционирования системы.

В соответствии с количеством различных типов распределяемых ресурсов иерархические системы разделяются на одноресурсные и многоресурсные. Особый интерес также представляют так называемые многоиндексные иерархические системы.

Одним из примеров задачи распределения ресурсов в одноресурсной иерархической системе является задача распределения мощностей каналов передачи данных провайдерами сети ИНТЕРНЕТ; в многоресурсной иерархической системе – транспортная задача с промежуточными пунктами; в многоиндексной иерархической системе – задача объемно-календарного планирования.

Во второй главе строится общая математическая модель проблемы распределения ресурсов в одноресурсных, многоресурсных и многоиндексных иерархических системах транспортного типа. Проводится исследование вопросов совместности построенных математических моделей.

В разделе 2.1 рассматривается случай одноресурсной иерархической системы. Иерархическую систему будем моделировать ориентированным графом G=(V,A) без петель и контуров, AV2, множество V, |V|=n, вершин которого соответствует элементам системы, а множество A, |A|=m, дуг – связям между элементами системы.

Введем вспомогательные обозначения: Qi={j|(i,j)A}, Ri={j|(j,i)A}, i.

Пусть X= – матрица, элемент xij которой определяет количество ресурсов, переданных по связи (i,j), (i,j)A. Ограничения на суммарные объемы ресурсов будем задавать с использованием множества U,.

Общая математическая модель распределения ресурсов в одноресурсной иерархической системе транспортного типа при заданном множестве U имеет следующий вид:

, iV,

(2.1) 2

, (i,j)A,

(2.2)

,,

(2.3)

где [Bi,Ci] – сегмент, соответствующий балансным ограничениям элемента i, BiCi, BiCi0, iV; [Dij,Eij] – сегмент, соответствующий пропускной способности связи (i,j), 0DijEij, (i,j)A; – сегмент, соответствующий ограничениям суммарного объема ресурсов, определяемого множеством,,.

Будем обозначать через, и множество производителей ресурсов, передающих элементов и потребителей ресурсов, соответственно.

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

Для исследования системы (2.1)-(2.3) могут быть использованы общие методы решения систем линейных неравенств. Однако специфика построенной математической модели позволила в некоторых частных случаях предложить более эффективные алгоритмы, основанные на сводимости к потоковым моделям.

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

Определение 3. Матрица,, сводится, сохраняя соответствие допустимости, к матрице,, если существует отображение такое, что для системы линейных неравенств вида, обозначаемой через, можно построить систему линейных неравенств вида, обозначаемую через, такую, что

  • если является допустимым решением системы, то является допустимым решением системы ;
  • система не совместна, если не совместна система ;
  • все компоненты вектора целочисленны, если целочисленны все компоненты вектора.

Определение 4. Система линейных неравенств сводится, сохраняя соответствие между переменными, к системе линейных неравенств, если матрица ограничений системы сводится, сохраняя соответствие допустимости, к матрице ограничений системы.

Под объемом ресурсов, соответствующих элементу i, обозначаемым через, будем понимать следующее выражение: если если В случае, когда ограничения суммарных объемов ресурсов представляют собой ограничения объемов ресурсов, соответствующих элементам системы, условия (2.3) имеют следующий вид:

, iV,

(2.9)

где для удобства через [Hi,Ii] обозначается сегмент, связанный с ограничением объема ресурсов, соответствующих элементу i, 0HiIi, iV.

Математическая модель распределения ресурсов в одноресурсной иерархической системе с ограничениями объемов ресурсов, соответствующих элементам системы, представляет собой систему ограничений (2.1),(2.2),(2.9), исследование которой сводится к поиску допустимой циркуляции транспортной сети.

Обоснование сводимости требует некоторых вспомогательных результатов.

Pages:     |
|



© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.