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

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

Докучаев Александр Владимирович

Математическое моделирование распределения ресурсов в задаче сетевого планирования средствами стохастического динамического программирования

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

1 7 НОЯ 2011

АВТОРЕФЕРАТ

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

005001145

Самара-2011

005001145

Работа выполнена на кафедре «Прикладная математика и информатика» в Федеральном государственном бюджетном образовательном учреждении высшего профессионального образования «Самарский государственный технический университет».

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

доцент Котенко Андрей Петрович

Официальные оппоненты: доктор физико-математических наук,

доцент Коваленко Алексей Гаврилович

кандидат физико-математических наук, доцент Воденин Дмитрий Ростиславович

Ведущая организация Федеральное государственное бюджетное

образовательное учреждение высшего профессионального образования «Самарский государственный аэрокосмический университет имени академика С.П. Королёва (национальный исследовательский университет)», г. Самара.

Защита состоится 14 декабря 2011 г. в 11 часов на заседании диссертационного совета Д212.278.02 при Федеральном государственном бюджетном образовательном учреждении высшего профессионального образования «Ульяновский государственный университет» по адресу: г. Ульяновск, ул. Набережная реки Свияги, 106, корпус 1, ауд. 703.

С диссертацией можно ознакомиться в научной библиотеке Ульяновского государственного университета, а с авторефератом на сайте ВУЗа www.uni.ulsu.ru и на сайте Высшей аттестационной комиссии при Министерстве образования и науки РФ http://vak.ed.gov.ru.

Отзывы и замечания по автореферату в двух экземплярах, заверенные печатью, просьба присылать адресу: 432017, г. Ульяновск, ул. Л. Толстого, д.42, Ульяновский государственный университет, Управление научных исследований.

Автореферат разослан «_&__» Юо^сУуиХ 2011 г.

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

Волков М.А.

Общая характеристика работы

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

В качестве структурных и количественных моделей сложных процессов и систем на практике часто используются сетевые модели с графическим представлением в виде ациклических орграфов «работа-дуга»1 (элементарным операциям ставятся в соответствие ребра графа).

Данные модели позволяют управлять сложными разветвленными комплексами работ с большим числом исполнителей и потреблением ограниченных ресурсов (планирование эксперимента, управление разработками2, управление проектами3'4, теория расписаний5, транспортные и логистические задачи6, оценка и разработка инвестиционных проектов и др.). Основная цель - минимизация времени выполнения проекта при заданном объёме ресурсов. Можно выделить два основных этапа решения этой задачи.

1. Построение сетевой модели «работа-дуга».

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

Во многих исследованиях задач сетевого планирования и управления1'10 упоминаются фиктивные дуги, которые добавляются интуитивно, либо процесс их добавления не уточняется1"3'5"7,9'10. Алгоритмы добавления фиктивных дуг в минимальном числе представлены недостаточно4'8,1'.

Лишние фиктивные дуги значительно (факториально) увеличивают число пол-

1 Малинина Н.Л. Противоречия в свойствах двух основных типов сетевых моделей и пути их разрешения. - Москва: Электронный журнал «Труды МАИ». - № 37. - 2010. - Элеиронный ресурс. Режим доступа:

http ://www. mal ju/science/trudy/published.php?ID=l 3440,

Голенко-Гинзбург Д.И. Стохастические сетевые модели планирования н управления разработками: Монография. -Воронеж: «Научная книга». - 2010. - 284 с.

Воропаев В.И., Гельруд Я.Д. Использование ЦАСМ при управлении проектами. / Публикации Российской Ассоциации Управления Проектами «СОВНЕТ». - 2001. - Электронный ресурс. Режим доступа: http://www.sovnet.ni/pages/casm4.rar. Горбовцов Г.Я. Управление проектом. -М.: ЕАОИ. - 2007. - 279 с.

Буторин В.К., Карпов В.В. Прикладной системный анализ: сетевой анализ и календарное планирование проектов, метод прогнозного графа. - Новокузнецк: НФИ КемГУ. - 2002. - 59 с.

6 Баркалов П.С., Буркова И.В., Глаголев A.B., Колпачев В.Н. Задачи распределения ресурсов в управлении проектами. - М.: ИПУ РАН. - 2002. - 65 с. •

Гельруд Я. Д. Оптимизация развития холдинговой структуры с использованием нечеткой логики // Управление проектами и программами. - 2007. - № 3. - С. 182-190.

Постовалова И. П. Струетурная оптимизация сложных сетевых проектов: автореф. дисс. канд <Ьиз -мат нате / Челябинск ЧелГУ. - 2005. - 22 с. ' Тынкевич М.А. Экономико-математические методы (исследование операций). - Т. 93. - Кемерово: КузГГУ. - 2000.

Эдцоус М., Стэнсфилд Р. Методы принятия решений. -М.: ЮНИТЙ. -1997. - 590 с.

Дыхнов А.Е., Постовалова И.П. Эффективный алгоритм формирования сета «дуга-работа)) // Обозрение прикладной и промышленной математики. - 2000, Т. 7, № 2. - С. 341-342.

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

2. Оптимальное распределение ограниченного ресурса в случае нелинейной и/или стохастической чувствительности времени выполнения проектных работ.

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

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

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

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

Объектом исследования являются задачи сетевого планирования и управления.

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

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

1. Разработка модели оптимального вложения ограниченного ресурса в задаче

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

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

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

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

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

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

Научная новизна диссертационной работы определяется следующими результатами:

1. Разработана новая сетевая модель «работа-дуга» со специальным свойством минимальности фиктивных дуг и предложены алгоритмы ее автоматизированного построения; в отличие от существующих, модель позволяет эффективнее решать задачу сетевого планирования в условиях нелинейной чувствительности работ проекта к привлекаемому ресурсу. Это позволило ввести новую оценку сложности сетевого проекта числом полных путей построенного орграфа проекта.

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

3. На основе предложенных моделей и алгоритмов для решения стохастических задач распределения ресурсов разработан комплекс программ для случаев большей размерности исходных данных: КМСЗРР (Комплекс для моделирования стохастических задач распределения ресурсов), позволивший исследовать зависимости моментов решения стохастической задачи распределения ресурсов от параметров задачи.

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

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

ния и оценка сложности сетевого проекта числом полных путей построенного орграфа.

2. Методика применения стохастического динамического программирования для оптимизации вложения ограниченного ресурса при неравномерном изменении разметки дуг орграфа проекта и статистического оценивания моментов решения стохастического сетевого проекта.

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

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

Теоретическая и практическая значимость исследований. Теоретическая

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

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

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

3. С помощью разработанного комплекса программ исследован ряд практических постановок задач сетевого планирования и управления.

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

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

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

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

3. Разработанный комплекс программ КМСЗРР зарегистрирован в Федеральной службе по интеллектуальной собственности, патентам и товарным знакам (Роспатент) и Объединенном фонде электронных ресурсов «Наука и образование» (ОФЕРНиО), может использоваться в практических задачах оптимизации вложения ограниченного ресурса с целью уменьшения критического времени проекта, в исследовательских целях, в образовательных учреждениях при обучении студентов, магистрантов и аспирантов дискретной математике, численным методам, комбинаторике и другим математическим дисциплинам, затрагивающим задачи переборного типа.

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

Связь диссертационной работы с планами научных исследований

Работа выполнялась в рамках плана НИР СамГТУ по теме «Разработка методов математического моделирования динамики и деградации процессов в механике сплошных сред, технических, экономических, биологических и социальных системах и методов решения неклассических краевых задач и их приложений».

Апробация работы

Результаты диссертационной работы докладывались и обсуждались на научных форумах: VIII Всероссийский симпозиум по прикладной и промышленной математике (Сочи, 2007 г.); Международная молодежная научная конференция «XXXIV Гагаринские чтения» (Москва, 2008 г.); V, VII Всероссийские научные конференции с международным участием «Математическое моделирование и краевые задачи» (Самара, 2008, 2010 г.); LUI Научная конференция МФТИ (Всероссийская молодежная научная конференция с международным участием) «Современные проблемы фундаментальных и прикладных наук» (Москва, 2010 г.); научные семинары «Механика и прикладная математика» Самарского государственного технического университета (рук. д.ф.-м.н., профессор В.П. Радченко, 2008, 2009, 2010 гг.); научный семинар кафедры «Математика и бизнес-информатика» Самарского государственного университета (рук. д.ф.-м.н., профессор Л.А. Сараев, 2010 г.); научный семинар кафедры «Прикладная математика» Самарского государственного аэрокосмического университета имени академика С.П. Королёва (национальный исследовательский университет)» (рук. д.ф.-м.н., профессор А.И. Жданов, 2011 г.), научный семинар кафедры «Математические методы и информационные технологии» Самарской академии государственного и муниципального управления (рук. д.т.н., д.э.н., профессор В.К. Семёнычев, 2011 г.).

Публикации

Основные результаты диссертационной работы опубликованы в 20 научных работах, из них 6 статей в рецензируемых журналах из перечня ВАК и одно свидетельство Роспатента о государственной регистрации программы для ЭВМ.

Личный вклад автора

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

Структура и объём диссертации

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

Содержание работы

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

Глава 1. Аналитический обзор и постановка задачи

В пункте 1.1 анализируются методы вложения ресурсов в задачах сетевого планирования и управления, представленные работами В.И. Алферова, Л.И. Авербаха,

A.B. Буркова, И.В. Бурковой, П.С. Баркалова, С.А. Баркалова, A.M. Валуева, В.И. Воропаева, Д.И. Голенко-Гинзбурга, Я.Д. Гельруда, А.Е. Дыхнова, А.Г. Коваленко,

B.C. Лубенцовой, С.А. Олейниковой, И.П. Постоваповой и др.

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

В пункте 1.2 дан обзор задач, решаемых средствами динамического программирования на основе модели распределения ресурсов. Рассматривается реализация метода динамического программирования в виде рекуррентных уравнений Беллма-на. Сделан вывод о возможности сведения задачи вложения ресурса сетевого планирования к модифицированной задаче динамического программирования.

В пункте 1.3 сформулированы основные задачи исследований данной диссертационной работы (см. рис. 1).

Глава 2. Разработка модели оптимального вложения дополнительного ресурса в задаче сетевого планирования и управления

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

В пункте 2.1 рассматривается задача сетевого планирования и управления связным проектом Р = из проектных работ a(i): if-j <=> a{i)£a(j) с предшественниками s(a(i))cP и временем выполнения t(a(i), *(0): PXU(X)-+R* при вложении

def к j

ресурсаx(i) е U(X) из разбиения ¡7(Х) = {х(г')}ы: ^ = x{i){\x(j) = 0.

Определение 2.1. Предшественниками s(a(i))czP проектных работ a(i) является собственное (возможно, пустое) подмножество работ проекта Р, требующих завер-

шения до начала выполнение работы а(г).

Задача СПУ

Построение орграфа сетевого проекта (теорема 2.7, пункт 2.2)

Переход к матрице непосредственного предшествования (теорема 2.1, пункт 2.1)

Необходимость введения фиктивных работ (теоремы 2.2 и 2.4, пункт 2.2)

Мшшмизация числа фиктивных работ (теорема 2.5, пункт 2.2.1)

Решение задачи СПУ при фиксированных значениях параметров

Вложение допол-шггельных ресурсов в нелинейном случае (пункт 2.3)

Стохастическое поведение параметров проекта (пункты 3.2,3.3,3.4)

Динамическое программирование (пункты 3.1 и 3.2)

Расчет статистических параметров: М, Д К (пункт 3.4)

Оценка сложности сетевого проекта (теоремы 2.3 и 2.6, пункт 2.2)

Комплекс программ (глава 4)

Снижение сложности задачи динамического программирования

Необходимое условие оптимальности, полученное переходом к континуальной постановке (теорема 3.1, пункт 3 5 2)

7ГГ

Метод факторизации по функциям освоения (пункт 3.5.1)

Рисунок 1. Схема моделирования в диссертации распределения ресурса в задаче сетевого планирования п управления: 1) алгоритм построения модели сетевого проекта в форме графа с минимальным числом фиктивных работ; 2) модели применения стохастического динамического программирования для нахождения оптимального вложения дополнительного ресурса в задаче сетевого планирования; 3) приближенные методы решения задачи распределения ресурсов; 4) комплекс программ для решения стохастических задач распределения ресурсов.

Ресурс X может быть вещественным числом с разбиением на неотрицательные слагаемые 0 < 5 X (энергетические затраты в химических или ядерных ре-

акциях, зарядовые затраты в ядерных реакциях, финансы и т.п.) или множители (передаточные числа в системе передач, коэффициенты усиления в каскадных системах управления, переменные процентные ставки, индексы роста и т.п.), дискретным множеством произвольных элементов X = {ус разбиением

на подмножества £/0) с 2х (признаки неколичественной природы, например, персоналии) и т.д.

Оптимизируется распределение ресурса {*(')},!,» минимизирующее суммарное время выполнения проекта Р:

2*(а(/),*(/))-»тт, (1)

где суммирование проводится по работам а(7), принадлежащим критическому пути проекта.

Отношение 5 предшествования проектных работ а^цеР описывается матрицей предшествования 5" = |у(/^: s(iJ) = х(я(ОХаОЖ выраженной характеристической функцией

Таким образом, единицы в /-ой строке матрицы Б (2) указывают на предшествование работы а(0 работам соответствующих столбцов.

Определение 2.2. Нумерацию проектных работ считаем правильной, если про-екгные работы {я(/)}*=1 упорядочены условием /'< у'=>а(у')е.$(а(/)). Такой список

предшествования назовем правильно упорядоченным.

Определение 23. Назовём работу а(г)еР непосредственным предшественником работы а{]~) е Р, если х(а(г),.у(а(/)))= 1 и нет такой работы а{Г) е Р, что

В противном случае предшествование (следование) назовём опосредованным.

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

Далее, сокращая списки предшествования до списков непосредст-

венного предшествования (а (/))}' ( и переставляя строки и столбцы матрицы предшествования Б, правильно упорядочим проектные работы.

В дальнейшем считаем нумерацию проектных работ {я(0}*=1 правильной, а списки предшественников сокращёнными. Согласно теореме 2.1 матрица

непосредственного предшествования правильно упорядоченных работ £=№*/,], ..А[1Гу]Г}), 2<г<к-\,

верхняя треугольная блочно-цепочная с нулевой главной диагональю, состоящая из нулевых элементов и непрерывной цепочки /,х/>блоков 1 <(<г, из которых

первый и последний блоки квадратные нулевые Л[г',х/1]=0, Л[/гхуг]=0, а остальные ненулевые: 2<г<г-1.

В пункте 2.2 описано построение орграфа С(У,К) сетевого проекта Р.

Теорема 2.2. Блок Л[/,х/г], 2<Кг-1 матрицы непосредственного предшествования работ (3), состоящий только из единиц, не требует добавления фиктивных работ.

Блок из теоремы 2.2 соответствует вершине проекта.

Теорема 2.3. Число вариантов прохождения полных путей проекта Р через единичный 6локА\},^Л\ (безучета предшествующих и последующих блоков) равно

Теорема 2.4. Если хотя бы один блок матрицы непосредственного предшествования работ (3) неединичный, то к проектным работам необходимо добавлять фиктивные.

Пусть неединичный блок И матрицы непосредственного предшествования работ соответствует случаю из теоремы 2.4. Добавим фиктивные работы по следующему алгоритму (а-с):

а. Выделим в блоке £> подматрицу Д<Д состоящую из трёх единичных и одного нулевого нижнего блока:

где /,, /2, /3 - единичные блоки, О - нулевой блок.

b. Для уменьшения числа добавляемых фиктивных работ необходимо так подобрать подматрицу Д<Д чтобы она не была собственной подматрицей другой аналогичной 2*2-блочной подматрицы Д<0.

c. Добавим фиктивную работу аы с условиями непосредственного предшествования а(/,)б5(а4+1) и аы е.$(аЦ)), где правильные номера ¡, непосредственно предшествующих фиктивной работе ам(Р проектных работ д(г,)еР соответствуют попавшим в блок подматрицы Д строкам, а правильные номера непосредственно последующих за фиктивной работой аы$Р проектных работ

соответствуют попавшим в блок О подматрицы Д столбцам.

Следствие 2.1. Число построенных алгоритмом (а-с) фиктивных работ минимально.

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

Теорема 2.6. (О числе полных путей). Общее число М полных путей проекта Р, проходящих через все блоки х / , имеет точную нижнюю оценку

екта включает блоки Л[г,х/,], полностью состоящие из единиц (теорема 2.1), и блоки, состоящие из нулей и единиц (теорема 2.2), то орграф проекта будет построен с помощью алгоритма (а-с).

На ОСНОВГ.НИИ теоремы 2.7 сделан вывод о том, что по крайне мере с добавлением фиктивных работ граф проекта будет построен.

В пункте 23 приводится алгоритм оптимизации вложения дополнительных ре/ ч А/Я.

сурсов. С помощью орграфа ОУД) найдём все полные пути (/,} проекта Р, соединяющие общее начало всех стартовых и общий конец всех финишных работ, и,

с учетом (1), оценим суммой времени исполнения их работ

.....

где число работ на полном пути /, равно /•(/,)> 1, / е 1, М.

Минимальное время Т* выполнения проекта Р (1) при оптимальном вложении ограниченного ресурса X составит

= А^'И'М^-П (4)

Выводы по главе 2 приводятся в пункте 2.4.

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

Сокращение времени исполнения работ а{1) при вложении ограниченного ресурса хе[0,Х], определено соответствующими неотрицательными функциями отклика /¡, как правило, нелинейными и заданными таблично. Их значения в точках дискретизации ресурса представляют абсолютное сокращение времени выполнения проектных работ после привлечения порции ресурса. Таким образом, задача (4) сводится к дискретной задаче распределения ресурсов.

Пункт 3.1 содержит общую постановку детерминированной задачи распределения ресурса

х = = (5)

по функциям освоения (откликам) х,), : 5К+ -» 9Г, с целью оптимизации суммарного эффекта

В соответствии с поставленной задачей и формулой (4), будем рассматривать задачу максимизации. Вид функций освоения задан таблицей значений Дуу) в фиксированных точках У] дискретизации ресурса X: х, Е(у1,у2,...,ук), $<у\<уг<...<ук$х, К € К. Зависимость функций освоения (откликов) / от порций у} распределяемого ресурса А'в общем случае нелинейная.

Суммарный эффект (6), а также оптимальный вектор распределения ресурсов X* = где х* - ресурс, при котором функция ) обеспечивает

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

В пункте 3.2 на основе байесовского подхода, сводящего стохастическую задачу динамического программирования к набору подзадач (каждая из которых может

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

М--

/Ы ЖХ

Р'./Ми)

(7)

В стохастической постановке критерием оптимизации служит математическое ожидание суммарного эффекта Щ2„„].

В пункте 3.3 на основе постановки модели распределения ресурсов решена стохастическая задача рапределения капиталовложений по предприятиям.

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

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

Сложность вычислений методом динамического программирования зависит от мощности пространства состояний задачи, факториально нарастающей при уменьшении шага дискретизации распределяемого ресурса, увеличении числа функций освоения и/или числа случайных параметров. Из-за «проклятия размерности» решение прикладных задач динамического программирования не всегда осуществимо даже с использованием современной вычислительной техники.

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

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

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

Теорема 3.1. (О необходимом условии оптимальности). Оптимальное решение

дискретной задачи распределения ресурса (5-6) представимо в виде

1 * * *

[х, +x2 + ... + xn = x.

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

1 <<■<«, ^<,-<^-1. (9)

В 1-ом столбце выбираем значение аргумента х], чтобы условия (8) выполнялись с точными равенствами. В этом случае получим точное решение исходной дискретной задачи динамического программирования.

Если точные равенства не получаются, подбираем набор ЛГ'= с мак-

симально точным выполнением приближенных равенств (8).

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

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

В пункте 3.6 приведены выводы по главе 3.

Глава 4. Разработка комплекса программ для оптимизации распределения ресурсов.

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

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

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

1) решение задач большей размерности;

2) применение к различным модификациям задач распределения ресурсов;

3) стохастическое варьирование параметров задачи.

12 Козинова A.T., Тарасов В.Л. Реализация метода динамического программирования для оптимального распределения ресурсов на VBA в Excel I/ Вестник Нижегородского университета им. Н.И. Лобачевского. Сер.: Экономика и финансы. - 2001. - № 1. - С. 84-90.

Кормен Т.Х., Лейзерзон Ч.И., Ривест РЛ. и др. Алгоритмы: построение и анализ: Пер. с англ. - М.: Вильяме. -2006.-1296 с.

14 Никульчев Е.В. Практикум по теории управления в среде Matlab. - M: МГАПИ. - 2002. - 88 с.

15 Охорзин В А. Прикладная математика в системе Mathcad. - СПб.: Лань. - 2008. - 352 с.

В пункте 4.2 описаны этапы разработки комплекса программ: общие требования, выбор среды программирования.

В ходе решения поставленных задач разработан комплекс программ КМСЗРР, реализующий в детерминированном случае метод динамического программирования, а в стохастическом случае - разработанные численные методы для сокращения объема вычислений. Структурная схема комплекса изображена на рис. 2.

