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

Размещено на http://www.allbest.ru/

МНОГОКРИТЕРИАЛЬНАЯ ПОСТАНОВКА ЗАДАЧИ ВЫБОРА ПРОЕКТОВ ЦЕЛЕВЫХ ПРОГРАММ

Кунижева Лариса Адамовна

Кочкаров Расул Ахматович

к.ф.-м.н., доцент

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

Ключевые слова: ЦЕЛЕВЫЕ ПРОГРАММЫ, ЗАТРАВКА, ФРАКТАЛЬНЫЙ И ВЗВЕШЕННЫЙ ГРАФЫ, ПАРАЛЛЕЛЬНЫЙ АЛГОРИТМ проект целевой программа математический

В настоящее время Российская Федерация входит в состав ВТО, в связи с чем, для устойчивого развития, для надежности, для стойкости [1, 2] появляется необходимость поддержания регионов страны в разных направлениях экономики (промышленность, сельское хозяйство, торговля и т.д.). Государство выделяет деньги под так называемые целевые программы [3]. Каждая государственная целевая программа содержит в своем тексте перечень целевых показателей и индикаторов. Целевые показатели и индикаторы позволяют контролировать ход реализации или текущую результативность программы на этапах, а после завершения реализации - оценивать результативность, успешность выполнения программы [4].

Набор целевых показателей и индикаторов, или по - другому, система целевых показателей и индикаторов, описывает состояние программы в ходе ее исполнения, но никак не влияет на исполнение. Чтобы влиять на исполнение целевой программы на стадии распределения и выбора проектов, необходимо построение экономико - математической модели (ЭММ). ЭММ позволяет формализовать некоторые целевые показатели, которые потом можно оптимизировать. Для построения ЭММ распределения проектов целевых программ опишем структуру распределения средств на целевые программы на примере РФ.

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

Аналогичная постановка задачи распределения средств возникает в Евросоюзе, где средства распределяются по государствам - членам Евросоюза, а далее по регионам этих государств.

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

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

Чтобы ответить на поставленный вопрос построим математическую модель распределения средств. Для построения математической модели определим инструментарий. Введем необходимые определения и понятия.

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

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

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

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

Потенциальных исполнителей освоения средств будем называть объектами (на первом этапе - это Федеральные Округа, на следующем - субъекты Округа, далее города и районы субъекта). Каждому исследуемому объекту ставим в соответствие вершину графа . Тогда на первом шаге распределения средств Федеральным Округам (или государствам Евросоюза, или научно - исследовательским институтам) поставим в соответствие вершины , . Вершины и будут соединены ребром , если между объектами, соответствующими этим вершинам могут существовать взаимоотношения (под взаимоотношениями будем понимать ситуацию, когда исследуемый объект может подключать для выполнения программы другой объект по договору). Если такое взаимоотношение существует, и если исполнитель подключает исполнителя, то будем говорить, что между и существует ресурс . Под ресурсом будем понимать скорость освоения выделенных средств, объемы предварительных договоров на поставку техники для исполнения тех или иных работ. Ребрам соответствуют ресурсы из промежутка , которые определяются из практических соображений. Вершинам графа приписываем веса (собственный ресурс исполнителя).

Таким образом, на первом шаге распределения средств получаем вершинно - реберно - взвешенный граф . На втором шаге каждый объект, в свою очередь, является распределителем средств по субъектам Федерального Округа (аналогично распределителем средств будет государство Евросоюза или научно- исследовательский институт). То есть вместо каждой вершины на последующем шаге графа будем рассматривать граф , , определенный с той лишь разницей, что ресурсы будут взяты из промежутка , а в вершины графа входят ребра предыдущего ранга. Как и на предыдущем шаге, вершине приписываем вес причем . Таким образом, получаем взвешенный граф . Инцидентность ребер первого ранга к вершинам определяется из практических соображений. На том шаге (определяем из практических соображений), проводя аналогичные рассуждения, получаем взвешенный граф , с той лишь разницей, что ребра взвешиваются из интервала , а вершинам приписываются веса , в точности также, как и на предыдущих шагах.

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

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

