ИСМАГУЛОВА ЖУЛДЫЗ САУЕЛХАНОВНА

УДК   519.8:519.876.3                                                                На правах рукописи

 

 

 

 

 

 

 

 

 

ИСМАГУЛОВА ЖУЛДЫЗ САУЕЛХАНОВНА

 

 

Разработка и исследование методов распределения ресурсов на сетевых моделях в условиях неопределенности

 

 

 

05.13.01 – Системный анализ, управление и обработка информации

 

 

 

 

 

 

Автореферат

диссертации на соискание ученой степени

кандидата технических наук

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Республика Казахстан

Алматы, 2010

 

Работа выполнена в Казахской академии транспорта и коммуникаций им. М. Тынышпаева.

 

 

 

 

Научный руководитель:

 

доктор технических наук

Ташев А.А.

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

доктор технических наук

Нысанбаева С.Е.

 

кандидат технических наук

Шевяков В.Ю.

 

 

Ведущая организация: 

Институт математики

Министерства образования

и науки Республики Казахстан

 

 

 

 

 

Защита состоится «12» марта 2010г. в 16.00 часов на заседании объединенного диссертационного совета Д14.13.03 при Казахском национальном техническом университете имени К.И. Сатпаева по адресу:

Республика Казахстан, 050013, г.Алматы, ул. Сатпаева 22, нефтянной корпус, конференц - зал.

 

 

 

С диссертацией можно ознакомиться в библиотеке Казахского национального технического университета имени К.И. Сатпаева

 

 

 

Автореферат разослан « __ »  _____ 2010 г.

 

 

 

 

Ученый секретарь

диссертационного совета                                           Б.Х. Айтчанов

 

ВВЕДЕНИЕ

 

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

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

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

В настоящее время для решения задачи РР в условиях неопределенности

используются различные аналитические, численные методы, а также методы,

 основанные на опыте и интуиции лица принимающего решения.

Методы решения таких задач рассматривались различными существующими научными школами. Большой вклад для решения рассматриваемого класса задач внесли советские ученые: Шкурба В.В., Подчасов Т.П., Бурдюк В.Я., Танаев B.C., Гордон B.C., Михалевич B.C., Шор Н.З., Мироносецкий Н.Б., Португал В.М., Батищев Д.И., Прилуцкий М.Х., Коган Д.И., Федосенко Ю.С., Н.Ш. Кремер, а также казахстанские ученые: Ашимов А.А., Шукаев Д.Н. и др.

Из зарубежных ученых необходимо отметить  Конвей Р., Джонсон Б., Максвелл У., Гиффлер Б., Томпсон Ж., Таха Х. и другие, которые внесли существенный вклад для решения задач сетевого планирования и управления.

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

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

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

1. Анализ проблем РР в сетевых моделях , выявление, систематизация и классификация основных типов неопределенностей, влияющих на этот процесс.

2. Разработка статических и динамических методов и алгоритмов  РР на сетевых моделях.

3. Разработка комплекса программ для решения задачи РР на сетевых моделях.

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

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

Научная новизна результатов исследования заключается в следующем:

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

- впервые предложена методика решения задачи РР на сетевых моделях в детерминированном случае, когда продолжительности выполнения работ фиксированы и зависят от выделенных ресурсов;

- впервые предложена методика решения задачи РР на сетевых моделях в условиях неопределенности, когда продолжительность выполнения работ фиксирована и зависит от выделенных ресурсов;

- теоретически исследованы эффективности разработанных методов РР на сетевых моделях;

- показана практическая эффективность разработанных методов и алгоритмов РР на сетевых моделях при решении конкретных задач.

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

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

Положения, выносимые на защиту:

- классификация неопределенностей, влияющих на РР;

- математическое описание неопределенностей, влияющих на РР;

-методы и алгоритмы решения задачи РР на сетевых моделях в детерминированном случае, когда продолжительности выполнения работ фиксированы и зависят от выделенных ресурсов;

- методы и алгоритмы решения задачи РР на сетевых моделях в условиях неопределенности, когда продолжительности выполнения работ фиксированы и зависят от выделенных ресурсов;

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

Внедрение результатов исследования. Выполненные в диссертационной работе исследования проводились в соответствии с планом госбюджетных работ кафедры «Вычислительная техника и информационные системы» АО «КазАТК им. М. Тынышпаева», г.Алматы.