В пункте 4.3 приведен интерфейс разработанного комплекса программ: блок ввода исходных данных задачи, блок вывода промежуточных вычислений, блок вывода результатов расчета. Комплекс программ позволяет решать задачи распределения ресурса размерностью до 11 точек дискретизации распределяемого ресурса, 12 функций освоения и 5 случайных откликов задачи, каждый из которых может включать до 10 значений. Сформулированы ограничения на начальные параметры задачи, приводится инструкция по работе.

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

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

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

В пункте 4.5 решена стохастическая задача планирования комплекса работ. Задача состоит в построении орграфа сетевого проекта с минимальным числом фиктивных дуг на основе списка технологического предшествования с целью дальнейшей оптимизации проекта. Каждой дуге проекта (кроме фиктивной) ставится в соответствие работа проекта, имеющая заданную длительность. Данные для построения орграфа сетевого проекта взяты из работы16. При этом с помощью разработанной модели удалось обнаружить лучшее решение по построению орграфа проекта, а с помощью разработанного комплекса программ решить задачу оптимизации проекта при нелинейном распределения ресурса по работам проекта и исследовать зависимость полученного решения от стохастических параметров проектных работ.

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

" Ельдештейн IO-M. Логистика. - Красноярск. - 2006. - 508 с.

Рисунок 2. Структурная схема разработанного комплекса программ

В пункте 4.7 сформулированы выводы по главе 4. Разработанный комплекс программ обладает следующими преимуществами:

1) позволяет решать стохастические задачи распределения ресурсов при большей размерности исходных данных;

2) позволяет решать задачу в различных постановках (дискретной и непрерывной, детерминированной и стохастической);

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

необходимости доработки кода программы.

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

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

2) предложен алгоритм модификации стохастического динамического программирования для моделирования оптимального вложения ресурса при неравномерном изменении разметки дуг орграфа проекта;

3) изложен универсальный метод статистического оценивания моментов оптимального решения стохастического сетевого проекта, впервые отмечено различие оценок в случае единственности и неединственности решения;

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

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

Список публикаций

В изданиях из перечня ВАК:

1. Докучаев A.B., Котенко А.П. Решение задачи календарного планирования производства в условиях стохастической неопределенности параметров // Вестник Самарского государственного технического университета. Серия Физ.-мат. науки. -2007.-№2(15).-С. 182-183.

2. Докучаев A.B., Котенко А.П. Алгоритмы решения стохастических задач динамического программирования большой размерности // Вестник Самарского государственного технического университета. Серия Физ.-мат. пауки. - 2008. - № 2(17).-С. 203-210.

3. Докучаев A.B. Алгоритмы и программное обеспечение задач календарного планирования производства в условиях неопределенности // Обозрение прикладной и промышленной математики. -2008. -Т. 15, №2-С. 288-289.

4. Докучаев A.B., Котенко А.П. Графоаналитический способ решения задачи о минимизации затрат при покупке товара у нескольких поставщиков // Вестник Самарского государственного технического университета. Серия Физ.-мат. науки. -2009. -№ 2(19). - С. 277-279.

i 7

5. Докучаев А.З., Котенко А.П. Оптимизация привлечения дополнительных ресурсов в сетевом планировании // Вестник Самарского государственного технического университета. Серия Физ.-мат. науки. -2010. -№ 1(20). - С. 234-238.

6. Докучаев A.B., Котенко АЛ. Свойства графов задач сетевого планирования и управления II Вестник Самарского государственного технического университета. Серия Физ.-мат. науки. -2010.-№5(21).-С. 204-211.

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

7. Докучаев A.B., Котенко А.П. Комплекс для моделирования стохастических задач динамического программирования. Роспатент. Свидетельство о государственной регистрации программы для ЭВМ №2011615999 от 03.08.2011.

В других изданиях:

8. Докучаев A.B. Использование дискретной модели распределения ресурсов в стохастических задачах календарного планирования // Труды III Международного форума (VIII Международной конференции) «Актуальные проблемы современной науки». - Ч. 2. - Самара: СамГТУ. - 2007. - С. 91-94.

9. Докучаев A.B. Использование байесовского подхода в стохастической постановке задачи динамического программирования для оценки влияния погрешностей исходных данных // Труды Международной молодежной научной конференции «ХХХГУГагаринские чтения». - М.: МАТИ. - 2008. - С. 54-55.

10. Докучаев A.B. Декомпозиция метода динамического программирования по функциям освоения // Труды IV Международного форума (IX Международной конференции) «Актуальные проблемы современной науки». - Ч. 2. - Самара: СамГТУ. - 2008. - С. 63-67.

11. Докучаев A.B. Адаптивный подход в одной стохастической задаче динамического программирования на основе континуальной постановки // Труды V Всероссийской научной конференции с международным участием «Математическое моделирование и краевые задачи». - Самара: СамГТУ. - 2008. - С. 25-30.

12. Докучаев A.B. Моделирование биржевой торговли динамическим программированием // Труды VII Международной конференции «Математическое моделирование физических, экономических, технических, социальных систем и процессов». - Ульяновск: УлГУ - 2009. - С. 93.

13. Докучаев A.B. Сокращение срока выполнения проекта в задаче сетевого планирования // Материалы Международной научной молодежной конференции по естественнонаучным и техническим дисциплинам «Научному прогрессу - творчество молодых». - Ч. 2 - Йошкар-Ола: МГТУ. - 2010. - С. 263-264.

14. Докучаев A.B. Оптимизация вложения дополнительных ресурсов в задачах сетевого планирования и управления // Труды V Международного форума (X Международной конференции) «Актуальные проблемы современной науки». - Ч. 2. -Самара: СамГТУ. - 2010. - С. 64-70.

15. -Докучаев A.B., Котенко A.II Построение графа задачи оптимизации сетевого планирования и управления // Материалы Международной научно-технической конференции «Информационные, измерительные и управляющие системы». - Самара: СамГТУ. - 2010. - С. 291-294.

16. Докучаев A.B., Котенко А.П. Построение графа задачи оптимизации сетевого планирования // Труды VII Всероссийской научной конференции с международным участием «Математическое моделирование и краевые задачи» -42- Самаоа-СамГТУ.-2010.-С. 86-90.

17. Докучаев A.B. Дисперсия стохастического процесса распределения ресурса // Труды Международной конференции с элементами научной школы для молодежи «Перспективные информационные технологии для авиации и космоса» - Самага-СГАУ,-2010.-С. 610-614. Р

18. Докучаев A.B. Исследование дисперсии при моделировании динамическим программированием стохастического процесса распределения ресурса // Материалы П Дальневосточной конференции студентов, аспирантов и молодых ученых «Теоретическая и прикладная математика». - Владивосток: ДВФУ. - 2010. - С 4246.

19. Докучаев АЛ Исследование стохастического процесса распределения ресурса методом динамического программирования // Труды 1ЛП Научной конференции МФТИ (Всероссийской молодежной научной конференции с международным участием) «Современные проблемы фундаментальных и прикладных наук» - Ч VII -М.: МФТИ - 2010. - Т. 1. - С. 67-68.

20. Докучаев A.B. Построение графа сетевого проекта с минимальным числом фиктивных дуг и учетом новой меры сложности // Труды XLII Всероссийской молодежной школы-конференции «Современные проблемы математики». - Екатеринбург: ИМиМ УрО РАН. - 2011. - С. 26-27.