Где

Множество всех допустимых решений обозначим через . На множестве определим критерии :

(1)

(общее время освоения средств, выделенных на проекты);

 (2)

(объем освоенных средств), где - время освоения или исполнения объема на ребре , -время освоения объема на вершине )

(3)

(количество главных исполнителей);

(4)

(количество компонент);

(5)

(степень вершин указывает на количество соисполнителей у главного исполнителя).

(6)

(общее количество связей).

Решением задачи (1) - (6) является Парето-Оптимальное (ПО) [6] множество из .

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

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

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

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

Параллельный алгоритм выделения дольного графа

Рассмотрим взвешенный предфрактальный граф , порожденный затравкой и k процессоров , где .

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

Процедура состоит из двух шагов.

На первом шаге выделяем максимальное паросочетание максимального веса (МПМВ) используя алгоритм, предложенный Эдмондсом [7].

Второй шаг состоит в следующем.

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

Множество вершин объединяем с множеством или двудольного графа по принципу:

1. Eсли все вершины смежны с вершинами только множества или только множества , то множество вершин объединяем с множеством или множеством соответственно. При этом инцидентные им ребра сохраняем.

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

Опишем принцип работы алгоритма .

Количество процессоров равно количеству всех затравок L-ого ранга, то есть . Тогда каждый из процессоров назначим одной из затравок , .

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

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

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

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

АЛГОРИТМ

Вход: взвешенный предфрактальный граф .

Выход: дольный граф

ШАГ 1. Параллельно и независимо друг от друга процессоров для каждой затравки , находят двудольный граф с помощью процедуры . На шаге 1 получаем двудольный граф максимальной затравки.

Шаг 2. Объединяя эти двудольные графы получаем покрытие предфрактального графа двудольными графами, которое дает в объединении дольный граф.

Процедура .

Вход: взвешенный предфрактальный граф .

Выход: двудольный граф .

Теорема 1. Алгоритм выделяет дольный граф () на предфрактальном - графе , порожденном затравкой , , , с коэффициентом подобия .

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

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

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

Дальнейшая работа алгоритма: на шаге используя те же процессоры, закрепляя их затравках предпоследнего ранга, применяя процедуру к каждой затравке , опять получим двудольный граф. Будем помнить, что каждая вершина этой затравки содержит внутри себя двудольный граф. Тогда если мы развернем эти двудольные графы, находящиеся внутри затравки , то у нас в покрытии получатся 4х - дольные графы. Продолжая этот процесс, на том шаге () получаем, что, на затравках применяя тот же принцип распределения процессоров и процедуру , опять получаем двудольные графы. Тогда на последнем шаге будет выделена последняя двудольная затравка и, объединяя выделенные затравки мы получим дольный граф (). Тем самым мы доказали, что алгоритм выделяет дольный граф. <

Теорема 2. Вычислительная сложность параллельного алгоритма выделения дольного графа () на предфрактальном -графе , порожденном затравкой , ,, где , равна .

Доказательство. Алгоритм представляет собой, по существу многократное выполнение шага 1, т.е. поиск двудольного графа для каждой подграф-затравки, а их . Шаг 1 потребует выполнения операций на каждой подграф-затравке - столько операций выполняет алгоритм Эдмондса.

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

Сравнив вычислительную сложность параллельного алгоритма с вычислительной сложностью алгоритма Эдмондса, получим: , то есть ускорение вычисления параллельного алгоритма относительно алгоритма Эдмондса ~ . <

Примечание 1. Вычислительная сложность параллельного алгоритма меньше вычислительной сложности алгоритма Эдмондса, в раз на предфрактальном - графе . <

