Содержание к диссертации
Введение
Глава 1. Аналитический обзор и постановка задачи 14
1.1. Методы вложения ресурсов в задачах сетевого планирования и управления 14
1.1.1. Фиктивные дуги в сетевых моделях 16
1.1.2. Стохастические модели вложения дискретных ресурсов в задачах сетевого планирования и управления 1 22
1.1.3. Другие модели распределения ресурсов в сетевом планировании 24
1.2. Метод динамического программирования 27
1.2.1. Задачи переборного типа 27
1.2.2. Стохастические задачи динамического программирования 28
1.2.3. Детерминированный метод динамического программирования 30
1.3. Постановка задачи 39
Глава 2. Разработка модели оптимального вложения дополнительного ресурса в задаче сетевого планирования и управления 42
2.1. Задача сетевого планирования и управления 44
2.1.1. Основные обозначения 44
2.1.2. Правильное упорядочение работ и сокращение списков предшественников 46
2.2. Построение графа проекта 50
2.2.1. Алгоритм добавления фиктивных работ 56
2.2.2. Завершение построения графа проекта 59
2.3. Алгоритм оптимизации вложений дополнительных ресурсов 60
2.4. Выводы по главе 2 61
Глава 3. Разработка и исследование численных методов для модели оптимального вложения ресурсов сетевого планирования 63
3.1. Общая постановка детерминированной задачи распределения ресурсов 64
3.2. Стохастическая постановка задачи распределения ресурса 66
3.3. Стохастическая задача распределении капиталовложений по предприятиям 68
3.4. Численные исследования стохастической модели распределения ресурсов 72
3.4.1. Влияние числа функций освоения и интервала распределяемой величины на математическое ожидание суммарного эффекта 72
3.4.2. Влияние шага дискретизации на математическое ожидание суммарного эффекта 74
3.4.3. Влияние вида распределения точек носителя 77
3.4.4. Исследование дисперсии при моделировании динамическим программированием стохастической задачи распределения ресурса 79
3.4.5. Исключение функций освоения, не находящихся на критическом пути 88
3.5. Разработка методов сокращения объема вычислений 89
3.5.1. Факторизация задачи по функциям освоения 90
3.5.2. Переход от дискретной к континуальной постановке 96
3.6. Выводы по главе 3 104
Глава 4. Разработка комплекса программ для задач распределения ресурсов 105
4.1. Обзор программных пакетов, использующих метод динамического программирования 105
4.2. Алгоритмы вычисления оптимального вектора распределения ресурсов и моментов суммарного эффекта средствами динамического программирования 109
4.2.1. Общие требования к комплексу программ 109
4.2.2. Структурная схема алгоритма для разработки комплекса программ 110
4.2.3. Выбор среды программирования 112
4.2.4. Алгоритм комплекса программ 112
4.3. Описание интерфейса комплекса программ для решения задач высокой размерности 114
4.3.1. Ввод исходных параметров задачи 115
4.3.2. Блок вывода промежуточных вычислений 119
4.3.3. Блок вывода результатов расчёта 119
4.3.4. Сообщения об ошибках, выводимые комплексом программ 120
4.4. Задача о процентных ставках 123
4.5. Задача сетевого планирования комплекса работ 131
4.6. Результаты математического моделирования 139
4.7. Выводы по главе 4 140
Заключение 141
Литература 142
- Стохастические модели вложения дискретных ресурсов в задачах сетевого планирования и управления
- Правильное упорядочение работ и сокращение списков предшественников
- Влияние числа функций освоения и интервала распределяемой величины на математическое ожидание суммарного эффекта
- Структурная схема алгоритма для разработки комплекса программ
Введение к работе
Актуальность исследования
В качестве структурных и количественных моделей сложных процессов и систем на практике часто используются сетевые модели с графическим представлением в виде ациклических орграфов «работа-дуга» (элементарным операциям ставятся в соответствие ребра графа).
Данные модели позволяют управлять сложными разветвленными комплексами работ с большим числом исполнителей и потреблением ограниченных ресурсов (планирование эксперимента, управление разработками, управление проектами,, теория расписаний, транспортные и логистические задачи, оценка и разработка инвестиционных проектов и др.). Основная цель – минимизация времени выполнения проекта при заданном объёме ресурсов. Можно выделить два основных этапа решения этой задачи.
1. Построение сетевой модели «работа-дуга».
Исходные данные имеют вид так называемой таблицы предшествования работ, отражающей особенности технологических связей между отдельными работами проекта. Каждой проектной работе ставится в соответствие дуга орграфа. При этом сетевые модели типа «работа-дуга» чрезвычайно сложны и трудоёмки для построения1, так как для обеспечения согласования расположения дуг, как правило, требуют введения фиктивных дуг с нулевым временем выполнения.
Во многих исследованиях задач сетевого планирования и управления1-10 упоминаются фиктивные дуги, которые добавляются интуитивно, либо процесс их добавления не уточняется1-3,5-7,9,10. Алгоритмы добавления фиктивных дуг в минимальном числе представлены недостаточно4,8,11.
Лишние фиктивные дуги значительно (факториально) увеличивают число полных путей проекта, делая практически невозможной оптимизацию распределения ресурса по работам проекта. Так проявляется необходимость автоматизированного построения сетевой модели проекта с минимально необходимым числом фиктивных дуг. Алгоритмическая реализация этой задачи сложна. К примеру, даже подсчёт числа полных путей проекта является трудной алгоритмической проблемой.
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 г.); LIII Научная конференция МФТИ (Всероссийская молодежная научная конференция с международным участием) «Современные проблемы фундаментальных и прикладных наук» (Москва, 2010 г.); научные семинары «Механика и прикладная математика» Самарского государственного технического университета (рук. д.ф.-м.н., профессор В.П. Радченко, 2008, 2009, 2010 гг.); научный семинар кафедры «Математика и бизнес-информатика» Самарского государственного университета (рук. д.ф.-м.н., профессор Л.А. Сараев, 2010 г.); научный семинар кафедры «Прикладная математика» Самарского государственного аэрокосмического университета имени академика С.П. Королёва (национальный исследовательский университет)» (рук. д.ф.-м.н., профессор А.И. Жданов, 2011 г.), научный семинар кафедры «Математические методы и информационные технологии» Самарской академии государственного и муниципального управления (рук. д.т.н., д.э.н., профессор В.К. Семёнычев, 2011 г.).
Публикации
Основные результаты диссертационной работы опубликованы в 20 научнох работах, из них 6 статей в рецензируемых журналах из перечня ВАК и одно свидетельство Роспатента о государственной регистрации программы для ЭВМ.
Личный вклад автора
Научному руководителю принадлежат постановки задач, а автору – математическая проработка задач, доказательство теорем, разработка алгоритмов, численных методов и их реализация в комплексе программ для решения поставленных задач.
Структура и объём диссертации
Диссертация состоит из введения, четырёх глав, общих выводов, списка литературы и приложений. Общий объём диссертации составляет 158 страниц, включая 26 рисунков и 31 таблицу. Библиографический список включает 136 наименований.
Стохастические модели вложения дискретных ресурсов в задачах сетевого планирования и управления
Появление даже одной лишней фиктивной дуги усложняет решение задачи вложения дополнительного ресурса в работы проекта, так как это ведет к увеличению числа полных путей орграфа проекта и, как следствие, к увеличению вариантов перебора полных путей при оптимизации критического пути.
В работе [90] сделан следующий вывод: «обыкновенные сетевые модели обладают сложностью (или невозможность) построения по произвольно заданной матрице бинарных соотношений». Данное утверждение связано с отсутствием методов построения графа сетевого проекта с минимальным числом фиктивных дуг. И поэтому II.Л. Малининой [90] предлагается ставить задачу синтеза сетевых моделей как задачу преобразования вершинных графов в реберные графы. Решение данной проблемы не приводится. 1
В данной диссертационной работе предлагается алгоритм построения орграфа сетевого проекта с минимальным числом фиктивных дуг. Данный , алгоритм опровергает утверждение о невозможности построения реберного орграфа сетевого проекта-по произвольно заданной матрице бинарных отношений;
В работах А. В. Буркова, И. В. Бурковой, С. А. Баркалова, П. G: Барка- лова и др. [6, 12, 13, 22, 24, 25] разрабатываются методы дихотомического программирования в сетевых задачах распределения ресурсов. Выполнение , проекта разделяется на этапы, моментами завершения работ. При: оптимальном выполнении проекта интенсивность работ в течение этапа постоянна [13]; таким образом, задача оптимального распределения ресурсов; при? выполнении проекта является задачей конечномерной оптимизации нестандартного вида. В работе G.A. Баркалова, И.В. Буркова, В.Н. Колпачева, A.M. Потапенко [13] исследуется применение для её приближенного решения эвристических методов, однако доказательства получения такими методами точного решения имеются только для комплексов работ специального вида. Также приводится сравнение с методами динамического программирования и методом ветвей и границ.
В работах И. В; Бурковой [25] и П. С. Баркалова [13] приводится определение фиктивной работы и утверждение о том, что иногда без фиктивных работ задачу решить невозможно. Далее- осуществляется переход к сетевой модели вершины-события, не требующей добавления фиктивных дуг. И разрабатывается метод дихотомического программирования, который позволяет решать частную задачу сокращения длительности-.проекта. Стохастическая постановка задачи не рассматривается.
Приводится несколько примеров решения задачи распределения ресурсов, в сетевом планировании на основе матричного подхода, позволяющего обходиться без построения орграфа проекта. В отличие от данной диссертационной работы, в работах [13, 25] отсутствует общее описание алгоритмов и методов решения задач и их математическое обоснование, предлагаемые приемы применимы в частном случае и имеют существенные ограничения. Вопросы построения графа проекта по итоговой матрице и оценки сложности проекта, а так же вариант стохастической зависимости времени выполнения работ от вкладываемого дополнительного ресурса в данных работах не рассматриваются.
В работах В.К. Буторина, В. В. Карпова [21] и М. Эддоуса, Р. Стэнс- филда [118] при построении графа сетевого проекта интуитивно добавляют I не известное заранее число фиктивных операций. После проводят процедуру сокращения по следующему правилу: «если единственной операцией, выходящей из некоторого узла, является фиктивная логическая операция, то по I всей вероятности без нее можно обойтись». Математическое обоснование и сравнение с существующими методами в работе отсутствуют. Кроме этого нет алгоритмизации предлагаемых приемов. Проблема минимальности вве I денных фиктивных работ не рассматривается.
В данной диссертационной работе, по сравнению с работами [21, 118] приводится обоснованный алгоритм изначального построения орграфа сете I вого проекта с минимальным числом фиктивных дуг.1 Число фиктивных дуг оценивается после перехода к матрице непосредственного предшествования работ проекта. 1 М.А. Тынкевичем [108] в обзоре методов решения задач сетевого планирования и управления дается определение фиктивных работ (фиктивных событий), но алгоритмы и методы их добавления не рассматриваются. В работе Д. В. Шкурко [115] рассматривается граф с уже добавленными фиктивными работами и некоторые методы удаления фиктивных дуг. Во 1 просы построения графа проекта с минимальным числом фиктивных дуг и оценка сложности проекта при построении орграфа не приводятся. В работе Д.И. Грленко-Гинзбурга [43] при описании математической модели альтернативной сети упоминаются фиктивные работы. Но алгоритмы их ввода, сокращения и удаления не рассматриваются.
В работе П.С. Баркалова, И.В. Бурковой, A.B. Глаголева, В.Н. Колпаче- ва [12] при решении произвольной транспортной схемы для решения задачи через паросочетания вводят фиктивные дуги: Методы ввода фиктивных дуг не приводятся и оценки их числа не рассматриваются.
У Г.Я. Горбовцова [38] иллюстрируется несколько приемов ввода фиктивных операций (дуг) в задаче моделирования сетевого графика. Четкого алгоритма не приводится:, вопрос об оптимальном добавлении фиктивных дуг не рассматривается. .
В работах В. И. Воропаева, Я. Д. Гельруда, JL И. Авербаха и др. [1,2, 33, 37] рассматриваются г/мкушческие альтернативные сетевые модели — ЦАСМ. Они являются синтезом? обобщенных сетевых моделей с вероятностными и стохастическими моделями,: в: значительной степени учитывающими фактор риска и неопределенности при осуществлении проекта.
Правильное упорядочение работ и сокращение списков предшественников
Определение 2.1. Предшественниками б ( я(/)) с:/5 проектных работ а(г): Щ = а(г)фа(;) является собственное (возможно, пустое) подмножество работ проекта Р, требующих завершения до начала выполнения работы а(г).
Нумерацию проектных работ считаем правильной, если проектные работы {я(0} =1 упорядочены условием / у = а(у) («(/)). Соответствующий список предшествования назовем правильно упорядоченным списком предшественников. Определение 2.3. Назовём работу а(г)еР непосредственным предше I ственником работы [69] а{]) е Р, если /(а(/)Дйг(/)))=1 и нет такой работы а(Г) е Р, что %(а(1)8(ат=хШЛаШ=1 В противном случае предшествование (следование) назовём опосредованным. s
Доказательство. Сократим списки предшественников {(«(/))} , оставив в них лишь непосредственно предшествующие работы. Проведём сокращение индукцией по возрастающим номерам правильно упорядоченных , работ. Основание индукции. Список стартовой работы а{ 1) не требует сокращения, так как пуст: я( я(1)) = 0. Предположение индукции. Пусть уже сокращены, то есть состоят лишь из непосредственно предшествующих работ, списки предшественников { ( ягС0)} _1 Работ {а(0}=1 при \ 1 к-\. , Шаг индукции. Сократим список $(а(/ +1)). Возможны два случая: а) работа а{1+1) стартовая, а значит её список предшественников пуст (5[а{1 +1)) = 0) и не требует сокращения; 1 б) список предшественников не пуст +1))Ф0) и состоит из работ а(г 1),а(/2),...,а(1т)еР, т 1, с уже сокращёнными по предположению индукции списками предшественников так как 1 1 /2 ... /ш / в силу правильной упорядоченности работ проекта Р. Оставим в списке предшественников я(а(/ + 1)) = \а{гх),я(/2 ),..., г(гот)} только непосредственно предшествующие работы, удовлетворяющие условию а(г,) 1—Тем самым будет построен сокращённый список предшественников .? (а(/ + 1)) = т, содержащий только про ектные работы д (7(), непосредственно предшествующие проектной работе а(1 +1). Шаг индукции доказан. Заключение индукции. Все списки предшественников могут быть сокращены до списков непосредственного предшествования. Теорема доказана.
С помощью списков непосредственных предшественников (теорема 2.1) ( "))}_ определим отношение б1 непосредственного предшество I вания к х-к-матрицей непосредственного предшествования 5 = I К 1.1=1 (.и) элементами с1е/ т 4 —1 а транспонированной матрицей 5 — обратное отношение непосредственного следования проектных работ. При этом отношения 5 и 51 -1 в общем случае транзитивными не являются, так как А-1 к-1 ( /=2 /=2 Правильно упорядочим проектные работы = 0) пере становкой строк и столбцов матрицы предшествования и сократим списки предшествования до списков непосредственного предшествова ния {я {а (г)) (рис. 2.1.).
Вначале найдём нулевые столбцы стартовых (не имеющих предшественников) и нулевые строки финишных (не имеющих последователей) работ. Занумеруем стартовые работы в любом порядке первыми натуральными числами 1, 2, 3, ..., а финишные работы — первыми отрицательными целыми —1, —2, -3, ... Для исключения опосредованного предшествования (следования) обнулим единицы в соответствующих стартовых строках (финишных столбцах), если в их столбце (строке) есть другие единичные элементы, расположенные в нестартовых строках (нефинишных столбцах), удалим стартовые строки (финишные столбцы) и повторим предыдущий шаг, наращивая положительные номера вновь появившихся стартовых и убавляя отрицательные номера вновь появившихся финишных работ полученной подматрицы.
Результат исключения стартовых и финишных работ в общем случае не зависит от порядка проведения этой процедуры, поскольку в силу связности проекта Р одной работе не могут соответствовать одновременно нулевые строка и столбец.
Если все проектные работы получат новый номер, то окончательно присвоим его работам с положительными номерами, а работы с отрицательными номерами занумеруем следующими натуральными числами в соответствии с убыванием модуля исходного отрицательного номера. При обычных предположениях задачи СПУ о связности и отсутствии циклического предшествования правильная перенумерация всегда завершится (см. доказательство теоремы 2.1).
Если же на одном из промежуточных шагов не окажется ни стартовых, ни финишных работ, то среди проектных работ есть циклическое предшествование. В этом случае правильно упорядочить можно только несколько первых и последних работ, в то время как расположенная на главной диагонали матрицы 5 подматрица предшествования остальных работ не будет содержать нулевых стартовых столбцов и нулевых финишных строк.
Влияние числа функций освоения и интервала распределяемой величины на математическое ожидание суммарного эффекта
Ответ: математическое ожидание прибыли составит М(2. (ХУ) = 15,64. При усреднении случайных откликов /(3) и (4) (случайные отклики заменяются их математическим ожиданием) получаем задачу с исходными данными в таблице 3.2. Ее суммарный эффект составил 2 {Х) = 14. Если , считать, что отклики (3) и (4) случайны, то решение задачи распределения ресурса является случайной величиной, при этом значению 2 (Х) = 14соответствует вероятность осуществления Р(2 сред(ХУ) = 1. Тогда м&:ред(х))=и. Усреднение случайных величин /х (3) и /2(4) ведет к потере математического ожидания суммарного эффекта: ДМ = (X)) - М{2 сред(Х)) = 15,64-14 = 1,64. Итак, усреднение случайных величин в задаче распределения ресурса может способствовать как заниженной, так и завышенной оценке математического ожидания суммарного эффекта от распределения ресурса. Поэтому необходим полный учет стохастических параметров задачи распределения ресурса.
В условиях большой размерности исходных данных (уменьшение шага дискретизации ресурса, увеличение числа функций отклика, числа случай I ных откликов и числа точек ряда распределения каждого случайного откли I ка) используются приближённые методы, приведённые в следующих пунктах данной главы, а также комплекс программ, реализующий данные методы и описанный в главе 4. 3.4. Численные исследования стохастической модели распределения ре I сурсов Численным моделированием на основе метода динамического про I граммирования была исследована стохастическая модель распределения ресурсов. Результаты можно использовать для статистического оценивания характеристик оптимизации стохастического сетевого проекта.
Исследуемые зависимости (при прочих фиксированных условиях): шаг дискретизации интервала аргумента (число точек дискретизации 1 интервала) — математическое ожидание суммарного эффекта; - интервал аргумента — математическое ожидание суммарного эффекта; число функций эффекта — математическое ожидание суммарного эффекта; число точек носителя распределения значений функций1 эффекта — I математическое ожидание суммарного эффекта; I - вид распределения значений функций эффекта —математическое ожидание суммарного эффекта; шаг дискретизации интервала аргумента, число точек носителя значений функций эффектов —» математическое ожидание суммарного эффекта. По каждому пункту было проведено не менее 10 экспериментов, опи I шем их результаты.
Рассмотрим детерминированную задачу распределения ресурсов (пример в табл. 3.3) с переменным числом линейных функций освоения. Найден суммарный эффект, который при изменении числа функций освоения оказался одинаковым.
Для стохастической задачи распределения ресурсов было найдено математическое ожидание суммарного эффекта при одинаковых размахах носи I теля дискретного распределения значений линейных функций эффектов; число точек носителя и вид распределения не изменялись.
Для проверки адекватности построенной модели было исследовано влияние интервала распределяемого ресурса на математическое ожидание суммарного эффекта для однородных линейных функций эффектов с равномерным распределением значений при возрастании шага дискретизации распределяемого ресурса.
В стохастической задаче распределения ресурсов число линейных функций освоения при одинаковых стохастических параметрах не влияет на математическое ожидание суммарного эффекта.
При увеличении распределяемой величины в 2 раза математическое ожидание суммарного максимального эффекта возрастает, ровно в 2 раза (рис. 3.1). Для нелинейных функций освоения выявлено изменение величины математического ожидания при изменении величины распределяемого ресурса и функций освоения в точках дискретизации ресурса.
Проанализируем влияние шага дискретизации распределяемого ресурса на математическое ожидание суммарного эффекта при оптимальном управлении.
Вначале рассмотрим детерминированную модель задачи в случае, когда функции эффектов заданы таблично с фиксированным шагом дискретизации (табл. 3.4). Так как была выявлена независимость суммарного эффекта от числа одинаковых линейных функций освоения, то для примера задачи с нелинейными функциями освоения достаточно взять две различные функции. Изменять шаг дискретизации путём дальнейшего увеличения числа то 74
Математическое ожидание суммарного эффекта чек дискретизации с пересчётом соответствующих откликов на одном и том же интервале изменения ресурса нет необходимости, так как суммарный эффект не будет меняться из-за неявного задания функций освоения.
Поэтому сперва рассчитывается суммарный эффект при 11 точках дискретизации (табл. 3.4), затем - при 6 точках дискретизации (при значениях аргумента 0, 2, 4, 6, 10), а также при трёх точках дискретизации (значения 0, 5, 10) и при двух (значения 0 и 10).
Результаты приведены в табл. 3.5 и на рис. 3.2. Аналогичные численные эксперименты проведены в стохастической задаче распределения ресурсов в случае равенства всех остальных параметров (число стохастических точек функций эффектов, число точек носителя дискретного распределения каждой стохастической точки, вид распределения значений случайных величин).
Структурная схема алгоритма для разработки комплекса программ
Для выбранных по необходимому условию оптимума конечных приращений составляем оптимальный вектор распределения ресурсов X и осуществляем расчёт суммарного эффекта 2тах.
Если точные равенства (3.7) не получаются, подбираем набор X - (х ,х ,...,х ) с максимально точным выполнением приближенных ра- 1 венств. Алгоритм II a. Среди рассчитанных конечных приращений (второе уравнение (3.7)) выбираем максимальное. Записываем соответствующее значение распределенного ресурса в качестве компоненты вектора распределения ресурса. b. Проверяем второе условие третье уравнение (3.7): - если равенство не соблюдается (не весь ресурс израсходован), то переходим к пункту (с) данного алгоритма; — иначе к пункту (е). c. Среди оставшихся-конечных приращений, ограниченных неизрасходованной порцией ресурса, выбираем максимальное. с1. Проверяем третье условие (3.7) с учетом выбранных приращений: — если израсходован не весь ресурс, то записываем найденную компоненту в качестве компоненты вектора распределения ресурса и переходим к пункту (с) данного алгоритма; - иначе к пункту (е). е. По составленному вектору распределения ресурсов рассчитываем суммарный эффект задачи.
Также существует возможность дальнейшего уточнения полученного решения. Для этого повторяем алгоритм (а)-(е), только в пункте (а) берем не максимальное из приращений, а меньшее его, но большее всех остальных. Если полученный суммарный эффект будет больше или равен предыдущему,
I
то алгоритм (а)-(е) снова повторяем, но в пункте (а) берем приращение, меньшее двух самых больших, но больше всех остальных. После этого снова рассчитывается суммарный эффект. Итерации продолжаются до тех пор, пока полученный суммарный эффект не окажется ниже одного из предыдущих.
Замечание. Если следующий максимум принадлежит той же функции освоения, то в рамках данного алгоритма вектор распределения ресурсов переписывается - найденная компонента заменяется другим значением.
Предложенный метод, по сравнению с динамическим программированием, использует на порядок меньшее число операций. Это позволяет моделировать распределение ресурса при большей размерности параметров ис I ходнои задачи.
Продемонстрируем работу разработанных алгоритмов на примерах. Пример 3.2. Рассмотрим детерминированную задачу динамического программирования. Необходимо распределить дискретную величину X = 7 ед. с шагом дискретизации \ кпо четырём функциям освоения, заданным
Применим методику сокращения объёма вычислений. В столбцах Ах - А4 табл. 3.16 (А, = А/Х у)) приведены конечные разности (3.6). В правой части табл. 3.16 представлены А СУ/) удовлетворяющие первому уравнению (3.7), в левой части - соответствующие им значения /( ). Жирно выделены элементы, удовлетворяющие второму уравнению (3.7).
В результате расчётов получаем: = ZIШX = 256 (ед.), где Z ax - максимальный суммарный эффект, найденный обычным методом динамического программирования, Z ax - эффект, найденный по приближённому методу.
Тогда оптимальный вектор распределения ресурсов Ха =Х ={3,1,2,1}. Пример 3.3. Рассмотрим детерминированную задачу динамического программирования о распределении дискретной величины X = 10 ед. с шагом дискретизации к = 1 по шести функциям освоения (табл. 3.17).
Алгоритм I в данной задаче не осуществим. Применение алгоритма II демонстрируют столбцы А, табл. 3.17: выделены используемые по алгоритму ! приращения. Таким образом, получаем решение. В столбцах А( табл. 3.17 выделены значения конечных разностей, выбранные по пунктам (а-с) алгоритма II. Конечные разности, выбранные при применении пунктов ( 1-е) алгоритма II отмечены в табл. 3.17 символом ( ). Вектор распределения ресурсов, соответствующий выбранным в результате применения алгоритма II (в табл. 3.17 отмечены символом ( )) конечных разностей соответствует полностью оптимальному вектору распределения ресурсов. Найдено решение полностью совпавшее с полученным динамическим программированием, но с гораздо меньшим числом операций.
Даже если вместо пунктов (ё-е) алгоритма II к значениям функций освоения, соответствующим выбранным конечным разностям, использовать обычный метод динамического программирования, то используемое число входных параметров даже для рассмотренного простейшего примера уменьшается с 66 (с учетом нулевых компонент) до 7 (именно столько откликов используется при распределении оставшегося ресурса в размере 7 единиц