Результаты работы внедрены в структурных подразделениях АО «КазТрансГаз Аймаќ», а также использованы при разработке лабораторных работ по дисциплинам: «Имитационное моделирование», «Теория систем и системный анализ», «Анализ и моделирование информационных систем» кафедры «Вычислительная техника и информационные системы» для студентов специальностей: 050704 – Вычислительная техника и программное обеспечение, 050703 – Информационные системы в Казахской академии транспорта и коммуникаций им. М.Тынышпаева.

Апробация работы. Основные положения и результаты диссертационной работы докладывались и обсуждались: на международных конференциях: Третьей международной научно - практической конференции «Транспорт Евразии: взгляд в XXI век». - Алматы, 2004; научно-практической конференции «От легендарного Турксиба к стратегической трансевразийской магистрали». – Алматы, 2006; Международной научно - практической конференции «Наука и инновации на железнодорожном транспорте».– Алматы, 2007; Пятой международной научно-практической конференции «Транспорт Евразии XXI века», посвященной 50-летию образования Единой Казахской железной дороги. - Алматы, 2008; на научных семинарах кафедры «Вычислительная техника и программное обеспечение» и НТС КазАТК М.Тынышпаева в 2008-2009 гг.

Публикации. Основные, вынесенные на защиту, научные результаты опубликованы в 10 печатных работах в изданиях, рекомендованных для публикации положений диссертации на соискание учёной степени кандидата технических наук, в том числе центральных научных журналах – 6, в материалах научных конференций – 4.

Структура и объём диссертации. Диссертационная работа состоит из введения, четырех глав, заключения, списка использованных источников из 130 наименований. Общий объем работы составляет 114 страниц машинного текста, 20 рисунков, 23 таблиц и 3 приложения.

 

ОСНОВНАЯ ЧАСТЬ

 

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

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

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

где     – множество вершины графа,

 множество дуг графа;

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

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

 

.

(1)

 

 

Рисунок 1 - Сетевая модель комплекса работ

 

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

 

,

(2)

 

где =( -  переменные характеризующие помехи, влияющие на выполнение работы .

Время выполнения комплекса работ T определяется  некоторой функцией

(3)

 

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

 

(4)

 

при ограничениях, задающих  на связь между работами  и

 

,

(5)

 

где M - знак математическое ожидания, -количество ресурсов -го типа.

В случае, когда используются только ресурсы одного вида, например, только денежные средства, то (4) при ограничениях (5) сводится к задаче

 

(6)

 

при ограничениях, задающих на связь между работами  и

 

(7)

 

А в детерминированном случае задача РР сводится к

 

(8)

 

при ограничениях , задающих на связь между работами  и

 

(9)

 

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

Во втором разделе приводятся классификация и систематизация задач РР на сетевых моделях. Здесь исследована и проведена классификация факторов, влияющих на РР, а также приведено математическое описание неопределенностей, влияющих на РР. Рассматриваются неопределенности, опсываемые: точечно, интервально, вероятностно, функционально и т.д.

Неопределенность принято характеризовать энтропией. Если  неопределенность описывается вероятностным распределением, то энтропия H (мера неопределенности) определяется по формуле:

 

,

(10)

 

где - - ый  интервал разбиения области изменения параметра .

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

 

G=<V, U >,,

(11)

 

где V - множество вершин, U -множество дуг (работ).

Сначала осуществляется упорядочение вершин графа G, т.е. разбивка множества вершин следующим образом:

1)  нулевая вершина nо    относится к нулевому рангу S0;

2) все вершины ÎV, которые имеют выходящие дуги из вершин ранга S0, относятся к первому рангу S1;

3) все вершины, следующие только за вершинами из рангов S0 или S1, относятся ко второму рангу S2 и т. д.

К m-му слою относятся  все вершины графы G, которые имеют выходящие дуги от вершин ранга Si, (последний ранг m содержит только конечную вершину).

Упорядочим вершины таким образом, чтобы  имело место неравенство i<j.

В результате этой процедуры получаются ранги Si,  и в каждом ранге можно пронумеровать вершины Î Si. Пусть в m-ом ранге имеется lm-вершин графа.