Теорема 3. Временная сложность параллельного алгоритма , где имеется процессоров , , равна .

Доказательство. Алгоритм выполняет шаг 1 параллельно, каждым из процессоров. Для выполнения шага 1 потребуется [7] времени (столько времени требуют процедура Эдмондса). Но все процессоры работают параллельно, то есть они закончат свою работу: «выполнение шага 1» в худшем случае за время . Таким образом, временная сложность алгоритма равна . <

Сравнив временную сложность параллельного алгоритма с вычислительной сложностью алгоритма Эдмондса, получим: .

Примечание 2. Временная сложность параллельного алгоритма меньше временной сложности алгоритма Эдмондса, в раз. <

Теорема 4. Временная сложность параллельного алгоритма , где используется процессоров , , равна .

Доказательство. Алгоритм выполняет шаг 1 параллельно, каждым из процессоров. Для выполнения шага 1 требуется времени. Но все процессоры работают параллельно, т.е. все процессоров закончат свою работу: «выполнение шага 1» - одновременно, за время . Шаг 1 будет выполнен ровно раз. Тогда, получим:

.

Получаем, что временная сложность алгоритма в случае использования процессоров, равна . <

Примечание 3. Временная сложность параллельного алгоритма , где используется процессоров , , меньше временной сложности алгоритма Эдмондса, в раз. <

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

Доказательство. Доказательство оптимальности по критерию следует из структуры работы алгоритма . Алгоритм выделяет один дольный граф, то есть состоит из одной компоненты.

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

Для доказательства этого утверждения сформулируем и докажем предложение.

Предложение. Двудольный граф на графе , , будет наибольшим по количеству ребер, если

(в случае, когда четно) и если (в случае, когда нечетно).

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

Если - четно, обозначим , тогда и максимальное количество ребер достигается при .

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

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

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

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

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

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

Литература

1. Залиханов М.Ч. Устойчивое развитие России: перспективы и угрозы // Безопасность Евразии. 2001. №2. С. 518-525.

2. Кочкаров А.А., Малинецкий Г.Г. Управление безопасностью и стойкостью сложных систем в условиях внешних воздействий // Проблемы управления. 2005. №5. С. 70-76.

3. Кочкаров Р.А. Целевые программы: инструментальная поддержка. М.: ЗАО «Издательство «Экономика» », 2007. 223 с.

4. Поспелов Г.С. Ириков В.А. Программно-целевое планирование и управление. М.: Сов. Радио. 1976. 440 с.

5. Кочкаров А.М. Распознавание фрактальных графов. Алгоритмический подход. Нижний Архыз: РАН САО, 1998.

6. Емеличев В.А., Перепелица В.А. Сложность дискретных многокритериальных задач // Дискретная математика. 1994. Т. 6, вып. 1.

С. 3 - 33.

7. Кристофидес Н. Теория графов. Алгоритмический подход. М.: Мир, 1978.

References

1. Zalikhanov M.C. Sustainable development of Russia: prospects and threats / / Security Evrazii.2001. № 2. S. 518-525.

2. Kochkarov A.A., Malinetskii G.G. Managing security and resilience of complex systems with external influences / / Control. 2005. № 5. S. 70-76.

3. Kochkarov R.A. Targeted programs: instrumental support. Moscow: ZAO "Publisher" Economy "," 2007. 223 s.

4. Pospelov G.S., Irikov V.A. Software-oriented planning and management - Sov. Radio. 1976. 440 C.

5. Kochkarov A.M. Recognition of fractal graphs. Algorithmic approach. Nizh. Arkhyz: SAO RAS, 1998.

6. Emelichev V.A., Perepelitsa V.A. Complexity of discrete multicriteria problems / / Appl. Math - 1994. T. 6, no. 1.

pp. 3 - 33.

7. N. Christofides, Graph Theory. Algorithmic approach. Academic Press, 1978.

Размещено на Allbest.ru