|
85 няться условие согласования шкал: два элемента с одинаковыми весами строк и одинаковыми весами столбцов обязательно должны быть равными. t У Х У2 6 6 6 Х з Х 4 б) Х У4 Х 2 Уз Хз 6 6 6 С ) Х 4 Х Х 2 Хз Х 4 Рис. 2.3.8 Заметим, что минимальное число различных элементов матриц P(xi, Хз), (или Р(х2, хД) равно числу различных строк (столбцов) матрицы Q. Действительно, одинаковые строки (столбцы) должны иметь одинаковый вес (одинаковую оценку Z). С другой стороны, разные строки (столбцы) |
пределения ресурсов при условии активности участников процедуры распределения. Но, к сожалению, не совсем ясно, каким будет поведение участников распределения в конкретных производственных ситуациях, при применении определенных механизмов распределения. В заключении рассмотрим общую постановку задачи дискретной оптимизации к которым сводятся практически большинство задач распределения ресурсов. Требуется определить вектор х с дискретными компонентами, обеспечивающий шах <р(х) при ограничении f(x) < b Обе функции <р(х) и f(x) допускают дихотомические представления. Однако, эти представления в общем случае разные, что не позволяет применить метод дихотомического программирования. Рассмотрим частный случай, когда обе функции допускают дихотомическое представление типа дерева [68]. Пусть задано дихотомическое представление G, имеющее структуру Si. Требуется ответить на вопрос, можно ли реализовать его дихотомическим представлением G2 , имеющим другую структуру S2. Реализация одного представления (Gi) другим (G2) здесь определяется как подбор элементов матриц в G2таким образом, чтобы для всех х: cpi(x) = < р 2(х), где 1.4.1а). Опишем алгоритм представления этого блока в другом структурном виде (рис. 1.4.16). Необходимо определить элементы матриц Р(хь Х 3), Р(х2, Х 4) и матрицу Р(У4, Уз) новой структуПусть число градаций шкалы показателей X j равно rrii показателей у;-Пь а оценка z-p. Определим матрицу Q с m = mxm3строками и g =m2xm4; столбцами; строка (i,j) соответствует паре оценок (i, j) показателей хь х3, а столбец (k, s) —паре оценок (k, s) показателей х2, х4. Элемент матрицы Q на пересечении строки (i, j) и столбца (k, s) равен значению соответствующей оценки z. Задача заключается в назначении весов (целых положительных чисел) строк и столбцов матрицы Q, которые и определяют элементы соответствующих матриц Р(хь х3) и Р(х2, х(), а значит, и матрицу Р(уз, у4). При этом должно выполняться условие согласования шкал: два элемента с одинаковыми весами строк и одинаковыми весами столбцов обязательно должны быть равными. Заметим, что минимальное число различных элементов матриц Р(Х, хз), (или Р(х2, х4)) равно числу различных строк (столб52 цов) матрицы Q. Действительно, одинаковые строки (столбцы) должны иметь одинаковый вес (одинаковую оценку Z). С другой стороны, разные строки (столбцы) не могут иметь равных весов, поскольку, беря столбец (строку) с разными элементами, мы получим противоречие с условием согласования шкал. Опираясь на этот факт, уже нетрудно построить требуемые матрицы Р(Х, х3), Р(х2, х4) и Р(у3, у4). Аналогично можно получить из структуры рис. 1.4.1а структуру рис. 1.4.1в. Имея два типа преобразований элементарных блоков, можно получить различные структуры матричной свертки из исходной G. Теорема 1.4.1[68]. Применяя описанные выше преобразования, из матричной свертки G можно получить любую другую матричную свертку тех же исходных показателей. Доказательство. Достаточно доказать, что путем описанных выше преобразований можно получить структуру, в которой на нижнем уровне производится свертка любой заданной пары показателей (х;, xj). Пусть G цепь, соединяющая вершины Х, Xj, имеет длину X. Применяя описанное выше преобразование, мы переходим к новой структуре, в которой длина цепи, соединяющей вершины X;, Xj, меньше на 2. За конечное число таких преобразований получим структуру с длиной цепи между этими вершиггами либо 2 (тогда задача решена), либо 3 (тогда применяем преобразование, показанное на рис. 1.4.1в). Таким образом, имея одно представление, мы можем получить эквивалентное представление любой структуры. Таким образом, из дихотомического представления функции ф(х) мы можем получить дихотомическое представление этой же функции, но с такой же структурой, какую имеет дихотомическое представление функции f(x). Одинаковая структура дихотомического представления функции <р(х) и f(x) позволяет применять метод дихотомического программирования. 53 |