Предположим, что имеется некоторый случайный показатель П, характеризующий эффективность пути от одной вершины к другой, например, в качестве П может служить длина пути от 0 вершины до  m-го ранга. Необходимо найти   путь от 0-ой вершины к m-му рангу, чтобы показатель П принимал минимальное значение. Обозначим через Пi(j)k(l)-значение показателя при переходе из j-ой вершины ранга i в l-ую вершину ранга к. Тогда на первом этапе оптимальный переход  из вершины j ранга m-1 к рангу m (так как на m-м этапе одна вершина) определим как

 

П* m-1(j),m 

(12)

 

На втором этапе необходимо найти оптимальную траекторию, соединяющую вершины ранга m-2 с вершинами ранга m-1. Для этого определятся  минимум показателя  от вершины слоя m-2  к вершине m:

 

 

(13)

 

 

где - оптимальное значение показателя при переходе из j-ой вершины, m-2 ранга к m-му рангу.

Продолжая этот процесс для нулевой вершины имеем:

 

(14)

 

 

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

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

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

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

 

(15)

 

 

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

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

 

 ,

(16)

 

где M( )знак математического ожидания.

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

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

Выделяется множество путей П=(П1, П2, …, ПN), состоящее из путей, начальное и конечное события которых совпадают с событиями из критического пути. И для каждого П  выполняется нижеописанная процедура.

Если функции  являются линейными, то есть=-sit+bi,+ (- некоторое случайное значение ), то для выделенного множества путей решается следующая задача линейного программирования

 

(17)

 

при ограничениях

 

(18)

 

где критическое время для пути Пi.

В детерминированном случае значение .

Продолжительность работ будет равна

 

(19)

 

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

 

(20)

 

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

Описанный процесс оценки показателя осуществляется N раз. В результате получаются следующие значения показателей . Тогда оценка показателя определяется как

 

(21)

 

 

с доверительным интервалом

 

(22)

 

 

(23)

 

где  – оценка среднеквадратического отклонения;  - берется из таблицы интеграла Лапласа.

Далее представлены теоретические исследования задач РР. Пусть заданы n работ и M ресурсов и имеют место следующие соотношения:

 

1)

 

 

 

2)

 

 

3) .

 

 

Когда функции  является линейной, имеем

 

 

4)

 

5)  для всех

Здесь введены следующие обозначения:

 - затраты для выполнения работы i в момент времени t;

Rj  - общее количество ресурсов j-го типа;

 - время, необходимое для выполнения i-ой работы;

ti – начальное время выполнения i-ой работы;

- функция, характеризующая зависимость времени выполнения i –й работы оn выделенных ресурсов ;

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

Исследуем задачу нахождения способа распределения ресурсов (РР)  при ограничениях 2) – 4),  минимизирующего времени выполнения комплекса работ. Эта задача сводится к  нахождению минимального времени  выполнения последней работы n:

 

(24)

 

Рассмотрим два случая.

I. РР без учета взаимосвязи и взаимозависимости между работами.

Работы упорядочиваются по убыванию минимального времени выполнения:

 

(25)

 

Для этого случая  доказаны  теоремы.

Теорема 1. Для существования допустимого решения вышерассмотренной задачи РР необходимо и достаточно выполнение условия:

 

(26)

 

 

Теорема 2. Минимальное (необходимое) количество ресурсов для выполнения комплекса работ за минимальное время определяется формулами:

 

(27)

 

(28)

 

 для l:, 

(29)

 

 для l:, .

(30)

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

1. Находим минимальное время выполнения работ. Оно равно .

2. Определим затраты, необходимые для выполнения работы  по формуле

 

(31)

 

3. Определим затраты, необходимые для выполнения работ, у которых время выполнения охватывает время выполнения -ой работы

 

(32)

 

4. Определим затраты на работы, максимальное время выполнения которых меньше, чем времени выполнения работы

 

(33)

 

5. Определим суммарные затраты

 

;

(34)

 

В линейном случае время выполнения комплекса работ t определяется по формуле

 

(35)

 

II. РР с учетом взаимосвязи и взаимозависимости между работами

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

Утверждение 1. Минимальное время, необходимое для выполнения комплекса работ, определяется критическим путем, полученным при задании всем работам времени   , .

При этом оптимальное количество ресурсов определяется формулой

 

,

(36)

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

- затраты для выполнения работ, находящихся не на критическом пути.

Затраты  определяются по формуле

 

(37)

 

