Cтраница 2
Всего на множестве X существует т п граней размерности п - 1, Если точках 0 1 р) принадлежит / - и ( j 1 т п) грани ( т.е. точка х удовлетворяет соотношению А / х 6 / как равенство), то в соответствующей клетке таблицы записывается единица, в противном случае - нуль. В последней строке записываются суммы элементов соответствующих столбцов. [16]
Последнее означает, что предположение об эффективности граней размерности и-2 недопустимо. [17]
В этом случае элементарные конъюнкции, соответствующие граням размерности 2, содержат три переменные. [18]
Из этой оценки Никулина следует, что средняя сложность грани заданной размерности простого полиэдра Р сг Я при увеличении п стремится к сложности куба. Именно это наблюдение для трехмерных граней и играет ключевую роль в доказательстве приведенной выше теоремы конечности Никулина. [19]
Чтобы установить, какие же из эффективных базисных решений принадлежат соответствующим граням размерности 2 и 1, сначала определяется принадлежность эффективных базисных решений граням размерности п - 1 5 - 14, далее граням размерности п - 23, и только после этого определяются грани нужной размерности. [20]
После рассмотрения принадлежности эффективных базисных решений граням размерности п - 2, необходимо перейти к граням размерности п - 3 и так далее, пока не дойдем до граней размерности k - 1 и меньше. Для этого также строятся соответствующие таблицы. [21]
Таким образом устанавливается, что только шестая грань ( или выпуклая комбинация решений г4, г5 иг6) из граней размерности п - 3 2 является эффективной. [22]
Эта теорема равносильна теореме однокритериального линейного программирования, согласно которой, если оптимальное решение достигается и на точках, лежащих на гранях размерности больше нуля, то значение целевой функции на этих точках равно значению целевой функции, вычисленной на грани нулевой размерности. [23]
Из теоремы 7 следует, что необходимо рассмотреть только выпуклые комбинации таких эффективных базисных решений, набор которых совпадает с набором вершин некоторой грани определенной размерности. Эти точки являются связанными), то все вершины этой грани являются эффективными. В противном случае среди вершин этой грани существует такая, которая не является эффективной. [24]
Чтобы установить, какие же из эффективных базисных решений принадлежат соответствующим граням размерности 2 и 1, сначала определяется принадлежность эффективных базисных решений граням размерности п - 1 5 - 14, далее граням размерности п - 23, и только после этого определяются грани нужной размерности. [25]
После рассмотрения принадлежности эффективных базисных решений граням размерности п - 2, необходимо перейти к граням размерности п - 3 и так далее, пока не дойдем до граней размерности k - 1 и меньше. Для этого также строятся соответствующие таблицы. [26]
Чтобы установить, какие же из эффективных базисных решений принадлежат соответствующим граням размерности 2 и 1, сначала определяется принадлежность эффективных базисных решений граням размерности п - 1 5 - 14, далее граням размерности п - 23, и только после этого определяются грани нужной размерности. [27]
Чтобы установить, какие же из эффективных базисных решений принадлежат соответствующим граням размерности 2 и 1, сначала определяется принадлежность эффективных базисных решений граням размерности п - 1 5 - 14, далее граням размерности п - 23, и только после этого определяются грани нужной размерности. [28]
Аналогичным образом доказывается, что седьмая и семнадцатая грани не могут быть эффективными. Из граней размерности п - 3 2 только шестая грань может быть эффективной, поскольку все вершины этой грани эффективны. Таким образом, только шестая грань ( или выпуклая комбинация точек z4, z5 и z6) подлежит проверке на эффективность. [29]
С /, либо достигает своего максимума на какой-то грани U многогранника U размерности меньшей, чем размерность многогранника U. Это может быть либо грань нулевой размерности, т.е. вершина, либо некоторая грань U ненулевой размерности. Итак, либо единственной точкой максимума функции ( u, ( t)) является некоторая вершина многогранника U, либо максимум достигается во всех точках некоторого ребра w этого многогранника. [30]