facebook
twitter
vk
instagram
linkedin
google+
tumblr
akademia
youtube
skype
mendeley
Page translation
 

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

diplomdiplom
Nabieva Gulnaz, deputy director, candidate of technical sciences, associate professor

Galim Kaziyev, director, doctor of technical sciences, full professor

Bakhyt Dautova, lecturer

Kazakh National Technical University named after K. Satpayev, Kazakhstan

Championship participant: the National Research Analytics Championship - "Kazakhstan";

В работе разработан и предложен новый класс задач постановки и решения прикладных задач: блочно-симметричные модели и методы дискретного программирования.

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

Введение. Большое число прикладных задач в различных отраслях экономики сводится к задачам дискретного программирования. Классические постановки и методы решения прикладных задач дискретного программирования успешно используются для решения многих практических задач в различных областях науки, техники и технологий.

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

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

В настоящей работе рассматривается постановка и решение нового класса задач дискретного программирования, который нашел применение при решении различных прикладных задач: блочно-симметричные задачи дискретного программирования (БСЗ).

1. Общая постановка задачи

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

Рассмотрим общую постановку и решение блочно-симметричных задач дискрет­ного программирования.

Пусть задано множество объектов  и множество объектов  с элементами различных типов, а также взаимо­связи между элементами этих множеств, которые определяются матрицей

элементы которой целочислены или булевы. Необходимо объединить элементы мно­жества  А в непересекающиеся подмножества, а элементы множества В - в непересекающиеся подмножества , таким образом, чтобы доставить экстремум целевой функции F (Аn, Bm, ).

Для формализованной постановки задачи введем следующие переменные. Пусть - булева матрица, где  xin=1 если i-й элемент распределяется   в   n-ю   группу,   xin=0,   в  противном   случае.   Аналогично  где yjm=1,  если j-й элемент распределяется в m-ю группу и yjm=0, в противном случае. В общем случае матрицы переменных X и Y могут быть целочисленными.

Определим на множестве А х В функцию F(X.Y), зависящую от распределения элементов множеств А и В по подмножествам An,и Bm. Соответственно на множестве А- функции , а на множестве В – функции , опреде­ляющие ограничения соответственно на множествах А и В.

Блочно-симметричная задача дискретного программирования формулируется следующим образом:

при ограничениях

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

В общем случае двухиндексные матрицы - переменные X и Y и заданная мат­рица W могут быть целочисленными.

Рассмотрим задачу при условии, когда переменные X, Y и W-булевы матрицы. В качестве функций F(X,Y) часто используют функцию вида F(Z), где

Рассмотрим выражение (4), которое представляет собой произведение матриц переменных X и Y и заданной матрицы W, на которой определена целевая функция. В отличие от традиционных постановок задач дискретного программирования в данной постановке имеются два типа переменных X и Y, переменные X и Y симметричны относительно заданной матрицы W.

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

Таким образом, задачу вида (1)-(3) назовем блочно-симметричной задачей дискрет­ного программирования.

Рассмотрим выражение (4). Из него следует что переменные X и Y симметричны относительно заданной матрицы W и функция (4) может быть определена как слева направо, так и наоборот, т. е.

На основе общей постановки определим основные свойства сформулированного класса задач, отличающие его от традиционных постановок задач дискретного програм­мирования

Свойство 1. Наличие двух типов переменных X и Y различных типов, представленных в виде булевых матриц, которые определены на заданной матрице W.

Свойство 2. Блочность задачи заключается в выделении в постановке отдель­ных блоков функций вида (2) и (3), зависящие только от одной переменной Xи Y.

Свойство 3. Симметричность задачи заключается в возможности вычисления (5) как в прямом так и обратном направлении.

2. Решение задачи.

Анализ особенностей и свойств сформулированной задачи позволяет предложить эффективные алгоритмы решения данного класса задач. Рас­смотрим решение блочно-симметричных задач дискретного программирования при условии, что X, Y и W - булевы матрицы. Легко доказать следующее утверждение.

Утверждение. Распределение элементов множества А по непересекающим подмножествам Аn соответствует логическому сложению строк матрицы ||wij|| распределение элементов множества B по непересекающимся подмножествам Bm - логическому сложению столбцов матрицы ||wij||.

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

Введем понятие базиса решения задачи. Под базисом понимается за­данный состав элементов подмножеств An и Bm на матрице W.

В матрице W базис находится как некоторая подматрица Z, элементы которой определены. Данную подматрицу путем перестановки номеров строки и столбцов матрицы W и их перенумеровки всегда можно определить в левом верхнем углу. Такое представление упрощает процедуру оценок и определения направления поиска решения.

Для решения блочно-симметричной задачи дискретного программирования при условии, когда X, Y и W - булевы матрицы, разработан и предложен эффективный алгоритм итеративных отображений. Алгоритм состоит из следующих основных этапов: [3].

1. В булевой матрице W выделим подматрицу  и опре­делим ее как базис решения задачи.

2. Определим матрицу  направления поиска ре­шения X путем логического сложения небазисных строк матрицы W со строками базиса и вычислим значения оценок только по позициям базиса.

3. В соответствии с полученными оценками осуществим распределение эле­ментов множества А по подмножествам An. В результате зафиксируем решение X и промежуточную матрицу 