Заказ № 1077. Тираж 100 экз.

Отпечатано на ризографе. ФГБОУ ВПО «Самарский государственный технический университет» Отдел типографии и оперативной печати 443100, г. Самара, Молодогвардейская ул., 244.

Введение.'.

Глава 1. Аналитический обзор и постановка задачи.

1.1. Методы вложения ресурсов в задачах сетевого планирования и управления.

1.1.1. Фиктивные дуги в сетевых моделях.

1.1.2. Стохастические модели вложения дискретных ресурсов в задачах сетевого планирования и управления.1.

1.1.3. Другие модели распределения ресурсов в сетевом планировании.

1.2. Метод динамического программирования.

1.2.1. Задачи переборного типа.

1.2.2. Стохастические задачи динамического программирования.

1.2.3. Детерминированный метод динамического программирования

1.3. Постановка задачи.

Глава 2. Разработка модели оптимального вложения дополнительного ресурса в задаче сетевого планирования и управления.

2.1. Задача сетевого планирования и управления.

2.1.1. Основные обозначения.

2.1.2. Правильное упорядочение работ и сокращение списков предшественников.

2.2. Построение графа проекта.

2.2.1. Алгоритм добавления фиктивных работ.

2.2.2. Завершение построения графа проекта.

2.3. Алгоритм оптимизации вложений дополнительных ресурсов.

2.4. Выводы по главе 2.

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

3.1. Общая постановка детерминированной задачи распределения ресурсов.

3.2. Стохастическая постановка задачи распределения ресурса.

3.3. Стохастическая задача распределении капиталовложений по предприятиям.

3.4. Численные исследования стохастической модели распределения ресурсов.

3.4.1. Влияние числа функций освоения и интервала распределяемой величины на математическое ожидание суммарного эффекта.

3.4.2. Влияние шага дискретизации на математическое ожидание суммарного эффекта.

3.4.3. Влияние вида распределения точек носителя.

3.4.4. Исследование дисперсии при моделировании динамическим программированием стохастической задачи распределения ресурса.

3.4.5. Исключение функций освоения, не находящихся на критическом пути.

3.5. Разработка методов сокращения объема вычислений.

3.5.1. Факторизация задачи по функциям освоения.

3.5.2. Переход от дискретной к континуальной постановке.

3.6. Выводы по главе 3.

Глава 4. Разработка комплекса программ для задач распределения ресурсов.>.

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

4.2. Алгоритмы вычисления оптимального вектора распределения ресурсов и моментов суммарного эффекта средствами динамического программирования

4.2.1. Общие требования к комплексу программ.

4.2.2. Структурная схема алгоритма для разработки комплекса программ.

4.2.3. Выбор среды программирования.

4.2.4. Алгоритм комплекса программ.

4.3. Описание интерфейса комплекса программ для решения задач высокой размерности.

4.3.1. Ввод исходных параметров задачи.

4.3.2. Блок вывода промежуточных вычислений.

4.3.3. Блок вывода результатов расчёта.

4.3.4. Сообщения об ошибках, выводимые комплексом программ.

4.4. Задача о процентных ставках.

4.5. Задача сетевого планирования комплекса работ.

4.6. Результаты математического моделирования.

4.7. Выводы по главе 4.

Актуальность работы |

В качестве структурных и количественных моделей сложных процессов и систем на практике часто используются сетевые модели с графическим I представлением в виде ациклических орграфов «работа-дуга» [90] (элементарным операциям ставятся в соответствие ребра графа). i

Данные модели позволяют управлять сложными разветвленными комплексами работ с большим числом исполнителей и потреблением ограниченных ресурсов (планирование эксперимента, управление разработками [43], i управление проектами [33, 38], теория расписаний [21], транспортные и логистические задачи [12, 76], оценка и разработка инвестиционных проектов и др.). Основная цель - минимизация времени выполнения проекта при заданном объёме ресурсов. Можно выделить два основных этапа решения этой задачи. I

1. Построение сетевой модели «работа-дуга».

Исходные данные имеют вид так называемой таблицы предшествования работ, отражающей особенности технологических связей между отдельными работами проекта. Каждой проектной работе ставится в соответствие I дуга орграфа. При этом сетевые модели типа «работа-дуга» чрезвычайно сложны и трудоёмки для построения [90], так как для обеспечения согласования расположения дуг, как правило, требуют введения фиктивных дуг с нулевым временем выполнения.

Во многих исследованиях задач сетевого планирования и управления упоминаются фиктивные дуги [12, 21, 33, 37, 38, 43, 76, 90, 99, 108, 118], которые добавляются интуитивно, либо процесс их добавления не уточняется

12, 21, 33, 37, 43, 76, 90, 108, 118]. Алгоритмы добавления фиктивных дуг в минимальном числе представлены недостаточно [38, 75, 99].

Лишние фиктивные дуги значительно (факториально) увеличивают

L I число полных путей проекта, делая практически невозможной оптимизацию распределения ресурса по работам проекта. Так проявляется необходимость автоматизированного построения сетевой модели проекта с минимально неI обходимым числом фиктивных дуг. Алгоритмическая реализация этой задачи сложна. К примеру, даже подсчёт числа полных путей проекта является трудной алгоритмической проблемой.

2. Оптимальное распределение ограниченного ресурса в случае нелинейной и/или стохастической чувствительности времени выполнения проектных работ.

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

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

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

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

Объектом исследования являются задачи сетевого планирования и управления.

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

Цели и задачи исследования.

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

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

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

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

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

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

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

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

1. Разработана новая сетевая модель «работа-дуга» со специальным свойством минимальности фиктивных дуг и предложены алгоритмы ее автоматизированного построения; в отличие от существующих, модель позволяет эффективнее решать задачу сетевого планирования в условиях нелинейной чувствительности работ проекта к привлекаемому ресурсу. Это позволило ввести новую оценку сложности сетевого проекта числом полных путей построенного орграфа проекта.

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

3. На основе предложенных моделей и алгоритмов для решения стохастических задач распределения ресурсов разработан комплекс программ для случаев большей размерности исходных данных: КМСЗРР (Комплекс для моделирования стохастических задач распределения ресурсов), позволивший исследовать зависимости моментов решения стохастической задачи распределения ресурсов от параметров задачи.

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

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

2. Методика применения стохастического динамического программирования для оптимизации вложения ограниченного ресурса при- неравномерном изменении: разметки дуг орграфа проекта и статистического оценивания моментов решения стохастического сетевого проекта.

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

4. Комплекс программ для моделирования; стохастических задач: распределения ресурсов средствами модифицированного, динамического программирования.

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

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

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

3. С помощью разработанного комплекса программ исследован ряд практических постановок задач сетевого планирования и управления;.

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

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

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

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

3. Разработанный комплекс программ КМСЗРР зарегистрирован в Федеральной службе по интеллектуальной собственности, патентам и товарным знакам (Роспатент) и Объединенном фонде электронных ресурсов «Наука и образование» (ОФЕРНиО), может использоваться в практических задачах оптимизации вложения ограниченного ресурса с целыо уменьшения критического времени проекта, в исследовательских целях, в образовательных учреждениях при обучении студентов, магистрантов и аспирантов дискретной математике, численным методам, комбинаторике и другим математическим дисциплинам, затрагивающим задачи переборного типа.

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