А для определения затрат  поступим следующим образом.

Для каждой работы определяем

 

, .

(38)

 

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

 

(39)

 

Выделим пути () из множества I, начинающиеся, и заканчивающиеся на критическом пути. Для каждого такого пути составляем неравенство

 

, ,

(40)

 

где - критический путь от начала до конца пути.

Функционал затрат имеет вид

 

=,

(41)

 

который необходимо минимизировать по  при ограничениях (40).

Эта задача есть задача линейного программирования, которая решается известным симплекс методом.

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

Общий объем  затрат составит

 

=

(42)

 

Минимальное время, необходимое для выполнения комплекса работ определяется формулой

 

,

(43)

 

где - множества работ из критического пути.

В третьем разделе приводятся алгоритмы и программы рассмотренных методов в разделе 2 для решения задачи РР, а также описание комплекса программ для РР на сетевых моделях в условиях неопределенности. Описываются программы  для решения следующих задач:

1. Определение  критического пути для детерминированного случая;

2. Определение критического пути в условиях неопределенности;

3. Распределение ресурсов на сетевых моделях в условиях неопределенности.

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

1. Задача нахождения оптимального проекта строительства железной дороги.

Пусть имеется две станции  (начальное состояние ) и  (конечное состояние ), которые нужно соединить железной дорогой. Допустим, что промежуток между станциями  и  можно разбить на четыре этапа, причем на каждом этапе состояние системы может принимать только семь значений. Другими словами, на каждом промежуточном этапе рассматриваем только семь возможных координат, через которых может пройти железнодорожный путь. Этим четырем промежуточным состояниям поставим в соответствии четыре состояния (рисунок 2).


 

Рисунок 2- Сетевой граф для определения оптимального проекта

 

Каждое состояние , , может принимать семь возможных значений, то есть =.

Для этой задачи получено оптимальное значение целевой функции из начального состояния :

13.5, а оптимальный путь есть  Оптимальные переходы из состояний  в   показаны жирной линией.

2. Оптимизация транспортировки газа по распределительным газопроводам.

Имеется ГРС, которая распределяет газ по двум пунктам ГРП-1 и ГРП-2. Пункты ГРП-1 и ГРП-2, в свою очередь, распределяют газ по 9-и потребителям (рисунок.3).

 

 

Рисунок 3 – Сетевой граф распределения газа

 

Объем газа в  ГРС составляет 111,68 млн.м3. Протяженности газопроводов между ГРС и поставщиками ГРП-1 и ГРП-2 составляют соответственно 2 и 3 км, а протяженности газопроводов между двумя поставщиками (ГРП-1, ГРП-2) и девяти потребителями  приведены в таблице 1.

 

Таблица 1- Исходные данные

 

Поставщики

Потребители

1

2

3

4

5

6

7

8

9

 

I

Протяженность газопроводов

10

15

7

20

30

16

24

21

0

II

12

17

19

31

25

8

11

13

0

Заявки

0,39

0,42

29,86

8,37

0,72

8,46

36,33

23,61

3,52

 

Задача заключалась в определении оптимального  объема газа, поставляемого из ГРС в пункты ГРП-1, ГРП-2, а также объема газа, поставляемого из пунктов ГРП-1 и ГРП-2 по девяти потребителям. Это задача была решена динамическим методом, описанным в разделе 2 диссертации. Для этого было составлена программа на Delphi 7. Результаты решения задачи представлены в таблице 2.

 

Таблица 2- Результаты оптимального распределения газа

 

Поставщики

Потребители

1

2

3

4

5

6

7

8

9

I

0,39

0,42

29,86

8,37

0,38

0

0

0

3,52

42,94

II

0

0

0

0

0,34

8,46

36,33

23,61

0

68,74

0,39

0,42

29,86

8,37

0,72

8,46

36,33

23,61

3,52

111,68

Оптимальное распределение газа из ГРС на ГРП-1, ГРП-2 составило 42,94 млн м3 и 68,74 млн м3, соответственно. При этом общие затраты составили

Z=59038000 тенге.

 

ЗАКЛЮЧЕНИЕ

 

В результате проведенных исследований автором получены следующие основные, имеющие научное и практическое значение, результаты:

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

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

3. Проанализированы неопределенности, влияющие на процесс РР, и осуществлена их систематизация и классификация.

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

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

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

