Общая постановка блочно-симметричных задач дискретного программирования

 

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

Рассмотрим общую постановку блочно-симметричных задач дискретного программирования [126, 127].

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

 

, , ,

 

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

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

Определим на множестве  функцию , зависящую от распределения элементов множеств  и  по подмножествам  и . Соответственно на множестве  - функции , а на множестве  - функции , определяющие ограничения на множествах  и .

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

,(2.1.1)

 

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

 

(2.1.2)

(2.1.3)

 

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

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

Рассмотрим задачу при условии, когда переменные ,  и  - булевы матрицы. В качестве функции  часто используют функцию вида , где

 

(2.1.4)

 

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

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

Функционал вида  можно представить следующим образом:

 

(2.1.5)

(2.1.6)

(2.1.7)

(2.1.8)

(2.1.9)

 

В постановке задачи (2.1.5) - (2.1.9) выделим блок функции (2.1.6), (2.1.7), зависящий только от переменной , и блок функций (2.1.8), (2.1.9), зависящий только от переменной , объединенных единым функционалом вида (2.1.5). Заметим, что в ряде постановок задач может быть блок ограничений вида

 

(2.1.10)

 

зависящий от переменных  и .

В этом случае можно выделить блок функционала цели вида (2.1.5), (2.1.10).

Отсюда следует.

Определение 2.1. Блочно-симметричной задачей дискретного программирования назовем задачу вида (2.1.5) - (2.1.9), где переменные  и  и значения функций , ,  - целые, либо булевые

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

 

(2.1.11)

 

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

Свойство 1. В блочно-симметричной задаче имеется два типа переменных  и  различного содержания, определенных как целочисленные (булевы) матрицы на заданной матрице .

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

Свойство 2. Блочность задачи заключается в выделении в постановке отдельных блоков функций вида (2.1.5), (2.1.10); (2.1.6), (2.1.7) и (2.1.8), (2.1.9), которые соответственно зависят от переменных  и .

Как видно из указанных соотношении каждый из блоков имеет свою целевую функцию и координируется общим функционалом вида (2.1.5).

Свойство 3. Блочно-симметричную задачу в большинстве случаев можно представить в матричной форме вида (2.1.11).

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

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

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

В ряде постановок задач функционал (2.1.1) можно представить в виде вектора функций . В этом случае формулируется многокритериальная блочно-симметричная задача дискретного программирования.

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

Утверждение. Распределение элементов множества  по непересекающим подмножествам  соответствует логическому сложению строк матриц , а распределение элементов множества  по непересекающимся подмножествам  - логическому сложению столбцов матрицы . [132, 133] Результаты данного утверждения позволяют просто вычислить оценки и направления поиска решения для разработки эффективных алгоритмов.

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

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

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

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

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

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

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

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

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

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

 

Предыдущая12345678910Следующая

Поделиться:

Воспользуйтесь поиском по сайту: