Содержание к диссертации
Введение
Глава I. Задачи распределения ресурсов в управлении проектами 24
1.1. Основные понятия и определения 24
1.2. Задачи календарного планирования 28
1.3. Механизмы распределения ресурсов 44
1.4. Методы решения оптимизационных задач 55
1.5. Выводы и постановка задач исследования 63
Глава II. Оптимизационные модели управления проектами при рекомендательных зависимостях между работами 67
2.1. Задачи управления проектами при зависимостях рекомендательного типа 67
2.2. Алгоритм решения задачи построения календарного плана с минимальной продолжительностью проекта 69
2.3. Определение очередности выполнения работ 81
2.4. Метод решения задачи определения календарного плана с минимальными дополнительными затратами для последовательного выполнения работ 88
2.5. Метод дихотомического программирования 92
2.6. Построение календарного плана заданной продолжительности при минимальном увеличение затрат 101
2.7. Оптимизация календарного плана при ограниченных ресурсах 103
Глава III. Оптимизационные модели управления проектами с учетом транспортных схем 117
3.1. Постановка задачи 117
3.2. Симметричная транспортная схема.., 118
3.3. Несимметричная транспортная схема 128
3.4. Линейная транспортная схема 130
3.5. Оптимизация календарного графика для радиальной транспортной схемы 136
3.6. Определение оптимальной очередности выполнения работ для
произвольного сетевого графика 138
Глава IV. Оптимизационные модели при управле нии мультипроектами 142
4.1 Диверсификация как средство развития предприятия 142
4.2 Применимость задач распределения ресурсов при формировании модели диверсификации 144
4.3. Моделирование неопределенности и риска при формировании инвестиционной стратегии 152
4.4. Формирование прогнозного финансового плана диверсифици рованной компании 167
4.5 Выбор критериев эффективности многокритериальной задачи распределения 172
4.6, Решение векторной задачи оптимизации методом последова тельных уступок 180
4.7. Имитационное моделирование как способ решения задачи 180
4.8, Определение относительной важности критериев 183
4.9. Построение портфеля аппроксимирующего оптимальное распределение 184
Глава V. Эвристические модели распределения ресурсов при управлении проектами 190
5.1. Основные правила приоритета 190
5.2. Распределение ресурсов по степени критичности работ 193
5.3. Распределение ресурсов по минимальной продолжительности работ 204
5.4. Распределение ресурсов по минимальным поздним моментам окончания 206
5.5. Гибкие правила приоритета работ 209
5.6. Эвристические алгоритмы локальной оптимизации 212
5.7. Геометрический метод составления расписаний в управлении проектами 213
5.8. Задача совмещения работ 226
Глава VI. Имитационное моделирование процесса распределения ресурсов 244
6.1. Моделирование процесса финансирования совместного проекта 244
6.2. Моделирование процесса распределения портфеля заказов 260
6.3. Механизмы смешанного финансирования и кредитования 265
6.4. Моделирование процесса конкурсного распределения портфеля заказов 274
Глава VII. Применение оптимизационных моделей управления проектами в строительстве 284
7.1. Формирование производственной программы строительного предприятия 284
7.1.1 Производственная программа ЗАО «Воронеж: -дом» 284
7.1.2. Определение оптимальной очередности включения объектов в поток 287
7.1.3. Определение оптимальной очередности включения объектов в поток при минимальных дополнительных затратах 291
7.2 Построение графика работ с учетом времени перемещения бригад 297
7.2.1. Определение оптимальной очередности при линейном располо жении объектов строительства 297
7.2.2 Оптимизация календарного плана работы предприятия при кольгевой системе располооїсения объектов строительства 303
7.2.3 Оптимизация движения бригад при радиальном расположении объектов 311
7.3. Оптимизация программы развития Всероссийского детского центра «Орленок» 315
7.3.1 План реконструкции и развития ВДЦ «Орленок"2004-2010 гг 315
7.3.2. Распределение ресурсов при реконструкции ВДЦ «Орленок» 327
7.4. Распределение ресурсов и затрат между бизнес-единицами 331
7.4.1 Структура затрат предприятия 331
7.4.2 Структура затрат по бизнес единицам 336
7.4.3 Распределение затрат между бизнес единицами 343
Заключение 346
Литература 349
- Методы решения оптимизационных задач
- Определение очередности выполнения работ
- Линейная транспортная схема
- Моделирование неопределенности и риска при формировании инвестиционной стратегии
Введение к работе
Актуальность проблемы. Деятельность современного предприятия можно представить, как последовательность выполняемых проектов. И вполне закономерным является тот факт, что управление проектами в настоящее время все чаще и быстрее становится стандартным способом ведения бизнеса. Все большая доля работ в обычных современных компаниях выполняется как проекты. И, современные тенденции развития экономики таковы, что в ближайшем будущем ожидается увеличение важности и роли проектов в повседневной деятельности современного предприятия.
Строительство относится к той области производственной деятельности чело-
века, в которой элементы технологии управления проектами применялись уже давно,
что являлось следствием специфических особенностей этой отрасли. Реализация строительных проектов связана с отвлечением больших объемов денежных средств на достаточно значительный срок и перемещением ресурсов строительных предприятий в пространстве. В связи с этой особенностью возникает необходимость тщательного обоснования проектов, принятых к реализации, причем обоснование необходимости реализации такого проекта должно быть тесно увязано с потребностями экономической жизни соответствующего региона.
Подготовка к реализации строительного проекта сводится к трем стадиям: общей подготовке строительного производства; подготовке к строительству объекта; подготовке генподрядных строительных организаций. Общая подготовка производства включает в себя предпроектную стадию проведения работ, заключающуюся в экономическом обосновании необходимости строительства и его увязки с комплексной программой развития региона и разработке проектно-сметной документации на проектируемый объект. Таким образом, основным документом, завершающим этап подготовки строительства, является календарный план выполнения работ, предусмотренных проектом. Расписанием работ определяется очередность выполнения работ по проекту. Но, далеко не все работы по проекту имеют жесткие ограничения на технологическую последовательность выполнения. Особенно это характерно для мультипроекта, состоящего из нескольких проектов, связанных между собой только используемыми ресурсами. В этом случае многие зависимости имеют рекомендательный характер. Возникает закономерный вопрос о влиянии возможных нарушений рекомендательных зависимостей на общую продолжительность и стоимость проекта в целом.
Учитывая проектную направленность строительства, на практике очень часто встает задача распределения имеющихся ресурсов по нескольким видам деятельности. Такая задача продиктована требованиями диверсификации видов деятельности производственной структуры с целью повышения конкурентоспособности и рыночной устойчивости в условиях нестабильной социально-экономической ситуации, так как в настоящее время однопродуктовые фирмы в своем подавляющем большинстве обречены на неудачу. Вместе с тем следует отметить, что проекты, как правило, тогда считаются успешными, когда удается достигнуть поставленных целей проектов при соблюдении установленных сроков и бюджета. К наиболее часто называемым причинам неудач реализации проектов относят: недостаток ресурсов и нереальные сроки, что является следствием низкого качества планирования.
Таким образом, актуальность темы диссертационной работы определяется тем, что повседневная практика хозяйственной деятельности предприятий требует разработки эффективных моделей составления расписания работ при рекомендательных
{ С Петй
—
(мягких) зависимостях между работами проекта с учетом времени перемещения исполнителей, механизмов распределения ресурсов по различным бизнес - направлениям производственной системы, моделей определения рационального совмещения работ с целью сокращения продолжительности выполнения проекта.
Основные исследования, получившие отражение в диссертации, выполнялись по планам научно-исследовательских работ: МНТП «Архитектура и строительство» 1997-98 г.г. - №5.030.3; 1999-2001 г.г.- №5.15; федеральная комплексная программа «Исследование и разработки по приоритетным направлениям науки и техники гражданского назначения»; грант РФФИ «Гуманитарные науки» «Разработка оптимизационных моделей управления распределением инвестиций на предприятии по видам деятельности» № ГОО-3.3-306. "Разработка и исследование механизмов управления организационными системами, функционирующими в условиях неопределенности" (357-96/57 ИЛУ РАН им. В.А. Трапезникова). "Разработка и исследование механизмов управления иерархическими активными системами" (357-00/57 ИЛУ РАН им. В.А. Трапезникова).
Дель и задачи исследования. Целью диссертации является разработка оптимизационных моделей при управлении проектами.
Для достижения поставленной цели необходимо решить следующие основные задачи:
провести анализ основных моделей распределения ресурсов при управлении проектами и определить возможность их применения при формировании моделей диверсификации;
разработать алгоритм решения задачи минимизации продолжительности проекта при рекомендательных (мягких) зависимостях между работами проекта, получить критерий сходимости итерационной процедуры решения задачи минимизации продолжительности проекта и решить задачу о минимальном суммарном увеличении продолжительностей работ или удорожании проекта при нарушении рекомендательных (мягких) зависимостей между работами проекта;
найти очередность выполнения работ одной бригадой (единицей ресурсов) при учете времени перемещения бригады для случаев линейного, кругового и радиального расположения объектов; определить оптимальную очередность выполнения работ для произвольного сетевого графика;
разработать методы устранения «узких мест», возникающих в процессе распределения ресурсов и получения нижних оценок продолжительности реализации проекта;
выделить классы задач, для которых эвристические правила приоритета работ дают оптимальные решения;
разработать системы гибких правил приоритета, когда по мере реализации проекта осуществляется анализ складывающейся ситуации и в зависимости от нее применяется конкретное правило приоритета;
модифицировать критериальное множество в задаче диверсификации Марковича при помощи энтропийных характеристик рисков производственной деятельности и логистических регрессионных зависимостей между распределением инвестиций и соответствующим распределением прибыли;
рассмотреть задачу равномерного распределения ресурсов по множеству работ, для каждой из которых задан интервал (множество периодов), в котором она должна быть выполнена (предполагается, что работа может быть выполнена в течение одного периода);
рассмотреть задачу составления расписания с учетом предпочтительных очербд-ностей (зависимостей) выполнения работ типа «финиш-старт» (операция j не может начаться, пока не завершена операция і) и типа «финиш-финиш» (операция j не может закончиться раньше операции і);
рассмотреть задачу определения оптимального коэффициента совмещения работ проекта с целью сокращения продолжительности выполнения проекта;
выполнить имитационное моделирование процессов распределения при выполнении совместного проекта и определить пороговые значения функции штрафа за представление недостоверной информации, когда сознательное искажение информации становится невыгодным.
Методы исследования. В работе использованы методы теории активных систем, моделирования организационных систем управления, системного анализа, имитационного моделирования, линейного и нелинейного программирования, динамического программирования, теории игр.
Научная новизна. В диссертации получены следующие результаты, характеризующиеся научной новизной:
модель минимизации продолжительности проекта при рекомендательных (мягких) зависимостях между работами проекта, позволяющая получать оптимальную очередность выполнения работ по проекту;
теорема о минимальных сроках завершения работ, позволяющая получать критерий сходимости итерационной процедуры решения задачи минимизации продолжительности проекта;
теорема о минимальном суммарном увеличении продолжительностей работ при нарушении рекомендательных (мягких) зависимостей между работами проекта, что позволяет получать оценки увеличения продолжительностей работ при различных последовательностях выполнения работ;
модель нахождения очередности выполнения работ одной бригадой (единицей ресурсов) при учете времени перемещения бригады для случаев линейного, кругового и радиального расположения объектов и определяющая оптимальную очередность выполнения работ для произвольного сетевого графика, позволяющая сократить время выполнения работ по проекту;
метод устранения «узких мест», возникающих в процессе распределения ресурсов по проекту, основанный на решении вспомогательной задачи редактора;
система применения гибких правил приоритета, когда по мере реализации проекта осуществляется анализ складывающейся ситуации и в зависимости от нее применяется конкретное правило приоритета, что позволяет получать распределения ресурсов лучшие, чем при использовании одного правила;
энтропийные характеристики распределения инвестиций, отличающиеся учетом меры неопределенности инвестиционных решений.
геометрический метод решения задачи равномерного распределения ресурсов по множеству работ;
геометрический метод решения задачи составления расписания с учётом предпочтительных очерёдностей (зависимостей) выполнения работ типа «финиш-старт» (операция j не может начаться, пока не завершена операция і) и типа «финиш-финиш» (операция j не может закончиться раньше операции і);
модель определения оптимального коэффициента совмещения работ проекта, позволяющая определить степень совмещения работ с целью максимально возможного сокращения продолжительности выполнения проекта;
- модель распределения ресурсов при выполнении совместного проекта, отличающаяся возможностью определения равновесных стратегий участников строительства при различных R-механизмах и найдены пороговые значения функции штрафа за представление недостоверной информации, что позволяет использовать систему сильных штрафов, когда сознательное искажение информации становится невыгодным.
Достоверность научных результатов. Научные положения, теоретические выводы и практические рекомендации, включенные в диссертацию, обоснованы математическими доказательствами. Они подтверждены расчетами на ЭВМ, производственными и имитационными экспериментами; многократной их проверкой при внедрении в практику управления строительных предприятий.
Практическая значимость результатов исследований. На основании выполненных автором исследований решена крупная научная проблема разработки моделей и методов распределения ресурсов по проекту, адаптированных к текущему состоянию производства с учетом различных условий хозяйственной деятельности предприятия и возможного манипулирования имеющейся информацией.
Разработанные модели и механизмы реализованы, внедрены в работу следующих предприятий: ЗАО «Воронеж-дом», Главное управление автомобильных дорог Воронежской области, ОАО ИКГ «РОЭЛ - Консалтинг» (г. Москва), ОАО «Вороне-жагропромстрой», ОАО «Туластрой», ОАО «Воронежхолдингстрой».
Модели, методы, алгоритмы и механизмы включены в состав учебных курсов и дисциплин: «Управление проектами», «Оптимизационные задачи в экономике», «Экономике - математические методы и модели», читаемых в Воронежском государственном архитектурно-строительном университете.
На защиту выносятся:
Модель минимизации продолжительности проекта при рекомендательных (мягких) зависимостях между работами проекта.
Теорема о минимальных сроках завершения работ.
Теорема о минимальном суммарном увеличении продолжительностей работ при нарушении рекомендательных зависимостей между работами проекта.
Модель нахождения очередности выполнения работ одной бригадой при учете времени ее перемещения для случаев линейного, кругового и радиального расположения объектов.
Метод устранения «узких мест», возникающих в процессе распределения ресурсов по проекту.
Система применения гибких правил приоритета, когда по мере реализации проекта осуществляется анализ складывающейся ситуации и в зависимости от нее применяется конкретное правило приоритета.
Энтропийные характеристики распределения инвестиций, отличающиеся учетом меры неопределенности инвестиционных решений.
Геометрический метод решения задачи равномерного распределения ресурсов по множеству работ при независимых работах и с учетом предпочтительных очерёд-ностей (зависимостей) выполнения работ типа «финиш-старт» (операция j не может начаться, пока не завершена операция і) и типа «финиш-финиш» (операция j не может закончиться раньше операции і).
Модель определения оптимального коэффициента совмещения работ проекта, позволяющая определить степень совмещения работ с целью максимально возможного сокращения продолжительности выполнения проекта.
Апробации работы. Материалы диссертации, ее основные положения и результаты доложены и обсуждены на международных и республиканских конференциях, симпозиумах и научных совещаниях в 1991-20О5гг.: 47-58 Научно-технические конференции ВГАСУ (г. Воронеж-1994-2005 гг.); «Ресурсосберегающие технологии" (Белгород-1991г.); «Реконструкция Санкт-Петербург 2005» (Санкт-Петербург-1994г.); «Организация управления деятельностью строительных предприятий в условиях рыночных отношений» (Новосибирск -1997г.); «Современные сложные системы управления» (г. Липешс-2002г., г. Старый Оскол-2002 г., г. Воронеж-2003г., г. Тула-2О05г.), «Теория активных систем» (г. Москва -2003г.), «Управление сложными системами» (г. Новокузнецк-2004г.).
Публикации. По теме диссертации опубликовано 85 печатных работ. Двадцать печатных работ опубликованы в изданиях, рекомендованных ВАК РФ для докторских диссертаций.
Личный вклад автора в работы, опубликованные в соавторстве, состоит в следующем: в работах [7], [15] автором построена модель минимизации продолжительности проекта при рекомендательных (мягких) зависимостей между работами проекта; в работах [13], [19], [34] автором сформулирована теорема о минимальных сроках завершения работ; в работах [14], [20], [47] автором выполнено доказательство теоремы о минимальном суммарном увеличении продолжительностей работ при нарушении рекомендательных (мягких) зависимостей между работами проекта; в работах [4], [10] автором построена модель нахождения очередности выполнения работ одной бригадой (единицей ресурсов) при учете времени перемещения бригады для случаев линейного, кругового и радиального расположения объектов и определяющая оптимальную очередность выполнения работ для произвольного сетевого графика; в работах [8], [12], [16] автором применен метод устранения «узких мест», возникающих в процессе распределения ресурсов по проекту, основанный на решении вспомогательной задачи редактора; в работах [9], [18], [53] автором построена система применения гибких правил приоритета, когда по мере реализации проекта осуществляется анализ складывающейся ситуации и в зависимости от нее применяется конкретное правило приоритета; в работах [3], [5], [74] автором получены энтропийные характеристики распределения инвестиций; в работе [11] автором предложен геометрический метод решения задачи равномерного распределения ресурсов по множеству работ; в работах [1], [6], [81] автором применен геометрический метод решения задачи составления расписания с учётом предпочтительных очерёдностей (зависимостей) выполнения работ типа «финиш-старт» (операция j не может начаться, пока не завершена операция і) и типа «финиш-финиш» (операция j не может закончиться раньше операции і); в работе [2] автором построена модель определения оптимального коэффициента совмещения работ проекта, позволяющая определить степень совмещения работ с целью максимально возможного сокращения продолжительности выполнения проекта; в работе [17] автором осуществлено имитационное моделирование процессов распределения при выполнении совместного проекта.
Объем и структура работы. Диссертация состоит из введения, семи глав, заключения, списка литературы и приложений. Она содержит 348 страниц основного текста, 126 рисунков, 94 таблицы и приложения. Библиография включает 270 наименований.
Методы решения оптимизационных задач
Рассмотренные выше методы распределения ресурсов не учитывали тот факт, что каждый проект имеет некоторую протяженность во времени и состоит из некоторого количества работ. Естественно возникает задача распределения ресурсов по работам проекта наиболее эффективным способом. Работы в проекте могут быть связаны или независимы. Зависимость между работами (или ее отсутствие) может быть передано в виде сетевой модели. Следовательно, возникает задача распределения ресурсов на сетях.
Известно, что сетевые модели могут быть представлены в виде последовательности событий либо же последовательностью выполняемых работ. В первом случае вершины сетевой модели представляют события (начало работы, завершение работы), а дуги, представляют работы, подлежащие выполнению. Во втором случае, работы представлены вершинами, а зависимость, опреде ляющая технологическую последовательность выполнения работ - дугами. Причем, как показано в [29] оба представления эквивалентны. В качестве примера рассмотрим сети, изображенные на рис. 1.4.1 и 1.4.2. В том случае, когда для выполнения нескольких работ необходимы одни и те же ресурсы, то такие ресурсные зависимости изображаются пунктиром.
Одним из временных параметров сетевой модели является полный резерв работы (i; j), определяемый величиной Ду = tf - t - Ц,
Решение задачи оптимального распределения ресурсов на сети приводит к тому, что необходимо найти длину критического пути для каждого варианта распределения ресурсов и, затем, выбрать оптимальный. Если рассмотреть вариант сетевой модели, представленный на рис. 1.4.1, то можно установить, что существует общий для операций «0-1» и «0-2» ресурс. В этом случае существует два способа распределения этого ресурса между работами: сначала выполняется операция «0-1», затем «0-2» и наоборот. Потенциалы вершин, соответствующие различным способам использования этого ресурса, приведены на рис. 1.4.1 соответственно в квадратных скобках и без скобок.
До настоящего времени, следует отметить, что универсальных эффективных точных методов решения задач распределения ресурсов на сетях не существует. В качестве частного случая, для которого существует простой алгоритм, приведем следующий пример. Для сети, изображенной на рис. 1.4.2, для трех операций известны длины критических путей ТІ (от них через некоторую сеть до конечной вершины). Необходимо определить очередность выполнения этихтрех операций при условии, что все операции выполняются одной единицей ресурса и поэтому не могут выполняться одновременно.
Учитывая условия задачи: работы выполняются одной единицей ресурса и поэтому не могут выполняться одновременно, возникает задача наилучшего использования имеющегося в наличии ресурса. В этом случае, момент /,- окончания работы і определяется как минимальное время, удовлетворяющее уравнению:где W( - объем /-ой операции, Дуі) - скорость ее выполнения в зависимости от количества ресурса v,-; Д-) - непрерывная справа неубывающая функция, причем ДО) = 0; v,(0 - количество ресурса на z-ой операции в момент времени t
В том случае, если количество ресурса, используемое при выполнении некоторой работы, не изменяется во времени, то эта работа выполняется с постоянной интенсивностью. В этом случае продолжительность работы определяется выражением
Но, как уже говорилось, общих алгоритмов поиска распределения ограниченных ресурсов между работами, минимизирующего время завершения проекта, не существует. В связи с этим рассмотрим несколько частных случаев.
Допустим все работы независимы и выполняются ресурсом одного вида, количество которого равно R, аДуІ) - непрерывные строго монотонные вогнутые функции.
Из [29, 36] известна следующая теорема: существует оптимальное решение, в котором каждая операция выполняется с постоянной интенсивностью и все операции заканчиваются одновременно в момент времени 7 , определяемый как минимальное время, удовлетворяющее следующему неравенству:
В практике реального управления проектами, возникает необходимость таким образом распределить ограниченные ресурсы, чтобы получить максимально возможный эффект от их использования при существующих ограничениях. Рассмотрим метод «затраты-эффект» на следующем примере.Пусть определена совокупность возможных мероприятий, данные о которых приведены в табл. 1.4.1
Определение очередности выполнения работ
Переходим к исследованию задачи 2. Пусть ограничение на продолжительность проекта отсутствует. В этом случае задача заключается в определении очередности выполнения работ, при которой дополнительные затраты минимальны. Эта задача была рассмотрена в [13]. Приведем метод ее решения следуя [40].
Для этой цели рассмотрим граф из п вершин (по числу проектов в муль-типроекте). Две вершины і и j соединим дугой (i j), если проект і рекомендуется завершить раньше начала проекта]. Каждой дуге (i,j) припишем пропускную способность су, равную потерям при нарушении рекомендуемой очередности реализации проектов і и j. Заметим, что если полученный граф не имеет контуров, то всегда существует очередность реализации проектов такая, что будут выполнены все рекомендации. Это следует из того, что в графе без контуров всегда существует правильная нумерация вершин сети, то есть такая нумерация, что для любой дуги номер ее начальной вершины меньше номера конечной. Эта нумерация и определяет оптимальную очередность проектов. Если граф имеет контуры, то не существует очередности проектов, такой что все они выполняются в предпочтительном порядке. Задача заключается в удалении из графа некоторого множества V дуг, такого что полученный частичный граф не будет иметь контуров и сумма пропускных способностей удаленных дуг C(V) будет минимальной. Это соответствует минимизации потерь от нарушения предпочтительной очередности проектов. Множество V назовем разрезом графа, a C(V) - пропускной способностью разреза. Фактически речь идет об определении перестановки из п чисел, гда п - число проектов. Как известно, число таких перестановок п!.. Таким образом, задача оносится к классу задач комбинаторной оптимизации, трудности решения которых известны. Для разработки методов ее решения введем ряд определений. Пусть 71 = (і], І2, ..., in) некоторая перестановка вершин графа. Дугу (iks is) графа назовем неправильно ориентированной относительно перестановки п, если k s [42].
Определение 2.3.1. Потенциалом перестановки С(тс) называется сумма пропускных способностей дуг, неправильно ориентированных относительно этой перестановки, то есть
Рассмотрим некоторые свойства потенциала перестановки: Свойство 2.3J.то есть при транспозиции элементов перестановки потенциал изменяется на разность соответствующих элементов матрицы пропускных способностей.
Доказательство, очевидно, следует из того, что при транспозиции (то есть при перестановке двух соседних элементов) одна дуга становится неправильно ориентированной, а другая - правильно ориентирована (для упрощения выводов считаем, что граф является полным симметрическим, полагая пропускные способности отсутствующих дуг равными 0).то есть сумма потенциалов двух обратных перестановок равна постоянной величине (сумма всех пропускных способностей дуг графа). Доказательство свойства 2.3.2 столь же очевидно.
Заметим теперь, что удаление множества неправильно ориентированных дуг V исключает (разрывает) все контуры графа. И наоборот, любому множеству дуг V, разрывающему все контуры графа, соответствует перестановка (возможно несколько перестановок), потенциал которой меньше или равен пропускной способности разреза C(V).
Рассмотрим следующую задачу о минимальном потенциале: определить перестановку, имеющую минимальный потенциал. Заметим, что оптимальное решение задачи дает оценку снизу для оптимального решения задачи определения разреза с минимальной пропускной способностью. Более того, эта оценка достигается, поскольку множество неправильно ориентированных дуг являются разрезом графа. Таким образом, задача определения минимального потенциала эквивалентна задаче определения минимальной пропускной способности разреза.
Опишем алгоритм решения задачи. Без ограничения общности можно считать граф сильносвязным (в противном случае, задача решается отдельно для каждой сильно связанной компоненты графа),/ шаг. Определяем все элементарные контуры графа. Это можно делать различными способами. Опишем один из простейших. Описание проведем на примере графа, изображенного на рис. 2.3.1.
Выберем произвольную вершину, например, вершину 1. Строим прадерево с корнем в вершине 1, пути которого соответствуют элементарным путям графа. Процедура построения ясна из рис. 2.3.2 и мы не будем ее описывать.
Висячие вершины прадерева с номером 1 определяют все элементарные контуры графа, содержащие вершину I. Эти контуры:1, снова разбиваем граф на сильно связные компоненты (если он окажется не сильно связным) и повторяем описанную процедуру для каждой из сильно связных компонент. В рассматриваемом примере после удаления вершины 1 граф остается сильно связным, что легко проверяется. Поэтому выбираем следующую вершину, например, вершину 2 и снова строим прадерево с корнем в вершине 2 (рис, 2.3.3).
Его висячие вершины определяют все элементарные контуры, содержащие вершину 2. Эти контурыЦ5 = (2,3,5,4,2): ц.6 = (2,3,4,2): Ит=(2,5,4,2). Если удалить вершину 2, то получим граф без контуров. Следовательно, определены все элементарные контуры графа.II шаг. Определим двудольный граф Н(Х, Y, V), вершины которого X соответствуют дугам исходного графа G, вершина Y- элементарным контурам графа G, а дуги соединяют вершину (1, j)eX с вершиной LJ:KGY, если дуга (((, j) принадлежит контуру ц.к (рис. 2.3.4).
Линейная транспортная схема
Рассмотрим частный случай задачи, когда все пункты расположены в линию (например, вдоль железнодорожного пути или автострады) (рис. 3.4.1)где qi - время переезда бригады из начального пункта 0 в пункт j. Обозначим через ik номер пункта, работа в котором выполняется в к-ю очередь. Пусть задана последовательность тск =(ik,ik+p...)in)J(k n) из (п-к+1) пунктов. Получим оценку снизу момента окончания работы в пункте ik. Для этого обозначим через р максимальный номер пункта, не вошедшего в последовательность пк (то ecTbp ij5j = k,n). Определим длину кратчайшего пути из пункта 0 в пункт ik проходящего через все пункты за исключением пунктов последовательности %к. Эта длина равна Зная А,(тікЛк) можно получить оценку снизу момента окончания работы в пункте ik Зная (3.4.2), можно получить оценку снизу моментов завершения работ во всех пунктах последовательности 7 Отметим, что Глагольевым были предложены более простые, но менее точные оценки, чем (3.4.3) [17]. Наконец, зная оценки снизу моментов окончания работ в каждом пункте, определяем оценки снизу критерия А на подмножестве решений, в которых работы в пунктах кк выполняются в последнюю очередь (в заданной очередности) Опишем метод ветвей и границ для решения задачи на основе полученной оценки. Метод ветвей и границ / шаг. Разобьем множество всех решений на подмножества %(і) і = l,n, такие что в подмножестве %([) работа в пункте і выполняется последней. Вычисляем оценку (3.4.4) для каждого подмножества. Общий шаг. Рассматриваем все полученные подмножества (висячие вершины дерева ветвлений) и выбираем подмножество с минимальной оценкой. Пусть это подмножество определяется последовательностью 7tk = (ik,ifc+1,...,in) Разбиваем это подмножество на (к-1) подмножеств, определяемых последовательностями 7Скч(І) (ІЛЛ+Р"-Л): гдеі ір] = к,п. Для каждого подмножества вычисляем оценку снизу по формуле (3.4.4). Алгоритм заканчивается при получении подмножества (решения ) тс, = (ipi2,...,in), такого что оценки снизу всех остальных подмножеств дерева ветвлений больше или равны С(яі). Полученное решение оптимально, поскольку С(7Сі)=Ф(тС]), а оценки снизу критерия А для всех остальных подмножеств больше или равны С(тіі). 1 шаг. Вычислим оценку (3.4.4) для пяти подмножеств. Для этого по формулам (3.4.1-3.4.3) определяем оценку снизу критерия Д (при условии, что работа в пункте і выполняется последней). Заметим, что Р=5 определяемое последовательностью тс5(3), имеющее минимальную оценку. Разбиваем его на 4 подмножества 7t4(i)=(U). где 1=1,2,4,5. Имеем 3 шаг. Выбираем подмножество, определяемое последовательностью (5,3)- Разбиваем его на три подмножества тг3(і)=(і,5,3). где і=1,2,4, Вычисляем оценки 4 шаг. Выбираем подмножество тсз(4)=(4,5,3) с минимальной оценкой 0 и разбиваем его на два подмножества 712(1)=0)4,5,3), где \ \ ,2. Вычисляем оценки 5 шаг. Выбираем подмножество, определяемое последовательностью тсі=(1,2,4,5,3) с минимальной оценкой. Поскольку П] является решением, то полученное решение является оптимальным (оценки всех остальных подмножеств больше чем С (1,2,4,5,3)). Дерево ветвлений приведено на рис.3.4.2, оценки подмножеств указаны в квадратных скобках у соответствующих вершин Описанный подход можно применить к ряду других схем расположения пунктов. Пусть все пункты расположены вдоль кольцевой дороги (Рис. 3.4.3) Обозначим через Q - множество пунктов, не входящих в последовательность, 7 St - максимальный номер среди пунктов ieQ. В случае одностороннего движения оценки X(%k,ik) определяются следующим выражением (3.4.5) kA) = L + V если "Si ЧпЛ) = % если К=$\ где L - длинна кольцевой дороги. В случае двустороннего движения оценка X(nk,\k) получается более сложным образом, поскольку возможны различные варианты выполнения работ (см. рис. 3.4.3). Для их перечисления обозначим через Pt - номер первого после пункта О из всех пунктов множества Q (при движении по часовой стрелке), P2GQ
Моделирование неопределенности и риска при формировании инвестиционной стратегии
При анализе деятельности диверсифицированной компании большое внимание уделяется сопоставлению уровней рентабельности, эффективности различных видов производимой продукции. Результаты такого сравнения дают основу для принятия решений об избавлении от убыточных или низкорентабельных сфер деятельности и расширении высокодоходных направлений. Подобная реорганизация требует определения инвестиционных приоритетов, изменения структуры производственных мощностей с целью перелива ресурсов предприятия в наиболее перспективные сферы.
Принимая решение о выборе структуры распределения собственных средств предприятия и заемных инвестиционных ресурсов, руководитель должен считаться с тем, что неопределенность, всегда существующая как в характеристиках производства, так и во внешней ситуации, вносит в деятельность элемент риска.
Поэтому ниже предлагаются варианты моделей распределения средств, одни из которых учитывают фактор неопределенности, давая в качестве результата последовательность решений, соответствующих различным условиям реализации действий, а другие непосредственно включают оценку риска.
При построении моделей в условиях неполной информации будем рассматривать два основных подхода: первый - принцип наилучшего ожидаемого результата, и второй - принцип наилучшего абсолютно гарантированного результата. В первом случае предполагается задание вероятностной меры на допустимой области параметров. Во втором случае указываются лишь диапазоны, области возможного разброса параметров, характеризующих отдельные черты внешней среды предприятия или производственной сферы. Именно этот вариант постановки задачи позволяет требовать установления варианта производственной деятельности, выполнение которого абсолютно гарантировано при любых сочетаниях неопределенных параметров из возможной области, и приводит к математическим формулировкам максминного типа.
Первый подход. Производственный процесс рассматривается в общем виде, т.е. анализируется только количественная связь «вход - выход». Будем считать функцию «затраты - выпуск» случайной, поскольку зависимость между физическим объемом произведенной продукции (или ее стоимостной оценкой) и количеством использованных при этом ресурсов (объемом капитальных вложений, стоимостью основных и оборотных фондов), во-первых, подвержена воздействию случайных факторов (неопределенность в характеристиках технологического комплекса, уровнях поставок внешних ингредиентов, уровне спроса на конечную продукцию), а, во-вторых, сам процесс построения производственной функции на основе реальной статистической информации о функционировании предприятия в предыдущие периоды не является абсолютно формализованной процедурой, а в большой степени определяется возможностями, навыками и информацией, доступной исследователю.
Процесс развития каждой технологии в самом общем, приблизительном виде может быть описан логистической кривой, определяемой дифференциальным уравнениемгде y(t) - значение объема выпуска рассматриваемой сферы деятельности, t - параметр, выражающий совокупные затраты по данному направлению в стоимостной форме, а - положительная постоянная, у\ и у2 - положительные константы, ограничивающие (соответственно снизу и сверху) производственный результат функционирования данного направления. При этом у\ - это нижняя граница y(t), выражающая исходные, стартовые, предельно низкие возможности технологии, а уг - ее технологический предел, характеризующий ее предельно высокие возможности.
С увеличением затрат на функционирование рассматриваемого направления деятельности предприятия (в какой бы форме они не измерялись) его технологически значимый результат может лишь возрастать, поэтому y(t) представляет собой монотонно возрастающую функцию на всей области определения.Логистическая (S-образная) кривая (рис.4.3.1), описывающая жизненный цикл каждого отдельного направления деятельности организации (см. рис. 4.3.1), обычно рассматривается как модель динамики различных кумулятивных величин, которые способны накапливаться и в каждый момент образуют некоторый фонд, от объема которого существенно зависит скорость дальнейшего роста или убывания данных величин. В рассматриваемом случае такой величиной является размер капитала каждой сферы деятельности.
Тот факт, что, согласно уравнению (4.3.1), первая производная (скорость роста) величины у прямо пропорциональна отрыву этой величины от ее стартовых возможностей, означает, что y(t) растет тем быстрее, чем больше этот отрыв. Сдругой стороны, пропорциональность первой производной значению {у2-у) означает замедление роста величины y(t) по мере приближения ее к своему технологическому пределу.Решением уравнения (4.3.1) служит функцияпри произвольном Ь 0, где 0(t)=exp[a-(yz -y ]. После несложных преобразований функция (4.3.2) может быть приведена к виду
Предположим, что связь между стоимостью производственных фондов {х,,і = Ги} различных сфер деятельности предприятия и стоимостной оценкой произведенной продукции и оказанных услуг {у/ ,;, і = Ш] в среднем может быть представлена в виде функцииі - 1где, yi(xj) имеет вид (4.3.2), в то время как действительный выпуск (объем производства, чистая прибыль), который мы обозначим через F(xh х& ..., х№ 4), является случайной функцией затраченных ресурсов (капитальных вложений в рассматриваемый период, стоимости основных и оборотных фондов), т.е.где 4 - случайная величина, такая, что
Случайная величина характеризует возможные отклонения реального объема от его среднего значения F(x}, х2, ..., х„), т.е. , означает степень неожиданности, непредвиденности результатов при данных затратах и определяется для каждого направления деятельности следующим образом