Связь диссертационной работы с планами научных исследований

Работа выполнялась в рамках плана НИР СамГТУ по теме «Разработка методов математического моделирования динамики и деградации процессов в механике сплошных сред, технических, экономических, биологических и социальных системах и методов решения неклассических краевых задач и их приложений».

Апробация работы

Результаты исследований по теме диссертационной работы докладывались на научных форумах:

- VIII Всероссийский симпозиум по прикладной и промышленной математике (Сочи, 2007 г.);

- III Международный форум «Актуальные проблемы современной науки» (Самара, 2007 г.);

- Международная молодёжная научная конференция «XXXIV Гагаринские чтения» (Москва, 2008 г.); ,

- IV Международный форум «Актуальные проблемы современной науки» (Самара, 2008 г.); ,

- V Всероссийская научная конференция с международным участием «Математическое моделирование и краевые задачи» (Самара, 2008 г.);

- VII Международная конференция «Математическое моделирование физических, экономических, технических, социальных систем и процессов» (УльI яновск, 2009 г.); !

- Международная молодёжная1 научная конференция «Научному прогрессу -творчество молодых» (Йошкар-Ола, 2010 г.);

- V Международный форум «Актуальные проблемы современной науки» (Самара, 2010 г.);

- Международная научно-техническая конференция «Информационные, измерительные и управляющие системы» (Самара, 2010 г.);

- VII Всероссийская научная конференция с международным участием «Математическое моделирование и краевые задачи» (Самара, 2010 г.);

- Международная конференция с элементами научной школы для молодёжи i

Перспективные информационные технологии для авиации и космоса» (Самара, 2010 г.); i 1

- II Дальневосточная конференция студентов, аспирантов и молодых учёных по теоретической и прикладной математике (Владивосток, 2010 г.);

- LUI научная конференция МФТИ (Всероссийская молодёжная научная конференция с международным участием) «Современные проблемы фундаментальных и прикладных наук» (Москва, 2010 г.);

- XLII Всероссийская молодёжная школа-конференция «Современные проблемы математики» (Екатеринбург, 2011 г.);

- научный семинар «Механика и прикладная математика» Самарского государственного технического университета (руководитель д.ф.-м.н., профессор В Л. Радченко, 2008-2010 гг.);

- научный семинар кафедры Математики и бизнес-информатики Самарского государственного университета (руководитель д.ф.-м.н., профессор JI.A. Сараев, 2010 г.);

- научный семинар кафедры «Прикладная математика» Самарского государственного аэрокосмического университета имени академика С.П. Королёва (национальный исследовательский университет)» (рук. д.ф.-м.н., профессор А.И.Жданов, 2011 г.);

- научный семинар кафедры Математических методов и информационных технологий Самарской академии государственного и муниципального управления (руководитель д.т.н., д.э.н., профессор В.К. Семёнычев, 2011 г.).

Публикации

Основные результаты диссертационной работы опубликованы в 20 научных работах, из них 6 статей в рецензируемых журналах из перечня ВАК и одно свидетельство Роспатента о государственной регистрации программы для ЭВМ.

Личный вклад автора

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

Структура и объём диссертации

Диссертация состоит из введения, четырёх глав, общих выводов, списка литературы и приложений, в которых приведена блок-схема разработанного комплекса программ и свидетельства о регистрации комплекса программ в Роспатенте и в ОФЕРНиО. Общий объём диссертации составляет 158 страниц, включая 26 рисунков и 31 таблицу. Библиографический список включает 136 наименований.

4.7. Выводы по главе 4

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

1) позволяет решать стохастические задачи распределения ресурсов при большей размерности исходных данных;

2) позволяет решать задачу в различных постановках: в дискретной и непре рывной, в детерминированной и стохастической;

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

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

Заключение

В ходе выполнения диссертационной работы были получены следующие основные результаты:

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

I \ зависимости времени выполнения работ проекта от вкладываемого дополнительного ограниченного ресурса) и введена оценка сложности сетевого проекта на основе числа полных путей построенного орграфа;

2) предложен алгоритм модификации стохастического динамического программирования для моделирования оптимального вложения ресурса при 1 неравномерном изменении разметки дуг орграфа проекта;

3) изложен универсальный метод статистического оценивания моментов оптимального решения стохастического сетевого проекта, впервые отмечено различие оценок в случае единственности и неединственности решения; I

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

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

1. Акуленко Л.Д. Асимптотические методы оптимального управления. — М.: Наука.- 1987.-368 с. '

2. Алферов В.И., Баркалов С.А., Набиуллин И.Ф., Черенков Ю.А. Задача поиска оптимальной иерархии в зависимости от функции затрат // Вестник Воронежского государственного технического университета.-2009.-Т. 5. № 11. — С. 237-239.

3. Алферов В.И., Бурков В.Н., Кравцов А.Е., Карпов Ю.А. Эвристические алгоритмы распределения ресурсов // Вестник Воронежского государственного технического университета. — 2009. — Т. 5. — № 12. — С. 176179.

4. Апатцев В.И., Бухало Г.И. Основы логистики. — М.: РГОТУПС. 2005. - 207 с.

5. Афанасьев М.Ю., Багриновский К.А., Матюшок В.М. Прикладные задачи исследования операций. М.: ИНФРА-М. — 2006. - 352 с.

6. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М.: Мир. - 1979. - 536 с. ,

7. Бабурин Д.Е. Иерархический подход для автоматического размещения ациклических графов // Современные проблемы конструирования программ. Новосибирск: ИСИ им. А.П. Ершова СО РАН. - 2002. - 256 с.

8. Баркалов П.С., Буркова И.В., Глаголев A.B., Колпачев В.Н. Задачи распределения ресурсов в управлении проектами. — М.: ИПУ РАН. 2002. -65 с.

9. Баркалов С.А., Буркова И.В., Колпачев В.Н., Потапенко А.М. Модели и методы распределения ресурсов в управлении проектами // М.: ИПУ РАН. 2004. - 85 с.

10. Берж К. Теория графов и ее применения. М.: Иностранной литературы. - 1962. - 320 с.

11. Беллман Р., Дрейфус С. Прикладные задачи динамического программирования М.: Наука. — >1965. — 460 с.

12. Беллман Р., Энджел Э. Динамическое программирование и уравнения в частных производных. М.: Мир. - 1974. - 204 с.

13. Беллман Р. Введение в теорию матриц. М: Наука. - 1969. - 375 с.

14. Беллман Р. Динамическое программирование. М.: Иностранной ли1.I ,тературы. 1960. — 400 с.

15. Беллман P., Заде Л. Принятие решений в расплывчатых условиях // Сб. переводов: Вопросы анализа и принятия решений. / Под редакцией Шахнова И. Ф. М.: Мир. - 1976. - С.173-215.

16. Бурков В.Н., Буркова И.В. Задачи дихотомической оптимизации. М.: Радио и связь. -2003.-156 с.

17. Бурков В.Н., Горгидзе И.А., Ловецкий С.Е. Прикладные задачи теории графов. Тбилиси: Мецниереба. - 1974. - 234 с.

