Методика исследования алгоритмов решения одноуровневой задачи унификации программного обеспечения компьютерной сети предприятия по экономическому критерию
В.
Н. ИзотовБиблиографическое описание статьи для цитирования:
Изотов
В.
Н. Методика исследования алгоритмов решения одноуровневой задачи унификации программного обеспечения компьютерной сети предприятия по экономическому критерию // Научно-методический электронный журнал «Концепт». –
2015. – Т. 13. – С.
2571–2575. – URL:
http://e-koncept.ru/2015/85515.htm.
Аннотация. Статья является продолжением целой серии статей, посвящённых экономическому обоснованию степени унификации программного обеспечения компьютерных сетей современных предприятий. В статье рассмотрена методика исследования алгоритмов решения одноуровневой задачи унификации программного обеспечения компьютерной сети предприятия по экономическому критерию. Технологическую основу методики составляет программная система для проведения исследований.
Ключевые слова:
компьютерная сеть, программное обеспечение, методика исследования алгоритмов унификации
Текст статьи
Изотов Виктор Николаевич,Доктор технических наук, профессор кафедры экономики и финансов Тульского филиала ФГБОУ ВПО «Российская академия народного хозяйства и государственной службы при Президенте Российской Федерации», г. Тулаizotovvntula@mail.ru
Методика исследованияалгоритмов решения одноуровневойзадачи унификациипрограммного обеспечения компьютерной сети предприятия
по экономическому критерию
Аннотация.Статья является продолжением целой серии статей, посвящённыхэкономическому обоснованию степени унификации программного обеспечения компьютерных сетей современных предприятий. В статье рассмотренаметодика исследования алгоритмов решения одноуровневой задачи унификации программного обеспечения компьютерной сети предприятия по экономическому критерию.Технологическую основу методики составляет программная система для проведения исследований.Ключевые слова:компьютерная сеть, программное обеспечение, методика исследования алгоритмовунификации.
Одноуровневаязадачаунификации программного обеспечения(ПО)компьютерной сети(КС)предприятия может быть сформулированатак[1]: выбратьряд типов операционных систем(ОС)компьютерной сети, удовлетворяющих заданным требованиям и минимизирующихфункцию
(1)при ограничениях
(2)
(3)
(4)где U={1,2,…,m} – номератипов ОС; X={1,2,…,n} – номеравариантов применения ОС; ||Gio|| – постоянные затратынаОС iго типа; ||Gij||– затратына покупку и эксплуатацию ОС iго типа при выполнении задач jго вида. , когдаiй тип ОС не имеет возможностивыполнять задачи jго вида.xiи xij–параметры оптимизации:xi 1, если iй тип ОС включен в типоразмерный ряд, xi= 0, –в противном случае;xij 1, если iй тип ОС включен в типоразмерный ряд и выполняет задачи jго вида, xij= 0, –если не выполняет;Исследование алгоритмов решения задачи (1) (4),основанных на идеях методаветвей и границ, должноучитывать следующиеособенности. В зависимости от конкретных значений исходных данных оптимальное решение может быть получено за один шаг выполнения алгоритма ветвей и границ, или может понадобиться максимальное число шагов (полный перебор допустимых решений). Факт получения оптимального решения с помощью проверяемого алгоритма и последующее сравнение его с решением, найденным с использованием ранее проверенного алгоритма, еще не говорит о наилучшей эффективности проверяемого алгоритма, поскольку оптимальное решение могло быть найдено в результате полного перебора. В связи с этим, для проверки алгоритма метода ветвей и границ (в том числе, способов построения нижней границы и схем ветвления) необходимо сформулировать такие исходные данные, которые проверяли бы алгоритм на границах его работоспособности. Такому требованию удовлетворяют исходные данные для задачи (1) (4), приведенные в [2].
.
С целью объективной оценки эффективности алгоритмов необходимо также предусмотреть сравнение по быстродействию алгоритмов на множестве случайных исходных данных, а также обеспечение одинаковых условий сравнения.Необходимость обеспечения одинаковых условий сравнения алгоритмов обусловлена тем,что формализация одного и того же алгоритма может быть различной. Это приводит к различиям в программной реализации алгоритмов, тем более что в большинстве случаев приходится сравнивать алгоритмы с опубликованными результатами, полученными с применением различных программ, разработанных различными программистами и апробированных на разных ЭВМ. С целью обеспечения одинаковых условий сравнения известных и предлагаемых алгоритмв[1] разработана программа на языке PASCALдля решения задачи (1) (4) методом ветвей и границ.Разработанная программа включена программную систему Expo2.0, в состав которой также входят программы решения различных классов задач исследования операций.На рисунке 1 изображено окно программной системы Expo2.0. Равноценность условий сравнения различных методов и стратегий обеспечена единым подходом к формализации алгоритмов и программной реализации всех стратегий, выбор которых в процессе исследования осуществляется параметрической настройкой программы. Кроме того, программа позволяетгенерировать случайные числа для заполнения матриц исходных данных.
Рис. 1. Окно программной системы Expo2.0 при решенииодномерной статической задачи унификации
Результаты исследований с помощью программной системы показали, что повышение быстродействия алгоритма ветвей и границ с применением предлагаемой усовершенствованной стратегией, по сравнению с известным способом построения нижней границы, достигает 12%. Требования к объему оперативной памяти во всех случаях одинаковы. Аналогичный подход примененпри проверке работоспособности и эффективности усовершенствованного способа построения нижней границы в приближенных алгоритмах решения задачи (1) (4).Применение этого способа для наиболее эффективного приближенного алгоритма, рассмотренного в [3], обеспечивает повышениеего быстродействияв 810 раз при такой же точности результатов. Быстродействие получения точного решения задач большой размерности методом отбора переменных[1]в 57 раз выше быстродействия метода ветвей и границ. Анализ эффективности разработанных алгоритмов позволяет сделать вывод о целесообразности применения схемы ветвей и границ с усовершенствованным способом построения нижней границы для точного решения задачи унификации ПО КС на уровне системного программного обеспечения(например, операционной системы), а применение усовершенствованных приближенных алгоритмов рекомендуется на уровне программных модулей, входящих в состав системного ПО, так как в этом случае значительно возрастает размерность задачи. Для получения точного решения задач большой размерности предпочтительнее применять алгоритм отбора переменных.В общем виде методика решения задачи унификации ПО КС представлена на рисунке 2.С целью проверки наиболее трудоемкой части методики обоснования рациональной степени унификации ПО КС решалась частная задача (1) (4) сокращения числа типов операционных систем в КС предприятия по экономическому критерию. На первом этапе методики решения задачи унификации по экономическому критерию формировались исходные данные. Исходныеданные представленыв таблице 1.
Рис.2.Методика решения задачи унификации ПО КС
Таблица 1Исходные данные для решения задачи унификации ОС
Типы ОС12345678Возможноеколичество ОС562025324
3080 100120 140110
130230
280Количество, принятое в задаче52532790130120250
С одной стороны, процесс формирования исходных данных может осуществляться с использованием графиковзависимостей, полученныхпо результатамэкспериментального исследования имитационной модели процесса функционирования КС, разработанной по методике, изложенной в [4].
Тогда формирование областей допустимых значений параметров ОС и допустимых значений частных показателей эффективности их функционирования производитсятакже на основеимитационного моделирования. Результаты исследований на модели функционирования компьютерной сети представлены в виде графиков (рисунки 3 –5).На рисунке 3по оси ординат указан показатель t
временязадержки сообщения в сети, С
пропускнаяспособностьканалов передачи данных при различном количестве виртуальных ОС в сети (10, 20, 30, 40). Данные эксперимента показывают, что время задержки сообщения в сети уменьшается с уменьшением МЕТОДИКАрешения задачи унификации ПО компьютерной сетиЗАДАЧИунификации ПО КСМЕТОДЫ решениязадач унификации ПОКС
одноуровневыемногоуровневыеточныеприближённыединамические
эвристическиеТЕХНОЛОГИЯподготовки данных ирешения задачи унификации ПО КСРЕКОМЕНДАЦИИпо рациональной унификации ПО КС
количества виртуальных ОС в сети и уменьшается с возрастанием пропускной способности каналов передачи данных.
Рис.3.Зависимость времени задержки сообщения в сети от пропускной способности каналов передачи данных при различном количестве виртуальных ОС
Рис. 4.Зависимость времени задержки сообщения в сети от среднего времени наработки на отказ каналов передачи данных при различном количестве виртуальных ОС
На рисунке 4показана другаязависимость, где tотк
наработкана отказ каналов передачи данных при различном количестве виртуальных ОС в сети (10, 20, 30, 40).С помощьюрисунка5можно оценить влияниеинтенсивности поступления запросов на обслуживание в сети на временязадержки сообщения в сети.
Рис.5.Зависимость времени задержки сообщения в сети от интенсивности поступления запросов при различном количестве виртуальных ОС
По результатам моделирования можно установитьвозможность замены реальной ОС на виртуальную. Этисведения используются при подготовке исходных данных длярешении задачи унификации ПО КС. Область возможных замен ОС для решения задачи задаётся в исходной матрице . С другой стороны, в большинстве случаев задача унификации ОС КС предприятиярешается после решения задачи рационального технического оснащения КС, то есть, предполагается, что ранее выбранные параметры и характеристики реальных ОС уже обоснованы с точки зрения допустимости их значений для решения задач конкретного вида. Поэтому необходимостьимитационного моделирования в этомслучае отпадает. Моделирование может понадобиться тольков случае выработки требований по унификации к вновь разрабатываемым ОС. В настоящей статьена примере решения частной задачи проверяется работоспособность разработанных алгоритмов и методики применительно к задаче унификации существующих ОС, сведения о характеристиках которых известны и доступны.На втором этапе методики обоснования рациональной степени унификации ПО КС решаласьзадача (1) (4) методом ветвей и границ.Результаты решения задачи показывают, что при унификации на уровне ОС рациональным сокращением числа типов ОС является сокращение с 8ми типов до 3х. В таблице 1оставшиеся после унификации типы ОС выделены. Такое сокращение дает снижение значения суммарных затрат на 10 % от исходного. Если сократить число применяемых типов ОС до двух (при условии обеспечения возможности решения всех видов задач), экономический эффект от унификации возрастает до 22%. Применение в корпоративной сети ОС одного типа экономически невыгодно (суммарные затраты возрастают в два раза), а также увеличивается время реакции системы на запросы пользователей.
Ссылки на источники1. Изотов, В.Н.Метод решения задачи оптимальной унификации программного обеспечения по экономическому критерию / В.Н. Изотов, Е.А. Дьяченко // Известия ТулГУ. Технические науки. Вып. 9. Ч. 2. –Тула: Издво ТулГУ, 2013. –С. 150 156. –ISSN20716168.2. Erlenkotter, D. A dualbased procedure for uncapacitated facility location / D. Erlenkotter // Oper. Res., 1978, V.26, № 6. P. 9921009.3. Алексеев, О.Г. Сведение задач оптимизации динамического параметрического ряда к многомерной задачи унификации / О.Г. Алексеев // Стандартизация военной техники, 1984, № 2. –С. 4753.4. Изотов, В.Н. Имитационная модель для решения задачи синтеза физической структуры АСУ нового поколения / В.Н. Изотов, Н.С. Акиншин, Ю.Б. Подчуфаров, П.В. Комогорцев // Оборонная техника, 1997, № 34. С. 99103.
Методика исследованияалгоритмов решения одноуровневойзадачи унификациипрограммного обеспечения компьютерной сети предприятия
по экономическому критерию
Аннотация.Статья является продолжением целой серии статей, посвящённыхэкономическому обоснованию степени унификации программного обеспечения компьютерных сетей современных предприятий. В статье рассмотренаметодика исследования алгоритмов решения одноуровневой задачи унификации программного обеспечения компьютерной сети предприятия по экономическому критерию.Технологическую основу методики составляет программная система для проведения исследований.Ключевые слова:компьютерная сеть, программное обеспечение, методика исследования алгоритмовунификации.
Одноуровневаязадачаунификации программного обеспечения(ПО)компьютерной сети(КС)предприятия может быть сформулированатак[1]: выбратьряд типов операционных систем(ОС)компьютерной сети, удовлетворяющих заданным требованиям и минимизирующихфункцию
(1)при ограничениях
(2)
(3)
(4)где U={1,2,…,m} – номератипов ОС; X={1,2,…,n} – номеравариантов применения ОС; ||Gio|| – постоянные затратынаОС iго типа; ||Gij||– затратына покупку и эксплуатацию ОС iго типа при выполнении задач jго вида. , когдаiй тип ОС не имеет возможностивыполнять задачи jго вида.xiи xij–параметры оптимизации:xi 1, если iй тип ОС включен в типоразмерный ряд, xi= 0, –в противном случае;xij 1, если iй тип ОС включен в типоразмерный ряд и выполняет задачи jго вида, xij= 0, –если не выполняет;Исследование алгоритмов решения задачи (1) (4),основанных на идеях методаветвей и границ, должноучитывать следующиеособенности. В зависимости от конкретных значений исходных данных оптимальное решение может быть получено за один шаг выполнения алгоритма ветвей и границ, или может понадобиться максимальное число шагов (полный перебор допустимых решений). Факт получения оптимального решения с помощью проверяемого алгоритма и последующее сравнение его с решением, найденным с использованием ранее проверенного алгоритма, еще не говорит о наилучшей эффективности проверяемого алгоритма, поскольку оптимальное решение могло быть найдено в результате полного перебора. В связи с этим, для проверки алгоритма метода ветвей и границ (в том числе, способов построения нижней границы и схем ветвления) необходимо сформулировать такие исходные данные, которые проверяли бы алгоритм на границах его работоспособности. Такому требованию удовлетворяют исходные данные для задачи (1) (4), приведенные в [2].
.
С целью объективной оценки эффективности алгоритмов необходимо также предусмотреть сравнение по быстродействию алгоритмов на множестве случайных исходных данных, а также обеспечение одинаковых условий сравнения.Необходимость обеспечения одинаковых условий сравнения алгоритмов обусловлена тем,что формализация одного и того же алгоритма может быть различной. Это приводит к различиям в программной реализации алгоритмов, тем более что в большинстве случаев приходится сравнивать алгоритмы с опубликованными результатами, полученными с применением различных программ, разработанных различными программистами и апробированных на разных ЭВМ. С целью обеспечения одинаковых условий сравнения известных и предлагаемых алгоритмв[1] разработана программа на языке PASCALдля решения задачи (1) (4) методом ветвей и границ.Разработанная программа включена программную систему Expo2.0, в состав которой также входят программы решения различных классов задач исследования операций.На рисунке 1 изображено окно программной системы Expo2.0. Равноценность условий сравнения различных методов и стратегий обеспечена единым подходом к формализации алгоритмов и программной реализации всех стратегий, выбор которых в процессе исследования осуществляется параметрической настройкой программы. Кроме того, программа позволяетгенерировать случайные числа для заполнения матриц исходных данных.
Рис. 1. Окно программной системы Expo2.0 при решенииодномерной статической задачи унификации
Результаты исследований с помощью программной системы показали, что повышение быстродействия алгоритма ветвей и границ с применением предлагаемой усовершенствованной стратегией, по сравнению с известным способом построения нижней границы, достигает 12%. Требования к объему оперативной памяти во всех случаях одинаковы. Аналогичный подход примененпри проверке работоспособности и эффективности усовершенствованного способа построения нижней границы в приближенных алгоритмах решения задачи (1) (4).Применение этого способа для наиболее эффективного приближенного алгоритма, рассмотренного в [3], обеспечивает повышениеего быстродействияв 810 раз при такой же точности результатов. Быстродействие получения точного решения задач большой размерности методом отбора переменных[1]в 57 раз выше быстродействия метода ветвей и границ. Анализ эффективности разработанных алгоритмов позволяет сделать вывод о целесообразности применения схемы ветвей и границ с усовершенствованным способом построения нижней границы для точного решения задачи унификации ПО КС на уровне системного программного обеспечения(например, операционной системы), а применение усовершенствованных приближенных алгоритмов рекомендуется на уровне программных модулей, входящих в состав системного ПО, так как в этом случае значительно возрастает размерность задачи. Для получения точного решения задач большой размерности предпочтительнее применять алгоритм отбора переменных.В общем виде методика решения задачи унификации ПО КС представлена на рисунке 2.С целью проверки наиболее трудоемкой части методики обоснования рациональной степени унификации ПО КС решалась частная задача (1) (4) сокращения числа типов операционных систем в КС предприятия по экономическому критерию. На первом этапе методики решения задачи унификации по экономическому критерию формировались исходные данные. Исходныеданные представленыв таблице 1.
Рис.2.Методика решения задачи унификации ПО КС
Таблица 1Исходные данные для решения задачи унификации ОС
Типы ОС12345678Возможноеколичество ОС562025324
3080 100120 140110
130230
280Количество, принятое в задаче52532790130120250
С одной стороны, процесс формирования исходных данных может осуществляться с использованием графиковзависимостей, полученныхпо результатамэкспериментального исследования имитационной модели процесса функционирования КС, разработанной по методике, изложенной в [4].
Тогда формирование областей допустимых значений параметров ОС и допустимых значений частных показателей эффективности их функционирования производитсятакже на основеимитационного моделирования. Результаты исследований на модели функционирования компьютерной сети представлены в виде графиков (рисунки 3 –5).На рисунке 3по оси ординат указан показатель t
временязадержки сообщения в сети, С
пропускнаяспособностьканалов передачи данных при различном количестве виртуальных ОС в сети (10, 20, 30, 40). Данные эксперимента показывают, что время задержки сообщения в сети уменьшается с уменьшением МЕТОДИКАрешения задачи унификации ПО компьютерной сетиЗАДАЧИунификации ПО КСМЕТОДЫ решениязадач унификации ПОКС
одноуровневыемногоуровневыеточныеприближённыединамические
эвристическиеТЕХНОЛОГИЯподготовки данных ирешения задачи унификации ПО КСРЕКОМЕНДАЦИИпо рациональной унификации ПО КС
количества виртуальных ОС в сети и уменьшается с возрастанием пропускной способности каналов передачи данных.
Рис.3.Зависимость времени задержки сообщения в сети от пропускной способности каналов передачи данных при различном количестве виртуальных ОС
Рис. 4.Зависимость времени задержки сообщения в сети от среднего времени наработки на отказ каналов передачи данных при различном количестве виртуальных ОС
На рисунке 4показана другаязависимость, где tотк
наработкана отказ каналов передачи данных при различном количестве виртуальных ОС в сети (10, 20, 30, 40).С помощьюрисунка5можно оценить влияниеинтенсивности поступления запросов на обслуживание в сети на временязадержки сообщения в сети.
Рис.5.Зависимость времени задержки сообщения в сети от интенсивности поступления запросов при различном количестве виртуальных ОС
По результатам моделирования можно установитьвозможность замены реальной ОС на виртуальную. Этисведения используются при подготовке исходных данных длярешении задачи унификации ПО КС. Область возможных замен ОС для решения задачи задаётся в исходной матрице . С другой стороны, в большинстве случаев задача унификации ОС КС предприятиярешается после решения задачи рационального технического оснащения КС, то есть, предполагается, что ранее выбранные параметры и характеристики реальных ОС уже обоснованы с точки зрения допустимости их значений для решения задач конкретного вида. Поэтому необходимостьимитационного моделирования в этомслучае отпадает. Моделирование может понадобиться тольков случае выработки требований по унификации к вновь разрабатываемым ОС. В настоящей статьена примере решения частной задачи проверяется работоспособность разработанных алгоритмов и методики применительно к задаче унификации существующих ОС, сведения о характеристиках которых известны и доступны.На втором этапе методики обоснования рациональной степени унификации ПО КС решаласьзадача (1) (4) методом ветвей и границ.Результаты решения задачи показывают, что при унификации на уровне ОС рациональным сокращением числа типов ОС является сокращение с 8ми типов до 3х. В таблице 1оставшиеся после унификации типы ОС выделены. Такое сокращение дает снижение значения суммарных затрат на 10 % от исходного. Если сократить число применяемых типов ОС до двух (при условии обеспечения возможности решения всех видов задач), экономический эффект от унификации возрастает до 22%. Применение в корпоративной сети ОС одного типа экономически невыгодно (суммарные затраты возрастают в два раза), а также увеличивается время реакции системы на запросы пользователей.
Ссылки на источники1. Изотов, В.Н.Метод решения задачи оптимальной унификации программного обеспечения по экономическому критерию / В.Н. Изотов, Е.А. Дьяченко // Известия ТулГУ. Технические науки. Вып. 9. Ч. 2. –Тула: Издво ТулГУ, 2013. –С. 150 156. –ISSN20716168.2. Erlenkotter, D. A dualbased procedure for uncapacitated facility location / D. Erlenkotter // Oper. Res., 1978, V.26, № 6. P. 9921009.3. Алексеев, О.Г. Сведение задач оптимизации динамического параметрического ряда к многомерной задачи унификации / О.Г. Алексеев // Стандартизация военной техники, 1984, № 2. –С. 4753.4. Изотов, В.Н. Имитационная модель для решения задачи синтеза физической структуры АСУ нового поколения / В.Н. Изотов, Н.С. Акиншин, Ю.Б. Подчуфаров, П.В. Комогорцев // Оборонная техника, 1997, № 34. С. 99103.