7. Теоретически исследованы методы распределения ресурсов.

8. Разработаны программы для реализаций разработанных алгоритмов решения задач РР на сетевых моделях в условиях неопределенности.

9. Осуществлена практическая реализация разработанных методов и алгоритмов при решении конкретных задач.

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

Результаты работы внедрены в структурных подразделениях АО «КазТрансГаз Аймаќ» и дали положительный результат, а также использованы при разработке лабораторных работ по дисциплинам: «Имитационное моделирование», «Теория систем и системный анализ», «Анализ и моделирование информационных систем» кафедры «Вычислительная техника и информационные системы» для студентов специальностей: 050704 – Вычислительная техника и программное обеспечение, 050703 – Информационные системы в Казахской академии транспорта и коммуникаций им. М.Тынышпаева.

Список опубликованных работ по теме диссертации

 

1       Исмагулова Ж.С. Решение сетевых задач с использованием метода динамического программирования //Третья Международная научно– практическая конференция «Транспорт Евразии: взгляд в XXI век».- Алматы: Изд-во КазАТК, 2004. С. 127-131.

2       Исмагулова Ж.С. Распределение ресурсов на сетевых графиках в детерминированном случае //Материалы научно-практической конференции «От легендарного Турксиба к стратегической трансевразийской магистрали».- Алматы: Изд-во КазАТК, 2006.Т.2. Стр.40-44.

3       Исмагулова Ж.С. Оценка времени выполнения комплекса взаимосвязанных работ методом имитационного моделирования //«Наука и инновации на железнодорожном транспорте»: Междунар.науч.-практ. конф. -  Алматы: Изд-во КазАТК, 2007. Т.5. С.66-69.

4       Исмагулова Ж.С. Распределение ресурсов на сетевых графиках в условиях неопределенности //Материалы Международной научно-практической конференции «Наука и инновации на железнодорожном транспорте». – Алматы: Изд-во КазАТК, 2007. Т.5.Стр.61-66.

5       Исмагулова Ж.С. Оптимальное использование излишков ресурсов.- Алматы: Вестник КазАТК, №5, 2008.С. 110-114.

6       Ташев А.А., Исмагулова Ж.С. Разработка программного обеспечения для определение критического пути //Материалы Пятой Международной научно-практической конференции «ТРАНСПОРТ ЕВРАЗИИ XXI ВЕКА».- Алматы: Изд-во КазАТК, 2008.Т.4.С.45-49.

7       Исмагулова Ж.С. Классификация и систематизация задач распределения ресурсов в условиях неопределенности. - Алматы: Вестник КазАТК, № 6, 2008.С. 117-119.

8       Ташев А.А., Исмагулова Ж.С. Классификация факторов, влияющих на распределение ресурсов //Материалы Пятой Международной научно-практической конференции «ТРАНСПОРТ ЕВРАЗИИ XXI ВЕКА».- Алматы: Изд-во КазАТК, 2008.Т.3.С.82-84.

9       Кобдиков М.А., Ташев А.А., Исмагулова Ж.С. Нахождение кратчайшего маршрута на графе с циклами.- Алматы: Вестник КазАТК, №1, 2009.С.110-114.

10      Исмагулова Ж.С. Оптимальное РР в задачах календарного  планирования.- Алматы: Вестник КазГАСА,№ 4, 2009.С.108-113.

 

 

 

 

 

 

 

 


Т‡ЙІН

Исмагулова Ж±лдыз Сєуелханќызы

 

Аныќталмаѓандыќ жаѓдайында желілік моделде ресурстарды ‰лестіру єдістерін жасау жєне зерттеу

 

05.13.01 – «Ж‰йелік талдау, басќару жєне аќпаратты µњдеу» мамандыѓы бойынша техника ѓылымдарыныњ кандидаты алу ‰шін дайындалѓан диссертация

 

Аныќталмаѓандыќ жаѓдайында желілік модельде ресурстарды ‰лестіру есебініњ ќиындыѓы, оларды белгілі аналитикалыќ єдістермен шешу кезінде тиімді шешім алу м‰мкіндігініњ жоќтыѓымен байланысты. Сондыќтан да шешім ќабылдаушыныњ тєжірибесіне жєне математикалыќ программалау єдістеріне негізделген тиімді єдістер мен алгоритмдерді жасау ќажетттігі туындайды.

