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

Запропоновано нову постановку задачі для формалізації вибору оптимальної проєктної структури організації, в основу якої покладено сучасні методології розроблення складних програмних систем, яка зводиться до нелінійних булевих рівнянь. Розроблено процедуру, що використовує ранговий підхід до розв’яза...

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2011
Hauptverfasser:	Листровой, С.В., Минухин, С.В.
Format:	Artikel
Sprache:	Russian
Veröffentlicht:	Інститут кібернетики ім. В.М. Глушкова НАН України 2011
Schriftenreihe:	Проблемы управления и информатики
Schlagworte:	Методы обработки информации
Online Zugang:	https://nasplib.isofts.kiev.ua/handle/123456789/207344
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:	Подход к формированию оптимальных проектных структур на основе рангового метода решения нелинейных булевых уравнений / С.В. Листровой, С.В. Минухин // Проблемы управления и информатики. — 2011. — № 5. — С. 110–122. — Бібліогр.: 19 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	nasplib_isofts_kiev_ua-123456789-207344
record_format	dspace
spelling	nasplib_isofts_kiev_ua-123456789-2073442025-10-07T00:05:26Z Подход к формированию оптимальных проектных структур на основе рангового метода решения нелинейных булевых уравнений Підхід до формування оптимальних проєктних структур на основі рангового методу розв’язання нелінійних булевих рівнянь Approach to the Formation of Optimal Project Structures Based on the Ranking Method for Solving Nonlinear Boolean Equations Листровой, С.В. Минухин, С.В. Методы обработки информации Запропоновано нову постановку задачі для формалізації вибору оптимальної проєктної структури організації, в основу якої покладено сучасні методології розроблення складних програмних систем, яка зводиться до нелінійних булевих рівнянь. Розроблено процедуру, що використовує ранговий підхід до розв’язання задач комбінаторної оптимізації, яка має поліноміальну часову складність. Наведено результати статистичного моделювання. A new formulation of the problem for the formalization of choice of the optimal design structure of the organization, based on a modern methodology for developing complex software systems, which reduces to nonlinear Boolean equations. A procedure is developed that uses the rank approach to solving combinatorial optimization problems, which has polynomial time complexity. The results of statistical modeling that substantiate the effectiveness of the proposed method are presented. 2011 Article Подход к формированию оптимальных проектных структур на основе рангового метода решения нелинейных булевых уравнений / С.В. Листровой, С.В. Минухин // Проблемы управления и информатики. — 2011. — № 5. — С. 110–122. — Бібліогр.: 19 назв. — рос. 0572-2691 https://nasplib.isofts.kiev.ua/handle/123456789/207344 519.854 10.1615/JAutomatInfScien.v43.i10.50 ru Проблемы управления и информатики application/pdf Інститут кібернетики ім. В.М. Глушкова НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
topic	Методы обработки информации Методы обработки информации
spellingShingle	Методы обработки информации Методы обработки информации Листровой, С.В. Минухин, С.В. Подход к формированию оптимальных проектных структур на основе рангового метода решения нелинейных булевых уравнений Проблемы управления и информатики
description	Запропоновано нову постановку задачі для формалізації вибору оптимальної проєктної структури організації, в основу якої покладено сучасні методології розроблення складних програмних систем, яка зводиться до нелінійних булевих рівнянь. Розроблено процедуру, що використовує ранговий підхід до розв’язання задач комбінаторної оптимізації, яка має поліноміальну часову складність. Наведено результати статистичного моделювання.
format	Article
author	Листровой, С.В. Минухин, С.В.
author_facet	Листровой, С.В. Минухин, С.В.
author_sort	Листровой, С.В.
title	Подход к формированию оптимальных проектных структур на основе рангового метода решения нелинейных булевых уравнений
title_short	Подход к формированию оптимальных проектных структур на основе рангового метода решения нелинейных булевых уравнений
title_full	Подход к формированию оптимальных проектных структур на основе рангового метода решения нелинейных булевых уравнений
title_fullStr	Подход к формированию оптимальных проектных структур на основе рангового метода решения нелинейных булевых уравнений
title_full_unstemmed	Подход к формированию оптимальных проектных структур на основе рангового метода решения нелинейных булевых уравнений
title_sort	подход к формированию оптимальных проектных структур на основе рангового метода решения нелинейных булевых уравнений
publisher	Інститут кібернетики ім. В.М. Глушкова НАН України
publishDate	2011
topic_facet	Методы обработки информации
url	https://nasplib.isofts.kiev.ua/handle/123456789/207344
citation_txt	Подход к формированию оптимальных проектных структур на основе рангового метода решения нелинейных булевых уравнений / С.В. Листровой, С.В. Минухин // Проблемы управления и информатики. — 2011. — № 5. — С. 110–122. — Бібліогр.: 19 назв. — рос.
series	Проблемы управления и информатики
work_keys_str_mv	AT listrovojsv podhodkformirovaniûoptimalʹnyhproektnyhstrukturnaosnoverangovogometodarešeniânelinejnyhbulevyhuravnenij AT minuhinsv podhodkformirovaniûoptimalʹnyhproektnyhstrukturnaosnoverangovogometodarešeniânelinejnyhbulevyhuravnenij AT listrovojsv pídhíddoformuvannâoptimalʹnihproêktnihstrukturnaosnovírangovogometodurozvâzannânelíníjnihbulevihrívnânʹ AT minuhinsv pídhíddoformuvannâoptimalʹnihproêktnihstrukturnaosnovírangovogometodurozvâzannânelíníjnihbulevihrívnânʹ AT listrovojsv approachtotheformationofoptimalprojectstructuresbasedontherankingmethodforsolvingnonlinearbooleanequations AT minuhinsv approachtotheformationofoptimalprojectstructuresbasedontherankingmethodforsolvingnonlinearbooleanequations
first_indexed	2025-11-27T00:00:17Z
last_indexed	2025-11-27T00:00:17Z
_version_	1849899482288750592
fulltext	© С.В. ЛИСТРОВОЙ, С.В. МИНУХИН, 2011 110 ISSN 0572-2691 УДК 519.854 С.В. Листровой, С.В. Минухин ПОДХОД К ФОРМИРОВАНИЮ ОПТИМАЛЬНЫХ ПРОЕКТНЫХ СТРУКТУР НА ОСНОВЕ РАНГОВОГО МЕТОДА РЕШЕНИЯ НЕЛИНЕЙНЫХ БУЛЕВЫХ УРАВНЕНИЙ Введение Исследования систем нелинейных уравнений с булевыми переменными име- ют достаточно широкий спектр приложений. Так, к ним можно отнести задачи формирования решений в системах управления сложными организационно- технологическими процессами, в системах диагностирования технических объек- тов, в которых могут возникать множественные отказы [1], в задачах маршрути- зации транспортных потоков, составления расписаний, упорядочения и календар- ного планирования комплекса взаимосвязанных работ [2, 3]. Выделим задачи ор- ганизационного проектирования [4–8], в которых актуальной остается проблема оптимизации состава исполнителей для разных уровней управления организация- ми, особенно в условиях современных проектно- и процессно ориентированной деятельности [9]. Системам булевых уравнений и методам их решения отводится важная роль во многих разделах науки о вычислениях, поскольку многие задачи сводятся к решению систем булевых уравнений и проверке совместности таких систем на множестве целых или натуральных чисел. Методы получения решений и крите- рии совместности систем линейных диофантовых уравнений (СЛДУ) в области натуральных чисел исследовались в работах [10–13]. В основе предлагаемых алго- ритмов решения СЛДУ лежит TSS-метод (Truncated Set Solution) построения мини- мального порождающего множества решений систем линейных однородных дио- фантовых уравнений во множестве натуральных чисел N. Показано также, что ал- горитмы решения СЛДУ в полях вычетов по модулю простого числа имеют наилучшую оценку — полиномиальную оценку временнóй сложности O(q 2 n 2 ), где q — число уравнений, а n — число неизвестных в системе. В других случаях эта оценка экспоненциальна, и при практической реализации необходимо определять состав решаемых задач в условиях, когда, например, существуют ограничения на оперативность принятия решений (временне ограничения) или на критерии стои- мости и т.д. Развитие и использование современных информационных технологий пред- полагает формализацию подходов, которые применяются в такой области, как со- здание сложных программных систем. Известно, что эта отрасль в настоящее время — одна из наиболее развивающихся и рентабельных. Она включает также преимущества, которые дает международная торговля и международный аутосор- синг. При этом одной из актуальных задач является задача оптимизации выпол- нения работ для организаций, в которых одновременно может выполняться не- сколько проектов, различных по трудоемкости, в условиях ограничений на чело- веческие ресурсы (количество исполнителей проектов). В этом случае применение систем булевых уравнений в рамках решения задач управления раз- работкой программных проектов позволяет формально описать используемые ме- тодологии проектирования и методы получения оптимальных решений. В насто- ящее время такая задача актуальна с точки зрения оптимизации организационных Международный научно-технический журнал «Проблемы управления и информатики», 2011, № 5 111 структур проектных организаций и решения других важных задач, из них выте- кающих, например формирование эффективных команд, методов эффективного управления персоналом и т.д. [6–8]. Постановка задачи исследования В данной работе рассматривается новая постановка задачи в рамках выпол- нения работ при управлении проектами (проектного менеджмента), выполняемых согласно методологии проектирования программного обеспечения MSF (Microsoft Solution Framework) [14, 15] (ее можно использовать и для другой известной мето- дологии разработки программного обеспечения — RUP (Rational Unified Process) [16], частично упростив). Особенность этой методологии заключается в том, что проек- тирование осуществляется согласно модели жизненного цикла, реализуемого с помощью фаз и итераций. Последнее создает возможности для реализации сле- дующих задач: многоверсионность, итеративность, инкрементность, что позволя- ет переходить к различным модификациям проекта в соответствии с изменяющи- мися условиями (задачами), особенно на первоначальных фазах разработки про- екта. Кроме того, в методологии реализована так называемая ролевая организация самого процесса проектирования (наряду с организацией, например, потоков ра- бот). В соответствии с ней в методологии MSF разрабатывается модель проектной группы MSF (MSF Team Model), в основе которой лежит подход фирмы Micro- soft [15] к организации работающего над проектом персонала для максимизации успешного выполнения проекта. Данная модель определяет так называемые роле- вые кластеры, области их компетенции и зоны ответственности, а также рекомен- дации членам проектной группы. Модель проектной группы MSF включает следующие ролевые кластеры: «Архитектор» (architect), «Управление продуктом» (product management), «Управ- ление программой» (program management), «Разработка» (development), «Тестиро- вание» (test), «Удовлетворение потребителя» (user experience) и «Управление вы- пуском» (release management). Они ответственны за различные области компетен- ции (functional areas) и связанные с ними цели и задачи проекта. Основная задача данной концепции проектной группы — построить основу производственных от- ношений и связанную с ней модель проектной команды таким образом, чтобы они были приспосабливаемыми (масштабируемыми) для удовлетворения нужд любо- го проекта. Одну роль (один кластер) может представлять (реализовывать) один или несколько сотрудников (участников проекта) в зависимости от масштабов проекта, его сложности, длительности и профессиональных навыков, требуемых для реализации всех областей компетенции ролевого кластера. Методология MSF легко масштабируема и может применяться в любых проектах: начиная с малых, в которых задействовано 2, 3 человека (малые многопрофильные команды), и за- канчивая большими (сотни исполнителей). При использовании проектной модели необходимо, чтобы в проектной команде обязательно были представлены семь основных ролей (ролевых кластеров) [14, 15]. Обычно выделение одного человека на каждый ролевой кластер обеспечивает защиту интересов каждой из ролей, но экономически не всегда оправданно для всех типов проектов. В связи с этим чле- ны проектной группы могут совмещать определенные роли. В малых проектных группах (командах) это просто необходимо. Для эффективного исполнения роли должно соблюдаться два принципа.  Роль команды разработчиков не может быть совмещена ни с какой другой ролью. Разработчики — это создатели проекта, и они не должны отвлекаться от своей главной задачи. Дополнительные обязанности могут повлечь невыполнение календарного графика проекта.  Избежание совмещения ролей, имеющих заранее предопределенные кон- фликты интересов, например роли «управление продуктом» и «управление про- граммой», имеют противоречащие друг другу интересы и, следовательно, в целях выполнения проекта не должны реализовываться одним участником. Менеджмент 112 ISSN 0572-2691 продукта должен удовлетворить заказчика, в то время как менеджмент программы обеспечивает готовность продукта в отведенное время и в рамках имеющегося бюджета проекта. При сочетании этих ролей возникает риск, что затребованное за- казчиком изменение либо не будет рассмотрено с должным вниманием, либо будет принято без надлежащего анализа его влияния на проект. Представление этих ролей различными исполнителями в проектной команде обеспечивает равновесие двух противоречащих точек зрения на задачи выполнения проекта. Это же относится и к попытке объединения ролей разработки и тестирования. В связи с особенностями, налагаемыми на ролевые кластеры, согласно реко- мендациям стандарта MSF 4.0 разработаны варианты возможных объединений ролей (кластеров) [15] (табл. 1). Таблица 1 Роли Архитекту- ра (P1) Управле- ние про- дуктом (P2) Управле- ние про- граммой (P3) Разработка (P4) Тестирова- ние (P5) Удовлетво- рение пот- ребителя (P6) Управле- ние выпус- ком (P7) Архитектура (P1) Нет Да Да Нежела- тельно Нежела- тельно Нежела- тельно Управление продуктом (P2) Нет Нет Нет Да Да Нежела- тельно Управление программой (P3) Да Нет Нет Нежела- тельно Нежела- тельно Да Разработка (P4) Да Нет Нет Нет Нет Нет Тестирование (P5) Нежела- тельно Да Нежела- тельно Нет Да Да Удовлетво- рение потре- бителя (P6) Нежела- тельно Да Нежела- тельно Нет Да Нежела- тельно Управление выпуском (P7) Нежела- тельно Нежела- тельно Да Нет Да Нежела- тельно Пусть имеются категории исполнителей X  {X1, X2 , X3 , X4 , X5 , X6 , X7 ,… …, Xn}, которые могут сочетать разные навыки ролевых кластеров, необходимых для выполнения проекта в соответствии с требованиями. В табл. 2 приведены все возможные комбинации непротиворечивых соче- таний ролей, когда исполнители проекта MSF 4.0 имеют навыки не меньше двух дополняющих друг друга ролевых кластеров. Таким образом, суще- ствует ограниченное количество комбинаций со- четаний ролей (навыков), которые могут быть у потенциальных исполнителей проекта. Поскольку в организации всегда осуществляется сертифика- ция и аттестация сотрудников, то можно сгруппи- ровать сотрудников в соответствии с категориями X1÷X12 , приведенными в табл. 2. Отметим, что в Software-организациях работают, как правило, та- кие категории исполнителей, как X4 , X6 , X7 , X8 , X9 , X10 , X12 , что на практике потенциально уменьшает количество возможных комбинаций различных типов проектных команд, выполняю- щих проекты. Таблица 2 Исполнитель Роли X1 P1 , P3 , P4 X2 P2 , P5 , P6 X3 P1 , P3 , P7 X4 P1 , P4 X5 P2 , P5 , P6 , P7 X6 P3 , P5 , P7 X7 P1 , P3 X8 P2 , P5 X9 P2 , P6 X10 P3 , P7 X11 P5 , P7 X12 P5 , P6 , P7 Международный научно-технический журнал «Проблемы управления и информатики», 2011, № 5 113 На основе категорий исполнителей MSF 4.0, приведенных в табл. 2, соста- вим возможные комбинации проектных команд согласно приведенным выше ре- комендациям (см. табл. 1) и сведем их в табл. 3 (общий теоретический подход). Таким образом, общее, теоретиче- ски рекомендуемое количество различ- ных типов команд проекта составляет 17. Вместе с тем на практике рекомен- дуется использовать различные типы команд, приведенные в табл. 4, и при этом их количество не превышает 8 (ра- циональный подход). Таким образом, количество раз- личных типов проектных команд может варьироваться от 8 до 17 в зависимости от сложности проекта, сроков его вы- полнения, стоимости (бюджета), что приводит к необходимости оптимиза- ции количества и типов команд по про- ектной организации в целом. Сформулируем задачу оптимизации состава исполнителей проектных ко- манд, в которых реализуются наиболее эффективные сочетания ролей (ролевых кластеров), следующим образом: необ- ходимо определить оптимальный состав проектных команд по исполнителям }{ iX и их количеству для выполнения проекта в рамках ограничений на его стоимость и стоимость его отдельных фаз, а также время выполнения (дли- тельности) проекта и его отдельных фаз. Будем полагать, что отдельную фазу проекта можно реализовать проектными командами, имеющими различный состав исполнителей (см. табл. 3), при бюдже- те Сi (ограничении на стоимость) i-й фазы проекта (в целом это можно определить как проектную структуру исполнителей проекта). Учитывая разное количество проектных команд и различный состав команд, которые могут реализовать отдельную фазу проекта при имеющемся ограничении Сi на ее стоимость (бюджет), сформируем следующее нелинейное уравнение:  12478346728641 XXXXbXXXbXXXb iii  104796487115114794 XXXXbXXXXbXXXXb iii ,1094128487127 iii CXXXXbXXXXb  (1) где ijb — коэффициент, учитывающий количество команд j-го типа, количество исполнителей j-й команды, стоимость единицы времени выполнения i-й фазы и коммуникаций между членами команд для исполнителей j-й команды, сочетаю- щие роли для различных участников (исполнителей) проекта. Таблица 3 № п/п № команды (тип) Состав исполните- лей команды 1 K1 X1, X5 2 K2 X2, X1, X11 3 K3 X4 , X6 , X8 4 K4 X6 , X1, X9 5 K5 X7 , X6 , X4 6 K6 X6 , X1, X8 7 K7 X9 , X7 , X4 , X11 8 K8 X9 , X3 , X4 9 K9 X10 , X3 , X4 10 K10 X10 , X2, X4 11 K11 X11 , X7 , X8 , X4 12 K12 X11 , X1, X8 13 K13 X11 , X4 , X9 , X10 14 K14 X1, X8, X12 15 K15 X1, X9 , X12 16 K16 X4 , X7 , X8 , X12 17 K17 X4 , X9 , X10 , X12 Таблица 4 № п/п № команды (тип) Состав исполните- лей команды 1 K3 X4 , X6 , X8 2 K5 X7 , X6 , X4 3 K6 X6 , X1, X8 4 K7 X9 , X7 , X4 , X11 5 K11 X11 , X7 , X8 , X4 6 K13 X11 , X4 , X9 , X10 7 K16 X4 , X7 , X8 , X12 8 K17 X4 , X9 , X10 , X12 114 ISSN 0572-2691 Следует отметить, что стоимость выполнения работ и сопутствующих ком- муникаций внутри команды можно учесть с помощью коэффициента ijb : затраты на выполнение всех работ фазы данной проектной командой с заданным составом исполнителей; затраты на коммуникации между членами проектной команды (различные ролевые кластеры; затраты на принятие решения относительно коор- динированного выполнения работ сотрудниками, относящихся к различным роле- вым кластерам. Для формализации условия выполнения всех работ i-й фазы введем еще один параметр — j , учитывающий участие (или неучастие) j-й проектной команды с определенным составом исполнителей, сочетающим в себе необходимый набор ролевых компетенций, по выполнению i-й фазы проекта следующим образом:     случае.противномв0 фазе;й-вучаствуеткомандапроектнаяесли,1 j i Тогда уравнение (1) примет следующий вид:  12478334672286411 XXXXbXXXbXXXb iii  104796648711551147944 XXXXbXXXXbXXXXb iii .109412884871277 iii CXXXXbXXXXb  (2) В случае оптимизации состава исполнителей для выполнения работ по всем фазам проекта для решения поставленной задачи необходимо дополнительно сформировать количество уравнений, определяемое количеством фаз проекта со- гласно используемой методологии выполнения проекта (в модели MSF 4.0 ис- пользуется пять фаз). В результате получим систему нелинейных булевых урав- нений, для которой необходимо определить условия ее совместности. Отличительная особенность поставленной задачи заключается в том, что размерность каждого из уравнений системы значительно возрастает вследствие учета таких факторов:  детализация отдельных фаз до уровня работ, выполняемых на каждой фазе проекта;  использование спиральной и инкрементной моделей жизненного цикла программного обеспечения, требующих постоянного изменения как количества команд, так и их состава [16];  итерационный характер выполнения отдельных фаз проекта в соответствии с выбранной моделью жизненного цикла программного обеспечения [16]. Приведенные факторы влияют на оперативность процесса формирования со- става и количества проектных команд организации, что предполагает разработку и исследование соответствующих подходов и методов с учетом того, что коли- чество проектов в организации может увеличиваться, а это потребует перерас- чета как количества команд, задействованных при выполнении различных про- ектов, так и состава их исполнителей для своевременного выполнения работ всех проектов. Поставленная задача сводится к перечислению корней уравнения (2), которое является нелинейным булевым уравнением (или системой нелинейных булевых уравнений типа (1)), решение которой носит комбинаторный характер. Для полу- чения решений предлагается формализация и алгоритмы решения поставленной за- дачи на основе рангового подхода к решению комбинаторных задач [9]. С учетом табл. 3, 4, а также уравнений (1), (2) общее количество слагаемых в одном нелинейном уравнении не превысит значения 17, точнее, будет варьиро- Международный научно-технический журнал «Проблемы управления и информатики», 2011, № 5 115 ваться в пределах от 8 до 17 в зависимости от конкретных проектов и ограниче- ний на структурный состав типов команд и их количества в рамках организацион- ной структуры проектной организации. Отметим, что постановку задачи можно распространить на оптимизацию со- става исполнителей сквозных бизнес-процессов предприятия для оптимизации его организационной структуры в условиях процессно-ориентированного подхода к управлению [17]. Формализация решения задачи систем нелинейных булевых уравнений В общем случае нелинейное уравнение можно представить в виде ,)(...)(...)()( 11 1 2 22 1 1 1 1 21 bCSCCSCCSCCSC nk p j n nnnj p j p j k nkkjnjn p j j      (3) где rp r n SSSCSr  ...)( 21 — сумма всех возможных сочетаний произве- дений переменных, содержащих в каждом произведении mkp XXXSr ... r различных переменных; ; !)(! ! rnr n pr   rjC — коэффициенты произведе- ний ,Sr содержащих r переменных. Пусть H — множество всех уравнений, ко- торое можно получить на основе (2), полагая равными нулю различные сочетания ljC в (3). Множество H полное в том смысле, что содержит в себе все возможные нелинейности, состоящие из всех возможных сочетаний переменных, образую- щих эти нелинейности, которые можно вообще построить на основе данного под- множества переменных }.,,,{ 21 nXXX  Нетрудно показать, что мощность данного множества очень велика, но ко- нечна и равна ,2 p где ...1 )!2(!2 ! )!2(!2 ! 1 )!1(!1 ! )!1(!1 ! 2 1 1                       n n n n n n n n p .)1 !1)!1( ! !1)!1( ! ...1 )!(! ! )!(! !                      n n n n knk n knk n  Задачу решения системы произвольных булевых уравнений представим в виде ,,1;)...,,,( 21 mjbXXXf jn  где ;;),...,,( 21 ZbHXXXf jn  Z — множество целых чисел; }.1,0{iX В работах [10–13, 18] рассматриваются алгоритмы построения минимального порождающего множества решений системы — TSS-алгоритмы и методы их оп- тимизации. Сложность решения задачи обусловлена тем, что даже задача опреде- ления числа корней булева уравнения имеет экспоненциальную сложность. Для решения линейных систем булевых уравнений в [19] предложен ранговый метод решения, где пространство решений представляется в виде многоярусного тре- угольного графа, являющегося эквивалентом n-мерного единичного куба. Следует отметить, что эффективные методы для решения нелинейных булевых уравнений вида (1) неизвестны, можно выделить лишь методы направленного перебора, раз- 116 ISSN 0572-2691 витые в работах [2, 3], которые имеют экспоненциальную сложность, поэтому ак- туальна разработка алгоритмов данной задачи с малой временной сложностью. Рассмотрим граф G(Х, Е) (рис. 1), в котором все вершины iX и jX соединены ребрами (i, j). В графе G(Х, Е) каждой вершине iX соответствует переменная iX . Выделим в графе G произвольную клику ,... mrp XXXQ  состоящую из r вершин, где r  n, и рассмотрим ее пересечения с )( r nr CS ),,...,,( 21 nXXXf а также с ).,...,,()( 21 nj r nr XXXgCS  Каждое пересечение можно охарактери- зовать суммами коэффициентов ,ljC стоящими при )( r nr CS в уравнении (3). Та- ким образом, произвольная задача решения булевых уравнений может рассматри- ваться как задача отыскания клик Q заданного веса в графе G. Так если решает- ся линейное булево уравнение ,44332211 bXCXCXCXC  то граф G будет иметь вид, изображенный на рис. 2. Каждой вершине iX графа G соответствует вес ,iC и для решения задачи в графе G следует найти клику }{  iQ из взвешенных вершин такую, чтобы ее сум- марный вес по весам }{ iC был равен b. Отметим, что в задачах решения уравне- ний с нелинейностью второй cтепени удобно вводить и весовые характеристики ребер. Рассмотрим уравнение следующего вида:  3113211244332211)( XXCXXCXCXCXCXCXf .4334422432234114 bXXCXXCXXCXXC  Ему можно поставить в соответствие следующий граф G для квадратичного буле- вого уравнения (рис. 2). Вершинам графа соответствуют веса ),( iC а ребрам — веса }.{ ijC Для реше- ния данной задачи в графе G требуется найти клики }{  iQ максимального сум- марного веса b. В этом случае граф G взвешенный и по вершинам, и по ребрам, аналогично взвешенными являются и все клики данного графа. Следует иметь в виду, что в квадратичной задаче .jiij CC  Таким образом, для решения произ- вольных булевых уравнений необходимо построить алгоритм, позволяющий находить в заданном графе G, взвешенном по вершинам или по ребрам, клики }{  iQ заданного веса b. Х1 Х2 Х3 Х4 С12 С13 С14 С23 С24 С34 Рис. 2 Х1 Х2 Х3 Х4 Хn Рис. 1 Международный научно-технический журнал «Проблемы управления и информатики», 2011, № 5 117 Решение задачи. Воспользуемся представлением исходного графа G в виде симметричного дерева путей, предложенного в [9]. Пусть все возможные состоя- ния некоторой системы определяются графом G(V, E) с n вершинами, которые соответствуют возможным состояниям системы. Перейдем к пространству с (n – 1) 2 состояниями. Для этого каждому из n состояний поставим в соответствие еще (n – 1) состояние, характеризующее способ достижения состояния из множе- ства {1, 2, ..., n}. При этом новые возникающие состояния будут определяться ран- гом пути в графе G(V, E), т.е. из вершины s графа G(V, E) в произвольную вершину j можно попасть по пути ранга r  1, используя одно ребро, по пути ранга r  2, ис- пользуя два ребра и т.д., по пути ранга r  n – 1, используя n – 1 ребро. Такое пространство состояний можно представить в виде стянутого дерева всех путей D графа G(V, E) (рис. 3). s n n n n 2 2 2 2 1 1 1 1 r  1 r  2 r  n  2 r  n  1 . . . . . . . . . . . . . . . . . . Рис. 3 Дерево всех путей D содержит n горизонтальных слоев вершин и (n – 1) ярус. Для прочтения путей на каждой горизонтальной линейке можно быть только один раз. Исходя из стянутого дерева путей, для произвольной вершины j множество путей, ведущих в эту вершину из некоторой вершины s, можно представить в сле- дующем виде: ,1,1;....)( 121   njmmmjm nr sj r sj r sjs где }{ r sj r sjm  — подмножества путей ранга r из произвольной вершины s в не- которую вершину j графа G(V, E). Таким образом, используя граф D и введя правила формирования путей сле- дующего ранга, из произвольной вершины s можно поэтапно строить пути }{ r sj произвольного ранга вплоть до ранга r  n – 1. В нашей задаче под состоянием си- стемы подразумеваются различные способы объединения вершин графа D в кли- ки. Тогда каждому пути }{ r sj ранга r в графе D, проходящем через вершины ),,,,( pkh vvv  в исходном графе G решаемой задачи соответствует клика из (r – 1) вершины ),...( pkh XXX характеризующаяся соответствующим весом. Ве- совые характеристики }{ 1r sjd произвольной клики ),(1 jQr состоящей из (r – 1) вершины и определяемой одним из путей r sj r sj m ранга r в графе D, вычисля- ются суммированием коэффициентов подмножества },{ rjf CL  стоящих при ,)( 1 1 f r nr PCS   где fP — все подмножества ,)}({ 1 1 f r nr CS   удовлетворяющие условию ,)()( 11 1    jQCS r f r nr а f r nr CS )( 1 1   определяется видом решае- мого уравнения. Таким образом, весовые характеристики клик ),(1 jQr определяемых мно- жеством путей ,r sjm запишем в соответствии с равенством rj LC rf sj Cd frj     )1( . 118 ISSN 0572-2691 Итак, в графе D каждый путь имеет в общем случае текущую длину d, и для решения поставленной задачи в графе D нужно перечислить все пути длины b. Если на основе подмножеств путей 1r sjm в графе D строить подмножества 2r sjm и так далее до подмножеств путей ,1nr sjm то необходимо построить (n – 1)! пу- тей. Поэтому для формирования путей вводится процедура А, позволяющая отсе- кать неперспективные пути. Для этого предлагается использовать весовую харак- теристику   С  d, где , ,  jr rjCC и проверить справедливость неравенств .; bdbd  Пути, для которых данные неравенства выполняются, можно исключить из дальнейшего анализа как неперспективные. При этом сами пути формируются на основе следующего рекуррентного соотношения: ,;,1;,1)};,(}{{1 pjnpnjpjr sj r sp   (4) где ( j, p) — ребро графа D; n — число различных вершин в графе D. Рассмотрим процедуру А решения задачи (3) на стянутых деревьях, приве- денных на рис. 3. Процедура А Шаг 1. Формируем множество путей на первом ярусе в соответствии с набо- рами переменных при коэффициентах уравнения и определяем весовые характе- ристики этих путей d; . Шаг 2. На основе сформированных путей текущего ранга r формируем пути следующего (r  1)-го ранга и для каждого пути проверяем выполнение неравенств ,; bdbd  если неравенства выполняются, то пути исключаются из дальней- шего анализа. Пути, длиной b, помечаем (). Шаг 3. Проверяем множества путей текущего ранга r : пустые или нет, если да, то алгоритм заканчивает работу, и пути, помеченные , соответствуют корням уравнения, в противном случае переходим к выполнению шага 2. Пример решения задачи. В качестве примера рассмотрим рациональный вариант использования состава исполнителей проекта, сформировав уравнение следующего вида: .12109433114792246711 iiii CXXXXbXXXXbXXXb  (5) В результате вычислений согласно рассмотренной методике получены такие коэффициенты в уравнении (5): ;51 ib ;32 ib .43 ib Допустим, что все типы команд участвуют в данной фазе проекта: 1  1, 2  1; 3  1. Таким образом, получим следующее уравнение: .9435 12109411479467  XXXXXXXXXXX (6) Решение уравнения на стянутом дереве путей отобразим в виде табл. 5, в ко- торой квадраты (ячейки) соответствуют вершинам в стянутом дереве путей графа. Таким образом, помеченные звездочками пути в табл. 5 соответствуют кор- ням уравнения (6). Все помеченные пути определяются одним и тем же множе- ством вершин: 7, 6, 4, 9, 10, 12. Итак, данное уравнение имеет один корень: X7 = 1; X6 = 1; X4 = 1; X9 = 1; X10 = 1; X12 = 1; X11 = 0. С точки зрения определения опти- мального количества и состава проектных команд, имеем, что для выполнения ра- бот фазы проекта требуются команды типа X7X6X4 и X4X9 X10X12 . Международный научно-технический журнал «Проблемы управления и информатики», 2011, № 5 119 Таблица 5 Решение уравнения (6) на основе процедуры A 764(5,7) 79114(3,9) 910124(4,8) 4 — 4 — 4 — 4 — 4 — 6 791146(8,4) 9101246(4,8) 6 91012476(9,3)* 910124116(4,8) 79114126(8,4) 6 — 6 — 6 — 7 9101247(4,8) 7 91012467(9,3)* 910124117(7,5) 7 — 7 — 7 — 9 7649(5,7) 9 764109(5,7) 764119(8,4) 764129(5,7) 9 76412109(9,7)* 76410119(8,4) 76412119(8,4) 76410129(9,7)* 9 — 9 — 10 76410(5,7) 10 79114610(8,4) 7641210(5,7) 791141210(7,5) 10 76412910(9,3)* 76491110(8,4) 76491210(9,3)* 10 — 10 — 11 76411(5,7) 91012411(4,8) 11 910124611(4,8) 910124711(7,5) 764911(8,4) 7641011(5,7) 7641211(5,7) 11 76410911(8,3) 76412911(8,3) 764121011(5,7) 76491211(8,3) 76491211(8,3) 764101211(5,7) 11 — 11 — 12 76412(5,7) 7911412(3,9) 12 79114612(8,4) 79114612(8,4) 764912(5,7) 7641012(5,7) 7641112(5,7) 12 76410912(7,5) 76411912(8,4) 76491112(8,4) 764101112(5,7) 12 — 12 Экспериментальное исследование разработанного алгоритма При экспериментальном иссле- довании разработанного алгоритма решения нелинейных булевых урав- нений коэффициенты в уравнениях генерировались по равномерному за- кону распределения. Исследовались зависимости временнóй сложности работы предложенного алгоритма от числа переменных и числа слагаемых в уравнении. Все результаты получе- ны с доверительной вероятностью 0,95, на каждую рассчитанную точку полученных графиков решалось не меньше 60 тестовых задач. На рис. 4, 5 приведены графики зависимости среднего времени решения уравнений от числа переменных при различных значениях числа слагаемых в уравне- нии (здесь и ниже N — количество переменных в уравнении; T — время решения задачи; Ksum — количество слагаемых в уравнении; Kseq — мак- симальное количество переменных в слагаемых уравнения). На рис. 6 при- веден график зависимости среднего 0 1 2 3 4 5 10 11 12 13 14 15 16 17 18 19 20 21 22 23 Время решения, с Аппроксимация полиномом T  10 2 , c N y  0,1622x 5  4,508x 4 44,417x 3 175,67x 2 223x R 2  0,9908; Ksum 80Kseq 3 0 0,5 1 1,5 2 2,5 3 3,5 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 Время решения, с Аппроксимация полиномом T  10 3 , c N y  0,1084x 5  3,2715x 4 34,271x 3 142,13x 2 187,26x R 2  0,9908; Ksum 80Kseq 3 0 1 2 3 4 5 5 10 15 20 25 30 Время решения, с Аппроксимация полиномом y  13,089x 5  99,1425x 4 226,19x 3 145 Ksum 20Kseq 4 T  10 2 , c N Рис. 4 120 ISSN 0572-2691 времени решения задачи от числа слагаемых (Ns) в уравнении при фиксирован- ном числе переменных в нелинейном уравнении, а на рис. 7–9 показаны графики зависимости числа элементарных операций (сравнения и сложения), выполняе- мых процедурой А, от числа переменных и слагаемых. 0 0,5 1,0 1,5 2,0 2,5 3,0 3,5 4,0 4,5 5 10 15 20 25 30 Время решения, с Аппроксимация полиномом T  10 2 , c Ns y  4,9222x 3  46,617x 2 35,97x Ksum 20Kseq 6 Рис. 6 0 2 4 6 8 5 10 15 20 25 30 Количество операций Аппроксимация полиномом T  10 5 , c y  7246,6x 3 26835x 2 17844x R 2  0,9901; Ksum 20; Kseq 2 Ns Рис. 8 Аппроксимация полученных гра- фиков проведена методом наименьших квадратов, из которой видно, что вре- мя решения нелинейных булевых уравнений пропорционально полино- мам 3- и 5-й степеней от размера входа задачи. Анализ результатов тестовых задач, содержащих до ста переменных, показал, что временнáя сложность остается такой же и при дальнейшем увеличении размерности решаемых за- дач при числе слагаемых, не превы- шающем 80. Экспериментальная часть данного исследования и расчеты сделаны в разра- ботанном авторами программном продукте, реализованном в среде Visual Studio 2008 на языке C#. Для визуализации результатов и экспорта их в Excel использо- вались библиотеки Microsoft.NET Framework 3.5. В качестве технического обес- печения использовался ноутбук Acer Aspire 4920 со следующими характеристи- ками: тип, модель — Intel® Core™ 2 Duo T5450; частота — 1.66 ГГц, размер кэша L2 — 2048 Кбайт; параметры процессора — технология Intel Centrino Duo Mobile, частота системной шины 667 МГц; чипсет — Intel® PM965 + ICH-8M; тип слотов памяти — DDR2 SoDIMM; установлено памяти — 2048 Мбайт. При необходимости решения вопроса непротиворечивости системы уравне- ний с помощью рассмотренной процедуры А для одного любого уравнения си- стемы можно перечислить все его корни и непосредственной подстановкой полу- 0 1 2 3 4 5 6 10 11 12 13 14 15 16 17 18 19 20 21 22 Время решения, с Аппроксимация полиномом T  10 3 , c N y  0,8494x 4  13,612x 3 70,159x 2 108,67x R 2  0,9987; Ksum 60Kseq 3 Рис. 5 0 2 4 6 8 10 5 10 15 20 25 30 Количество операций Аппроксимация полиномом T  10 6 , c N y  8328x 3 341561x 2 322362x R 2  0,9997; Ksum 30 Рис. 7 0 0,5 1 1,5 2 2,5 3 3,5 4 4,5 5 10 15 20 25 30 Время решения, с Аппроксимация полиномом Ns T  10 7 , c y  462170x 3 5E  06x 2 5E  06x R 2  0,9906; Ksum 20; Kseq 6 Рис. 9 Международный научно-технический журнал «Проблемы управления и информатики», 2011, № 5 121 ченных корней в оставшиеся уравнения за полиномиальное время определить, совместна система или нет, поскольку число таких уравнений в рассматриваемой задаче не превышает нескольких десятков, а число слагаемых в уравнении 14. Заключение Таким образом, предложенная процедура А перечисления корней нелинейно- го булевого уравнения на основе идей рангового подхода позволяет за полиноми- альное время решить задачу, если количество переменных в задаче не превыша- ет 30, а количество слагаемых не превышает 80 (тенденция сохраняется и при ко- личестве переменных, не превышающем 100), т.е. при таких размерностях задача может быть решена за время, вполне приемлемое для процесса формирования проектных команд при выполнении работ в задачах управления проектами, вы- полняемых согласно методологиям проектирования программного обеспечения MSF и RUP. Следует отметить, что при количестве переменных, значительно пре- вышающем 100, проявляется экспоненциальный рост временнóй сложности алго- ритма. Представление пространства решений в виде симметричного графа (см. рис. 3) по сравнению с треугольным графом, рассмотренным в [16], кроме за- дач нелинейных булевых уравнений, позволяет решать и задачи линейных буле- вых уравнений. При этом временнáя сложность их решения остается такой же, как и в [16], т.е. определяется полиномом третьей степени (сложность O(n 3 )) при ко- личестве переменных, не превышающем 30, что следует из рис. 8 (эта тенденция сохраняется и при решении тестовых задач, содержащих количество переменных, не превышающее 100). Данный алгоритм также можно эффективно использовать для решения задач диагностики множественных отказов распределенных систем управления слож- ными объектами, задач сетевого планирования и составления расписаний. С.В. Лістровий, С.В. Мінухін ПІДХІД ДО ФОРМУВАННЯ ОПТИМАЛЬНИХ ПРОЕКТНИХ СТРУКТУР НА ОСНОВІ РАНГОВОГО МЕТОДУ РОЗВ’ЯЗАННЯ НЕЛІНІЙНИХ БУЛЕВИХ РІВНЯНЬ Запропоновано нову постановку задачі для формалізації вибору оптимальної проектної структури організації, в основу якої покладено сучасні методології розроблення складних програмних систем, яка зводиться до нелінійних буле- вих рівнянь. Розроблено процедуру, що використовує ранговий підхід до розв’язання задач комбінаторної оптимізації, яка має поліноміальну часову складність. Наведено результати статистичного моделювання. S.V. Listrovoy, S.V. Minukhin AN APPROACH TO FORMING OPTIMAL DESIGN STRUCTURES BASED ON RANKING METHOD OF SOLVING NONLINEAR BOOLEAN EQUATIONS A new formulation of the problem for the formalization of choice of the optimal de- sign structure of the organization, based on a modern methodology for developing complex software systems, which reduces to nonlinear Boolean equations. A proce- dure is developed that uses the rank approach to solving combinatorial optimization problems, which has polynomial time complexity. The results of statistical modeling that substantiate the effectiveness of the proposed method are presented. 122 ISSN 0572-2691 1. Литвиненко А.Е. Модели и алгоритмы определения множественных отказов в сложных си- стемах // Проблеми інформатизації і управління. — 2004. — Вип. 11. — С. 139–147. 2. Литвиненко А.Е. Метод направленного перебора в системах управления и диагностики. — Киев : Научн.-изд. Центр НБУВ, 2007. — 328 с. 3. Литвиненко А.Е. Определение класса истинности логических формул методом направлен- ного перебора // Кибернетика и системный анализ. — 2000. — № 5. — С. 23–31. 4. Новиков Д.А., Суханов А.Л. Модели и методы управления научными проектами. — М. : ИУО РАО, 2005. — 84 с. 5. Новиков Д.А. Теория управления организационными системами. — М. : Физматлит, 2007. — 2-е изд. — 584 с. 6. Новиков Д.А. Модели формирования и функционирования неоднородных команд // Управ- ление большими системами. — 2007. — № 18. — С. 73–90. 7. Новиков Д.А., Баркалов С.А., Калинина Н.Ю. Механизмы компромисса в моделях функци- онирования команд управления проектами // Вестн. ВГТУ. — 2008. — 4, № 7. — С. 47–50. 8. Новиков Д.А. Математические модели формирования и функционирования команд. — М. : Физматлит, 2008. — 184 с. 9. Пономаренко В.С., Листровой С.В., Минухин С.В., Знахур С.В. Методы и модели планиро- вания ресурсов в GRID-системах. — Харьков : ИД «ИНЖЭК», 2008. — 408 с. 10. Кривый С.Л. Алгоритмы решения систем линейных диофантовых уравнений в целочис- ленных областях // Кибернетика и системный анализ. — 2006. — № 2. — С. 3–17. 11. Кривый С.Л. Алгоритмы решения систем линейных диофантовых уравнений в полях выче- тов // Там же. — 2007. — № 2. — С. 15–23. 12. Кривый С.Л. О некоторых методах решения и критериях совместности систем линейных диофантовых уравнений в области натуральных чисел // Там же. — 1999. — № 4. — С. 12–36. 13. Кривый С.Л. Алгоритм построения базиса множества решений систем линейных диофан- товых уравнений в кольце целых чисел // Там же. — 2009. — № 6. — С. 36–41. 14. MSF for Agile software development projects. — http://msdn.microsoft.com/ en-us/library/ bb668951.aspХ. 15. http://www.microsoft.com/msf. 16. Орлов С.А. Технологии разработки программного обеспечения : Учебник для вузов. — СПб : Питер, 2002. — 463 с. 17. Пономаренко В.С., Мінухін С.В., Беседовський О.М. Механізм прийняття рішень на підпри- ємстві: процесний підхід. — Харків : ХНЕУ, 2005. — 240 с. 18. Кривый С.Л., Матвеева Л.Е. Формальные методы анализа свойств систем // Кибернетика и системный анализ. — 2003. — № 2. — С. 15–36. 19. Кожухов В.Д., Лістрова О.С. Методи рішення задачі про найменший поділ на основі ран- гового підходу // Вісті академії інженерних наук . — 1999. — № 4. — С. 117–123. Получено 12.04.2010 После доработки 12.01.2011 http://msdn.microsoft.com/%20en-us/library/%0bbb668951.aspХ http://msdn.microsoft.com/%20en-us/library/%0bbb668951.aspХ http://www.microsoft.com/msf/

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

Institution

Ähnliche Einträge