|
Получим оценку, решая нецелочисленную задачу линейного программирования. Ее решение Х1= / Х2 = ^ ; Ф о=48>42 Как видим, оценка существенно хуже. Рассмотрим общую постановку задачи дискретной оптимизации: определить вектор X с дискретными компонентами, обеспечивающий max ф(х) при ограничении f(x) < Ь Обе функции ф(х) и f(x) допускают дихотомические представления. Однако, эти представления в общем случае разные, что не позволяет применить метод дихотомического программирования. Рассмотрим частный случай, когда обе функции допускают дихотомическое представление типа дерева [30]. Пусть задано дихотомическое представление G, имеющее структуру Sj. Требуется ответить на вопрос, можно ли реализовать его дихотомическим представлением G j , имеющим другую структуру S2. Реализация одного представления (G i) другим (Gi) здесь определяется как подбор элементов матриц в G2таким образом, чтобы для всех х: ф1 (х) = ф2(х), где ф1функция, определяемая G, а 92 определяемая G2 . Рассмотрим типовой блок структуры (рис. 2.3.8 а). Опишем алгоритм представления этого блока в другом структурном виде (рис. 2.3.8 б). Необходимо определить элементы матриц Р(Х], хз), Р(хг, Х4) и матрицу Р(У4, Уз) новой структуры. Пусть число градаций шкалы показателей Xj равно mj показателей у[-П], а оценка z-p. Определим матрицу Q с m = т ]х т з строками и g = т 2ХШ4; столбцами; строка (i,j) соответствует паре оценок (i,j) показателей Х], хз, а столбец (к, s) паре оценок (к, s) показателей Хг, Х4. Элемент матрицы Q на пересечении строки (i, j) и столбца (к, s) равен значению соответствующей оценки z. Задача заключается в назначении весов (целых положительных чисел) строк и столбцов матрицы Q, которые и определяют элементы соответствующих матриц Р(Х, Хз) и Р(х2, Х4), а значит, и матрицу Р(уз, У4). При этом должно выпол84 |
пределения ресурсов при условии активности участников процедуры распределения. Но, к сожалению, не совсем ясно, каким будет поведение участников распределения в конкретных производственных ситуациях, при применении определенных механизмов распределения. В заключении рассмотрим общую постановку задачи дискретной оптимизации к которым сводятся практически большинство задач распределения ресурсов. Требуется определить вектор х с дискретными компонентами, обеспечивающий шах <р(х) при ограничении 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 |