Частные задачи синтеза структуры.

Большинство задач, связанных с синтезом структуры АСУ, является задачами целочисленного линейного программирования [3-4].

I. Рассмотрим решение задачи минимизации общих затрат (3-8) либо общего времени решения (3-9) при ограничениях на загрузку каждого из узлов (3-12) или на затраты в каждом j-м узле, т. Е. Задачи вида

(3-15)

(3-16)

. (3-17)

Рассмотренную задачу удобно решать известным в целочисленном программировании методом “ветвей и границ” который применительно к ней состоит в направленном движении по вершинам дерева, получаемого из матрицы системы (3-16) путем последовательного фиксирования переменной Xij, принимающей значение 0 или 1.

Сначала получаем вершины первого уровня ветвления, полагая эту переменную равной еденице последовательно для всех значений i при j=1. Затем для каждой из вершин первого уровня выделяем вершины второго уровня ветвления, пологая Xij=1 последовательно для всех значений i при j=2; для каждой вершины второго уровня фиксируем вершины третьего для всех i при j=3 и т. д.

До ветвления исключаем из матрицы коэффициентов aij все элементы, у которых aij>bj. При этом возможны случаи, когда в некотором столбце:

исключены все элементы aij – оптимального решения нет;

остался лишь один элемент aij; именно он входит в оптимальное решение, если оно существует. Значение bj заменяем на (bj-aij), и этот элемент в дальнейшем поиске не участвуют;

осталось несколько элементов – они участвуют в дальнейшем поиске оптимального решения.

Для каждой вершины находят оценку, равную

+ ,

Где i* - число рассмотренных уровней ветвления; =

II. Рассмотрим задачи типа минимизации затрат (3-8) или времени решения (3-9) при ограничениях в на время (3-13) или затраты (3-11) соответственно, т. Е. Задачи вида

(3-18)

(3-19)

(3-20)

Вначале отбрасываем все элементы из матриц коэффициентов в системах (3-18) и (3-19), которые не могут войти ни в одно допустимое решение.

Для этого последовательно рассматриваем все элементы матрицы (3-19), проверяя условие

; (3-21)

где - рассматриваемый элемент; - минимальные элементыэлементы всех столбцов при

Если условие (3-21) нарушается, рассматриваемый элемент не входит в допустимое решение. При этом из матрицы (3-18) отбрасывают элемент с одноименными индексами.

Поскольку из (3-20) следует, что в каждом столбце может быть только один элемент, то без учета ограничения (3-19)

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

Если минимальным по столбцам элементам начальной системы (3-18) соответствуют элементы матриц (3-19), удовлетворяющие ограничениям, то они составляют оптимальное решение. В в противном случае полученное решение используют в качестве оценки в методе «ветвей и границ».

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

Оценку каждой вершины находясь по коэфициентам матрицы (3-18), как и в предыдущей задаче.

Ограничение при этом имеет вид:

где - уровень ветвления; для столбцов,

элементы которых еще не вошли в решение.

Оценки вершин и значения ограничений сравнивают со значением решения задачи при ветвлении и ветвлении и с заданным значением ограничения В в системе (3-19).