18. Бурков В.Н., Ловецкий С.Е. Эвристический подход к решению динамических задач распределения ресурсов // Автоматика и телемеханика. — 1966. Т. XXVII. - № 5. - С. 82-90.

19. Буркова И.В., Толстых A.B., Семенов П.И. Метод дихотомического программирования в задаче оптимизации программ по стоимости // Системы управления и информационные технологии. — 2004. — № 3 (15).-С. 47-50.

20. Вагнер Г. Основы исследования операций. М.: Мир. - 1973. - Т.З. -504 с. 1

21. Валуев A.M. Методы распределения ресурсов в сетевом планировании И Труды XLIX научной конференции МФТИ. — Ч. III: Аэрофизика и космические исследования. Москва - Долгопрудный. - 2006. - С. 7778.

22. Валуев A.M. Планирование и управление динамическим распределением ресурсов при выполнении комплекса работ // Горный информационно-аналитический бюллетень (научно-технический журнал) . — 2008. — №8.-С. 307-311.

23. Вентцель Е.С. Элементы динамического программирования. — М.: Наука. 1964.-176 с.

24. Вентцель Е.С. Исследование операций: задачи, принципы, методология. М.: Наука. - 1988. - 208 с.

25. Визгунов Н.П. Динамическое программирование в экономических задачах с применением системы MATLAB. — Н.Новгород: ННГУ. — 2006. -50 с.

26. Вороновский Г.К., Махотило КВ., Петрашев С.Н., Сергеев С.А. Генетические алгоритмы, искусственные нейронные сети и проблемы виртуальной реальности. — Харьков: Основа. — 1997. — 112 с.

27. Воропаев В.И., Гельруд ЯД. Использование ЦАСМ при управлении, проектами. Электронный ресурс. / Публикации Российской АссоциаI

28. Гамбаров Г.М. и др. Статистическое моделирование и прогнозирование. / Под редакцией Гранберга А.Г. — М.: Финансы и статистика. — 1990.-382 с.I

29. Гатауллин Т.М., Карандаев И. С., Статкус A.B. Целочисленное программирование в управлении производством / Т.М. Гатауллин, И.С. Карандаев, A.B. Статкус. -М.: МИУ. 1987.

30. Гасфилд Д. Строки, деревья и последовательности в алгоритмах. Информатика и вычислительная биология. С.-П.: Невский Диалект БВХ-Петербург. - 2003. - 654 с.

31. Гельруд ЯД. Оптимизация развития холдинговой структуры с использованием нечеткой логики // Управление проектами и программами. — 2007.-№3.-С. 182-190.

32. Горбовцов Г.Я. Управление проектом. -М.: ЕАОИ. 2007. - 279 с.

33. Голенко Д.И. Статистические методы сетевого планирования и управления. М.: Наука. - 1968. - 400 с. ,

34. Голенко Д.И., Тарнополъский Ю.Я. Оптимизация календарных планов методами направленного поиска // Кибернетика. — 1970. — № 6. — С. 138-144.

35. Голенко-Гинзбург Д.И., Сидоренко Е.А., Хицков Д.Э. Задача оптимального распределения затрат между проектами, представленными сетевыми графиками // Вестник Воронежского государственного технического университета. — 2010. — Т. 6. — № 4. — С. 169-171.

36. Голенко-Гинзбург Д.И., Павлов П.В., Сенюшкин A.B. Построение опти- , мального календарного плана выполнения всех работ проекта // Вестник Воронежского государственного технического университета. — 2010.-Т. 6.-№4.-С. 183-185.

37. Голенко-Гинзбург Д.И. Стохастические сетевые модели планирования и управления разработками: Монография. — Воронеж: «Научная книга». 2010. - 284 с.

38. Головицына М.В. Автоматизация конструкторского и технологического проектирования РЭС с применением САПР. Основные компоненты САПР и средства их реализации. М.: МГОУ. - 2001. - 118 с.

39. Греишлов A.A. Прикладные задачи математического программирова- • ния.-М.: Логос.-2006.-288 с. 1

40. Докучаев A.B. Алгоритмы и программное обеспечение задач календарного планирования производства в условиях неопределенности // Обозрение прикладной и промышленной математики. — 2008. — Т. 15, вып. 2.-С. 288-289.

41. Докучаев A.B. Декомпозиция метода динамического программирования по функциям освоения // Труды IV Международного, форума (IX Международной конференции) «Актуальные проблемы современной науки». Ч. 2. - Самара: СамГТУ. - 2008. - С. 63-67.

42. Докучаев A.B. Моделирование биржевой торговли динамическим программированием // Труды Vil Международной конференции «Математическое моделирование физических, экономических, технических, социальных систем1 и процессов». Ульяновск: УлГУ - 2009. - С. 93.

43. Докучаев A.B., Котенко А.П. Оптимизация привлечения дополнительных ресурсов в сетевом планировании // Вестник Самарского государственного технического университета. Серия физ.-мат. науки. — 2010. № 1(20). - С. 234-238.

44. Докучаев A.B. Оптимизация вложения дополнительных ресурсов в задачах сетевого планирования и управления // Труды V Международного форума (X Международной конференции) «Актуальные проблемы современной науки». Ч, 2. - Самара: СамГТУ. - 2010. — С. 64-70.

45. Докучаев A.B., Котенко А.П. Построение графа задачи оптимизации сетевого планирования и управления // Материалы Международной научно-технической конференции «Информационные, измерительные и управляющие системы». Самара: СамГТУ. — 2010. — С. 291-294.

46. Докучаев A.B., Котенко А.П. Построение графа задачи оптимизации сетевого планирования // Труды VII Всероссийской научной конференции с международным участием «Математическое моделирование и краевые задачи». 4.2. - Самара: СамГТУ. - 2010. — С. 86-90.

47. Докучаев A.B. Дисперсия стохастического процесса распределения ресурса // Труды Международной конференции с элементами научной школы для молодежи «Перспективные информационные технологии для авиации и космоса». Самара: СГАУ. — 2010. - С. 610-614.

48. Докучаев A.B. Котенко А.П. Комплекс для моделирования стохастических задач динамического программирования. Роспатент. Свидетельство о государственной регистрации программы для ЭВМ №2011615999 от 03.08.2011.

49. Докучаев A.B., Котенко А.П. Свойства графов задач сетевого планирования и управления // Вестник Самарского государственного технического университета. Серия физ.-мат. науки. — 2010. — № 2(21). — С. 204-211.

50. Докучаев A.B. Построение графа сетевого проекта с минимальным числом фиктивных дуг и учетом новой меры сложности // Труды XLII Всероссийской молодежной школы-конференции «Современные проблемы математики». Екатеринбург: ИМиМ УрО РАН. - 2011. - С. 2627.

51. Дрозденко К.А. Динамическое программирование в стохастических задачах распределения ресурсов // Обозрение прикладной и промышленной математики. —2008. — Т. 15, № 1. —С. 88.

52. Дрозденко К.А., Котенко А.П. Применение метода динамического программирования в стохастических задачах распределения ресурсов // Вестник Самарского государственного технического университета. Серия физ.-мат. науки. 2007. - № 1(15). - С. 184-186.

