Параллельное программирование


Развитие стратегии решения задачи ЛП - часть 2


В результате анализа первой строки, соответствующей грани q6, находим грани {q6, q7, q9}, возможно, образующие некоторую вершину. В результате решения выделенной системы уравнений получаем точку (0, 55, 0). Эта точка не удовлетворяет ограничениям q4

0 и q5
0. Мы видим по рисунку 6.3, что ошибки бы не произошло, если бы из рассмотрения не была исключена грань q4. Мы делаем вывод о том, что "на стыке" поверхностей, где частично отсутствует информация об образующих некоторых вершин многогранника R, возможны ошибки. Нормаль к q4 составила бы с нормалью к q6 меньший угол, который был бы включен в формируемую комбинацию трех углов.

В результате анализа строки, соответствующей грани q7

(игнорируя нули), находим только грани q6 и q7. Однако для нахождения третьей грани придется все же организовать перебор (именно перебор) нулей. Проверим комбинацию граней {q6, q7, q8}. Их совместное решение определяет точку (0, 75, 0), не удовлетворяющую тем же ограничениям. Комбинация {q6, q7, q9} уже рассматривалась.

Анализ следующей строки приводит к необходимости проверки комбинаций {q6, q7, q8} и {q6, q8, q9}. Первая комбинация уже исследовалась, а вторая приводит к получению точки (5, 0, 0), удовлетворяющей всем ограничениям (точка B на рис. 6.3).

Анализ последней строки приводит к необходимости проверки комбинаций {q6, q7, q9} и {q6, q8, q9}. Обе комбинации уже рассматривались: первая — как неудачная, вторая — повторно образующая вершину.

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

  • Отсюда вывод: в общем случае необходимо избегать анализа строк матрицы S, соответствующих координатным плоскостям. Помимо того, что это — лишь возможные, но не действительные грани, углы, образуемые нормалями к ним и нормалями к другим граням, могут превышать

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




    Начало  Назад  Вперед



    Книжный магазин