Ќарастырылып отырган аныќталмаѓандыќ жаѓдайында желілік модельде ресурстарды ‰лестіру ж±мысы µлшеміне (пайдаланатын ресурстар мен ж±мыстын санына), ж±мыстар арасындагы µзара байланыстыњ к‰рделілігіне, сол сияќты ж±мыстын орындалу ±заќтыѓыныњ туындайтын єсеріне карай к‰рделі болып табылады.М±нда ж±мыстын орындалу ±заќтыѓы єр т‰рлі таралу зањдарына баѓынуы м‰мкін.

Ж±мыстыњ маќсаты аныќталмаѓандыќ жаѓдайында желілік модельде ресурстарды ‰лестірудіњ єдістері мен алгоритмдерін жасауды наќты есептерді шешуде теориялыќ жєне практика ж‰зінде зерттеу.

Зерттеу єдістері. Ќойылѓан есепті шешу барысында тиімділік єдістері, динамикалыќ программалау, ыќтималдыќтар теориясы мен математикалыќ статистика ресурстарды бµлу жєне иммитациялыќ моделдеу  єдістері ќолданылѓан.

Зерттеу нєтижесініњ ѓылыми жаналыќтары мынада:

1. Аныќталмаѓандыќ жаѓдайында ресурстарды ‰лестірудіњ ќолданыста бар єдістері талданѓан.

2. Аныќталмаѓандыќ жєне детерминделген жаѓдайында ресурстарды ‰лестіру есебініњ єдістері мен алгоритмдері талданѓан. Б±л жерде ‰зіліссіз жєне дискретті ‰дерістерде, априорлы аныќталмаѓандыќпен сипатталѓан аныќталмаѓандыќ жаѓдайында ресурстарды бµлу есебі ‰шін казіргі кезде жаксы жасалѓан математикалыќ єдістер жетіспейтіндігі кµрсетілген. М±нда кµп жаѓдайда адамнын тєжірибесіне жєне ішкі сеніміне негізделген эвристикалыќ тєсілдер ќолданылады.

3. Ресурстарды ‰лестіру ‰дерісіне єсер ететін аныќталмаѓандыќ талданып, оларды жіктеу мен ж‰йелеу ж‰зеге асырылѓан.

4. Ж±мыс ±заќтыѓы тіркелген жєне бµлінген ресурстардан тєуелді болѓанда детерминделген, аныќталмаѓандыќ жаѓдайлар ‰шін ресурстарды ‰лестіру есебі т±жырымдалѓан.


5. Ж±мыс ±заќтыѓы тіркелген жєне бµлінген ресурстардан тєуелді болѓанда детерминделген жаѓдай ‰шін желілік модельде ресурстарды ‰лестіру есебініњ єдістері мен алгоритмдері жасалѓан.

6. Ж±мыс ±заќтыѓы тіркелген жєне бµлінген ресурстардан тєуелді болѓанда аныќталмаѓандыќ жаѓдай ‰шін желілік модельде ресурстарды ‰лестіру есебініњ єдістері мен алгоритмдері жасалѓан.

7. Ресурстарды ‰лестіру есебініњ єдістері теория ж‰зінде зерттелген.

8. Аныќталмаѓандыќ жаѓдайында желілік модельде ресурстарды ‰лестіру есебініњ жасалѓан алгоритмдерін ж‰зеге асыру ‰шін баѓдарламалар жасалѓан.

9 Жасалѓан єдістер мен алгоритмдерді наќты есепті шешуге ќолдану ж‰зеге асырылѓан.

Тєжірибелік мањызы. Ресурстарды ‰лестіру есебініњ єдістері мен алгоритмдері халыќ шаруашылыѓыныњ єр т‰рлі салаларында ќолданбалы есептерді шешуде пайдаланылуы м‰мкін: темір жол ќ‰рылысын жобалауда жєне салуда шыѓынды минимумдау ‰шін, тиімді кесте ќ±ру ‰шін, ж±мыс кешенін орындау мерзімін минимумдау ‰шін, т±тынушыларѓа газды тиімді тарату маќсатында.

Аныќталмаѓандыќ жаѓдайында ресурстарды бµлудін єдістері наќты есептерге ќолданылѓан.