53. Дрозденко К.А. Адаптивный подход к управлению ресурсами в стохастических задачах на основе динамического программирования // Труды Международной молодежной научной конференции «XXXIV Гагарин-ские чтения». 2008. - С. 58-59.

54. Дроздов Н.Д. Алгоритмы дискретного программирования. Тверь: ТГУ. - 2000. - 82 с.

55. Дудченко A.A. Оптимальное проектирование элементов авиационных конструкций из композиционных материалов. — М.: МАИ. — 2002. — 84 с.

56. Дыхнов А.Е., Постовалова И.П. Эффективный алгоритм формирования сети «дуга-работа» // Обозрение прикладной и промышленной математики. 2000, Т. 7, № 2. - С. 341-342.

57. Елъдештейн Ю.М. Логистика. — Красноярск. — 2006. — 508 с.

58. Зайченко Ю.П. Исследование операций. — К.: Высшая школа. — 1988. — 552 с. '

59. Зимин И.Н. Алгоритм расчета сетей при переменных интенсивностях выполнения операций // известия АН СССР: Техническая кибернетика. 1973.-№6.-С. 17-23.

60. Кнут ДЕ. Искусство программирования на ЭВМ. — М.: Мир. 1977. -Т. 2. - 724 с.

61. Коваленко А.Г. Развитие математических моделей и методов теории1 iгидравлических сетей и их применение для моделирования рассредоточенного рынка: автореф. дисс. докт. физ.-мат. наук / Москва: ЧелГУ. -2006. 40 с.

62. Колмогоров А.Н. Теория информации и теория алгоритмов. — М.: Наука. 1987. - 303 с.

63. Кормен Т.Х. и др. Алгоритмы: построение и анализ / Томас X. Кормен.- М.: Вильяме. 2006. - с. 1296.

64. Крамере Х.Н. Химические реакторы: расчет и управление ими. — М: Химия. 1967.-264 с.

65. Левитин А.В. Алгоритмы: введение в разработку и анализ. М.: Вильяме, 2006.-С. 349-353.

66. Лубенцова B.C., Манякова Е.П. Методика исследования и оптимизации задачи сетевого планирования в условия неопределенности имитационным методом // Математическое, моделирование и краевые задачи. — Самара: СамГТУ. 2008. - 4.2. - С. 69-75.

67. Майника Э. Алгоритмы оптимизации на сетях и графах. — М.: Мир. — 1981.-323 с.

68. Малинина Н.Л. Противоречия в свойствах двух основных типов сетевых моделей и пути их разрешения. — Москва: Труды МАИ. — № 37. -2010.

69. Малыхин В.К, Прохоров Ю.Г. и др. Модели управления запасами. — М.: МИУ. 1987. - 52 с.I

70. Моррис У. Наука об управлении. Байесовский подход. М.: Мир. -1971.-304 с.

71. Мину М. Математическое программирование. Теория и алгоритмы. — М.: Наука.-1990.-488 с.

72. Михалевич B.C., Кукса А.И. Методы последовательной оптимизации в дискретных сетевых задачах распределения ресурсов. — М.: Наука. -1983.-208 с.

73. Никулъчев Е.В. Практикум по теории управления в среде Matlab. М.: МГАПИ. - 2002. - 88 с.

74. Охорзин В.А. Прикладная математика в системе Mathcad. — СПб.: Лань. -2008.-352 с.

75. Охорзин В.А. Оптимизация экономических систем. Примеры и алгоритмы в среде Mathcad. M.: Финансы и статистика. — 2005. - 144 с.9%.Полетаев В.А. Компьютерно-интегрированные производственные сис- 1 темы. Кемерово: КузГТУ. - 2006. - 199 с.

76. Постовалова И.П. Структурная оптимизация сложных сетевых проектов: автореф. дисс. канд. физ.-мат. наук / Челябинск: ЧелГУ. 2005. — 22 с.

77. Рыжиков Ю.И. Управление запасами. М.: Наука. — 1969. - 344 с.i

78. Саати Т. Целочисленные методы оптимизации и связанные с ними экстремальные проблемы. — М.: Мир. — 1973. — 304 с.

79. Светлов Н.М. Принцип полного использования информации в приложении к стохастическим двухэтапным моделям. — Электронный ресурс. Режим доступа: http: //svetlov.timacad.ru/ svetlovrus.html.

80. Струченков В.И. Методы оптимизации. — М.: Экзамен. — 2005. 254

81. Taxa X.А. Введение в исследование операций. Пер.с англ. М.: Вильяме. - 2005. - 912 с.

82. Терехов С.А. Адаптивные нейросетевые методы в многошаговых играх с неполной информацией // Научная сессия МИФИ-2005. VII Всероссийская научно-техническая конференция «Нейроинформатика-2005»: Лекции по нейроинформатике. М.: МИФИ. - 2005. - 214 с.

83. Терехов В.А., Тюкин И.Ю. Синтез адаптивных нейросетевых регуляторов нелинейных динамических объектов. — СПб.: С. Петербургский ун-т.-2005.-265 с.

84. Тынкевич М.А. Экономико-математические методы (исследование операций). Т. 93. - Кемерово: КузГТУ. - 2000. - 177 с.

85. Уздемир А.П. Динамические целочисленные задачи оптимизации в экономике. -М.: Физматлит. — 1995. — 288 с.

86. Хахулин Г.Ф., Красовская М.А., Булыгин B.C. Теоретические основы автоматизированного управления. — М.: МАИ. — 2005. — 396 с.

87. Хедли Дж. Нелинейное и динамическое программирование. М.: Мир. - 1967. - 533 с.

88. Черноусько Ф.Л., Меликян А. А. Игровые задачи управления и поиска. -М.: Наука.- 1978.-271 с.

89. Щербина О.А. Методологические аспекты динамического программирования // Динамические системы — 2007. — № 22. — С. 21-36.

90. Щербина Ю.В. Технические средства автоматизации и управления. — М.: МГУП. 2002. - 448 с.

91. Эддоус М., Стэнсфилд Р. Методы принятия решений. М.: ЮНИТИ. - 1997.-590 с.

92. Arman G., Davar К., Mohammad К. Development of stochastic dynamic Nash game model for reservoir operation. I. The symmetric stochastic model with perfect information // Advances in Water Resources. — 2007. — no. 30. — Pp. 528-542.

93. Belzil C. The return to schooling in structural dynamic models: a survey //

94. Kerachian R., Karamouz M. A stochastic conflict resolution model for water quality management in reservoir river systems // Advances in Water Resources. 2007. - no. 30. - Pp. 866-882. '

95. Myyra S., Pietola K., Yli-Halla M. Exploring long-term land improvements under land tenure insecurity // Agricultural Systems. 2007. - no. 92. - Pp.127.1990.63.75.

96. Sabbadin R., Spring D, Rabier C.-E. Dynamic reserve site selection under contagion risk of deforestation // Ecological modeling. 2007. - no. 201. -Pp. 75-81. I

97. Schensted C. Longest increasing and decreasing subsequences. // Canadian Journal of Mathematics. 1961. — no. 13. — Pp. 179-191.

98. Wijnen R.A. Runway Capacity Planning Supported by Dynamic Programming // Aerospace science and technology. — 2003. — no. 7.i