4. Определим матрицу   направления поиска решения Y путем логического сложения небазисных столбцов промежуточной матрицы со столбцами базиса и вычислим значения оценок только по позициям базиса матрицы P.

5. В соответствии с полученными оценками матрицы P распределим элементы множества В по подмножествам Bm. В результате фиксируем решение Y и целевую матрицу Z, на которой определено значение целевой функции F (Z).

Следует отметить, что поиск решения задачи может осуществляться как в пря­мом направлении по схеме  так и в обратном направлении по схеме .

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

3. Пример постановки  прикладной задачи

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

При большом числе прикладных задач и сложном документообороте возникает необходимость декомпозиции системы на кластеры.

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

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

Для математической постановки задачи декомпозиции системы введём следующие переменные и обозначения.

 Пусть,  и - множество прикладных задач обработки данных, подлежащие автоматизации;  - множество исходных документов, используемое для решения прикладных задач. Задана, матрица  где  если j-й исходный документ используется для решения i-ой прикладной задачи системы и  в противном случае. Введем переменные  - переменная отражающая распределенные i-ой прикладной задачи в m -ой кластер (группу) задач. В данном случае

Аналогично введём переменную

В ряде случаев на данном этапе определяются характеристики задач и документов. Введем ti - время разработки i-ой задачи, vj - объем j-ого документа, cij- общая стоимость разработки i-ой задачи и j-ого документа, fj - время разработки и подготовки j-го документа, ci- стоимость разработки i-ой задачи, sj- стоимость подготовки j-ого документа.

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

Определим дополнительные переменные следующи образом:

Данная переменная отражает использование j-гo документа для решения задач m-го кластера.

Переменная  отражает использование в процессе решения i-ой задачи n-го кластера документов.

Взаимосвязи между кластерами прикладных задач и документов определяются из выражения:

Задачу кластеризации проектируемой автоматизированной системы сформулируем следующим образом.

Необходимо минимизировать функцию вида

При ограничениях на:

- включение каждой прикладной задачи только в один кластер

- включение документа только в один кластер документов

- время разработки каждого кластера задач

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

- число прикладных задач в кластере

- число исходных документов в кластере

Поставленная задача (6-15) относится к блочно-симметричным задачам дискретного программирования. 

Выводы

1. Разработан и предложен новый класс задач – блочно-симметричные задач дискретного программирования, отличающихся от традиционных постановок свойствами: наличием различных типов переменных, блочности и симметричности.

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

3. Предложенные блочно-симметричные модели и методы использованы при постановке и  решении ряда прикладных задач.

Литература:

  • 1. Казиев Г.З. Синтез модульных блок-схем в  автоматизированных системах управления// Автоматика и телемеханика. 1992. №11. С. 160-171.
  • 2. Казиев Г.З. Блочно-симметричные модели и методы постановки и решения задач дискретного программирования.// Вестник инженерной академии Республики Казахстан, №2(10) 2003, с.55-59.
  • 3. Казиев Г.З., Набиева Г.С., Сатмагамбетова Ж.З., Абылхасенова Д.К.  Модели и методы дискретного программирования. Блочно-симметричные модели - эффективный класс задач дискретного программирования. // «Вестник КБТУ»,  №3, 2010. С.61-68                     
0
Your rating: None Average: 7.8 (10 votes)
Comments: 7

Taratin Vjacheslav Victorovich

Блочно-симметричные модели и методы постановки и решения задач дискретного программирования безусловно представляют большой интерес. В статье суть этих моделей и методов раскрыта достаточно хорошо. Работа авторов заслуживает высокой оценки. Хотелось бы узнать конкретно при решении каких прикладных задач инновация быдла уже использована? С уважением, Вячеслав Викторович Таратин

Nabieva Gulnaz Sotsialovna

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

Taratin Vjacheslav Victorovich

Спасибо за информацию по практической реализации Ваших исследований. Желаю дальнейших успехов!

Rodionova Zinaida Valeryevna

Чем подтверждается эффективность алгоритма итеративных отображений? Была ли проведена оценка сложности алгоритма?

Nabieva Gulnaz Sotsialovna

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

Ignatova Anna

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

Nabieva Gulnaz Sotsialovna

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

Taratin Vjacheslav Victorovich

Блочно-симметричные модели и методы постановки и решения задач дискретного программирования безусловно представляют большой интерес. В статье суть этих моделей и методов раскрыта достаточно хорошо. Работа авторов заслуживает высокой оценки. Хотелось бы узнать конкретно при решении каких прикладных задач инновация быдла уже использована? С уважением, Вячеслав Викторович Таратин

Nabieva Gulnaz Sotsialovna

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

Taratin Vjacheslav Victorovich

Спасибо за информацию по практической реализации Ваших исследований. Желаю дальнейших успехов!

Rodionova Zinaida Valeryevna

Чем подтверждается эффективность алгоритма итеративных отображений? Была ли проведена оценка сложности алгоритма?

Nabieva Gulnaz Sotsialovna

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

Ignatova Anna

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

Nabieva Gulnaz Sotsialovna

Массовый пользователь может использовать программное обеспечение для решения прикладных задач указанного класса.
PARTNERS
 
 
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
Would you like to know all the news about GISAP project and be up to date of all news from GISAP? Register for free news right now and you will be receiving them on your e-mail right away as soon as they are published on GISAP portal.