Ќ±рылѓан єдістер мен алгоритмдердіњ практикалыќ ж‰зеге асуы наќты есептерді шешуде ќолданылѓан жєне Delphi программалау ортасында баѓдарламалыќ  кешен жасалынѓан.

Ж±мыс нєтижелері «КазТрансГаз Аймаќ» АЌ ‰шін ќолданылды жєне «М.Тынышпаев атындаѓы Ќазаќ кµлік жєне коммуникациялар академиясындаѓы» «Есептеу техникасы жєне баѓдарламалыќ ќамтамасыз ету», кафедрасыныњ «050704 – Есептеу техникасы жєне баѓдарламалыќ ќамтамасыз ету», «050703 –Аќпараттыќ ж‰йелер» мамандыќтарыныњ студенттері ‰шін «Имитациялыќ модельдеу», «Кµліктегі математикалыќ модельдеу» пєндері бойынша зертханалыќ ж±мыстарды дайындауда ќолданылды.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 


 

SUMMARY

 

Ismagulova Zhuldyz Sauelhanovna

 

Working out and research of methods of distribution of resources on network models in the conditions of uncertainty

 

05.13.01 – Systematic analysis, management and processing if informations

Dissertation is presented for the scientific degree of candidate of technical sciences

 

 

The Difficulties of the decision of problems distributions of resources on network models in the conditions of vague at the big dimensions are connected with impossibility of reception of the optimum decisions known analytical methods. Therefore there is a necessity of working out of effective methods and the algorithms based on mathematical programming and on intuition and experience of the person makinga decision.

Considered work distributions of resources on network models in the conditions of vague is difficult because of dimension (a considerable quantity of works and used resources), difficultis of interrelation between works, and also presence of revolting influences on duration of performance of works. Here duration of performance of works can submit to various laws of distribution.

The purpose of dissertational work is working out of methods and algorithms distributions of resources in the conditions of vague on network models and in theoretical and their practical research at the decision of specific problems.

The methods of the research. During the decision of tasks in a view methods of optimisation, dynamic programming, probability theory and the mathematical statistics, distribution of resources and methods of imitating modelling were used.

Scientific novelty of results of research consists in the following:

1. Existing works on distributions of resources both in the determined case, and in the conditions of vague are analysed.

2. Methods and algorithms of the decision of the problems distributions of resources for the determined case and in the conditions of vague are analysed. It is thus established that for problems of distribution of resources in the conditions of vague at the continuous and discrete processes characterised by aprioristic uncertainty, now is absent well developed mathematical methods. Here the most approaches based on experience and intuition of the person are used in most cases.

3. Analysed the uncertainty, influencing process distributions of resources, and their ordering and classifications are carried out.

4. The problem of distribution of resources for the determined case and in the conditions of uncertainty when duration of works is fixed are formulated and depends on the allocated resources. The urgency of the considered problem is shown.


5. The Methods and the algorithms of the decision of problem distributions of resources on network models in the determined case when duration of works is fixed are developed and depends on the allocated resources.

6. Methods and algorithms of the decision of problem distributions of resources on network models in the conditions of uncertainty when duration of works is fixed are developed and depends on the allocated resources.

7. Methods of distribution of resources are theoretically investigated

8. Programs for realisations of the developed algorithms of the decision of problems distributions of resources on network models in the conditions of uncertainty are developed;

9. Practical realisation of the developed methods and algorithms is carried out at the decision of specific targets.

Practical value. The developed methods and algorithms distributions of resources can be used at the decision of applied problems in various branches of a national economy: for minimisation of expenses for designing and building of railways, for drawing up of the optimum schedule, for minimisation of term of performance of a complex of works, for optimum distribution of gas on consumers and etc.

 The Results of work are introduced in structural divisions of joint-stock company «KazTransGaz», and also used by working out of laboratory works on disciplines: «Imitating modelling», «the Theory of systems and the system of analysis», «the Analysis and modelling of information systems» of the chair «Computer facilities and information systems» for students of specialities: 050704 – Computer facilities and the software, 050703 – Information systems of Kazakh academy of transport and communications named after M.Tynyshpaev.

The offered methods and algorithms can find the wide application at the decision of problems distributions of resources on network models in the conditions of vague of various branches of a national economy.

 

 

 

 

 

 

 

 

 

 

 

Вы 7248-й посетитель.
Powered by Drupal
Copyright © KazNRTU, 2007-2016